source: trunk/CbcBranchActual.cpp @ 104

Last change on this file since 104 was 104, checked in by forrest, 16 years ago

get overlapping sets to work

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 61.2 KB
Line 
1// Copyright (C) 2002, 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 <cmath>
9#include <cfloat>
10//#define CBC_DEBUG
11
12#include "OsiSolverInterface.hpp"
13#include "CbcModel.hpp"
14#include "CbcMessage.hpp"
15#include "CbcBranchActual.hpp"
16#include "CoinSort.hpp"
17#include "CoinError.hpp"
18
19// Default Constructor
20CbcClique::CbcClique ()
21  : CbcObject(),
22    numberMembers_(0),
23    numberNonSOSMembers_(0),
24    members_(NULL),
25    type_(NULL),
26    cliqueType_(-1),
27    slack_(-1)
28{
29}
30
31// Useful constructor (which are integer indices)
32CbcClique::CbcClique (CbcModel * model, int cliqueType, int numberMembers,
33           const int * which, const char * type, int identifier,int slack)
34  : CbcObject(model)
35{
36  id_=identifier;
37  numberMembers_=numberMembers;
38  if (numberMembers_) {
39    members_ = new int[numberMembers_];
40    memcpy(members_,which,numberMembers_*sizeof(int));
41    type_ = new char[numberMembers_];
42    if (type) {
43      memcpy(type_,type,numberMembers_*sizeof(char));
44    } else {
45      for (int i=0;i<numberMembers_;i++)
46        type_[i]=1;
47    }
48  } else {
49    members_ = NULL;
50    type_ = NULL;
51  }
52  // Find out how many non sos
53  int i;
54  numberNonSOSMembers_=0;
55  for (i=0;i<numberMembers_;i++)
56    if (!type_[i])
57      numberNonSOSMembers_++;
58  cliqueType_ = cliqueType;
59  slack_ = slack;
60}
61
62// Copy constructor
63CbcClique::CbcClique ( const CbcClique & rhs)
64  :CbcObject(rhs)
65{
66  numberMembers_ = rhs.numberMembers_;
67  numberNonSOSMembers_ = rhs.numberNonSOSMembers_;
68  if (numberMembers_) {
69    members_ = new int[numberMembers_];
70    memcpy(members_,rhs.members_,numberMembers_*sizeof(int));
71    type_ = new char[numberMembers_];
72    memcpy(type_,rhs.type_,numberMembers_*sizeof(char));
73  } else {
74    members_ = NULL;
75    type_ = NULL;
76  }
77  cliqueType_ = rhs.cliqueType_;
78  slack_ = rhs.slack_;
79}
80
81// Clone
82CbcObject *
83CbcClique::clone() const
84{
85  return new CbcClique(*this);
86}
87
88// Assignment operator
89CbcClique & 
90CbcClique::operator=( const CbcClique& rhs)
91{
92  if (this!=&rhs) {
93    CbcObject::operator=(rhs);
94    delete [] members_;
95    delete [] type_;
96    numberMembers_ = rhs.numberMembers_;
97    numberNonSOSMembers_ = rhs.numberNonSOSMembers_;
98    if (numberMembers_) {
99      members_ = new int[numberMembers_];
100      memcpy(members_,rhs.members_,numberMembers_*sizeof(int));
101      type_ = new char[numberMembers_];
102      memcpy(type_,rhs.type_,numberMembers_*sizeof(char));
103    } else {
104      members_ = NULL;
105      type_ = NULL;
106    }
107    cliqueType_ = rhs.cliqueType_;
108    slack_ = rhs.slack_;
109  }
110  return *this;
111}
112
113// Destructor
114CbcClique::~CbcClique ()
115{
116  delete [] members_;
117  delete [] type_;
118}
119
120// Infeasibility - large is 0.5
121double 
122CbcClique::infeasibility(int & preferredWay) const
123{
124  int numberUnsatis=0, numberFree=0;
125  int j;
126  const int * integer = model_->integerVariable();
127  OsiSolverInterface * solver = model_->solver();
128  const double * solution = model_->currentSolution();
129  const double * lower = solver->getColLower();
130  const double * upper = solver->getColUpper();
131  double largestValue=0.0;
132  double integerTolerance = 
133    model_->getDblParam(CbcModel::CbcIntegerTolerance);
134  double * sort = new double[numberMembers_];
135
136  double slackValue=0.0;
137  for (j=0;j<numberMembers_;j++) {
138    int sequence = members_[j];
139    int iColumn = integer[sequence];
140    double value = solution[iColumn];
141    value = CoinMax(value, lower[iColumn]);
142    value = CoinMin(value, upper[iColumn]);
143    double nearest = floor(value+0.5);
144    double distance = fabs(value-nearest);
145    if (distance>integerTolerance) {
146      if (!type_[j])
147        value = 1.0-value; // non SOS
148      // if slack then choose that
149      if (j==slack_&&value>0.05)
150        slackValue = value;
151      largestValue = CoinMax(value,largestValue);
152      sort[numberUnsatis++]=-value;
153    } else if (upper[iColumn]>lower[iColumn]) {
154      numberFree++;
155    }
156  }
157  preferredWay=1;
158  double otherWay = 0.0;
159  if (numberUnsatis) {
160    // sort
161    std::sort(sort,sort+numberUnsatis);
162    for (j=0;j<numberUnsatis;j++) {
163      if ((j&1)!=0)
164        otherWay += -sort[j];
165    }
166    // Need to think more
167    double value = 0.2*numberUnsatis+0.01*(numberMembers_-numberFree);
168    if (fabs(largestValue-0.5)<0.1) {
169      // close to half
170      value +=0.1;
171    }
172    if (slackValue) {
173      // branching on slack
174      value += slackValue;
175    }
176    // scale other way
177    otherWay *= value/(1.0-otherWay);
178    delete [] sort;
179    return value;
180  } else {
181    delete [] sort;
182    return 0.0; // satisfied
183  }
184}
185
186// This looks at solution and sets bounds to contain solution
187void 
188CbcClique::feasibleRegion()
189{
190  int j;
191  const int * integer = model_->integerVariable();
192  OsiSolverInterface * solver = model_->solver();
193  const double * solution = model_->currentSolution();
194  const double * lower = solver->getColLower();
195  const double * upper = solver->getColUpper();
196  double integerTolerance = 
197    model_->getDblParam(CbcModel::CbcIntegerTolerance);
198 
199  for (j=0;j<numberMembers_;j++) {
200    int sequence = members_[j];
201    int iColumn = integer[sequence];
202    double value = solution[iColumn];
203    value = CoinMax(value, lower[iColumn]);
204    value = CoinMin(value, upper[iColumn]);
205    double nearest = floor(value+0.5);
206    double distance = fabs(value-nearest);
207    assert(distance<=integerTolerance);
208    solver->setColLower(iColumn,nearest);
209    solver->setColUpper(iColumn,nearest);
210  }
211}
212
213
214// Creates a branching object
215CbcBranchingObject * 
216CbcClique::createBranch(int way) const
217{
218  int numberUnsatis=0;
219  int j;
220  int nUp=0;
221  int nDown=0;
222  int numberFree=numberMembers_;
223  const int * integer = model_->integerVariable();
224  OsiSolverInterface * solver = model_->solver();
225  const double * solution = model_->currentSolution();
226  const double * lower = solver->getColLower();
227  const double * upper = solver->getColUpper();
228  int * upList = new int[numberMembers_];
229  int * downList = new int[numberMembers_];
230  double * sort = new double[numberMembers_];
231  double integerTolerance = 
232      model_->getDblParam(CbcModel::CbcIntegerTolerance);
233
234  double slackValue=0.0;
235  for (j=0;j<numberMembers_;j++) {
236    int sequence = members_[j];
237    int iColumn = integer[sequence];
238    double value = solution[iColumn];
239    value = CoinMax(value, lower[iColumn]);
240    value = CoinMin(value, upper[iColumn]);
241    double nearest = floor(value+0.5);
242    double distance = fabs(value-nearest);
243    if (distance>integerTolerance) {
244      if (!type_[j])
245        value = 1.0-value; // non SOS
246      // if slack then choose that
247      if (j==slack_&&value>0.05)
248        slackValue = value;
249      value = -value; // for sort
250      upList[numberUnsatis]=j;
251      sort[numberUnsatis++]=value;
252    } else if (upper[iColumn]>lower[iColumn]) {
253      upList[--numberFree]=j;
254    }
255  }
256  assert (numberUnsatis);
257  if (!slackValue) {
258    // sort
259    CoinSort_2(sort,sort+numberUnsatis,upList);
260    // put first in up etc
261    int kWay=1;
262    for (j=0;j<numberUnsatis;j++) {
263      if (kWay>0) 
264        upList[nUp++]=upList[j];
265      else
266        downList[nDown++]=upList[j];
267      kWay = -kWay;
268    }
269    for (j=numberFree;j<numberMembers_;j++) {
270      if (kWay>0)
271        upList[nUp++]=upList[j];
272      else
273        downList[nDown++]=upList[j];
274      kWay = -kWay;
275    }
276  } else {
277    // put slack to 0 in first way
278    nUp = 1;
279    upList[0]=slack_;
280    for (j=0;j<numberUnsatis;j++) {
281      downList[nDown++]=upList[j];
282    }
283    for (j=numberFree;j<numberMembers_;j++) {
284      downList[nDown++]=upList[j];
285    }
286  }
287  // create object
288  CbcBranchingObject * branch;
289  if (numberMembers_ <=64)
290     branch = new CbcCliqueBranchingObject(model_,this,way,
291                                         nDown,downList,nUp,upList);
292  else
293    branch = new CbcLongCliqueBranchingObject(model_,this,way,
294                                            nDown,downList,nUp,upList);
295  delete [] upList;
296  delete [] downList;
297  delete [] sort;
298  return branch;
299}
300
301// Default Constructor
302CbcSOS::CbcSOS ()
303  : CbcObject(),
304    members_(NULL),
305    weights_(NULL),
306    numberMembers_(0),
307    sosType_(-1)
308{
309}
310
311// Useful constructor (which are indices)
312CbcSOS::CbcSOS (CbcModel * model,  int numberMembers,
313           const int * which, const double * weights, int identifier,int type)
314  : CbcObject(model),
315    numberMembers_(numberMembers),
316    sosType_(type)
317{
318  id_=identifier;
319  if (numberMembers_) {
320    members_ = new int[numberMembers_];
321    weights_ = new double[numberMembers_];
322    memcpy(members_,which,numberMembers_*sizeof(int));
323    if (weights) {
324      memcpy(weights_,weights,numberMembers_*sizeof(double));
325    } else {
326      for (int i=0;i<numberMembers_;i++)
327        weights_[i]=i;
328    }
329    // sort so weights increasing
330    CoinSort_2(weights_,weights_+numberMembers_,members_);
331  } else {
332    members_ = NULL;
333    weights_ = NULL;
334  }
335  assert (sosType_>0&&sosType_<3);
336}
337
338// Copy constructor
339CbcSOS::CbcSOS ( const CbcSOS & rhs)
340  :CbcObject(rhs)
341{
342  numberMembers_ = rhs.numberMembers_;
343  sosType_ = rhs.sosType_;
344  if (numberMembers_) {
345    members_ = new int[numberMembers_];
346    weights_ = new double[numberMembers_];
347    memcpy(members_,rhs.members_,numberMembers_*sizeof(int));
348    memcpy(weights_,rhs.weights_,numberMembers_*sizeof(double));
349    weights_ = new double[numberMembers_];
350    memcpy(weights_,rhs.weights_,numberMembers_*sizeof(double));
351  } else {
352    members_ = NULL;
353    weights_ = NULL;
354  }
355}
356
357// Clone
358CbcObject *
359CbcSOS::clone() const
360{
361  return new CbcSOS(*this);
362}
363
364// Assignment operator
365CbcSOS & 
366CbcSOS::operator=( const CbcSOS& rhs)
367{
368  if (this!=&rhs) {
369    CbcObject::operator=(rhs);
370    delete [] members_;
371    delete [] weights_;
372    numberMembers_ = rhs.numberMembers_;
373    sosType_ = rhs.sosType_;
374    if (numberMembers_) {
375      members_ = new int[numberMembers_];
376      weights_ = new double[numberMembers_];
377      memcpy(members_,rhs.members_,numberMembers_*sizeof(int));
378      memcpy(weights_,rhs.weights_,numberMembers_*sizeof(double));
379      weights_ = new double[numberMembers_];
380      memcpy(weights_,rhs.weights_,numberMembers_*sizeof(double));
381    } else {
382      members_ = NULL;
383      weights_ = NULL;
384    }
385  }
386  return *this;
387}
388
389// Destructor
390CbcSOS::~CbcSOS ()
391{
392  delete [] members_;
393  delete [] weights_;
394}
395
396// Infeasibility - large is 0.5
397double 
398CbcSOS::infeasibility(int & preferredWay) const
399{
400  int j;
401  int firstNonZero=-1;
402  int lastNonZero = -1;
403  OsiSolverInterface * solver = model_->solver();
404  const double * solution = model_->currentSolution();
405  const double * lower = solver->getColLower();
406  const double * upper = solver->getColUpper();
407  //double largestValue=0.0;
408  double integerTolerance = 
409    model_->getDblParam(CbcModel::CbcIntegerTolerance);
410  double weight = 0.0;
411  double sum =0.0;
412
413  // check bounds etc
414  double lastWeight=-1.0e100;
415  for (j=0;j<numberMembers_;j++) {
416    int iColumn = members_[j];
417    if (lower[iColumn]&&(lower[iColumn]!=1.0||sosType_!=1))
418      throw CoinError("Non zero lower bound in SOS","constructor","CbcSOS");
419    if (lastWeight>=weights_[j]-1.0e-7)
420      throw CoinError("Weights too close together in SOS","constructor","CbcSOS");
421    double value = CoinMax(0.0,solution[iColumn]);
422    sum += value;
423    if (value>integerTolerance&&upper[iColumn]) {
424      // Possibly due to scaling a fixed variable might slip through
425      if (value>upper[iColumn]) {
426        // Could change to #ifdef CBC_DEBUG
427#ifndef NDEBUG
428        if (model_->messageHandler()->logLevel()>1)
429          printf("** Variable %d (%d) has value %g and upper bound of %g\n",
430                 iColumn,j,value,upper[iColumn]);
431#endif
432      } 
433      weight += weights_[j]*value;
434      if (firstNonZero<0)
435        firstNonZero=j;
436      lastNonZero=j;
437    }
438  }
439  preferredWay=1;
440  if (lastNonZero-firstNonZero>=sosType_) {
441    // find where to branch
442    assert (sum>0.0);
443    weight /= sum;
444    //int iWhere;
445    //for (iWhere=firstNonZero;iWhere<lastNonZero;iWhere++)
446    //if (weight<weights_[iWhere+1])
447    //break;
448    // probably best to use pseudo duals
449    double value = lastNonZero-firstNonZero+1;
450    value *= 0.5/((double) numberMembers_);
451    return value;
452  } else {
453    return 0.0; // satisfied
454  }
455}
456
457// This looks at solution and sets bounds to contain solution
458void 
459CbcSOS::feasibleRegion()
460{
461  int j;
462  int firstNonZero=-1;
463  int lastNonZero = -1;
464  OsiSolverInterface * solver = model_->solver();
465  const double * solution = model_->currentSolution();
466  //const double * lower = solver->getColLower();
467  const double * upper = solver->getColUpper();
468  double integerTolerance = 
469    model_->getDblParam(CbcModel::CbcIntegerTolerance);
470  double weight = 0.0;
471  double sum =0.0;
472
473  for (j=0;j<numberMembers_;j++) {
474    int iColumn = members_[j];
475    double value = CoinMax(0.0,solution[iColumn]);
476    sum += value;
477    if (value>integerTolerance&&upper[iColumn]) {
478      weight += weights_[j]*value;
479      if (firstNonZero<0)
480        firstNonZero=j;
481      lastNonZero=j;
482    }
483  }
484  assert (lastNonZero-firstNonZero<sosType_) ;
485  for (j=0;j<firstNonZero;j++) {
486    int iColumn = members_[j];
487    solver->setColUpper(iColumn,0.0);
488  }
489  for (j=lastNonZero+1;j<numberMembers_;j++) {
490    int iColumn = members_[j];
491    solver->setColUpper(iColumn,0.0);
492  }
493}
494
495
496// Creates a branching object
497CbcBranchingObject * 
498CbcSOS::createBranch(int way) const
499{
500  int j;
501  const double * solution = model_->currentSolution();
502  double integerTolerance = 
503      model_->getDblParam(CbcModel::CbcIntegerTolerance);
504  OsiSolverInterface * solver = model_->solver();
505  const double * upper = solver->getColUpper();
506  int firstNonFixed=-1;
507  int lastNonFixed=-1;
508  int firstNonZero=-1;
509  int lastNonZero = -1;
510  double weight = 0.0;
511  double sum =0.0;
512  for (j=0;j<numberMembers_;j++) {
513    int iColumn = members_[j];
514    if (upper[iColumn]) {
515      double value = CoinMax(0.0,solution[iColumn]);
516      sum += value;
517      if (firstNonFixed<0)
518        firstNonFixed=j;
519      lastNonFixed=j;
520      if (value>integerTolerance) {
521        weight += weights_[j]*value;
522        if (firstNonZero<0)
523          firstNonZero=j;
524        lastNonZero=j;
525      }
526    }
527  }
528  assert (lastNonZero-firstNonZero>=sosType_) ;
529  // find where to branch
530  assert (sum>0.0);
531  weight /= sum;
532  int iWhere;
533  double separator=0.0;
534  for (iWhere=firstNonZero;iWhere<lastNonZero;iWhere++) 
535    if (weight<weights_[iWhere+1])
536      break;
537  if (sosType_==1) {
538    // SOS 1
539    separator = 0.5 *(weights_[iWhere]+weights_[iWhere+1]);
540  } else {
541    // SOS 2
542    if (iWhere==firstNonFixed)
543      iWhere++;;
544    if (iWhere==lastNonFixed-1)
545      iWhere = lastNonFixed-2;
546    separator = weights_[iWhere+1];
547  }
548  // create object
549  CbcBranchingObject * branch;
550  branch = new CbcSOSBranchingObject(model_,this,way,separator);
551  return branch;
552}
553
554
555
556/** Default Constructor
557
558  Equivalent to an unspecified binary variable.
559*/
560CbcSimpleInteger::CbcSimpleInteger ()
561  : CbcObject(),
562    sequence_(-1),
563    columnNumber_(-1),
564    originalLower_(0.0),
565    originalUpper_(1.0),
566    breakEven_(0.5)
567{
568}
569
570/** Useful constructor
571
572  Loads actual upper & lower bounds for the specified variable.
573*/
574CbcSimpleInteger::CbcSimpleInteger (CbcModel * model, int sequence,
575                                    int iColumn, double breakEven)
576  : CbcObject(model)
577{
578  sequence_ = sequence ;
579  id_ = iColumn; // set as well
580  columnNumber_ = iColumn ;
581  originalLower_ = model_->solver()->getColLower()[columnNumber_] ;
582  originalUpper_ = model_->solver()->getColUpper()[columnNumber_] ;
583  breakEven_ = breakEven;
584  assert (breakEven_>0.0&&breakEven_<1.0);
585}
586
587// Copy constructor
588CbcSimpleInteger::CbcSimpleInteger ( const CbcSimpleInteger & rhs)
589  :CbcObject(rhs)
590
591{
592  sequence_ = rhs.sequence_;
593  columnNumber_ = rhs.columnNumber_;
594  originalLower_ = rhs.originalLower_;
595  originalUpper_ = rhs.originalUpper_;
596  breakEven_ = rhs.breakEven_;
597}
598
599// Clone
600CbcObject *
601CbcSimpleInteger::clone() const
602{
603  return new CbcSimpleInteger(*this);
604}
605
606// Assignment operator
607CbcSimpleInteger & 
608CbcSimpleInteger::operator=( const CbcSimpleInteger& rhs)
609{
610  if (this!=&rhs) {
611    CbcObject::operator=(rhs);
612    columnNumber_ = model_->integerVariable()[sequence_];
613    breakEven_ = rhs.breakEven_;
614  }
615  return *this;
616}
617
618// Destructor
619CbcSimpleInteger::~CbcSimpleInteger ()
620{
621}
622
623// Infeasibility - large is 0.5
624double 
625CbcSimpleInteger::infeasibility(int & preferredWay) const
626{
627  OsiSolverInterface * solver = model_->solver();
628  const double * solution = model_->currentSolution();
629  const double * lower = solver->getColLower();
630  const double * upper = solver->getColUpper();
631  double value = solution[columnNumber_];
632  value = CoinMax(value, lower[columnNumber_]);
633  value = CoinMin(value, upper[columnNumber_]);
634  /*printf("%d %g %g %g %g\n",columnNumber_,value,lower[columnNumber_],
635    solution[columnNumber_],upper[columnNumber_]);*/
636  double nearest = floor(value+(1.0-breakEven_));
637  double integerTolerance = 
638    model_->getDblParam(CbcModel::CbcIntegerTolerance);
639  if (nearest>value) 
640    preferredWay=1;
641  else
642    preferredWay=-1;
643  double weight = fabs(value-nearest);
644  // normalize so weight is 0.5 at break even
645  if (nearest<value)
646    weight = (0.5/breakEven_)*weight;
647  else
648    weight = (0.5/(1.0-breakEven_))*weight;
649  if (fabs(value-nearest)<=integerTolerance) 
650    return 0.0;
651  else
652    return weight;
653}
654
655// This looks at solution and sets bounds to contain solution
656/** More precisely: it first forces the variable within the existing
657    bounds, and then tightens the bounds to fix the variable at the
658    nearest integer value.
659*/
660void 
661CbcSimpleInteger::feasibleRegion()
662{
663  OsiSolverInterface * solver = model_->solver();
664  const double * lower = solver->getColLower();
665  const double * upper = solver->getColUpper();
666  const double * solution = model_->currentSolution();
667  double value = solution[columnNumber_];
668  value = CoinMax(value, lower[columnNumber_]);
669  value = CoinMin(value, upper[columnNumber_]);
670
671  double nearest = floor(value+0.5);
672  //double integerTolerance =
673  //model_->getDblParam(CbcModel::CbcIntegerTolerance);
674  // Scaling may have moved it a bit
675  //assert (fabs(value-nearest)<=100.0*integerTolerance);
676  assert (fabs(value-nearest)<=0.01);
677  solver->setColLower(columnNumber_,nearest);
678  solver->setColUpper(columnNumber_,nearest);
679}
680/* Column number if single column object -1 otherwise,
681   so returns >= 0
682   Used by heuristics
683*/
684int 
685CbcSimpleInteger::columnNumber() const
686{
687  return columnNumber_;
688}
689
690// Creates a branching object
691CbcBranchingObject * 
692CbcSimpleInteger::createBranch(int way) const
693{
694  OsiSolverInterface * solver = model_->solver();
695  const double * solution = model_->currentSolution();
696  const double * lower = solver->getColLower();
697  const double * upper = solver->getColUpper();
698  double value = solution[columnNumber_];
699  value = CoinMax(value, lower[columnNumber_]);
700  value = CoinMin(value, upper[columnNumber_]);
701  double nearest = floor(value+0.5);
702  double integerTolerance = 
703    model_->getDblParam(CbcModel::CbcIntegerTolerance);
704  assert (upper[columnNumber_]>lower[columnNumber_]);
705  int hotstartStrategy=model_->getHotstartStrategy();
706  if (hotstartStrategy<=0) {
707    assert (fabs(value-nearest)>integerTolerance);
708  } else {
709    const double * bestSolution = model_->bestSolution();
710    double targetValue = bestSolution[columnNumber_];
711    if (way>0)
712      value = targetValue-0.1;
713    else
714      value = targetValue+0.1;
715  }
716  return new CbcIntegerBranchingObject(model_,sequence_,way,
717                                             value);
718}
719
720
721/* Given valid solution (i.e. satisfied) and reduced costs etc
722   returns a branching object which would give a new feasible
723   point in direction reduced cost says would be cheaper.
724   If no feasible point returns null
725*/
726CbcBranchingObject * 
727CbcSimpleInteger::preferredNewFeasible() const
728{
729  OsiSolverInterface * solver = model_->solver();
730  double value = model_->currentSolution()[columnNumber_];
731
732  double nearest = floor(value+0.5);
733  double integerTolerance = 
734    model_->getDblParam(CbcModel::CbcIntegerTolerance);
735  assert (fabs(value-nearest)<=integerTolerance);
736  double dj = solver->getObjSense()*solver->getReducedCost()[columnNumber_];
737  CbcIntegerBranchingObject * object = NULL;
738  if (dj>=0.0) {
739    // can we go down
740    if (nearest>originalLower_+0.5) {
741      // yes
742      object = new CbcIntegerBranchingObject(model_,sequence_,-1,
743                                             nearest-1.0,nearest-1.0);
744    }
745  } else {
746    // can we go up
747    if (nearest<originalUpper_-0.5) {
748      // yes
749      object = new CbcIntegerBranchingObject(model_,sequence_,-1,
750                                             nearest+1.0,nearest+1.0);
751    }
752  }
753  return object;
754}
755 
756/* Given valid solution (i.e. satisfied) and reduced costs etc
757   returns a branching object which would give a new feasible
758   point in direction opposite to one reduced cost says would be cheaper.
759   If no feasible point returns null
760*/
761CbcBranchingObject * 
762CbcSimpleInteger::notPreferredNewFeasible() const 
763{
764  OsiSolverInterface * solver = model_->solver();
765  double value = model_->currentSolution()[columnNumber_];
766
767  double nearest = floor(value+0.5);
768  double integerTolerance = 
769    model_->getDblParam(CbcModel::CbcIntegerTolerance);
770  assert (fabs(value-nearest)<=integerTolerance);
771  double dj = solver->getObjSense()*solver->getReducedCost()[columnNumber_];
772  CbcIntegerBranchingObject * object = NULL;
773  if (dj<=0.0) {
774    // can we go down
775    if (nearest>originalLower_+0.5) {
776      // yes
777      object = new CbcIntegerBranchingObject(model_,sequence_,-1,
778                                             nearest-1.0,nearest-1.0);
779    }
780  } else {
781    // can we go up
782    if (nearest<originalUpper_-0.5) {
783      // yes
784      object = new CbcIntegerBranchingObject(model_,sequence_,-1,
785                                             nearest+1.0,nearest+1.0);
786    }
787  }
788  return object;
789}
790 
791/*
792  Bounds may be tightened, so it may be good to be able to refresh the local
793  copy of the original bounds.
794 */
795void 
796CbcSimpleInteger::resetBounds()
797{
798  originalLower_ = model_->solver()->getColLower()[columnNumber_];
799  originalUpper_ = model_->solver()->getColUpper()[columnNumber_];
800}
801
802
803// Default Constructor
804CbcIntegerBranchingObject::CbcIntegerBranchingObject()
805  :CbcBranchingObject()
806{
807  down_[0] = 0.0;
808  down_[1] = 0.0;
809  up_[0] = 0.0;
810  up_[1] = 0.0;
811}
812
813// Useful constructor
814CbcIntegerBranchingObject::CbcIntegerBranchingObject (CbcModel * model, 
815                                                      int variable, int way , double value)
816  :CbcBranchingObject(model,variable,way,value)
817{
818  int iColumn = model_->integerVariable()[variable_];
819  down_[0] = model_->solver()->getColLower()[iColumn];
820  down_[1] = floor(value_);
821  up_[0] = ceil(value_);
822  up_[1] = model->getColUpper()[iColumn];
823}
824// Useful constructor for fixing
825CbcIntegerBranchingObject::CbcIntegerBranchingObject (CbcModel * model, 
826                                                      int variable, int way,
827                                                      double lowerValue, 
828                                                      double upperValue)
829  :CbcBranchingObject(model,variable,way,lowerValue)
830{
831  numberBranchesLeft_=1;
832  down_[0] = lowerValue;
833  down_[1] = upperValue;
834  up_[0] = lowerValue;
835  up_[1] = upperValue;
836}
837 
838
839// Copy constructor
840CbcIntegerBranchingObject::CbcIntegerBranchingObject ( const CbcIntegerBranchingObject & rhs) :CbcBranchingObject(rhs)
841{
842  down_[0] = rhs.down_[0];
843  down_[1] = rhs.down_[1];
844  up_[0] = rhs.up_[0];
845  up_[1] = rhs.up_[1];
846}
847
848// Assignment operator
849CbcIntegerBranchingObject & 
850CbcIntegerBranchingObject::operator=( const CbcIntegerBranchingObject& rhs)
851{
852  if (this != &rhs) {
853    CbcBranchingObject::operator=(rhs);
854    down_[0] = rhs.down_[0];
855    down_[1] = rhs.down_[1];
856    up_[0] = rhs.up_[0];
857    up_[1] = rhs.up_[1];
858  }
859  return *this;
860}
861CbcBranchingObject * 
862CbcIntegerBranchingObject::clone() const
863{ 
864  return (new CbcIntegerBranchingObject(*this));
865}
866
867
868// Destructor
869CbcIntegerBranchingObject::~CbcIntegerBranchingObject ()
870{
871}
872
873/*
874  Perform a branch by adjusting the bounds of the specified variable. Note
875  that each arm of the branch advances the object to the next arm by
876  advancing the value of way_.
877
878  Providing new values for the variable's lower and upper bounds for each
879  branching direction gives a little bit of additional flexibility and will
880  be easily extensible to multi-way branching.
881  Returns change in guessed objective on next branch
882*/
883double
884CbcIntegerBranchingObject::branch(bool normalBranch)
885{
886  if (model_->messageHandler()->logLevel()>2&&normalBranch)
887    print(normalBranch);
888  numberBranchesLeft_--;
889  int iColumn = model_->integerVariable()[variable_];
890  if (way_<0) {
891#ifdef CBC_DEBUG
892  { double olb,oub ;
893    olb = model_->solver()->getColLower()[iColumn] ;
894    oub = model_->solver()->getColUpper()[iColumn] ;
895    printf("branching down on var %d: [%g,%g] => [%g,%g]\n",
896           iColumn,olb,oub,down_[0],down_[1]) ; }
897#endif
898    model_->solver()->setColLower(iColumn,down_[0]);
899    model_->solver()->setColUpper(iColumn,down_[1]);
900    way_=1;
901  } else {
902#ifdef CBC_DEBUG
903  { double olb,oub ;
904    olb = model_->solver()->getColLower()[iColumn] ;
905    oub = model_->solver()->getColUpper()[iColumn] ;
906    printf("branching up on var %d: [%g,%g] => [%g,%g]\n",
907           iColumn,olb,oub,up_[0],up_[1]) ; }
908#endif
909    model_->solver()->setColLower(iColumn,up_[0]);
910    model_->solver()->setColUpper(iColumn,up_[1]);
911    way_=-1;      // Swap direction
912  }
913  return 0.0;
914}
915// Print what would happen 
916void
917CbcIntegerBranchingObject::print(bool normalBranch)
918{
919  int iColumn = model_->integerVariable()[variable_];
920  if (way_<0) {
921  { double olb,oub ;
922    olb = model_->solver()->getColLower()[iColumn] ;
923    oub = model_->solver()->getColUpper()[iColumn] ;
924    printf("CbcInteger would branch down on var %d: [%g,%g] => [%g,%g]\n",
925           iColumn,olb,oub,down_[0],down_[1]) ; }
926  } else {
927  { double olb,oub ;
928    olb = model_->solver()->getColLower()[iColumn] ;
929    oub = model_->solver()->getColUpper()[iColumn] ;
930    printf("CbcInteger would branch up on var %d: [%g,%g] => [%g,%g]\n",
931           iColumn,olb,oub,up_[0],up_[1]) ; }
932  }
933}
934
935
936/** Default Constructor
937
938  Equivalent to an unspecified binary variable.
939*/
940CbcSimpleIntegerPseudoCost::CbcSimpleIntegerPseudoCost ()
941  : CbcSimpleInteger(),
942    downPseudoCost_(1.0e-5),
943    upPseudoCost_(1.0e-5),
944    method_(0)
945{
946}
947
948/** Useful constructor
949
950  Loads actual upper & lower bounds for the specified variable.
951*/
952CbcSimpleIntegerPseudoCost::CbcSimpleIntegerPseudoCost (CbcModel * model, int sequence,
953                                    int iColumn, double breakEven)
954  : CbcSimpleInteger(model,sequence,iColumn,breakEven)
955{
956  const double * cost = model->getObjCoefficients();
957  double costValue = CoinMax(1.0e-5,fabs(cost[iColumn]));
958  // treat as if will cost what it says up
959  upPseudoCost_=costValue;
960  // and balance at breakeven
961  downPseudoCost_=((1.0-breakEven_)*upPseudoCost_)/breakEven_;
962  method_=0;
963}
964
965/** Useful constructor
966
967  Loads actual upper & lower bounds for the specified variable.
968*/
969CbcSimpleIntegerPseudoCost::CbcSimpleIntegerPseudoCost (CbcModel * model, int sequence,
970                                    int iColumn, double downPseudoCost,
971                                                        double upPseudoCost)
972  : CbcSimpleInteger(model,sequence,iColumn)
973{
974  downPseudoCost_ = downPseudoCost;
975  upPseudoCost_ = upPseudoCost;
976  breakEven_ = upPseudoCost_/(upPseudoCost_+downPseudoCost_);
977  method_=0;
978}
979
980// Copy constructor
981CbcSimpleIntegerPseudoCost::CbcSimpleIntegerPseudoCost ( const CbcSimpleIntegerPseudoCost & rhs)
982  :CbcSimpleInteger(rhs),
983   downPseudoCost_(rhs.downPseudoCost_),
984   upPseudoCost_(rhs.upPseudoCost_),
985   method_(rhs.method_)
986
987{
988}
989
990// Clone
991CbcObject *
992CbcSimpleIntegerPseudoCost::clone() const
993{
994  return new CbcSimpleIntegerPseudoCost(*this);
995}
996
997// Assignment operator
998CbcSimpleIntegerPseudoCost & 
999CbcSimpleIntegerPseudoCost::operator=( const CbcSimpleIntegerPseudoCost& rhs)
1000{
1001  if (this!=&rhs) {
1002    CbcSimpleInteger::operator=(rhs);
1003    downPseudoCost_=rhs.downPseudoCost_;
1004    upPseudoCost_=rhs.upPseudoCost_;
1005    method_=rhs.method_;
1006  }
1007  return *this;
1008}
1009
1010// Destructor
1011CbcSimpleIntegerPseudoCost::~CbcSimpleIntegerPseudoCost ()
1012{
1013}
1014// Creates a branching object
1015CbcBranchingObject * 
1016CbcSimpleIntegerPseudoCost::createBranch(int way) const
1017{
1018  OsiSolverInterface * solver = model_->solver();
1019  const double * solution = model_->currentSolution();
1020  const double * lower = solver->getColLower();
1021  const double * upper = solver->getColUpper();
1022  double value = solution[columnNumber_];
1023  value = CoinMax(value, lower[columnNumber_]);
1024  value = CoinMin(value, upper[columnNumber_]);
1025  double nearest = floor(value+0.5);
1026  double integerTolerance = 
1027    model_->getDblParam(CbcModel::CbcIntegerTolerance);
1028  assert (upper[columnNumber_]>lower[columnNumber_]);
1029  int hotstartStrategy=model_->getHotstartStrategy();
1030  if (hotstartStrategy<=0) {
1031    assert (fabs(value-nearest)>integerTolerance);
1032  } else {
1033    const double * bestSolution = model_->bestSolution();
1034    double targetValue = bestSolution[columnNumber_];
1035    if (way>0)
1036      value = targetValue-0.1;
1037    else
1038      value = targetValue+0.1;
1039  }
1040  CbcIntegerPseudoCostBranchingObject * newObject = 
1041    new CbcIntegerPseudoCostBranchingObject(model_,sequence_,way,
1042                                            value);
1043  double up =  upPseudoCost_*(ceil(value)-value);
1044  double down =  downPseudoCost_*(value-floor(value));
1045  double changeInGuessed=up-down;
1046  if (way>0)
1047    changeInGuessed = - changeInGuessed;
1048  changeInGuessed=CoinMax(0.0,changeInGuessed);
1049  //if (way>0)
1050  //changeInGuessed += 1.0e8; // bias to stay up
1051  newObject->setChangeInGuessed(changeInGuessed);
1052  return newObject;
1053}
1054// Infeasibility - large is 0.5
1055double 
1056CbcSimpleIntegerPseudoCost::infeasibility(int & preferredWay) const
1057{
1058  OsiSolverInterface * solver = model_->solver();
1059  const double * solution = model_->currentSolution();
1060  const double * lower = solver->getColLower();
1061  const double * upper = solver->getColUpper();
1062  if (upper[columnNumber_]==lower[columnNumber_]) {
1063    // fixed
1064    preferredWay=1;
1065    return 0.0;
1066  }
1067  double value = solution[columnNumber_];
1068  value = CoinMax(value, lower[columnNumber_]);
1069  value = CoinMin(value, upper[columnNumber_]);
1070  /*printf("%d %g %g %g %g\n",columnNumber_,value,lower[columnNumber_],
1071    solution[columnNumber_],upper[columnNumber_]);*/
1072  double nearest = floor(value+0.5);
1073  double integerTolerance = 
1074    model_->getDblParam(CbcModel::CbcIntegerTolerance);
1075  double below = floor(value+integerTolerance);
1076  double above = below+1.0;
1077  if (above>upper[columnNumber_]) {
1078    above=below;
1079    below = above -1;
1080  }
1081  double downCost = CoinMax((value-below)*downPseudoCost_,0.0);
1082  double upCost = CoinMax((above-value)*upPseudoCost_,0.0);
1083  if (downCost>=upCost)
1084    preferredWay=1;
1085  else
1086    preferredWay=-1;
1087  if (fabs(value-nearest)<=integerTolerance) {
1088    return 0.0;
1089  } else {
1090    // can't get at model so 1,2 don't make sense
1091    assert(method_<1||method_>2);
1092    if (!method_)
1093      return CoinMin(downCost,upCost);
1094    else
1095      return CoinMax(downCost,upCost);
1096  }
1097}
1098
1099// Return "up" estimate
1100double 
1101CbcSimpleIntegerPseudoCost::upEstimate() const
1102{
1103  OsiSolverInterface * solver = model_->solver();
1104  const double * solution = model_->currentSolution();
1105  const double * lower = solver->getColLower();
1106  const double * upper = solver->getColUpper();
1107  double value = solution[columnNumber_];
1108  value = CoinMax(value, lower[columnNumber_]);
1109  value = CoinMin(value, upper[columnNumber_]);
1110  if (upper[columnNumber_]==lower[columnNumber_]) {
1111    // fixed
1112    return 0.0;
1113  }
1114  double integerTolerance = 
1115    model_->getDblParam(CbcModel::CbcIntegerTolerance);
1116  double below = floor(value+integerTolerance);
1117  double above = below+1.0;
1118  if (above>upper[columnNumber_]) {
1119    above=below;
1120    below = above -1;
1121  }
1122  double upCost = CoinMax((above-value)*upPseudoCost_,0.0);
1123  return upCost;
1124}
1125// Return "down" estimate
1126double 
1127CbcSimpleIntegerPseudoCost::downEstimate() const
1128{
1129  OsiSolverInterface * solver = model_->solver();
1130  const double * solution = model_->currentSolution();
1131  const double * lower = solver->getColLower();
1132  const double * upper = solver->getColUpper();
1133  double value = solution[columnNumber_];
1134  value = CoinMax(value, lower[columnNumber_]);
1135  value = CoinMin(value, upper[columnNumber_]);
1136  if (upper[columnNumber_]==lower[columnNumber_]) {
1137    // fixed
1138    return 0.0;
1139  }
1140  double integerTolerance = 
1141    model_->getDblParam(CbcModel::CbcIntegerTolerance);
1142  double below = floor(value+integerTolerance);
1143  double above = below+1.0;
1144  if (above>upper[columnNumber_]) {
1145    above=below;
1146    below = above -1;
1147  }
1148  double downCost = CoinMax((value-below)*downPseudoCost_,0.0);
1149  return downCost;
1150}
1151
1152// Default Constructor
1153CbcIntegerPseudoCostBranchingObject::CbcIntegerPseudoCostBranchingObject()
1154  :CbcIntegerBranchingObject()
1155{
1156  changeInGuessed_=1.0e-5;
1157}
1158
1159// Useful constructor
1160CbcIntegerPseudoCostBranchingObject::CbcIntegerPseudoCostBranchingObject (CbcModel * model, 
1161                                                      int variable, int way , double value)
1162  :CbcIntegerBranchingObject(model,variable,way,value)
1163{
1164}
1165// Useful constructor for fixing
1166CbcIntegerPseudoCostBranchingObject::CbcIntegerPseudoCostBranchingObject (CbcModel * model, 
1167                                                      int variable, int way,
1168                                                      double lowerValue, 
1169                                                      double upperValue)
1170  :CbcIntegerBranchingObject(model,variable,way,lowerValue)
1171{
1172  changeInGuessed_=1.0e100;
1173}
1174 
1175
1176// Copy constructor
1177CbcIntegerPseudoCostBranchingObject::CbcIntegerPseudoCostBranchingObject ( 
1178                                 const CbcIntegerPseudoCostBranchingObject & rhs)
1179  :CbcIntegerBranchingObject(rhs)
1180{
1181  changeInGuessed_ = rhs.changeInGuessed_;
1182}
1183
1184// Assignment operator
1185CbcIntegerPseudoCostBranchingObject & 
1186CbcIntegerPseudoCostBranchingObject::operator=( const CbcIntegerPseudoCostBranchingObject& rhs)
1187{
1188  if (this != &rhs) {
1189    CbcIntegerBranchingObject::operator=(rhs);
1190    changeInGuessed_ = rhs.changeInGuessed_;
1191  }
1192  return *this;
1193}
1194CbcBranchingObject * 
1195CbcIntegerPseudoCostBranchingObject::clone() const
1196{ 
1197  return (new CbcIntegerPseudoCostBranchingObject(*this));
1198}
1199
1200
1201// Destructor
1202CbcIntegerPseudoCostBranchingObject::~CbcIntegerPseudoCostBranchingObject ()
1203{
1204}
1205
1206/*
1207  Perform a branch by adjusting the bounds of the specified variable. Note
1208  that each arm of the branch advances the object to the next arm by
1209  advancing the value of way_.
1210
1211  Providing new values for the variable's lower and upper bounds for each
1212  branching direction gives a little bit of additional flexibility and will
1213  be easily extensible to multi-way branching.
1214  Returns change in guessed objective on next branch
1215*/
1216double
1217CbcIntegerPseudoCostBranchingObject::branch(bool normalBranch)
1218{
1219  CbcIntegerBranchingObject::branch(normalBranch);
1220  return changeInGuessed_;
1221}
1222
1223
1224// Default Constructor
1225CbcCliqueBranchingObject::CbcCliqueBranchingObject()
1226  :CbcBranchingObject()
1227{
1228  clique_ = NULL;
1229  downMask_[0]=0;
1230  downMask_[1]=0;
1231  upMask_[0]=0;
1232  upMask_[1]=0;
1233}
1234
1235// Useful constructor
1236CbcCliqueBranchingObject::CbcCliqueBranchingObject (CbcModel * model,
1237                                                    const CbcClique * clique,
1238                                                    int way ,
1239                                                    int numberOnDownSide, const int * down,
1240                                                    int numberOnUpSide, const int * up)
1241  :CbcBranchingObject(model,clique->id(),way,0.5)
1242{
1243  clique_ = clique;
1244  downMask_[0]=0;
1245  downMask_[1]=0;
1246  upMask_[0]=0;
1247  upMask_[1]=0;
1248  int i;
1249  for (i=0;i<numberOnDownSide;i++) {
1250    int sequence = down[i];
1251    int iWord = sequence>>5;
1252    int iBit = sequence - 32*iWord;
1253    unsigned int k = 1<<iBit;
1254    downMask_[iWord] |= k;
1255  }
1256  for (i=0;i<numberOnUpSide;i++) {
1257    int sequence = up[i];
1258    int iWord = sequence>>5;
1259    int iBit = sequence - 32*iWord;
1260    unsigned int k = 1<<iBit;
1261    upMask_[iWord] |= k;
1262  }
1263}
1264
1265// Copy constructor
1266CbcCliqueBranchingObject::CbcCliqueBranchingObject ( const CbcCliqueBranchingObject & rhs) :CbcBranchingObject(rhs)
1267{
1268  clique_=rhs.clique_;
1269  downMask_[0]=rhs.downMask_[0];
1270  downMask_[1]=rhs.downMask_[1];
1271  upMask_[0]=rhs.upMask_[0];
1272  upMask_[1]=rhs.upMask_[1];
1273}
1274
1275// Assignment operator
1276CbcCliqueBranchingObject & 
1277CbcCliqueBranchingObject::operator=( const CbcCliqueBranchingObject& rhs)
1278{
1279  if (this != &rhs) {
1280    CbcBranchingObject::operator=(rhs);
1281    clique_=rhs.clique_;
1282    downMask_[0]=rhs.downMask_[0];
1283    downMask_[1]=rhs.downMask_[1];
1284    upMask_[0]=rhs.upMask_[0];
1285    upMask_[1]=rhs.upMask_[1];
1286  }
1287  return *this;
1288}
1289CbcBranchingObject * 
1290CbcCliqueBranchingObject::clone() const
1291{ 
1292  return (new CbcCliqueBranchingObject(*this));
1293}
1294
1295
1296// Destructor
1297CbcCliqueBranchingObject::~CbcCliqueBranchingObject ()
1298{
1299}
1300double
1301CbcCliqueBranchingObject::branch(bool normalBranch)
1302{
1303  if (model_->messageHandler()->logLevel()>2&&normalBranch)
1304    print(normalBranch);
1305  numberBranchesLeft_--;
1306  int iWord;
1307  int numberMembers = clique_->numberMembers();
1308  const int * which = clique_->members();
1309  const int * integerVariables = model_->integerVariable();
1310  int numberWords=(numberMembers+31)>>5;
1311  // *** for way - up means fix all those in down section
1312  if (way_<0) {
1313#ifdef FULL_PRINT
1314    printf("Down Fix ");
1315#endif
1316    for (iWord=0;iWord<numberWords;iWord++) {
1317      int i;
1318      for (i=0;i<32;i++) {
1319        unsigned int k = 1<<i;
1320        if ((upMask_[iWord]&k)!=0) {
1321          int iColumn = which[i+32*iWord];
1322#ifdef FULL_PRINT
1323          printf("%d ",i+32*iWord);
1324#endif
1325          // fix weak way
1326          if (clique_->type(i+32*iWord))
1327            model_->solver()->setColUpper(integerVariables[iColumn],0.0);
1328          else
1329            model_->solver()->setColLower(integerVariables[iColumn],1.0);
1330        }
1331      }
1332    }
1333    way_=1;       // Swap direction
1334  } else {
1335#ifdef FULL_PRINT
1336    printf("Up Fix ");
1337#endif
1338    for (iWord=0;iWord<numberWords;iWord++) {
1339      int i;
1340      for (i=0;i<32;i++) {
1341        unsigned int k = 1<<i;
1342        if ((downMask_[iWord]&k)!=0) {
1343          int iColumn = which[i+32*iWord];
1344#ifdef FULL_PRINT
1345          printf("%d ",i+32*iWord);
1346#endif
1347          // fix weak way
1348          if (clique_->type(i+32*iWord))
1349            model_->solver()->setColUpper(integerVariables[iColumn],0.0);
1350          else
1351            model_->solver()->setColLower(integerVariables[iColumn],1.0);
1352        }
1353      }
1354    }
1355    way_=-1;      // Swap direction
1356  }
1357#ifdef FULL_PRINT
1358  printf("\n");
1359#endif
1360  return 0.0;
1361}
1362// Print what would happen 
1363void
1364CbcCliqueBranchingObject::print(bool normalBranch)
1365{
1366  int iWord;
1367  int numberMembers = clique_->numberMembers();
1368  const int * which = clique_->members();
1369  const int * integerVariables = model_->integerVariable();
1370  int numberWords=(numberMembers+31)>>5;
1371  // *** for way - up means fix all those in down section
1372  if (way_<0) {
1373    printf("Clique - Down Fix ");
1374    for (iWord=0;iWord<numberWords;iWord++) {
1375      int i;
1376      for (i=0;i<32;i++) {
1377        unsigned int k = 1<<i;
1378        if ((upMask_[iWord]&k)!=0) {
1379          int iColumn = which[i+32*iWord];
1380          printf("%d ",integerVariables[iColumn]);
1381        }
1382      }
1383    }
1384  } else {
1385    printf("Clique - Up Fix ");
1386    for (iWord=0;iWord<numberWords;iWord++) {
1387      int i;
1388      for (i=0;i<32;i++) {
1389        unsigned int k = 1<<i;
1390        if ((downMask_[iWord]&k)!=0) {
1391          int iColumn = which[i+32*iWord];
1392          printf("%d ",integerVariables[iColumn]);
1393        }
1394      }
1395    }
1396  }
1397  printf("\n");
1398}
1399 
1400// Default Constructor
1401CbcLongCliqueBranchingObject::CbcLongCliqueBranchingObject()
1402  :CbcBranchingObject()
1403{
1404  clique_=NULL;
1405  downMask_=NULL;
1406  upMask_=NULL;
1407}
1408
1409// Useful constructor
1410CbcLongCliqueBranchingObject::CbcLongCliqueBranchingObject (CbcModel * model,
1411                                                            const CbcClique * clique, 
1412                                                            int way ,
1413                                                    int numberOnDownSide, const int * down,
1414                                                    int numberOnUpSide, const int * up)
1415  :CbcBranchingObject(model,clique->id(),way,0.5)
1416{
1417  clique_ = clique;
1418  int numberMembers = clique_->numberMembers();
1419  int numberWords=(numberMembers+31)>>5;
1420  downMask_ = new unsigned int [numberWords];
1421  upMask_ = new unsigned int [numberWords];
1422  memset(downMask_,0,numberWords*sizeof(unsigned int));
1423  memset(upMask_,0,numberWords*sizeof(unsigned int));
1424  int i;
1425  for (i=0;i<numberOnDownSide;i++) {
1426    int sequence = down[i];
1427    int iWord = sequence>>5;
1428    int iBit = sequence - 32*iWord;
1429    unsigned int k = 1<<iBit;
1430    downMask_[iWord] |= k;
1431  }
1432  for (i=0;i<numberOnUpSide;i++) {
1433    int sequence = up[i];
1434    int iWord = sequence>>5;
1435    int iBit = sequence - 32*iWord;
1436    unsigned int k = 1<<iBit;
1437    upMask_[iWord] |= k;
1438  }
1439}
1440
1441// Copy constructor
1442CbcLongCliqueBranchingObject::CbcLongCliqueBranchingObject ( const CbcLongCliqueBranchingObject & rhs) :CbcBranchingObject(rhs)
1443{
1444  clique_=rhs.clique_;
1445  if (rhs.downMask_) {
1446    int numberMembers = clique_->numberMembers();
1447    int numberWords=(numberMembers+31)>>5;
1448    downMask_ = new unsigned int [numberWords];
1449    memcpy(downMask_,rhs.downMask_,numberWords*sizeof(unsigned int));
1450    upMask_ = new unsigned int [numberWords];
1451    memcpy(upMask_,rhs.upMask_,numberWords*sizeof(unsigned int));
1452  } else {
1453    downMask_=NULL;
1454    upMask_=NULL;
1455  }   
1456}
1457
1458// Assignment operator
1459CbcLongCliqueBranchingObject & 
1460CbcLongCliqueBranchingObject::operator=( const CbcLongCliqueBranchingObject& rhs)
1461{
1462  if (this != &rhs) {
1463    CbcBranchingObject::operator=(rhs);
1464    clique_=rhs.clique_;
1465    delete [] downMask_;
1466    delete [] upMask_;
1467    if (rhs.downMask_) {
1468      int numberMembers = clique_->numberMembers();
1469      int numberWords=(numberMembers+31)>>5;
1470      downMask_ = new unsigned int [numberWords];
1471      memcpy(downMask_,rhs.downMask_,numberWords*sizeof(unsigned int));
1472      upMask_ = new unsigned int [numberWords];
1473      memcpy(upMask_,rhs.upMask_,numberWords*sizeof(unsigned int));
1474    } else {
1475      downMask_=NULL;
1476      upMask_=NULL;
1477    }   
1478  }
1479  return *this;
1480}
1481CbcBranchingObject * 
1482CbcLongCliqueBranchingObject::clone() const
1483{ 
1484  return (new CbcLongCliqueBranchingObject(*this));
1485}
1486
1487
1488// Destructor
1489CbcLongCliqueBranchingObject::~CbcLongCliqueBranchingObject ()
1490{
1491  delete [] downMask_;
1492  delete [] upMask_;
1493}
1494double
1495CbcLongCliqueBranchingObject::branch(bool normalBranch)
1496{
1497  if (model_->messageHandler()->logLevel()>2&&normalBranch)
1498    print(normalBranch);
1499  numberBranchesLeft_--;
1500  int iWord;
1501  int numberMembers = clique_->numberMembers();
1502  const int * which = clique_->members();
1503  const int * integerVariables = model_->integerVariable();
1504  int numberWords=(numberMembers+31)>>5;
1505  // *** for way - up means fix all those in down section
1506  if (way_<0) {
1507#ifdef FULL_PRINT
1508    printf("Down Fix ");
1509#endif
1510    for (iWord=0;iWord<numberWords;iWord++) {
1511      int i;
1512      for (i=0;i<32;i++) {
1513        unsigned int k = 1<<i;
1514        if ((upMask_[iWord]&k)!=0) {
1515          int iColumn = which[i+32*iWord];
1516#ifdef FULL_PRINT
1517          printf("%d ",i+32*iWord);
1518#endif
1519          // fix weak way
1520          if (clique_->type(i+32*iWord))
1521            model_->solver()->setColUpper(integerVariables[iColumn],0.0);
1522          else
1523            model_->solver()->setColLower(integerVariables[iColumn],1.0);
1524        }
1525      }
1526    }
1527    way_=1;       // Swap direction
1528  } else {
1529#ifdef FULL_PRINT
1530    printf("Up Fix ");
1531#endif
1532    for (iWord=0;iWord<numberWords;iWord++) {
1533      int i;
1534      for (i=0;i<32;i++) {
1535        unsigned int k = 1<<i;
1536        if ((downMask_[iWord]&k)!=0) {
1537          int iColumn = which[i+32*iWord];
1538#ifdef FULL_PRINT
1539          printf("%d ",i+32*iWord);
1540#endif
1541          // fix weak way
1542          if (clique_->type(i+32*iWord))
1543            model_->solver()->setColUpper(integerVariables[iColumn],0.0);
1544          else
1545            model_->solver()->setColLower(integerVariables[iColumn],1.0);
1546        }
1547      }
1548    }
1549    way_=-1;      // Swap direction
1550  }
1551#ifdef FULL_PRINT
1552  printf("\n");
1553#endif
1554  return 0.0;
1555}
1556void
1557CbcLongCliqueBranchingObject::print(bool normalBranch)
1558{
1559  int iWord;
1560  int numberMembers = clique_->numberMembers();
1561  const int * which = clique_->members();
1562  const int * integerVariables = model_->integerVariable();
1563  int numberWords=(numberMembers+31)>>5;
1564  // *** for way - up means fix all those in down section
1565  if (way_<0) {
1566    printf("Clique - Down Fix ");
1567    for (iWord=0;iWord<numberWords;iWord++) {
1568      int i;
1569      for (i=0;i<32;i++) {
1570        unsigned int k = 1<<i;
1571        if ((upMask_[iWord]&k)!=0) {
1572          int iColumn = which[i+32*iWord];
1573          printf("%d ",integerVariables[iColumn]);
1574        }
1575      }
1576    }
1577  } else {
1578    printf("Clique - Up Fix ");
1579    for (iWord=0;iWord<numberWords;iWord++) {
1580      int i;
1581      for (i=0;i<32;i++) {
1582        unsigned int k = 1<<i;
1583        if ((downMask_[iWord]&k)!=0) {
1584          int iColumn = which[i+32*iWord];
1585          printf("%d ",integerVariables[iColumn]);
1586        }
1587      }
1588    }
1589  }
1590  printf("\n");
1591}
1592// Default Constructor
1593CbcSOSBranchingObject::CbcSOSBranchingObject()
1594  :CbcBranchingObject()
1595{
1596  set_ = NULL;
1597  separator_=0.0;
1598}
1599
1600// Useful constructor
1601CbcSOSBranchingObject::CbcSOSBranchingObject (CbcModel * model,
1602                                              const CbcSOS * set,
1603                                              int way ,
1604                                              double separator)
1605  :CbcBranchingObject(model,set->id(),way,0.5)
1606{
1607  set_ = set;
1608  separator_ = separator;
1609}
1610
1611// Copy constructor
1612CbcSOSBranchingObject::CbcSOSBranchingObject ( const CbcSOSBranchingObject & rhs) :CbcBranchingObject(rhs)
1613{
1614  set_=rhs.set_;
1615  separator_ = rhs.separator_;
1616}
1617
1618// Assignment operator
1619CbcSOSBranchingObject & 
1620CbcSOSBranchingObject::operator=( const CbcSOSBranchingObject& rhs)
1621{
1622  if (this != &rhs) {
1623    CbcBranchingObject::operator=(rhs);
1624    set_=rhs.set_;
1625    separator_ = rhs.separator_;
1626  }
1627  return *this;
1628}
1629CbcBranchingObject * 
1630CbcSOSBranchingObject::clone() const
1631{ 
1632  return (new CbcSOSBranchingObject(*this));
1633}
1634
1635
1636// Destructor
1637CbcSOSBranchingObject::~CbcSOSBranchingObject ()
1638{
1639}
1640double
1641CbcSOSBranchingObject::branch(bool normalBranch)
1642{
1643  if (model_->messageHandler()->logLevel()>2&&normalBranch)
1644    print(normalBranch);
1645  numberBranchesLeft_--;
1646  int numberMembers = set_->numberMembers();
1647  const int * which = set_->members();
1648  const double * weights = set_->weights();
1649  OsiSolverInterface * solver = model_->solver();
1650  //const double * lower = solver->getColLower();
1651  //const double * upper = solver->getColUpper();
1652  // *** for way - up means fix all those in down section
1653  if (way_<0) {
1654    int i;
1655    for ( i=0;i<numberMembers;i++) {
1656      if (weights[i] > separator_)
1657        break;
1658    }
1659    assert (i<numberMembers);
1660    for (;i<numberMembers;i++) 
1661      solver->setColUpper(which[i],0.0);
1662    way_=1;       // Swap direction
1663  } else {
1664    int i;
1665    for ( i=0;i<numberMembers;i++) {
1666      if (weights[i] >= separator_)
1667        break;
1668      else
1669        solver->setColUpper(which[i],0.0);
1670    }
1671    assert (i<numberMembers);
1672    way_=-1;      // Swap direction
1673  }
1674  return 0.0;
1675}
1676// Print what would happen 
1677void
1678CbcSOSBranchingObject::print(bool normalBranch)
1679{
1680  int numberMembers = set_->numberMembers();
1681  const int * which = set_->members();
1682  const double * weights = set_->weights();
1683  OsiSolverInterface * solver = model_->solver();
1684  //const double * lower = solver->getColLower();
1685  const double * upper = solver->getColUpper();
1686  int first=numberMembers;
1687  int last=-1;
1688  int numberFixed=0;
1689  int numberOther=0;
1690  int i;
1691  for ( i=0;i<numberMembers;i++) {
1692    double bound = upper[which[i]];
1693    if (bound) {
1694      first = CoinMin(first,i);
1695      last = CoinMax(last,i);
1696    }
1697  }
1698  // *** for way - up means fix all those in down section
1699  if (way_<0) {
1700    printf("SOS Down");
1701    for ( i=0;i<numberMembers;i++) {
1702      double bound = upper[which[i]];
1703      if (weights[i] > separator_)
1704        break;
1705      else if (bound)
1706        numberOther++;
1707    }
1708    assert (i<numberMembers);
1709    for (;i<numberMembers;i++) {
1710      double bound = upper[which[i]];
1711      if (bound)
1712        numberFixed++;
1713    }
1714  } else {
1715    printf("SOS Up");
1716    for ( i=0;i<numberMembers;i++) {
1717      double bound = upper[which[i]];
1718      if (weights[i] >= separator_)
1719        break;
1720      else if (bound)
1721        numberFixed++;
1722    }
1723    assert (i<numberMembers);
1724    for (;i<numberMembers;i++) {
1725      double bound = upper[which[i]];
1726      if (bound)
1727        numberOther++;
1728    }
1729  }
1730  printf(" - at %g, free range %d (%g) => %d (%g), %d would be fixed, %d other way\n",
1731         separator_,which[first],weights[first],which[last],weights[last],numberFixed,numberOther);
1732}
1733 
1734// Default Constructor
1735CbcBranchDefaultDecision::CbcBranchDefaultDecision()
1736  :CbcBranchDecision()
1737{
1738  bestCriterion_ = 0.0;
1739  bestChangeUp_ = 0.0;
1740  bestNumberUp_ = 0;
1741  bestChangeDown_ = 0.0;
1742  bestNumberDown_ = 0;
1743  bestObject_ = NULL;
1744}
1745
1746// Copy constructor
1747CbcBranchDefaultDecision::CbcBranchDefaultDecision (
1748                                    const CbcBranchDefaultDecision & rhs)
1749  :CbcBranchDecision()
1750{
1751  bestCriterion_ = rhs.bestCriterion_;
1752  bestChangeUp_ = rhs.bestChangeUp_;
1753  bestNumberUp_ = rhs.bestNumberUp_;
1754  bestChangeDown_ = rhs.bestChangeDown_;
1755  bestNumberDown_ = rhs.bestNumberDown_;
1756  bestObject_ = rhs.bestObject_;
1757}
1758
1759CbcBranchDefaultDecision::~CbcBranchDefaultDecision()
1760{
1761}
1762
1763// Clone
1764CbcBranchDecision * 
1765CbcBranchDefaultDecision::clone() const
1766{
1767  return new CbcBranchDefaultDecision(*this);
1768}
1769
1770// Initialize i.e. before start of choosing at a node
1771void 
1772CbcBranchDefaultDecision::initialize(CbcModel * model)
1773{
1774  bestCriterion_ = 0.0;
1775  bestChangeUp_ = 0.0;
1776  bestNumberUp_ = 0;
1777  bestChangeDown_ = 0.0;
1778  bestNumberDown_ = 0;
1779  bestObject_ = NULL;
1780}
1781
1782
1783/*
1784  Simple default decision algorithm. Compare based on infeasibility (numInfUp,
1785  numInfDn) until a solution is found by search, then switch to change in
1786  objective (changeUp, changeDn). Note that bestSoFar is remembered in
1787  bestObject_, so the parameter bestSoFar is unused.
1788*/
1789
1790int
1791CbcBranchDefaultDecision::betterBranch(CbcBranchingObject * thisOne,
1792                            CbcBranchingObject * bestSoFar,
1793                            double changeUp, int numInfUp,
1794                            double changeDn, int numInfDn)
1795{
1796  bool beforeSolution = thisOne->model()->getSolutionCount()==
1797    thisOne->model()->getNumberHeuristicSolutions();;
1798  int betterWay=0;
1799  if (beforeSolution) {
1800    if (!bestObject_) {
1801      bestNumberUp_=INT_MAX;
1802      bestNumberDown_=INT_MAX;
1803    }
1804    // before solution - choose smallest number
1805    // could add in depth as well
1806    int bestNumber = CoinMin(bestNumberUp_,bestNumberDown_);
1807    if (numInfUp<numInfDn) {
1808      if (numInfUp<bestNumber) {
1809        betterWay = 1;
1810      } else if (numInfUp==bestNumber) {
1811        if (changeUp<bestCriterion_)
1812          betterWay=1;
1813      }
1814    } else if (numInfUp>numInfDn) {
1815      if (numInfDn<bestNumber) {
1816        betterWay = -1;
1817      } else if (numInfDn==bestNumber) {
1818        if (changeDn<bestCriterion_)
1819          betterWay=-1;
1820      }
1821    } else {
1822      // up and down have same number
1823      bool better=false;
1824      if (numInfUp<bestNumber) {
1825        better=true;
1826      } else if (numInfUp==bestNumber) {
1827        if (min(changeUp,changeDn)<bestCriterion_)
1828          better=true;;
1829      }
1830      if (better) {
1831        // see which way
1832        if (changeUp<=changeDn)
1833          betterWay=1;
1834        else
1835          betterWay=-1;
1836      }
1837    }
1838  } else {
1839    if (!bestObject_) {
1840      bestCriterion_=-1.0;
1841    }
1842    // got a solution
1843    if (changeUp<=changeDn) {
1844      if (changeUp>bestCriterion_)
1845        betterWay=1;
1846    } else {
1847      if (changeDn>bestCriterion_)
1848        betterWay=-1;
1849    }
1850  }
1851  if (betterWay) {
1852    bestCriterion_ = CoinMin(changeUp,changeDn);
1853    bestChangeUp_ = changeUp;
1854    bestNumberUp_ = numInfUp;
1855    bestChangeDown_ = changeDn;
1856    bestNumberDown_ = numInfDn;
1857    bestObject_=thisOne;
1858  }
1859  return betterWay;
1860}
1861// Default Constructor
1862CbcFollowOn::CbcFollowOn ()
1863  : CbcObject(),
1864    rhs_(NULL)
1865{
1866}
1867
1868// Useful constructor
1869CbcFollowOn::CbcFollowOn (CbcModel * model)
1870  : CbcObject(model)
1871{
1872  assert (model);
1873  OsiSolverInterface * solver = model_->solver();
1874  matrix_ = *solver->getMatrixByCol();
1875  matrix_.removeGaps();
1876  matrixByRow_ = *solver->getMatrixByRow();
1877  int numberRows = matrix_.getNumRows();
1878 
1879  rhs_ = new int[numberRows];
1880  int i;
1881  const double * rowLower = solver->getRowLower();
1882  const double * rowUpper = solver->getRowUpper();
1883  // Row copy
1884  const double * elementByRow = matrixByRow_.getElements();
1885  const int * column = matrixByRow_.getIndices();
1886  const CoinBigIndex * rowStart = matrixByRow_.getVectorStarts();
1887  const int * rowLength = matrixByRow_.getVectorLengths();
1888  for (i=0;i<numberRows;i++) {
1889    rhs_[i]=0;
1890    double value = rowLower[i];
1891    if (value==rowUpper[i]) {
1892      if (floor(value)==value&&value>=1.0&&value<10.0) {
1893        // check elements
1894        bool good=true;
1895        for (int j=rowStart[i];j<rowStart[i]+rowLength[i];j++) {
1896          int iColumn = column[j];
1897          if (!solver->isBinary(iColumn))
1898            good=false;
1899          double elValue = elementByRow[j];
1900          if (floor(elValue)!=elValue||value<1.0)
1901            good=false;
1902        }
1903        if (good)
1904          rhs_[i]=(int) value;
1905      }
1906    }
1907  }
1908}
1909
1910// Copy constructor
1911CbcFollowOn::CbcFollowOn ( const CbcFollowOn & rhs)
1912  :CbcObject(rhs),
1913   matrix_(rhs.matrix_),
1914   matrixByRow_(rhs.matrixByRow_)
1915{
1916  int numberRows = matrix_.getNumRows();
1917  rhs_= CoinCopyOfArray(rhs.rhs_,numberRows);
1918}
1919
1920// Clone
1921CbcObject *
1922CbcFollowOn::clone() const
1923{
1924  return new CbcFollowOn(*this);
1925}
1926
1927// Assignment operator
1928CbcFollowOn & 
1929CbcFollowOn::operator=( const CbcFollowOn& rhs)
1930{
1931  if (this!=&rhs) {
1932    CbcObject::operator=(rhs);
1933    delete [] rhs_;
1934    matrix_ = rhs.matrix_;
1935    matrixByRow_ = rhs.matrixByRow_;
1936    int numberRows = matrix_.getNumRows();
1937    rhs_= CoinCopyOfArray(rhs.rhs_,numberRows);
1938  }
1939  return *this;
1940}
1941
1942// Destructor
1943CbcFollowOn::~CbcFollowOn ()
1944{
1945  delete [] rhs_;
1946}
1947// As some computation is needed in more than one place - returns row
1948int 
1949CbcFollowOn::gutsOfFollowOn(int & otherRow, int & preferredWay) const
1950{
1951  int whichRow=-1;
1952  otherRow=-1;
1953  int numberRows = matrix_.getNumRows();
1954 
1955  int i;
1956  // For sorting
1957  int * sort = new int [numberRows];
1958  int * isort = new int [numberRows];
1959  // Column copy
1960  //const double * element = matrix_.getElements();
1961  const int * row = matrix_.getIndices();
1962  const CoinBigIndex * columnStart = matrix_.getVectorStarts();
1963  const int * columnLength = matrix_.getVectorLengths();
1964  // Row copy
1965  const double * elementByRow = matrixByRow_.getElements();
1966  const int * column = matrixByRow_.getIndices();
1967  const CoinBigIndex * rowStart = matrixByRow_.getVectorStarts();
1968  const int * rowLength = matrixByRow_.getVectorLengths();
1969  OsiSolverInterface * solver = model_->solver();
1970  const double * columnLower = solver->getColLower();
1971  const double * columnUpper = solver->getColUpper();
1972  const double * solution = solver->getColSolution();
1973  double integerTolerance = model_->getDblParam(CbcModel::CbcIntegerTolerance);
1974  int nSort=0;
1975  for (i=0;i<numberRows;i++) {
1976    if (rhs_[i]) {
1977      // check elements
1978      double smallest=1.0e10;
1979      double largest=0.0;
1980      int rhsValue=rhs_[i];
1981      int number1=0;
1982      int numberUnsatisfied=0;
1983      for (int j=rowStart[i];j<rowStart[i]+rowLength[i];j++) {
1984        int iColumn = column[j];
1985        double value = elementByRow[j];
1986        double solValue = solution[iColumn];
1987        if (columnLower[iColumn]!=columnUpper[iColumn]) {
1988          smallest = CoinMin(smallest,value);
1989          largest = CoinMax(largest,value);
1990          if (value==1.0)
1991            number1++;
1992          if (solValue<1.0-integerTolerance&&solValue>integerTolerance)
1993            numberUnsatisfied++;
1994        } else {
1995          rhsValue -= (int)(value*floor(solValue+0.5));
1996        }
1997      }
1998      if (numberUnsatisfied>1) {
1999        if (smallest<largest) {
2000          // probably no good but check a few things
2001          assert (largest<=rhsValue);
2002          if (number1==1&&largest==rhsValue)
2003            printf("could fix\n");
2004        } else if (largest==rhsValue) {
2005          sort[nSort]=i;
2006          isort[nSort++]=-numberUnsatisfied;
2007        }
2008      }
2009    }
2010  }
2011  if (nSort>1) {
2012    CoinSort_2(isort,isort+nSort,sort);
2013    CoinZeroN(isort,numberRows);
2014    double * other = new double[numberRows];
2015    CoinZeroN(other,numberRows);
2016    int * which = new int[numberRows];
2017    //#define COUNT
2018#ifndef COUNT
2019    bool beforeSolution = model_->getSolutionCount()==0;
2020#endif
2021    for (int k=0;k<nSort-1;k++) {
2022      i=sort[k];
2023      int numberUnsatisfied = 0;
2024      int n=0;
2025      int j;
2026      for (j=rowStart[i];j<rowStart[i]+rowLength[i];j++) {
2027        int iColumn = column[j];
2028        if (columnLower[iColumn]!=columnUpper[iColumn]) {
2029          double solValue = solution[iColumn]-columnLower[iColumn];
2030          if (solValue<1.0-integerTolerance&&solValue>integerTolerance) {
2031            numberUnsatisfied++;
2032            for (int jj=columnStart[iColumn];jj<columnStart[iColumn]+columnLength[iColumn];jj++) {
2033              int iRow = row[jj];
2034              if (rhs_[iRow]) {
2035                other[iRow]+=solValue;
2036                if (isort[iRow]) {
2037                  isort[iRow]++;
2038                } else {
2039                  isort[iRow]=1;
2040                  which[n++]=iRow;
2041                }
2042              }
2043            }
2044          }
2045        }
2046      }
2047      double total=0.0;
2048      // Take out row
2049      double sumThis=other[i];
2050      other[i]=0.0;
2051      assert (numberUnsatisfied==isort[i]);
2052      // find one nearest half if solution, one if before solution
2053      int iBest=-1;
2054      double dtarget=0.5*total;
2055#ifdef COUNT
2056      int target = (numberUnsatisfied+1)>>1;
2057      int best=numberUnsatisfied;
2058#else
2059      double best;
2060      if (beforeSolution)
2061        best=dtarget;
2062      else
2063        best=1.0e30;
2064#endif
2065      for (j=0;j<n;j++) {
2066        int iRow = which[j];
2067        double dvalue=other[iRow];
2068        other[iRow]=0.0;
2069#ifdef COUNT
2070        int value = isort[iRow];
2071#endif
2072        isort[iRow]=0;
2073        if (fabs(dvalue)<1.0e-8||fabs(sumThis-dvalue)<1.0e-8)
2074          continue;
2075        if (dvalue<integerTolerance||dvalue>1.0-integerTolerance)
2076          continue;
2077#ifdef COUNT
2078        if (abs(value-target)<best&&value!=numberUnsatisfied) {
2079          best=abs(value-target);
2080          iBest=iRow;
2081          if (dvalue<dtarget)
2082            preferredWay=1;
2083          else
2084            preferredWay=-1;
2085        }
2086#else
2087        if (beforeSolution) {
2088          if (fabs(dvalue-dtarget)>best) {
2089            best = fabs(dvalue-dtarget);
2090            iBest=iRow;
2091            if (dvalue<dtarget)
2092              preferredWay=1;
2093            else
2094              preferredWay=-1;
2095          }
2096        } else {
2097          if (fabs(dvalue-dtarget)<best) {
2098            best = fabs(dvalue-dtarget);
2099            iBest=iRow;
2100            if (dvalue<dtarget)
2101              preferredWay=1;
2102            else
2103              preferredWay=-1;
2104          }
2105        }
2106#endif
2107      }
2108      if (iBest>=0) {
2109        whichRow=i;
2110        otherRow=iBest;
2111        break;
2112      }
2113    }
2114    delete [] which;
2115    delete [] other;
2116  }
2117  delete [] sort;
2118  delete [] isort;
2119  return whichRow;
2120}
2121
2122// Infeasibility - large is 0.5
2123double 
2124CbcFollowOn::infeasibility(int & preferredWay) const
2125{
2126  int otherRow=0;
2127  int whichRow = gutsOfFollowOn(otherRow,preferredWay);
2128  if (whichRow<0)
2129    return 0.0;
2130  else
2131  return 2.0* model_->getDblParam(CbcModel::CbcIntegerTolerance);
2132}
2133
2134// This looks at solution and sets bounds to contain solution
2135void 
2136CbcFollowOn::feasibleRegion()
2137{
2138}
2139
2140
2141// Creates a branching object
2142CbcBranchingObject * 
2143CbcFollowOn::createBranch(int way) const
2144{
2145  int otherRow=0;
2146  int preferredWay;
2147  int whichRow = gutsOfFollowOn(otherRow,preferredWay);
2148  assert(way==preferredWay);
2149  assert (whichRow>=0);
2150  int numberColumns = matrix_.getNumCols();
2151 
2152  // Column copy
2153  //const double * element = matrix_.getElements();
2154  const int * row = matrix_.getIndices();
2155  const CoinBigIndex * columnStart = matrix_.getVectorStarts();
2156  const int * columnLength = matrix_.getVectorLengths();
2157  // Row copy
2158  //const double * elementByRow = matrixByRow_.getElements();
2159  const int * column = matrixByRow_.getIndices();
2160  const CoinBigIndex * rowStart = matrixByRow_.getVectorStarts();
2161  const int * rowLength = matrixByRow_.getVectorLengths();
2162  OsiSolverInterface * solver = model_->solver();
2163  const double * columnLower = solver->getColLower();
2164  const double * columnUpper = solver->getColUpper();
2165  //const double * solution = solver->getColSolution();
2166  int nUp=0;
2167  int nDown=0;
2168  int * upList = new int[numberColumns];
2169  int * downList = new int[numberColumns];
2170  int j;
2171  for (j=rowStart[whichRow];j<rowStart[whichRow]+rowLength[whichRow];j++) {
2172    int iColumn = column[j];
2173    if (columnLower[iColumn]!=columnUpper[iColumn]) {
2174      bool up=true;
2175      for (int jj=columnStart[iColumn];jj<columnStart[iColumn]+columnLength[iColumn];jj++) {
2176        int iRow = row[jj];
2177        if (iRow==otherRow) {
2178          up=false;
2179          break;
2180        }
2181      }
2182      if (up)
2183        upList[nUp++]=iColumn;
2184      else
2185        downList[nDown++]=iColumn;
2186    }
2187  }
2188  //printf("way %d\n",way);
2189  // create object
2190  //printf("would fix %d down and %d up\n",nDown,nUp);
2191  CbcBranchingObject * branch
2192     = new CbcFixingBranchingObject(model_,way,
2193                                         nDown,downList,nUp,upList);
2194  delete [] upList;
2195  delete [] downList;
2196  return branch;
2197}
2198// Default Constructor
2199CbcFixingBranchingObject::CbcFixingBranchingObject()
2200  :CbcBranchingObject()
2201{
2202  numberDown_=0;
2203  numberUp_=0;
2204  downList_=NULL;
2205  upList_=NULL;
2206}
2207
2208// Useful constructor
2209CbcFixingBranchingObject::CbcFixingBranchingObject (CbcModel * model,
2210                                                    int way ,
2211                                                    int numberOnDownSide, const int * down,
2212                                                    int numberOnUpSide, const int * up)
2213  :CbcBranchingObject(model,0,way,0.5)
2214{
2215  numberDown_=numberOnDownSide;
2216  numberUp_=numberOnUpSide;
2217  downList_ = CoinCopyOfArray(down,numberDown_);
2218  upList_ = CoinCopyOfArray(up,numberUp_);
2219}
2220
2221// Copy constructor
2222CbcFixingBranchingObject::CbcFixingBranchingObject ( const CbcFixingBranchingObject & rhs) :CbcBranchingObject(rhs)
2223{
2224  numberDown_=rhs.numberDown_;
2225  numberUp_=rhs.numberUp_;
2226  downList_ = CoinCopyOfArray(rhs.downList_,numberDown_);
2227  upList_ = CoinCopyOfArray(rhs.upList_,numberUp_);
2228}
2229
2230// Assignment operator
2231CbcFixingBranchingObject & 
2232CbcFixingBranchingObject::operator=( const CbcFixingBranchingObject& rhs)
2233{
2234  if (this != &rhs) {
2235    CbcBranchingObject::operator=(rhs);
2236    delete [] downList_;
2237    delete [] upList_;
2238    numberDown_=rhs.numberDown_;
2239    numberUp_=rhs.numberUp_;
2240    downList_ = CoinCopyOfArray(rhs.downList_,numberDown_);
2241    upList_ = CoinCopyOfArray(rhs.upList_,numberUp_);
2242  }
2243  return *this;
2244}
2245CbcBranchingObject * 
2246CbcFixingBranchingObject::clone() const
2247{ 
2248  return (new CbcFixingBranchingObject(*this));
2249}
2250
2251
2252// Destructor
2253CbcFixingBranchingObject::~CbcFixingBranchingObject ()
2254{
2255  delete [] downList_;
2256  delete [] upList_;
2257}
2258double
2259CbcFixingBranchingObject::branch(bool normalBranch)
2260{
2261  if (model_->messageHandler()->logLevel()>2&&normalBranch)
2262    print(normalBranch);
2263  numberBranchesLeft_--;
2264  OsiSolverInterface * solver = model_->solver();
2265  const double * columnLower = solver->getColLower();
2266  int i;
2267  // *** for way - up means fix all those in up section
2268  if (way_<0) {
2269#ifdef FULL_PRINT
2270    printf("Down Fix ");
2271#endif
2272    //printf("Down Fix %d\n",numberDown_);
2273    for (i=0;i<numberDown_;i++) {
2274      int iColumn = downList_[i];
2275      model_->solver()->setColUpper(iColumn,columnLower[iColumn]);
2276#ifdef FULL_PRINT
2277      printf("Setting bound on %d to lower bound\n",iColumn);
2278#endif
2279    }
2280    way_=1;       // Swap direction
2281  } else {
2282#ifdef FULL_PRINT
2283    printf("Up Fix ");
2284#endif
2285    //printf("Up Fix %d\n",numberUp_);
2286    for (i=0;i<numberUp_;i++) {
2287      int iColumn = upList_[i];
2288      model_->solver()->setColUpper(iColumn,columnLower[iColumn]);
2289#ifdef FULL_PRINT
2290      printf("Setting bound on %d to lower bound\n",iColumn);
2291#endif
2292    }
2293    way_=-1;      // Swap direction
2294  }
2295#ifdef FULL_PRINT
2296  printf("\n");
2297#endif
2298  return 0.0;
2299}
2300void
2301CbcFixingBranchingObject::print(bool normalBranch)
2302{
2303  int i;
2304  // *** for way - up means fix all those in up section
2305  if (way_<0) {
2306    printf("Down Fix ");
2307    for (i=0;i<numberDown_;i++) {
2308      int iColumn = downList_[i];
2309      printf("%d ",iColumn);
2310    }
2311  } else {
2312    printf("Up Fix ");
2313    for (i=0;i<numberUp_;i++) {
2314      int iColumn = upList_[i];
2315      printf("%d ",iColumn);
2316    }
2317  }
2318  printf("\n");
2319}
Note: See TracBrowser for help on using the repository browser.