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

Last change on this file since 1121 was 1121, checked in by forrest, 10 years ago

compiler warnings, deterministic parallel and stability

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 23.7 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  // leave as cut
223  //model_->setNextRowCut(*cut);
224  //return 0.0;
225  // assume cut was cunningly constructed so we need not worry too much about tolerances
226  if (low+1.0e-8>=ub&&canFix_) {
227    // fix
228    for (int i=0;i<n;i++) {
229      int iColumn = column[i];
230      double value = element[i];
231      if (value>0.0) {
232        solver->setColUpper(iColumn,lower[iColumn]);
233      } else {
234        solver->setColLower(iColumn,upper[iColumn]);
235      }
236    }
237  } else if (high-1.0e-8<=lb&&canFix_) {
238    // fix
239    for (int i=0;i<n;i++) {
240      int iColumn = column[i];
241      double value = element[i];
242      if (value>0.0) {
243        solver->setColLower(iColumn,upper[iColumn]);
244      } else {
245        solver->setColUpper(iColumn,lower[iColumn]);
246      }
247    }
248  } else {
249    // leave as cut
250    model_->setNextRowCut(*cut);
251  }
252  return 0.0;
253}
254// Print what would happen 
255void
256CbcCutBranchingObject::print()
257{
258  OsiRowCut * cut;
259  if (way_<0) {
260    cut = &down_;
261    printf("CbcCut would branch down");
262  } else {
263    cut = &up_;
264    printf("CbcCut would branch up");
265  }
266  double lb = cut->lb();
267  double ub = cut->ub();
268  int n=cut->row().getNumElements();
269  const int * column = cut->row().getIndices();
270  const double * element = cut->row().getElements();
271  if (n>5) {
272    printf(" - %d elements, lo=%g, up=%g\n",n,lb,ub);
273  } else {
274    printf(" - %g <=",lb);
275    for (int i=0;i<n;i++) {
276      int iColumn = column[i];
277      double value = element[i];
278      printf(" (%d,%g)",iColumn,value);
279    }
280    printf(" <= %g\n",ub);
281  }
282}
283
284// Return true if branch should fix variables
285bool 
286CbcCutBranchingObject::boundBranch() const
287{
288  return false;
289}
290
291/** Compare the original object of \c this with the original object of \c
292    brObj. Assumes that there is an ordering of the original objects.
293    This method should be invoked only if \c this and brObj are of the same
294    type.
295    Return negative/0/positive depending on whether \c this is
296    smaller/same/larger than the argument.
297*/
298int
299CbcCutBranchingObject::compareOriginalObject
300(const CbcBranchingObject* brObj) const
301{
302  const CbcCutBranchingObject* br =
303    dynamic_cast<const CbcCutBranchingObject*>(brObj);
304  assert(br);
305  const OsiRowCut& r0 = way_ == -1 ? down_ : up_;
306  const OsiRowCut& r1 = br->way_ == -1 ? br->down_ : br->up_;
307  return r0.row().compare(r1.row());
308}
309
310/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
311    same type and must have the same original object, but they may have
312    different feasible regions.
313    Return the appropriate CbcRangeCompare value (first argument being the
314    sub/superset if that's the case). In case of overlap (and if \c
315    replaceIfOverlap is true) replace the current branching object with one
316    whose feasible region is the overlap.
317*/
318
319CbcRangeCompare
320CbcCutBranchingObject::compareBranchingObject
321(const CbcBranchingObject* brObj, const bool replaceIfOverlap)
322{
323  const CbcCutBranchingObject* br =
324    dynamic_cast<const CbcCutBranchingObject*>(brObj);
325  assert(br);
326  OsiRowCut& r0 = way_ == -1 ? down_ : up_;
327  const OsiRowCut& r1 = br->way_ == -1 ? br->down_ : br->up_;
328  double thisBd[2];
329  thisBd[0] = r0.lb();
330  thisBd[1] = r0.ub();
331  double otherBd[2];
332  otherBd[0] = r1.lb();
333  otherBd[1] = r1.ub();
334  CbcRangeCompare comp = CbcCompareRanges(thisBd, otherBd, replaceIfOverlap);
335  if (comp != CbcRangeOverlap || (comp==CbcRangeOverlap && !replaceIfOverlap)) {
336    return comp;
337  }
338  r0.setLb(thisBd[0]);
339  r0.setUb(thisBd[1]);
340  return comp;
341}
342
343//##############################################################################
344
345/** Default Constructor
346
347  Equivalent to an unspecified binary variable.
348*/
349CbcBranchToFixLots::CbcBranchToFixLots ()
350  : CbcBranchCut(),
351    djTolerance_(COIN_DBL_MAX),
352    fractionFixed_(1.0),
353    mark_(NULL),
354    depth_(-1),
355    numberClean_(0),
356    alwaysCreate_(false)
357{
358}
359
360/* Useful constructor - passed reduced cost tolerance and fraction we would like fixed.
361   Also depth level to do at.
362   Also passed number of 1 rows which when clean triggers fix
363   Always does if all 1 rows cleaned up and number>0 or if fraction columns reached
364   Also whether to create branch if can't reach fraction.
365*/ 
366CbcBranchToFixLots::CbcBranchToFixLots (CbcModel * model, double djTolerance,
367                                        double fractionFixed, int depth,
368                                        int numberClean,
369                                        const char * mark, bool alwaysCreate)
370  : CbcBranchCut(model)
371{
372  djTolerance_ = djTolerance;
373  fractionFixed_ = fractionFixed;
374  if (mark) {
375    int numberColumns = model->getNumCols();
376    mark_ = new char[numberColumns];
377    memcpy(mark_,mark,numberColumns);
378  } else {
379    mark_ = NULL;
380  }
381  depth_ = depth;
382  assert (model);
383  OsiSolverInterface * solver = model_->solver();
384  matrixByRow_ = *solver->getMatrixByRow();
385  numberClean_ = numberClean;
386  alwaysCreate_ = alwaysCreate;
387}
388// Copy constructor
389CbcBranchToFixLots::CbcBranchToFixLots ( const CbcBranchToFixLots & rhs)
390  :CbcBranchCut(rhs)
391{
392  djTolerance_ = rhs.djTolerance_;
393  fractionFixed_ = rhs.fractionFixed_;
394  int numberColumns = model_->getNumCols();
395  mark_ = CoinCopyOfArray(rhs.mark_,numberColumns);
396  matrixByRow_=rhs.matrixByRow_;
397  depth_ = rhs.depth_;
398  numberClean_ = rhs.numberClean_;
399  alwaysCreate_ = rhs.alwaysCreate_;
400}
401
402// Clone
403CbcObject *
404CbcBranchToFixLots::clone() const
405{
406  return new CbcBranchToFixLots(*this);
407}
408
409// Assignment operator
410CbcBranchToFixLots & 
411CbcBranchToFixLots::operator=( const CbcBranchToFixLots& rhs)
412{
413  if (this!=&rhs) {
414    CbcBranchCut::operator=(rhs);
415    djTolerance_ = rhs.djTolerance_;
416    fractionFixed_ = rhs.fractionFixed_;
417    int numberColumns = model_->getNumCols();
418    delete [] mark_;
419    mark_ = CoinCopyOfArray(rhs.mark_,numberColumns);
420    matrixByRow_=rhs.matrixByRow_;
421    depth_ = rhs.depth_;
422    numberClean_ = rhs.numberClean_;
423    alwaysCreate_ = rhs.alwaysCreate_;
424  }
425  return *this;
426}
427
428// Destructor
429CbcBranchToFixLots::~CbcBranchToFixLots ()
430{
431  delete [] mark_;
432}
433// Creates a branching object
434CbcBranchingObject * 
435CbcBranchToFixLots::createBranch(int way) 
436{
437  // by default way must be -1
438  assert (way==-1);
439  OsiSolverInterface * solver = model_->solver();
440  const double * solution = model_->testSolution();
441  const double * lower = solver->getColLower();
442  const double * upper = solver->getColUpper();
443  const double * dj = solver->getReducedCost();
444  int i;
445  int numberIntegers = model_->numberIntegers();
446  const int * integerVariable = model_->integerVariable();
447  double integerTolerance = 
448    model_->getDblParam(CbcModel::CbcIntegerTolerance);
449  // make smaller ?
450  double tolerance = CoinMin(1.0e-8,integerTolerance);
451  // How many fixed are we aiming at
452  int wantedFixed = static_cast<int> (static_cast<double>(numberIntegers)*fractionFixed_);
453  int nSort=0;
454  int numberFixed=0;
455  int numberColumns = solver->getNumCols();
456  int * sort = new int[numberColumns];
457  double * dsort = new double[numberColumns];
458  int type = shallWe();
459  assert (type);
460  // Take clean first
461  if (type==1) {
462    for (i=0;i<numberIntegers;i++) {
463      int iColumn = integerVariable[i];
464      if (upper[iColumn]>lower[iColumn]) {
465        if (!mark_||!mark_[iColumn]) {
466          if(solution[iColumn]<lower[iColumn]+tolerance) {
467            if (dj[iColumn]>djTolerance_) {
468              dsort[nSort]=-dj[iColumn];
469              sort[nSort++]=iColumn;
470            }
471          } else if (solution[iColumn]>upper[iColumn]-tolerance) {
472            if (dj[iColumn]<-djTolerance_) {
473              dsort[nSort]=dj[iColumn];
474              sort[nSort++]=iColumn;
475            }
476          }
477        }
478      } else {
479        numberFixed++;
480      }
481    }
482    // sort
483    CoinSort_2(dsort,dsort+nSort,sort);
484    nSort= CoinMin(nSort,wantedFixed-numberFixed);
485  } else if (type<10) {
486    int i;
487    //const double * rowLower = solver->getRowLower();
488    const double * rowUpper = solver->getRowUpper();
489    // Row copy
490    const double * elementByRow = matrixByRow_.getElements();
491    const int * column = matrixByRow_.getIndices();
492    const CoinBigIndex * rowStart = matrixByRow_.getVectorStarts();
493    const int * rowLength = matrixByRow_.getVectorLengths();
494    const double * columnLower = solver->getColLower();
495    const double * columnUpper = solver->getColUpper();
496    const double * solution = solver->getColSolution();
497    int numberColumns = solver->getNumCols();
498    int numberRows = solver->getNumRows();
499    for (i=0;i<numberColumns;i++) {
500      sort[i]=i;
501      if (columnLower[i]!=columnUpper[i]){
502        dsort[i]=1.0e100;
503      } else {
504        dsort[i]=1.0e50;
505        numberFixed++;
506      }
507    }
508    for (i=0;i<numberRows;i++) {
509      double rhsValue = rowUpper[i];
510      bool oneRow=true;
511      // check elements
512      int numberUnsatisfied=0;
513      for (int j=rowStart[i];j<rowStart[i]+rowLength[i];j++) {
514        int iColumn = column[j];
515        double value = elementByRow[j];
516        double solValue = solution[iColumn];
517        if (columnLower[iColumn]!=columnUpper[iColumn]) {
518          if (solValue<1.0-integerTolerance&&solValue>integerTolerance)
519            numberUnsatisfied++;
520          if (value!=1.0) {
521            oneRow=false;
522            break;
523          }
524        } else {
525          rhsValue -= value*floor(solValue+0.5);
526        }
527      }
528      if (oneRow&&rhsValue<=1.0+tolerance) {
529        if (!numberUnsatisfied) {
530          for (int j=rowStart[i];j<rowStart[i]+rowLength[i];j++) {
531            int iColumn = column[j];
532            if (dsort[iColumn]>1.0e50){
533              dsort[iColumn]=0;
534              nSort++;
535            }
536          }
537        }
538      }
539    }
540    // sort
541    CoinSort_2(dsort,dsort+numberColumns,sort);
542  } else {
543    // new way
544    for (i=0;i<numberIntegers;i++) {
545      int iColumn = integerVariable[i];
546      if (upper[iColumn]>lower[iColumn]) {
547        if (!mark_||!mark_[iColumn]) {
548          double distanceDown=solution[iColumn]-lower[iColumn];
549          double distanceUp=upper[iColumn]-solution[iColumn];
550          double distance = CoinMin(distanceDown,distanceUp);
551          if (distance>0.001&&distance<0.5) {
552            dsort[nSort]=distance;
553            sort[nSort++]=iColumn;
554          }
555        }
556      }
557    }
558    // sort
559    CoinSort_2(dsort,dsort+nSort,sort);
560    int n=0;
561    double sum=0.0;
562    for (int k=0;k<nSort;k++) {
563      sum += dsort[k];
564      if (sum<=djTolerance_)
565        n=k;
566      else
567        break;
568    }
569    nSort = CoinMin(n,numberClean_/1000000);
570  }
571  OsiRowCut down;
572  down.setLb(-COIN_DBL_MAX);
573  double rhs=0.0;
574  for (i=0;i<nSort;i++) {
575    int iColumn = sort[i];
576    double distanceDown=solution[iColumn]-lower[iColumn];
577    double distanceUp=upper[iColumn]-solution[iColumn];
578    if(distanceDown<distanceUp) {
579      rhs += lower[iColumn];
580      dsort[i]=1.0;
581    } else {
582      rhs -= upper[iColumn];
583      dsort[i]=-1.0;
584    }
585  }
586  down.setUb(rhs);
587  down.setRow(nSort,sort,dsort);
588  down.setEffectiveness(COIN_DBL_MAX); // so will persist
589  delete [] sort;
590  delete [] dsort;
591  // up is same - just with rhs changed
592  OsiRowCut up = down;
593  up.setLb(rhs +1.0);
594  up.setUb(COIN_DBL_MAX);
595  // Say can fix one way
596  CbcCutBranchingObject * newObject = 
597    new CbcCutBranchingObject(model_,down,up,true);
598  if (model_->messageHandler()->logLevel()>1)
599    printf("creating cut in CbcBranchCut\n");
600  return newObject;
601}
602/* Does a lot of the work,
603   Returns 0 if no good, 1 if dj, 2 if clean, 3 if both
604   10 if branching on ones away from bound
605*/
606int 
607CbcBranchToFixLots::shallWe() const
608{
609  int returnCode=0;
610  OsiSolverInterface * solver = model_->solver();
611  int numberRows = matrixByRow_.getNumRows();
612  //if (numberRows!=solver->getNumRows())
613  //return 0;
614  const double * solution = model_->testSolution();
615  const double * lower = solver->getColLower();
616  const double * upper = solver->getColUpper();
617  const double * dj = solver->getReducedCost();
618  int i;
619  int numberIntegers = model_->numberIntegers();
620  const int * integerVariable = model_->integerVariable();
621  if (numberClean_>1000000) {
622    int wanted = numberClean_%1000000;
623    int * sort = new int[numberIntegers];
624    double * dsort = new double[numberIntegers];
625    int nSort=0;
626    for (i=0;i<numberIntegers;i++) {
627      int iColumn = integerVariable[i];
628      if (upper[iColumn]>lower[iColumn]) {
629        if (!mark_||!mark_[iColumn]) {
630          double distanceDown=solution[iColumn]-lower[iColumn];
631          double distanceUp=upper[iColumn]-solution[iColumn];
632          double distance = CoinMin(distanceDown,distanceUp);
633          if (distance>0.001&&distance<0.5) {
634            dsort[nSort]=distance;
635            sort[nSort++]=iColumn;
636          }
637        }
638      }
639    }
640    // sort
641    CoinSort_2(dsort,dsort+nSort,sort);
642    int n=0;
643    double sum=0.0;
644    for (int k=0;k<nSort;k++) {
645      sum += dsort[k];
646      if (sum<=djTolerance_)
647        n=k;
648      else
649        break;
650    }
651    delete [] sort;
652    delete [] dsort;
653    return (n>=wanted) ? 10 : 0;
654  }
655  double integerTolerance = 
656    model_->getDblParam(CbcModel::CbcIntegerTolerance);
657  // make smaller ?
658  double tolerance = CoinMin(1.0e-8,integerTolerance);
659  // How many fixed are we aiming at
660  int wantedFixed = static_cast<int> (static_cast<double>(numberIntegers)*fractionFixed_);
661  if (djTolerance_<1.0e10) {
662    int nSort=0;
663    int numberFixed=0;
664    for (i=0;i<numberIntegers;i++) {
665      int iColumn = integerVariable[i];
666      if (upper[iColumn]>lower[iColumn]) {
667        if (!mark_||!mark_[iColumn]) {
668          if(solution[iColumn]<lower[iColumn]+tolerance) {
669            if (dj[iColumn]>djTolerance_) {
670              nSort++;
671            }
672          } else if (solution[iColumn]>upper[iColumn]-tolerance) {
673            if (dj[iColumn]<-djTolerance_) {
674              nSort++;
675            }
676          }
677        }
678      } else {
679        numberFixed++;
680      }
681    }
682    if (numberFixed+nSort<wantedFixed&&!alwaysCreate_) {
683      returnCode = 0;
684    } else if (numberFixed<wantedFixed) {
685      returnCode = 1;
686    } else {
687      returnCode = 0;
688    }
689  }
690  if (numberClean_) {
691    // see how many rows clean
692    int i;
693    //const double * rowLower = solver->getRowLower();
694    const double * rowUpper = solver->getRowUpper();
695    // Row copy
696    const double * elementByRow = matrixByRow_.getElements();
697    const int * column = matrixByRow_.getIndices();
698    const CoinBigIndex * rowStart = matrixByRow_.getVectorStarts();
699    const int * rowLength = matrixByRow_.getVectorLengths();
700    const double * columnLower = solver->getColLower();
701    const double * columnUpper = solver->getColUpper();
702    const double * solution = solver->getColSolution();
703    int numberClean=0;
704    bool someToDoYet=false;
705    int numberColumns = solver->getNumCols();
706    char * mark = new char[numberColumns];
707    int numberFixed=0;
708    for (i=0;i<numberColumns;i++) {
709      if (columnLower[i]!=columnUpper[i]){
710        mark[i]=0;
711      } else {
712        mark[i]=1;
713        numberFixed++;
714      }
715    }
716    int numberNewFixed=0;
717    for (i=0;i<numberRows;i++) {
718      double rhsValue = rowUpper[i];
719      bool oneRow=true;
720      // check elements
721      int numberUnsatisfied=0;
722      for (int j=rowStart[i];j<rowStart[i]+rowLength[i];j++) {
723        int iColumn = column[j];
724        double value = elementByRow[j];
725        double solValue = solution[iColumn];
726        if (columnLower[iColumn]!=columnUpper[iColumn]) {
727          if (solValue<1.0-integerTolerance&&solValue>integerTolerance)
728            numberUnsatisfied++;
729          if (value!=1.0) {
730            oneRow=false;
731            break;
732          }
733        } else {
734          rhsValue -= value*floor(solValue+0.5);
735        }
736      }
737      if (oneRow&&rhsValue<=1.0+tolerance) {
738        if (numberUnsatisfied) {
739          someToDoYet=true;
740        } else {
741          numberClean++;
742          for (int j=rowStart[i];j<rowStart[i]+rowLength[i];j++) {
743            int iColumn = column[j];
744            if (columnLower[iColumn]!=columnUpper[iColumn]&&!mark[iColumn]){
745              mark[iColumn]=1;
746              numberNewFixed++;
747            }
748          }
749        }
750      }
751    }
752    delete [] mark;
753    //printf("%d clean, %d old fixed, %d new fixed\n",
754    //   numberClean,numberFixed,numberNewFixed);
755    if (someToDoYet&&numberClean<numberClean_
756        &&numberNewFixed+numberFixed<wantedFixed) {
757    } else if (numberFixed<wantedFixed) {
758      returnCode |= 2;
759    } else {
760    }
761  }
762  return returnCode;
763}
764// Infeasibility - large is 0.5
765double 
766CbcBranchToFixLots::infeasibility(int & preferredWay) const
767{
768  preferredWay=-1;
769  CbcNode * node = model_->currentNode();
770  int depth;
771  if (node)
772    depth=CoinMax(node->depth(),0);
773  else
774    return 0.0;
775  if (depth_<0) {
776    return 0.0;
777  } else if (depth_>0) {
778    if ((depth%depth_)!=0)
779      return 0.0;
780  }
781  if (!shallWe())
782    return 0.0;
783  else
784    return 1.0e20;
785}
786
787/** Default Constructor
788*/
789CbcBranchAllDifferent::CbcBranchAllDifferent ()
790  : CbcBranchCut(),
791    numberInSet_(0),
792    which_(NULL)
793{
794}
795
796/* Useful constructor - passed set of variables
797*/ 
798CbcBranchAllDifferent::CbcBranchAllDifferent (CbcModel * model, int numberInSet,
799                                              const int * members)
800  : CbcBranchCut(model)
801{
802  numberInSet_=numberInSet;
803  which_ = CoinCopyOfArray(members,numberInSet_);
804}
805// Copy constructor
806CbcBranchAllDifferent::CbcBranchAllDifferent ( const CbcBranchAllDifferent & rhs)
807  :CbcBranchCut(rhs)
808{
809  numberInSet_=rhs.numberInSet_;
810  which_ = CoinCopyOfArray(rhs.which_,numberInSet_);
811}
812
813// Clone
814CbcObject *
815CbcBranchAllDifferent::clone() const
816{
817  return new CbcBranchAllDifferent(*this);
818}
819
820// Assignment operator
821CbcBranchAllDifferent & 
822CbcBranchAllDifferent::operator=( const CbcBranchAllDifferent& rhs)
823{
824  if (this!=&rhs) {
825    CbcBranchCut::operator=(rhs);
826    delete [] which_;
827    numberInSet_=rhs.numberInSet_;
828    which_ = CoinCopyOfArray(rhs.which_,numberInSet_);
829  }
830  return *this;
831}
832
833// Destructor
834CbcBranchAllDifferent::~CbcBranchAllDifferent ()
835{
836  delete [] which_;
837}
838// Creates a branching object
839CbcBranchingObject * 
840CbcBranchAllDifferent::createBranch(int way) 
841{
842  // by default way must be -1
843  assert (way==-1);
844  const double * solution = model_->testSolution();
845  double * values = new double[numberInSet_];
846  int * which = new int[numberInSet_];
847  int i;
848  for (i=0;i<numberInSet_;i++) {
849    int iColumn = which_[i];
850    values[i]=solution[iColumn];
851    which[i]=iColumn;
852  }
853  CoinSort_2(values,values+numberInSet_,which);
854  double last = -1.0;
855  double closest=1.0;
856  int worst=-1;
857  for (i=0;i<numberInSet_;i++) {
858    if (values[i]-last<closest) {
859      closest=values[i]-last;
860      worst=i-1;
861    }
862    last=values[i];
863  }
864  assert (closest<=0.99999);
865  OsiRowCut down;
866  down.setLb(-COIN_DBL_MAX);
867  down.setUb(-1.0);
868  int pair[2];
869  double elements[]={1.0,-1.0};
870  pair[0]=which[worst];
871  pair[1]=which[worst+1];
872  delete [] values;
873  delete [] which;
874  down.setRow(2,pair,elements);
875  // up is same - just with rhs changed
876  OsiRowCut up = down;
877  up.setLb(1.0);
878  up.setUb(COIN_DBL_MAX);
879  // Say is not a fix type branch
880  CbcCutBranchingObject * newObject = 
881    new CbcCutBranchingObject(model_,down,up,false);
882  if (model_->messageHandler()->logLevel()>1)
883    printf("creating cut in CbcBranchCut\n");
884  return newObject;
885}
886// Infeasibility - large is 0.5
887double 
888CbcBranchAllDifferent::infeasibility(int & preferredWay) const
889{
890  preferredWay=-1;
891  //OsiSolverInterface * solver = model_->solver();
892  const double * solution = model_->testSolution();
893  //const double * lower = solver->getColLower();
894  //const double * upper = solver->getColUpper();
895  double * values = new double[numberInSet_];
896  int i;
897  for (i=0;i<numberInSet_;i++) {
898    int iColumn = which_[i];
899    values[i]=solution[iColumn];
900  }
901  std::sort(values,values+numberInSet_);
902  double last = -1.0;
903  double closest=1.0;
904  for (i=0;i<numberInSet_;i++) {
905    if (values[i]-last<closest) {
906      closest=values[i]-last;
907    }
908    last=values[i];
909  }
910  delete [] values;
911  if (closest>0.99999)
912    return 0.0;
913  else
914    return 0.5*(1.0-closest);
915}
Note: See TracBrowser for help on using the repository browser.