source: trunk/Cbc/src/CbcBranchCut.cpp @ 912

Last change on this file since 912 was 912, checked in by ladanyi, 13 years ago

Incorporated changes from branches/heur

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 22.0 KB
Line 
1// Copyright (C) 2004, International Business Machines
2// Corporation and others.  All Rights Reserved.
3#if defined(_MSC_VER)
4// Turn off compiler warning about long names
5#  pragma warning(disable:4786)
6#endif
7#include <cassert>
8#include <cstdlib>
9#include <cmath>
10#include <cfloat>
11//#define CBC_DEBUG
12
13#include "OsiSolverInterface.hpp"
14#include "CbcModel.hpp"
15#include "CbcMessage.hpp"
16#include "CbcBranchCut.hpp"
17#include "CoinSort.hpp"
18#include "CoinError.hpp"
19
20
21/** Default Constructor
22
23*/
24CbcBranchCut::CbcBranchCut ()
25  : CbcObject()
26{
27}
28
29/* Constructor so model can be passed up
30*/ 
31CbcBranchCut::CbcBranchCut (CbcModel * model)
32  : CbcObject(model)
33{
34}
35// Copy constructor
36CbcBranchCut::CbcBranchCut ( const CbcBranchCut & rhs)
37  :CbcObject(rhs)
38
39{
40}
41
42// Clone
43CbcObject *
44CbcBranchCut::clone() const
45{
46  return new CbcBranchCut(*this);
47}
48
49// Assignment operator
50CbcBranchCut & 
51CbcBranchCut::operator=( const CbcBranchCut& rhs)
52{
53  return *this;
54}
55
56// Destructor
57CbcBranchCut::~CbcBranchCut ()
58{
59}
60
61// Infeasibility - large is 0.5
62double 
63CbcBranchCut::infeasibility(int & preferredWay) const
64{
65  throw CoinError("Use of base class","infeasibility","CbcBranchCut");
66  preferredWay=-1;
67  return 0.0;
68}
69
70// This looks at solution and sets bounds to contain solution
71/** More precisely: it first forces the variable within the existing
72    bounds, and then tightens the bounds to fix the variable at the
73    nearest integer value.
74*/
75void 
76CbcBranchCut::feasibleRegion()
77{
78}
79/* Return true if branch created by object should fix variables
80 */
81bool 
82CbcBranchCut::boundBranch() const 
83{return false;}
84
85// Creates a branching object
86CbcBranchingObject * 
87CbcBranchCut::createBranch(int way) 
88{
89  throw CoinError("Use of base class","createBranch","CbcBranchCut");
90  return new CbcCutBranchingObject();
91}
92
93
94/* Given valid solution (i.e. satisfied) and reduced costs etc
95   returns a branching object which would give a new feasible
96   point in direction reduced cost says would be cheaper.
97   If no feasible point returns null
98*/
99CbcBranchingObject * 
100CbcBranchCut::preferredNewFeasible() const
101{
102  throw CoinError("Use of base class","preferredNewFeasible","CbcBranchCut");
103  return new CbcCutBranchingObject();
104}
105 
106/* Given valid solution (i.e. satisfied) and reduced costs etc
107   returns a branching object which would give a new feasible
108   point in direction opposite to one reduced cost says would be cheaper.
109   If no feasible point returns null
110*/
111CbcBranchingObject * 
112CbcBranchCut::notPreferredNewFeasible() const 
113{
114  throw CoinError("Use of base class","notPreferredNewFeasible","CbcBranchCut");
115  return new CbcCutBranchingObject();
116}
117 
118/*
119  Bounds may be tightened, so it may be good to be able to refresh the local
120  copy of the original bounds.
121 */
122void 
123CbcBranchCut::resetBounds()
124{
125}
126
127
128// Default Constructor
129CbcCutBranchingObject::CbcCutBranchingObject()
130  :CbcBranchingObject()
131{
132  down_=OsiRowCut();
133  up_=OsiRowCut();
134  canFix_=false;
135}
136
137// Useful constructor
138CbcCutBranchingObject::CbcCutBranchingObject (CbcModel * model, 
139                                              OsiRowCut & down,
140                                              OsiRowCut &up,
141                                              bool canFix)
142  :CbcBranchingObject(model,0,-1,0.0)
143{
144  down_ = down;
145  up_ = up;
146  canFix_ = canFix;
147}
148
149// Copy constructor
150CbcCutBranchingObject::CbcCutBranchingObject ( const CbcCutBranchingObject & rhs) :CbcBranchingObject(rhs)
151{
152  down_ = rhs.down_;
153  up_ = rhs.up_;
154  canFix_ = rhs.canFix_;
155}
156
157// Assignment operator
158CbcCutBranchingObject & 
159CbcCutBranchingObject::operator=( const CbcCutBranchingObject& rhs)
160{
161  if (this != &rhs) {
162    CbcBranchingObject::operator=(rhs);
163    down_ = rhs.down_;
164    up_ = rhs.up_;
165    canFix_ = rhs.canFix_;
166  }
167  return *this;
168}
169CbcBranchingObject * 
170CbcCutBranchingObject::clone() const
171{ 
172  return (new CbcCutBranchingObject(*this));
173}
174
175
176// Destructor
177CbcCutBranchingObject::~CbcCutBranchingObject ()
178{
179}
180
181/*
182  Perform a branch by adjusting bounds and/or adding a cut. Note
183  that each arm of the branch advances the object to the next arm by
184  advancing the value of way_.
185
186  Returns change in guessed objective on next branch
187*/
188double
189CbcCutBranchingObject::branch()
190{
191  decrementNumberBranchesLeft();
192  OsiRowCut * cut;
193  if (way_<0) {
194    cut = &down_;
195    way_=1;
196  } else {
197    cut = &up_;
198    way_=-1;      // Swap direction
199  }
200  // See if cut just fixes variables
201  double lb = cut->lb();
202  double ub = cut->ub();
203  int n=cut->row().getNumElements();
204  const int * column = cut->row().getIndices();
205  const double * element = cut->row().getElements();
206  OsiSolverInterface * solver = model_->solver();
207  const double * upper = solver->getColUpper();
208  const double * lower = solver->getColLower();
209  double low = 0.0;
210  double high=0.0;
211  for (int i=0;i<n;i++) {
212    int iColumn = column[i];
213    double value = element[i];
214    if (value>0.0) {
215      high += upper[iColumn]*value;
216      low += lower[iColumn]*value;
217    } else {
218      high += lower[iColumn]*value;
219      low += upper[iColumn]*value;
220    }
221  }
222  // assume cut was cunningly constructed so we need not worry too much about tolerances
223  if (low+1.0e-8>=ub&&canFix_) {
224    // fix
225    for (int i=0;i<n;i++) {
226      int iColumn = column[i];
227      double value = element[i];
228      if (value>0.0) {
229        solver->setColUpper(iColumn,lower[iColumn]);
230      } else {
231        solver->setColLower(iColumn,upper[iColumn]);
232      }
233    }
234  } else if (high-1.0e-8<=lb&&canFix_) {
235    // fix
236    for (int i=0;i<n;i++) {
237      int iColumn = column[i];
238      double value = element[i];
239      if (value>0.0) {
240        solver->setColLower(iColumn,upper[iColumn]);
241      } else {
242        solver->setColUpper(iColumn,lower[iColumn]);
243      }
244    }
245  } else {
246    // leave as cut
247    model_->setNextRowCut(*cut);
248  }
249  return 0.0;
250}
251// Print what would happen 
252void
253CbcCutBranchingObject::print()
254{
255  OsiRowCut * cut;
256  if (way_<0) {
257    cut = &down_;
258    printf("CbcCut would branch down");
259  } else {
260    cut = &up_;
261    printf("CbcCut would branch up");
262  }
263  double lb = cut->lb();
264  double ub = cut->ub();
265  int n=cut->row().getNumElements();
266  const int * column = cut->row().getIndices();
267  const double * element = cut->row().getElements();
268  if (n>5) {
269    printf(" - %d elements, lo=%g, up=%g\n",n,lb,ub);
270  } else {
271    printf(" - %g <=",lb);
272    for (int i=0;i<n;i++) {
273      int iColumn = column[i];
274      double value = element[i];
275      printf(" (%d,%g)",iColumn,value);
276    }
277    printf(" <= %g\n",ub);
278  }
279}
280
281// Return true if branch should fix variables
282bool 
283CbcCutBranchingObject::boundBranch() const
284{
285  return false;
286}
287
288/** Compare the original object of \c this with the original object of \c
289    brObj. Assumes that there is an ordering of the original objects.
290    This method should be invoked only if \c this and brObj are of the same
291    type.
292    Return negative/0/positive depending on whether \c this is
293    smaller/same/larger than the argument.
294*/
295int
296CbcCutBranchingObject::compareOriginalObject
297(const CbcBranchingObject* brObj) const
298{
299  const CbcCutBranchingObject* br =
300    dynamic_cast<const CbcCutBranchingObject*>(brObj);
301  assert(br);
302  const OsiRowCut& r0 = way_ == -1 ? down_ : up_;
303  const OsiRowCut& r1 = br->way_ == -1 ? br->down_ : br->up_;
304  return r0.row().compare(r1.row());
305}
306
307/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
308    same type and must have the same original object, but they may have
309    different feasible regions.
310    Return the appropriate CbcRangeCompare value (first argument being the
311    sub/superset if that's the case). In case of overlap (and if \c
312    replaceIfOverlap is true) replace the current branching object with one
313    whose feasible region is the overlap.
314*/
315
316CbcRangeCompare
317CbcCutBranchingObject::compareBranchingObject
318(const CbcBranchingObject* brObj, const bool replaceIfOverlap)
319{
320  const CbcCutBranchingObject* br =
321    dynamic_cast<const CbcCutBranchingObject*>(brObj);
322  assert(br);
323  OsiRowCut& r0 = way_ == -1 ? down_ : up_;
324  const OsiRowCut& r1 = br->way_ == -1 ? br->down_ : br->up_;
325  double thisBd[2];
326  thisBd[0] = r0.lb();
327  thisBd[1] = r0.ub();
328  double otherBd[2];
329  otherBd[0] = r1.lb();
330  otherBd[1] = r1.ub();
331  CbcRangeCompare comp = CbcCompareRanges(thisBd, otherBd, replaceIfOverlap);
332  if (comp != CbcRangeOverlap || (comp==CbcRangeOverlap && !replaceIfOverlap)) {
333    return comp;
334  }
335  r0.setLb(thisBd[0]);
336  r0.setUb(thisBd[1]);
337  return comp;
338}
339
340//##############################################################################
341
342/** Default Constructor
343
344  Equivalent to an unspecified binary variable.
345*/
346CbcBranchToFixLots::CbcBranchToFixLots ()
347  : CbcBranchCut(),
348    djTolerance_(COIN_DBL_MAX),
349    fractionFixed_(1.0),
350    mark_(NULL),
351    depth_(-1),
352    numberClean_(0),
353    alwaysCreate_(false)
354{
355}
356
357/* Useful constructor - passed reduced cost tolerance and fraction we would like fixed.
358   Also depth level to do at.
359   Also passed number of 1 rows which when clean triggers fix
360   Always does if all 1 rows cleaned up and number>0 or if fraction columns reached
361   Also whether to create branch if can't reach fraction.
362*/ 
363CbcBranchToFixLots::CbcBranchToFixLots (CbcModel * model, double djTolerance,
364                                        double fractionFixed, int depth,
365                                        int numberClean,
366                                        const char * mark, bool alwaysCreate)
367  : CbcBranchCut(model)
368{
369  djTolerance_ = djTolerance;
370  fractionFixed_ = fractionFixed;
371  if (mark) {
372    int numberColumns = model->getNumCols();
373    mark_ = new char[numberColumns];
374    memcpy(mark_,mark,numberColumns);
375  }
376  depth_ = depth;
377  assert (model);
378  OsiSolverInterface * solver = model_->solver();
379  matrixByRow_ = *solver->getMatrixByRow();
380  numberClean_ = numberClean;
381  alwaysCreate_ = alwaysCreate;
382}
383// Copy constructor
384CbcBranchToFixLots::CbcBranchToFixLots ( const CbcBranchToFixLots & rhs)
385  :CbcBranchCut(rhs)
386{
387  djTolerance_ = rhs.djTolerance_;
388  fractionFixed_ = rhs.fractionFixed_;
389  int numberColumns = model_->getNumCols();
390  mark_ = CoinCopyOfArray(rhs.mark_,numberColumns);
391  matrixByRow_=rhs.matrixByRow_;
392  depth_ = rhs.depth_;
393  numberClean_ = rhs.numberClean_;
394  alwaysCreate_ = rhs.alwaysCreate_;
395}
396
397// Clone
398CbcObject *
399CbcBranchToFixLots::clone() const
400{
401  return new CbcBranchToFixLots(*this);
402}
403
404// Assignment operator
405CbcBranchToFixLots & 
406CbcBranchToFixLots::operator=( const CbcBranchToFixLots& rhs)
407{
408  if (this!=&rhs) {
409    CbcBranchCut::operator=(rhs);
410    djTolerance_ = rhs.djTolerance_;
411    fractionFixed_ = rhs.fractionFixed_;
412    int numberColumns = model_->getNumCols();
413    delete [] mark_;
414    mark_ = CoinCopyOfArray(rhs.mark_,numberColumns);
415    matrixByRow_=rhs.matrixByRow_;
416    depth_ = rhs.depth_;
417    numberClean_ = rhs.numberClean_;
418    alwaysCreate_ = rhs.alwaysCreate_;
419  }
420  return *this;
421}
422
423// Destructor
424CbcBranchToFixLots::~CbcBranchToFixLots ()
425{
426  delete [] mark_;
427}
428// Creates a branching object
429CbcBranchingObject * 
430CbcBranchToFixLots::createBranch(int way) 
431{
432  // by default way must be -1
433  assert (way==-1);
434  OsiSolverInterface * solver = model_->solver();
435  const double * solution = model_->testSolution();
436  const double * lower = solver->getColLower();
437  const double * upper = solver->getColUpper();
438  const double * dj = solver->getReducedCost();
439  int i;
440  int numberIntegers = model_->numberIntegers();
441  const int * integerVariable = model_->integerVariable();
442  double integerTolerance = 
443    model_->getDblParam(CbcModel::CbcIntegerTolerance);
444  // make smaller ?
445  double tolerance = CoinMin(1.0e-8,integerTolerance);
446  // How many fixed are we aiming at
447  int wantedFixed = (int) ((double)numberIntegers*fractionFixed_);
448  int nSort=0;
449  int numberFixed=0;
450  int numberColumns = solver->getNumCols();
451  int * sort = new int[numberColumns];
452  double * dsort = new double[numberColumns];
453  int type = shallWe();
454  assert (type);
455  // Take clean first
456  if (type==1) {
457    for (i=0;i<numberIntegers;i++) {
458      int iColumn = integerVariable[i];
459      if (upper[iColumn]>lower[iColumn]) {
460        if (!mark_||!mark_[iColumn]) {
461          if(solution[iColumn]<lower[iColumn]+tolerance) {
462            if (dj[iColumn]>djTolerance_) {
463              dsort[nSort]=-dj[iColumn];
464              sort[nSort++]=iColumn;
465            }
466          } else if (solution[iColumn]>upper[iColumn]-tolerance) {
467            if (dj[iColumn]<-djTolerance_) {
468              dsort[nSort]=dj[iColumn];
469              sort[nSort++]=iColumn;
470            }
471          }
472        }
473      } else {
474        numberFixed++;
475      }
476    }
477    // sort
478    CoinSort_2(dsort,dsort+nSort,sort);
479    nSort= CoinMin(nSort,wantedFixed-numberFixed);
480  } else {
481    int i;
482    //const double * rowLower = solver->getRowLower();
483    const double * rowUpper = solver->getRowUpper();
484    // Row copy
485    const double * elementByRow = matrixByRow_.getElements();
486    const int * column = matrixByRow_.getIndices();
487    const CoinBigIndex * rowStart = matrixByRow_.getVectorStarts();
488    const int * rowLength = matrixByRow_.getVectorLengths();
489    const double * columnLower = solver->getColLower();
490    const double * columnUpper = solver->getColUpper();
491    const double * solution = solver->getColSolution();
492    int numberColumns = solver->getNumCols();
493    int numberRows = solver->getNumRows();
494    for (i=0;i<numberColumns;i++) {
495      sort[i]=i;
496      if (columnLower[i]!=columnUpper[i]){
497        dsort[i]=1.0e100;
498      } else {
499        dsort[i]=1.0e50;
500        numberFixed++;
501      }
502    }
503    for (i=0;i<numberRows;i++) {
504      double rhsValue = rowUpper[i];
505      bool oneRow=true;
506      // check elements
507      int numberUnsatisfied=0;
508      for (int j=rowStart[i];j<rowStart[i]+rowLength[i];j++) {
509        int iColumn = column[j];
510        double value = elementByRow[j];
511        double solValue = solution[iColumn];
512        if (columnLower[iColumn]!=columnUpper[iColumn]) {
513          if (solValue<1.0-integerTolerance&&solValue>integerTolerance)
514            numberUnsatisfied++;
515          if (value!=1.0) {
516            oneRow=false;
517            break;
518          }
519        } else {
520          rhsValue -= value*floor(solValue+0.5);
521        }
522      }
523      if (oneRow&&rhsValue<=1.0+tolerance) {
524        if (!numberUnsatisfied) {
525          for (int j=rowStart[i];j<rowStart[i]+rowLength[i];j++) {
526            int iColumn = column[j];
527            if (dsort[iColumn]>1.0e50){
528              dsort[iColumn]=0;
529              nSort++;
530            }
531          }
532        }
533      }
534    }
535    // sort
536    CoinSort_2(dsort,dsort+numberColumns,sort);
537  }
538  OsiRowCut down;
539  down.setLb(-COIN_DBL_MAX);
540  double rhs=0.0;
541  for (i=0;i<nSort;i++) {
542    int iColumn = sort[i];
543    if(solution[iColumn]<lower[iColumn]+tolerance) {
544      rhs += lower[iColumn];
545      dsort[i]=1.0;
546      assert (!lower[iColumn]);
547    } else {
548      assert (solution[iColumn]>upper[iColumn]-tolerance);
549      rhs -= upper[iColumn];
550      dsort[i]=-1.0;
551      //printf("%d at ub of %g\n",iColumn,upper[iColumn]);
552    }
553  }
554  down.setUb(rhs);
555  down.setRow(nSort,sort,dsort);
556  delete [] sort;
557  delete [] dsort;
558  // up is same - just with rhs changed
559  OsiRowCut up = down;
560  up.setLb(rhs +1.0);
561  up.setUb(COIN_DBL_MAX);
562  // Say can fix one way
563  CbcCutBranchingObject * newObject = 
564    new CbcCutBranchingObject(model_,down,up,true);
565  if (model_->messageHandler()->logLevel()>1)
566    printf("creating cut in CbcBranchCut\n");
567  return newObject;
568}
569/* Does a lot of the work,
570   Returns 0 if no good, 1 if dj, 2 if clean, 3 if both
571*/
572int 
573CbcBranchToFixLots::shallWe() const
574{
575  int returnCode=0;
576  OsiSolverInterface * solver = model_->solver();
577  int numberRows = matrixByRow_.getNumRows();
578  //if (numberRows!=solver->getNumRows())
579  //return 0;
580  const double * solution = model_->testSolution();
581  const double * lower = solver->getColLower();
582  const double * upper = solver->getColUpper();
583  const double * dj = solver->getReducedCost();
584  int i;
585  int numberIntegers = model_->numberIntegers();
586  const int * integerVariable = model_->integerVariable();
587  double integerTolerance = 
588    model_->getDblParam(CbcModel::CbcIntegerTolerance);
589  // make smaller ?
590  double tolerance = CoinMin(1.0e-8,integerTolerance);
591  // How many fixed are we aiming at
592  int wantedFixed = (int) ((double)numberIntegers*fractionFixed_);
593  if (djTolerance_<1.0e10) {
594    int nSort=0;
595    int numberFixed=0;
596    for (i=0;i<numberIntegers;i++) {
597      int iColumn = integerVariable[i];
598      if (upper[iColumn]>lower[iColumn]) {
599        if (!mark_||!mark_[iColumn]) {
600          if(solution[iColumn]<lower[iColumn]+tolerance) {
601            if (dj[iColumn]>djTolerance_) {
602              nSort++;
603            }
604          } else if (solution[iColumn]>upper[iColumn]-tolerance) {
605            if (dj[iColumn]<-djTolerance_) {
606              nSort++;
607            }
608          }
609        }
610      } else {
611        numberFixed++;
612      }
613    }
614    if (numberFixed+nSort<wantedFixed&&!alwaysCreate_) {
615      returnCode = 0;
616    } else if (numberFixed<wantedFixed) {
617      returnCode = 1;
618    } else {
619      returnCode = 0;
620    }
621  }
622  if (numberClean_) {
623    // see how many rows clean
624    int i;
625    //const double * rowLower = solver->getRowLower();
626    const double * rowUpper = solver->getRowUpper();
627    // Row copy
628    const double * elementByRow = matrixByRow_.getElements();
629    const int * column = matrixByRow_.getIndices();
630    const CoinBigIndex * rowStart = matrixByRow_.getVectorStarts();
631    const int * rowLength = matrixByRow_.getVectorLengths();
632    const double * columnLower = solver->getColLower();
633    const double * columnUpper = solver->getColUpper();
634    const double * solution = solver->getColSolution();
635    int numberClean=0;
636    bool someToDoYet=false;
637    int numberColumns = solver->getNumCols();
638    char * mark = new char[numberColumns];
639    int numberFixed=0;
640    for (i=0;i<numberColumns;i++) {
641      if (columnLower[i]!=columnUpper[i]){
642        mark[i]=0;
643      } else {
644        mark[i]=1;
645        numberFixed++;
646      }
647    }
648    int numberNewFixed=0;
649    for (i=0;i<numberRows;i++) {
650      double rhsValue = rowUpper[i];
651      bool oneRow=true;
652      // check elements
653      int numberUnsatisfied=0;
654      for (int j=rowStart[i];j<rowStart[i]+rowLength[i];j++) {
655        int iColumn = column[j];
656        double value = elementByRow[j];
657        double solValue = solution[iColumn];
658        if (columnLower[iColumn]!=columnUpper[iColumn]) {
659          if (solValue<1.0-integerTolerance&&solValue>integerTolerance)
660            numberUnsatisfied++;
661          if (value!=1.0) {
662            oneRow=false;
663            break;
664          }
665        } else {
666          rhsValue -= value*floor(solValue+0.5);
667        }
668      }
669      if (oneRow&&rhsValue<=1.0+tolerance) {
670        if (numberUnsatisfied) {
671          someToDoYet=true;
672        } else {
673          numberClean++;
674          for (int j=rowStart[i];j<rowStart[i]+rowLength[i];j++) {
675            int iColumn = column[j];
676            if (columnLower[iColumn]!=columnUpper[iColumn]&&!mark[iColumn]){
677              mark[iColumn]=1;
678              numberNewFixed++;
679            }
680          }
681        }
682      }
683    }
684    delete [] mark;
685    //printf("%d clean, %d old fixed, %d new fixed\n",
686    //   numberClean,numberFixed,numberNewFixed);
687    if (someToDoYet&&numberClean<numberClean_
688        &&numberNewFixed+numberFixed<wantedFixed) {
689    } else if (numberFixed<wantedFixed) {
690      returnCode |= 2;
691    } else {
692    }
693  }
694  return returnCode;
695}
696// Infeasibility - large is 0.5
697double 
698CbcBranchToFixLots::infeasibility(int & preferredWay) const
699{
700  preferredWay=-1;
701  CbcNode * node = model_->currentNode();
702  int depth;
703  if (node)
704    depth=CoinMax(node->depth(),0);
705  else
706    return 0.0;
707  if (depth_<0) {
708    return 0.0;
709  } else if (depth_>0) {
710    if ((depth%depth_)!=0)
711      return 0.0;
712  }
713  if (!shallWe())
714    return 0.0;
715  else
716    return 1.0e20;
717}
718
719/** Default Constructor
720*/
721CbcBranchAllDifferent::CbcBranchAllDifferent ()
722  : CbcBranchCut(),
723    numberInSet_(0),
724    which_(NULL)
725{
726}
727
728/* Useful constructor - passed set of variables
729*/ 
730CbcBranchAllDifferent::CbcBranchAllDifferent (CbcModel * model, int numberInSet,
731                                              const int * members)
732  : CbcBranchCut(model)
733{
734  numberInSet_=numberInSet;
735  which_ = CoinCopyOfArray(members,numberInSet_);
736}
737// Copy constructor
738CbcBranchAllDifferent::CbcBranchAllDifferent ( const CbcBranchAllDifferent & rhs)
739  :CbcBranchCut(rhs)
740{
741  numberInSet_=rhs.numberInSet_;
742  which_ = CoinCopyOfArray(rhs.which_,numberInSet_);
743}
744
745// Clone
746CbcObject *
747CbcBranchAllDifferent::clone() const
748{
749  return new CbcBranchAllDifferent(*this);
750}
751
752// Assignment operator
753CbcBranchAllDifferent & 
754CbcBranchAllDifferent::operator=( const CbcBranchAllDifferent& rhs)
755{
756  if (this!=&rhs) {
757    CbcBranchCut::operator=(rhs);
758    delete [] which_;
759    numberInSet_=rhs.numberInSet_;
760    which_ = CoinCopyOfArray(rhs.which_,numberInSet_);
761  }
762  return *this;
763}
764
765// Destructor
766CbcBranchAllDifferent::~CbcBranchAllDifferent ()
767{
768  delete [] which_;
769}
770// Creates a branching object
771CbcBranchingObject * 
772CbcBranchAllDifferent::createBranch(int way) 
773{
774  // by default way must be -1
775  assert (way==-1);
776  const double * solution = model_->testSolution();
777  double * values = new double[numberInSet_];
778  int * which = new int[numberInSet_];
779  int i;
780  for (i=0;i<numberInSet_;i++) {
781    int iColumn = which_[i];
782    values[i]=solution[iColumn];
783    which[i]=iColumn;
784  }
785  CoinSort_2(values,values+numberInSet_,which);
786  double last = -1.0;
787  double closest=1.0;
788  int worst=-1;
789  for (i=0;i<numberInSet_;i++) {
790    if (values[i]-last<closest) {
791      closest=values[i]-last;
792      worst=i-1;
793    }
794    last=values[i];
795  }
796  assert (closest<=0.99999);
797  OsiRowCut down;
798  down.setLb(-COIN_DBL_MAX);
799  down.setUb(-1.0);
800  int pair[2];
801  double elements[]={1.0,-1.0};
802  pair[0]=which[worst];
803  pair[1]=which[worst+1];
804  delete [] values;
805  delete [] which;
806  down.setRow(2,pair,elements);
807  // up is same - just with rhs changed
808  OsiRowCut up = down;
809  up.setLb(1.0);
810  up.setUb(COIN_DBL_MAX);
811  // Say is not a fix type branch
812  CbcCutBranchingObject * newObject = 
813    new CbcCutBranchingObject(model_,down,up,false);
814  if (model_->messageHandler()->logLevel()>1)
815    printf("creating cut in CbcBranchCut\n");
816  return newObject;
817}
818// Infeasibility - large is 0.5
819double 
820CbcBranchAllDifferent::infeasibility(int & preferredWay) const
821{
822  preferredWay=-1;
823  //OsiSolverInterface * solver = model_->solver();
824  const double * solution = model_->testSolution();
825  //const double * lower = solver->getColLower();
826  //const double * upper = solver->getColUpper();
827  double * values = new double[numberInSet_];
828  int i;
829  for (i=0;i<numberInSet_;i++) {
830    int iColumn = which_[i];
831    values[i]=solution[iColumn];
832  }
833  std::sort(values,values+numberInSet_);
834  double last = -1.0;
835  double closest=1.0;
836  for (i=0;i<numberInSet_;i++) {
837    if (values[i]-last<closest) {
838      closest=values[i]-last;
839    }
840    last=values[i];
841  }
842  delete [] values;
843  if (closest>0.99999)
844    return 0.0;
845  else
846    return 0.5*(1.0-closest);
847}
Note: See TracBrowser for help on using the repository browser.