source: trunk/Cbc/src/CbcNode.cpp @ 819

Last change on this file since 819 was 819, checked in by forrest, 13 years ago

fixes for bonmin and other stuff

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 157.7 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
8#include "CbcConfig.h"
9
10#include <string>
11//#define CBC_DEBUG 1
12//#define CHECK_CUT_COUNTS
13//#define CHECK_NODE
14//#define CBC_CHECK_BASIS
15#define CBC_WEAK_STRONG
16#include <cassert>
17#include <cfloat>
18#define CUTS
19#include "OsiSolverInterface.hpp"
20#include "OsiChooseVariable.hpp"
21#include "OsiAuxInfo.hpp"
22#include "OsiSolverBranch.hpp"
23#include "CoinWarmStartBasis.hpp"
24#include "CoinTime.hpp"
25#include "CbcModel.hpp"
26#include "CbcNode.hpp"
27#include "CbcStatistics.hpp"
28#include "CbcStrategy.hpp"
29#include "CbcBranchActual.hpp"
30#include "CbcBranchDynamic.hpp"
31#include "OsiRowCut.hpp"
32#include "OsiRowCutDebugger.hpp"
33#include "OsiCuts.hpp"
34#include "CbcCountRowCut.hpp"
35#include "CbcFeasibilityBase.hpp"
36#include "CbcMessage.hpp"
37#ifdef COIN_HAS_CLP
38#include "OsiClpSolverInterface.hpp"
39#include "ClpSimplexOther.hpp"
40#endif
41using namespace std;
42#include "CglCutGenerator.hpp"
43// Default Constructor
44CbcNodeInfo::CbcNodeInfo ()
45  :
46  numberPointingToThis_(0),
47  parent_(NULL),
48  owner_(NULL),
49  numberCuts_(0),
50  nodeNumber_(0),
51  cuts_(NULL),
52  numberRows_(0),
53  numberBranchesLeft_(0)
54{
55#ifdef CHECK_NODE
56  printf("CbcNodeInfo %x Constructor\n",this);
57#endif
58}
59// Constructor given parent
60CbcNodeInfo::CbcNodeInfo (CbcNodeInfo * parent)
61  :
62  numberPointingToThis_(2),
63  parent_(parent),
64  owner_(NULL),
65  numberCuts_(0),
66  nodeNumber_(0),
67  cuts_(NULL),
68  numberRows_(0),
69  numberBranchesLeft_(2)
70{
71#ifdef CHECK_NODE
72  printf("CbcNodeInfo %x Constructor from parent %x\n",this,parent_);
73#endif
74  if (parent_) {
75    numberRows_ = parent_->numberRows_+parent_->numberCuts_;
76    //parent_->increment();
77  }
78}
79// Copy Constructor
80CbcNodeInfo::CbcNodeInfo (const CbcNodeInfo & rhs)
81  :
82  numberPointingToThis_(rhs.numberPointingToThis_),
83  parent_(rhs.parent_),
84  owner_(rhs.owner_),
85  numberCuts_(rhs.numberCuts_),
86  nodeNumber_(rhs.nodeNumber_),
87  cuts_(NULL),
88  numberRows_(rhs.numberRows_),
89  numberBranchesLeft_(rhs.numberBranchesLeft_)
90{
91#ifdef CHECK_NODE
92  printf("CbcNodeInfo %x Copy constructor\n",this);
93#endif
94  if (numberCuts_) {
95    cuts_ = new CbcCountRowCut * [numberCuts_];
96    int n=0;
97    for (int i=0;i<numberCuts_;i++) {
98      CbcCountRowCut * thisCut = rhs.cuts_[i];
99      if (thisCut) {
100        // I think this is correct - new one should take priority
101        thisCut->setInfo(this,n);
102        thisCut->increment(numberBranchesLeft_); 
103        cuts_[n++] = thisCut;
104      }
105    }
106    numberCuts_=n;
107  }
108}
109// Constructor given parent and owner
110CbcNodeInfo::CbcNodeInfo (CbcNodeInfo * parent, CbcNode * owner)
111  :
112  numberPointingToThis_(2),
113  parent_(parent),
114  owner_(owner),
115  numberCuts_(0),
116  nodeNumber_(0),
117  cuts_(NULL),
118  numberRows_(0),
119  numberBranchesLeft_(2)
120{
121#ifdef CHECK_NODE
122  printf("CbcNodeInfo %x Constructor from parent %x\n",this,parent_);
123#endif
124  if (parent_) {
125    numberRows_ = parent_->numberRows_+parent_->numberCuts_;
126  }
127}
128
129/**
130  Take care to detach from the owning CbcNode and decrement the reference
131  count in the parent.  If this is the last nodeInfo object pointing to the
132  parent, make a recursive call to delete the parent.
133*/
134CbcNodeInfo::~CbcNodeInfo()
135{
136#ifdef CHECK_NODE
137  printf("CbcNodeInfo %x Destructor parent %x\n",this,parent_);
138#endif
139
140  assert(!numberPointingToThis_);
141  // But they may be some left (max nodes?)
142  for (int i=0;i<numberCuts_;i++) {
143#ifndef GLOBAL_CUTS_JUST_POINTERS
144    delete cuts_[i];
145#else
146    if (cuts_[i]->globallyValidAsInteger()!=2)
147      delete cuts_[i];
148#endif
149  }
150  delete [] cuts_;
151  if (owner_) 
152    owner_->nullNodeInfo();
153  if (parent_) {
154    int numberLinks = parent_->decrement();
155    if (!numberLinks) delete parent_;
156  }
157}
158
159
160//#define ALLCUTS
161void
162CbcNodeInfo::decrementCuts(int change)
163{
164  int i;
165  // get rid of all remaining if negative
166  int changeThis;
167  if (change<0)
168    changeThis = numberBranchesLeft_;
169  else
170    changeThis = change;
171 // decrement cut counts
172  for (i=0;i<numberCuts_;i++) {
173    if (cuts_[i]) {
174      int number = cuts_[i]->decrement(changeThis);
175      if (!number) {
176        //printf("info %x del cut %d %x\n",this,i,cuts_[i]);
177#ifndef GLOBAL_CUTS_JUST_POINTERS
178        delete cuts_[i];
179#else
180        if (cuts_[i]->globallyValidAsInteger()!=2)
181          delete cuts_[i];
182#endif
183        cuts_[i]=NULL;
184      }
185    }
186  }
187}
188void
189CbcNodeInfo::decrementParentCuts(int change)
190{
191  if (parent_) {
192    // get rid of all remaining if negative
193    int changeThis;
194    if (change<0)
195      changeThis = numberBranchesLeft_;
196    else
197      changeThis = change;
198    int i;
199    // Get over-estimate of space needed for basis
200    CoinWarmStartBasis dummy;
201    dummy.setSize(0,numberRows_+numberCuts_);
202    buildRowBasis(dummy);
203    /* everything is zero (i.e. free) so we can use to see
204       if latest basis */
205    CbcNodeInfo * thisInfo = parent_;
206    while (thisInfo) 
207      thisInfo = thisInfo->buildRowBasis(dummy);
208    // decrement cut counts
209    thisInfo = parent_;
210    int numberRows=numberRows_;
211    while (thisInfo) {
212      for (i=thisInfo->numberCuts_-1;i>=0;i--) {
213        CoinWarmStartBasis::Status status = dummy.getArtifStatus(--numberRows);
214#ifdef ALLCUTS
215        status = CoinWarmStartBasis::isFree;
216#endif
217        if (thisInfo->cuts_[i]) {
218          int number=1;
219          if (status!=CoinWarmStartBasis::basic) {
220            // tight - drop 1 or 2
221            if (change<0)
222              number = thisInfo->cuts_[i]->decrement(changeThis);
223            else
224              number = thisInfo->cuts_[i]->decrement(change);
225          }
226          if (!number) {
227#ifndef GLOBAL_CUTS_JUST_POINTERS
228            delete thisInfo->cuts_[i];
229#else
230            if (thisInfo->cuts_[i]->globallyValidAsInteger()!=2)
231              delete thisInfo->cuts_[i];
232#endif
233            thisInfo->cuts_[i]=NULL;
234          }
235        }
236      }
237      thisInfo = thisInfo->parent_;
238    }
239  }
240}
241
242void
243CbcNodeInfo::incrementParentCuts(int change)
244{
245  if (parent_) {
246    int i;
247    // Get over-estimate of space needed for basis
248    CoinWarmStartBasis dummy;
249    dummy.setSize(0,numberRows_+numberCuts_);
250    /* everything is zero (i.e. free) so we can use to see
251       if latest basis */
252    buildRowBasis(dummy);
253    CbcNodeInfo * thisInfo = parent_;
254    while (thisInfo) 
255      thisInfo = thisInfo->buildRowBasis(dummy);
256    // increment cut counts
257    thisInfo = parent_;
258    int numberRows=numberRows_;
259    while (thisInfo) {
260      for (i=thisInfo->numberCuts_-1;i>=0;i--) {
261        CoinWarmStartBasis::Status status = dummy.getArtifStatus(--numberRows);
262#ifdef ALLCUTS
263        status = CoinWarmStartBasis::isFree;
264#endif
265        if (thisInfo->cuts_[i]&&status!=CoinWarmStartBasis::basic) {
266          thisInfo->cuts_[i]->increment(change);
267        }
268      }
269      thisInfo = thisInfo->parent_;
270    }
271  }
272}
273
274/*
275  Append cuts to the cuts_ array in a nodeInfo. The initial reference count
276  is set to numberToBranchOn, which will normally be the number of arms
277  defined for the CbcBranchingObject attached to the CbcNode that owns this
278  CbcNodeInfo.
279*/
280void
281CbcNodeInfo::addCuts (OsiCuts & cuts, int numberToBranchOn,
282                      int * whichGenerator)
283{
284  int numberCuts = cuts.sizeRowCuts();
285  if (numberCuts) {
286    int i;
287    if (!numberCuts_) {
288      cuts_ = new CbcCountRowCut * [numberCuts];
289    } else {
290      CbcCountRowCut ** temp = new CbcCountRowCut * [numberCuts+numberCuts_];
291      memcpy(temp,cuts_,numberCuts_*sizeof(CbcCountRowCut *));
292      delete [] cuts_;
293      cuts_ = temp;
294    }
295    for (i=0;i<numberCuts;i++) {
296      CbcCountRowCut * thisCut = new CbcCountRowCut(*cuts.rowCutPtr(i),
297                                                    this,numberCuts_);
298      thisCut->increment(numberToBranchOn); 
299      cuts_[numberCuts_++] = thisCut;
300#ifdef CBC_DEBUG
301#if CBC_DEBUG>1
302      int n=thisCut->row().getNumElements();
303      printf("Cut %d has %d entries, rhs %g %g =>",i,n,thisCut->lb(),
304             thisCut->ub());
305      int j;
306      const int * index = thisCut->row().getIndices();
307      const double * element = thisCut->row().getElements();
308      for (j=0;j<n;j++) {
309        printf(" (%d,%g)",index[j],element[j]);
310        assert(fabs(element[j])>1.00e-12);
311      }
312      printf("\n");
313#else
314      int n=thisCut->row().getNumElements();
315      int j;
316      const double * element = thisCut->row().getElements();
317      for (j=0;j<n;j++) {
318        assert(fabs(element[j])>1.00e-12);
319      }
320#endif
321#endif
322    }
323  }
324}
325
326void
327CbcNodeInfo::addCuts(int numberCuts, CbcCountRowCut ** cut, 
328                     int numberToBranchOn)
329{
330  if (numberCuts) {
331    int i;
332    if (!numberCuts_) {
333      cuts_ = new CbcCountRowCut * [numberCuts];
334    } else {
335      CbcCountRowCut ** temp = new CbcCountRowCut * [numberCuts+numberCuts_];
336      memcpy(temp,cuts_,numberCuts_*sizeof(CbcCountRowCut *));
337      delete [] cuts_;
338      cuts_ = temp;
339    }
340    for (i=0;i<numberCuts;i++) {
341      CbcCountRowCut * thisCut = cut[i];
342      thisCut->setInfo(this,numberCuts_);
343      //printf("info %x cut %d %x\n",this,i,thisCut);
344      thisCut->increment(numberToBranchOn); 
345      cuts_[numberCuts_++] = thisCut;
346#ifdef CBC_DEBUG
347      int n=thisCut->row().getNumElements();
348#if CBC_DEBUG>1
349      printf("Cut %d has %d entries, rhs %g %g =>",i,n,thisCut->lb(),
350             thisCut->ub());
351#endif
352      int j;
353#if CBC_DEBUG>1
354      const int * index = thisCut->row().getIndices();
355#endif
356      const double * element = thisCut->row().getElements();
357      for (j=0;j<n;j++) {
358#if CBC_DEBUG>1
359        printf(" (%d,%g)",index[j],element[j]);
360#endif
361        assert(fabs(element[j])>1.00e-12);
362      }
363      printf("\n");
364#endif
365    }
366  }
367}
368
369// delete cuts
370void
371CbcNodeInfo::deleteCuts(int numberToDelete, CbcCountRowCut ** cuts)
372{
373  int i;
374  int j;
375  int last=-1;
376  for (i=0;i<numberToDelete;i++) {
377    CbcCountRowCut * next = cuts[i];
378    for (j=last+1;j<numberCuts_;j++) {
379      if (next==cuts_[j])
380        break;
381    }
382    if (j==numberCuts_) {
383      // start from beginning
384      for (j=0;j<last;j++) {
385        if (next==cuts_[j])
386          break;
387      }
388      assert(j<last);
389    }
390    last=j;
391    int number = cuts_[j]->decrement();
392    if (!number) {
393#ifndef GLOBAL_CUTS_JUST_POINTERS
394      delete cuts_[j];
395#else
396      if (cuts_[j]->globallyValidAsInteger()!=2)
397        delete cuts_[j];
398#endif
399    }
400    cuts_[j]=NULL;
401  }
402  j=0;
403  for (i=0;i<numberCuts_;i++) {
404    if (cuts_[i])
405      cuts_[j++]=cuts_[i];
406  }
407  numberCuts_ = j;
408}
409
410// delete cuts
411void
412CbcNodeInfo::deleteCuts(int numberToDelete, int * which)
413{
414  int i;
415  for (i=0;i<numberToDelete;i++) {
416    int iCut=which[i];
417    int number = cuts_[iCut]->decrement();
418    if (!number) {
419#ifndef GLOBAL_CUTS_JUST_POINTERS
420      delete cuts_[iCut];
421#else
422      if (cuts_[iCut]->globallyValidAsInteger()!=2)
423        delete cuts_[iCut];
424#endif
425    }
426    cuts_[iCut]=NULL;
427  }
428  int j=0;
429  for (i=0;i<numberCuts_;i++) {
430    if (cuts_[i])
431      cuts_[j++]=cuts_[i];
432  }
433  numberCuts_ = j;
434}
435
436// Really delete a cut
437void 
438CbcNodeInfo::deleteCut(int whichOne)
439{
440  assert(whichOne<numberCuts_);
441  cuts_[whichOne]=NULL;
442}
443
444CbcFullNodeInfo::CbcFullNodeInfo() :
445  CbcNodeInfo(),
446  basis_(),
447  numberIntegers_(0),
448  lower_(NULL),
449  upper_(NULL)
450{
451}
452CbcFullNodeInfo::CbcFullNodeInfo(CbcModel * model,
453                                 int numberRowsAtContinuous) :
454  CbcNodeInfo()
455{
456  OsiSolverInterface * solver = model->solver();
457  numberRows_ = numberRowsAtContinuous;
458  numberIntegers_ = model->numberIntegers();
459  int numberColumns = model->getNumCols();
460  lower_ = new double [numberColumns];
461  upper_ = new double [numberColumns];
462  const double * lower = solver->getColLower();
463  const double * upper = solver->getColUpper();
464  int i;
465
466  for (i=0;i<numberColumns;i++) {
467    lower_[i]=lower[i];
468    upper_[i]=upper[i];
469  }
470
471  basis_ =  dynamic_cast<CoinWarmStartBasis*>(solver->getWarmStart());
472}
473
474CbcFullNodeInfo::CbcFullNodeInfo(const CbcFullNodeInfo & rhs) :
475  CbcNodeInfo(rhs)
476{ 
477  basis_= dynamic_cast<CoinWarmStartBasis *>(rhs.basis_->clone()) ;
478  numberIntegers_=rhs.numberIntegers_;
479  lower_=NULL;
480  upper_=NULL;
481  if (rhs.lower_!=NULL) {
482    int numberColumns = basis_->getNumStructural();
483    lower_ = new double [numberColumns];
484    upper_ = new double [numberColumns];
485    assert (upper_!=NULL);
486    memcpy(lower_,rhs.lower_,numberColumns*sizeof(double));
487    memcpy(upper_,rhs.upper_,numberColumns*sizeof(double));
488  }
489}
490
491CbcNodeInfo * 
492CbcFullNodeInfo::clone() const
493{ 
494  return (new CbcFullNodeInfo(*this));
495}
496
497CbcFullNodeInfo::~CbcFullNodeInfo ()
498{
499  delete basis_ ;
500  delete [] lower_;
501  delete [] upper_;
502}
503
504/*
505   The basis supplied as a parameter is deleted and replaced with a new basis
506   appropriate for the node, and lower and upper bounds on variables are
507   reset according to the stored bounds arrays. Any cuts associated with this
508   node are added to the list in addCuts, but not actually added to the
509   constraint system in the model.
510
511   Why pass in a basis at all? The short answer is ``We need the parameter to
512   pass out a basis, so might as well use it to pass in the size.''
513   
514   A longer answer is that in practice we take a memory allocation hit up in
515   addCuts1 (the only place applyToModel is called) when we setSize() the
516   basis that's passed in. It's immediately tossed here in favour of a clone
517   of the basis attached to this nodeInfo. This can probably be fixed, given
518   a bit of thought.
519*/
520
521void CbcFullNodeInfo::applyToModel (CbcModel *model,
522                                    CoinWarmStartBasis *&basis,
523                                    CbcCountRowCut **addCuts,
524                                    int &currentNumberCuts) const 
525
526{ OsiSolverInterface *solver = model->solver() ;
527
528  // branch - do bounds
529  int i;
530  solver->setColLower(lower_);
531  solver->setColUpper(upper_);
532  int numberColumns = model->getNumCols();
533  // move basis - but make sure size stays
534  // for bon-min - should not be needed int numberRows = model->getNumRows();
535  int numberRows=basis->getNumArtificial();
536  delete basis ;
537  if (basis_) {
538    basis = dynamic_cast<CoinWarmStartBasis *>(basis_->clone()) ;
539    basis->resize(numberRows,numberColumns);
540  } else {
541    // We have a solver without a basis
542    basis=NULL;
543  }
544  for (i=0;i<numberCuts_;i++) 
545    addCuts[currentNumberCuts+i]= cuts_[i];
546  currentNumberCuts += numberCuts_;
547  assert(!parent_);
548  return ;
549}
550
551/* Builds up row basis backwards (until original model).
552   Returns NULL or previous one to apply .
553   Depends on Free being 0 and impossible for cuts
554*/
555CbcNodeInfo * 
556CbcFullNodeInfo::buildRowBasis(CoinWarmStartBasis & basis ) const 
557{
558  const unsigned int * saved = 
559    (const unsigned int *) basis_->getArtificialStatus();
560  unsigned int * now = 
561    (unsigned int *) basis.getArtificialStatus();
562  int number=basis_->getNumArtificial()>>4;;
563  int i;
564  for (i=0;i<number;i++) { 
565    if (!now[i])
566      now[i] = saved[i];
567  }
568  return NULL;
569}
570
571
572// Default constructor
573CbcPartialNodeInfo::CbcPartialNodeInfo()
574
575  : CbcNodeInfo(),
576    basisDiff_(NULL),
577    variables_(NULL),
578    newBounds_(NULL),
579    numberChangedBounds_(0)
580
581{ /* this space intentionally left blank */ }
582
583// Constructor from current state
584CbcPartialNodeInfo::CbcPartialNodeInfo (CbcNodeInfo *parent, CbcNode *owner,
585                                        int numberChangedBounds,
586                                        const int *variables,
587                                        const double *boundChanges,
588                                        const CoinWarmStartDiff *basisDiff)
589 : CbcNodeInfo(parent,owner)
590{
591  basisDiff_ = basisDiff->clone() ;
592
593  numberChangedBounds_ = numberChangedBounds;
594  int size = numberChangedBounds_*(sizeof(double)+sizeof(int));
595  char * temp = new char [size];
596  newBounds_ = (double *) temp;
597  variables_ = (int *) (newBounds_+numberChangedBounds_);
598
599  int i ;
600  for (i=0;i<numberChangedBounds_;i++) {
601    variables_[i]=variables[i];
602    newBounds_[i]=boundChanges[i];
603  }
604}
605
606CbcPartialNodeInfo::CbcPartialNodeInfo (const CbcPartialNodeInfo & rhs)
607
608  : CbcNodeInfo(rhs.parent_)
609
610{ basisDiff_ = rhs.basisDiff_->clone() ;
611
612  numberChangedBounds_ = rhs.numberChangedBounds_;
613  int size = numberChangedBounds_*(sizeof(double)+sizeof(int));
614  char * temp = new char [size];
615  newBounds_ = (double *) temp;
616  variables_ = (int *) (newBounds_+numberChangedBounds_);
617
618  int i ;
619  for (i=0;i<numberChangedBounds_;i++) {
620    variables_[i]=rhs.variables_[i];
621    newBounds_[i]=rhs.newBounds_[i];
622  }
623}
624
625CbcNodeInfo * 
626CbcPartialNodeInfo::clone() const
627{ 
628  return (new CbcPartialNodeInfo(*this));
629}
630
631
632CbcPartialNodeInfo::~CbcPartialNodeInfo ()
633{
634  delete basisDiff_ ;
635  delete [] newBounds_;
636}
637
638
639/**
640   The basis supplied as a parameter is incrementally modified, and lower and
641   upper bounds on variables in the model are incrementally modified. Any
642   cuts associated with this node are added to the list in addCuts.
643*/
644
645void CbcPartialNodeInfo::applyToModel (CbcModel *model,
646                                       CoinWarmStartBasis *&basis,
647                                       CbcCountRowCut **addCuts,
648                                       int &currentNumberCuts) const 
649
650{ OsiSolverInterface *solver = model->solver();
651  basis->applyDiff(basisDiff_) ;
652
653  // branch - do bounds
654  int i;
655  for (i=0;i<numberChangedBounds_;i++) {
656    int variable = variables_[i];
657    int k = variable&0x7fffffff;
658    if ((variable&0x80000000)==0) {
659      // lower bound changing
660#ifndef NDEBUG
661      double oldValue = solver->getColLower()[k];
662      assert (newBounds_[i]>oldValue-1.0e-8);
663      if (newBounds_[i]<oldValue+1.0e-8)
664        printf("bad null lower change for column %d - bound %g\n",k,oldValue);
665#endif
666      solver->setColLower(k,newBounds_[i]);
667    } else {
668      // upper bound changing
669#ifndef NDEBUG
670      double oldValue = solver->getColUpper()[k];
671      assert (newBounds_[i]<oldValue+1.0e-8);
672      if (newBounds_[i]>oldValue-1.0e-8)
673        printf("bad null upper change for column %d - bound %g\n",k,oldValue);
674#endif
675      solver->setColUpper(k,newBounds_[i]);
676    }
677  }
678  for (i=0;i<numberCuts_;i++) {
679    addCuts[currentNumberCuts+i]= cuts_[i];
680    if (cuts_[i]&&model->messageHandler()->logLevel()>4) {
681      cuts_[i]->print();
682    }
683  }
684   
685  currentNumberCuts += numberCuts_;
686  return ;
687}
688
689/* Builds up row basis backwards (until original model).
690   Returns NULL or previous one to apply .
691   Depends on Free being 0 and impossible for cuts
692*/
693
694CbcNodeInfo * 
695CbcPartialNodeInfo::buildRowBasis(CoinWarmStartBasis & basis ) const 
696
697{ basis.applyDiff(basisDiff_) ;
698
699  return parent_ ; }
700
701CbcNode::CbcNode() :
702  nodeInfo_(NULL),
703  objectiveValue_(1.0e100),
704  guessedObjectiveValue_(1.0e100),
705  sumInfeasibilities_(0.0),
706  branch_(NULL),
707  depth_(-1),
708  numberUnsatisfied_(0)
709{
710#ifdef CHECK_NODE
711  printf("CbcNode %x Constructor\n",this);
712#endif
713}
714
715CbcNode::CbcNode(CbcModel * model,
716                 CbcNode * lastNode) :
717  nodeInfo_(NULL),
718  objectiveValue_(1.0e100),
719  guessedObjectiveValue_(1.0e100),
720  sumInfeasibilities_(0.0),
721  branch_(NULL),
722  depth_(-1),
723  numberUnsatisfied_(0)
724{
725#ifdef CHECK_NODE
726  printf("CbcNode %x Constructor from model\n",this);
727#endif
728  model->setObjectiveValue(this,lastNode);
729
730  if (lastNode)
731    if (lastNode->nodeInfo_)
732    lastNode->nodeInfo_->increment();
733}
734
735#define CBC_NEW_CREATEINFO
736#ifdef CBC_NEW_CREATEINFO
737
738/*
739  New createInfo, with basis manipulation hidden inside mergeBasis. Allows
740  solvers to override and carry over all information from one basis to
741  another.
742*/
743
744void
745CbcNode::createInfo (CbcModel *model,
746                     CbcNode *lastNode,
747                     const CoinWarmStartBasis *lastws,
748                     const double *lastLower, const double *lastUpper,
749                     int numberOldActiveCuts, int numberNewCuts)
750
751{ OsiSolverInterface *solver = model->solver();
752  CbcStrategy *strategy = model->strategy();
753/*
754  The root --- no parent. Create full basis and bounds information.
755*/
756  if (!lastNode)
757  { 
758    if (!strategy)
759      nodeInfo_=new CbcFullNodeInfo(model,solver->getNumRows());
760    else
761      nodeInfo_ = strategy->fullNodeInfo(model,solver->getNumRows());
762  } else {
763/*
764  Not the root. Create an edit from the parent's basis & bound information.
765  This is not quite as straightforward as it seems. We need to reintroduce
766  cuts we may have dropped out of the basis, in the correct position, because
767  this whole process is strictly positional. Start by grabbing the current
768  basis.
769*/
770    const CoinWarmStartBasis *ws =
771      dynamic_cast<const CoinWarmStartBasis*>(solver->getWarmStart());
772    assert(ws!=NULL); // make sure not volume
773    //int numberArtificials = lastws->getNumArtificial();
774    int numberColumns = solver->getNumCols();
775    int numberRowsAtContinuous = model->numberRowsAtContinuous();
776    int currentNumberCuts = model->currentNumberCuts();
777#   ifdef CBC_CHECK_BASIS
778    std::cout
779      << "Before expansion: orig " << numberRowsAtContinuous
780      << ", old " << numberOldActiveCuts
781      << ", new " << numberNewCuts
782      << ", current " << currentNumberCuts << "." << std::endl ;
783    ws->print();
784#   endif
785/*
786  Clone the basis and resize it to hold the structural constraints, plus
787  all the cuts: old cuts, both active and inactive (currentNumberCuts),
788  and new cuts (numberNewCuts). This will become the expanded basis.
789*/
790    CoinWarmStartBasis *expanded = 
791      dynamic_cast<CoinWarmStartBasis *>(ws->clone()) ;
792    int iCompact = numberRowsAtContinuous+numberOldActiveCuts+numberNewCuts ;
793    // int nPartial = numberRowsAtContinuous+currentNumberCuts;
794    int iFull = numberRowsAtContinuous+currentNumberCuts+numberNewCuts;
795    // int maxBasisLength = ((iFull+15)>>4)+((numberColumns+15)>>4);
796    // printf("l %d full %d\n",maxBasisLength,iFull);
797    expanded->resize(iFull,numberColumns);
798#   ifdef CBC_CHECK_BASIS
799    std::cout
800      << "\tFull basis " << iFull << " rows, "
801      << numberColumns << " columns; compact "
802      << iCompact << " rows." << std::endl ;
803#   endif
804/*
805  Now flesh out the expanded basis. The clone already has the
806  correct status information for the variables and for the structural
807  (numberRowsAtContinuous) constraints. Any indices beyond nPartial must be
808  cuts created while processing this node --- they can be copied en bloc
809  into the correct position in the expanded basis. The space reserved for
810  xferRows is a gross overestimate.
811*/
812    CoinWarmStartBasis::XferVec xferRows ;
813    xferRows.reserve(iFull-numberRowsAtContinuous+1) ;
814    if (numberNewCuts) {
815      xferRows.push_back(
816          CoinWarmStartBasis::XferEntry(iCompact-numberNewCuts,
817                                        iFull-numberNewCuts,numberNewCuts)) ;
818    }
819/*
820  From nPartial down, record the entries we want to copy from the current
821  basis (the entries for the active cuts; non-zero in the list returned
822  by addedCuts). Fill the expanded basis with entries showing a status of
823  basic for the deactivated (loose) cuts.
824*/
825    CbcCountRowCut **cut = model->addedCuts();
826    iFull -= (numberNewCuts+1) ;
827    iCompact -= (numberNewCuts+1) ;
828    int runLen = 0 ;
829    CoinWarmStartBasis::XferEntry entry(-1,-1,-1) ;
830    while (iFull >= numberRowsAtContinuous) { 
831      for ( ; iFull >= numberRowsAtContinuous &&
832              cut[iFull-numberRowsAtContinuous] ; iFull--)
833        runLen++ ;
834      if (runLen) {
835        iCompact -= runLen ;
836        entry.first = iCompact+1 ;
837        entry.second = iFull+1 ;
838        entry.third = runLen ;
839        runLen = 0 ;
840        xferRows.push_back(entry) ;
841      }
842      for ( ; iFull >= numberRowsAtContinuous &&
843              !cut[iFull-numberRowsAtContinuous] ; iFull--)
844        expanded->setArtifStatus(iFull,CoinWarmStartBasis::basic);
845    }
846/*
847  Finally, call mergeBasis to copy over entries from the current basis to
848  the expanded basis. Since we cloned the expanded basis from the active basis
849  and haven't changed the number of variables, only row status entries need
850  to be copied.
851*/
852    expanded->mergeBasis(ws,&xferRows,0) ;
853
854#ifdef CBC_CHECK_BASIS
855    std::cout << "Expanded basis:" << std::endl ;
856    expanded->print() ;
857    std::cout << "Diffing against:" << std::endl ;
858    lastws->print() ;
859#endif   
860
861/*
862  Now that we have two bases in proper positional correspondence, creating
863  the actual diff is dead easy.
864
865  Note that we're going to compare the expanded basis here to the stripped
866  basis (lastws) produced by addCuts. It doesn't affect the correctness (the
867  diff process has no knowledge of the meaning of an entry) but it does
868  mean that we'll always generate a whack of diff entries because the expanded
869  basis is considerably larger than the stripped basis.
870*/
871    CoinWarmStartDiff *basisDiff = expanded->generateDiff(lastws) ;
872/*
873  Diff the bound vectors. It's assumed the number of structural variables
874  is not changing. For branching objects that change bounds on integer
875  variables, we should see at least one bound change as a consequence
876  of applying the branch that generated this subproblem from its parent.
877  This need not hold for other types of branching objects (hyperplane
878  branches, for example).
879*/
880    const double * lower = solver->getColLower();
881    const double * upper = solver->getColUpper();
882
883    double *boundChanges = new double [2*numberColumns] ;
884    int *variables = new int [2*numberColumns] ;
885    int numberChangedBounds=0;
886   
887    int i;
888    for (i=0;i<numberColumns;i++) {
889      if (lower[i]!=lastLower[i]) {
890        variables[numberChangedBounds]=i;
891        boundChanges[numberChangedBounds++]=lower[i];
892      }
893      if (upper[i]!=lastUpper[i]) {
894        variables[numberChangedBounds]=i|0x80000000;
895        boundChanges[numberChangedBounds++]=upper[i];
896      }
897#ifdef CBC_DEBUG
898      if (lower[i] != lastLower[i]) {
899        std::cout
900          << "lower on " << i << " changed from "
901          << lastLower[i] << " to " << lower[i] << std::endl ;
902      }
903      if (upper[i] != lastUpper[i]) {
904        std::cout
905          << "upper on " << i << " changed from "
906          << lastUpper[i] << " to " << upper[i] << std::endl ;
907      }
908#endif
909    }
910#ifdef CBC_DEBUG
911    std::cout << numberChangedBounds << " changed bounds." << std::endl ;
912#endif
913    //if (lastNode->branchingObject()->boundBranch())
914    //assert (numberChangedBounds);
915/*
916  Hand the lot over to the CbcPartialNodeInfo constructor, then clean up and
917  return.
918*/
919    if (!strategy)
920      nodeInfo_ =
921        new CbcPartialNodeInfo(lastNode->nodeInfo_,this,numberChangedBounds,
922                               variables,boundChanges,basisDiff) ;
923    else
924      nodeInfo_ =
925        strategy->partialNodeInfo(model,lastNode->nodeInfo_,this,
926                                  numberChangedBounds,variables,boundChanges,
927                                  basisDiff) ;
928    delete basisDiff ;
929    delete [] boundChanges;
930    delete [] variables;
931    delete expanded ;
932    delete ws;
933  }
934  // Set node number
935  nodeInfo_->setNodeNumber(model->getNodeCount2());
936}
937
938#else   // CBC_NEW_CREATEINFO
939
940/*
941  Original createInfo, with bare manipulation of basis vectors. Fails if solver
942  maintains additional information in basis.
943*/
944
945void
946CbcNode::createInfo (CbcModel *model,
947                     CbcNode *lastNode,
948                     const CoinWarmStartBasis *lastws,
949                     const double *lastLower, const double *lastUpper,
950                     int numberOldActiveCuts,int numberNewCuts)
951{ OsiSolverInterface * solver = model->solver();
952 CbcStrategy * strategy = model->strategy();
953/*
954  The root --- no parent. Create full basis and bounds information.
955*/
956  if (!lastNode)
957  { 
958    if (!strategy)
959      nodeInfo_=new CbcFullNodeInfo(model,solver->getNumRows());
960    else
961      nodeInfo_ = strategy->fullNodeInfo(model,solver->getNumRows());
962  }
963/*
964  Not the root. Create an edit from the parent's basis & bound information.
965  This is not quite as straightforward as it seems. We need to reintroduce
966  cuts we may have dropped out of the basis, in the correct position, because
967  this whole process is strictly positional. Start by grabbing the current
968  basis.
969*/
970  else
971  { const CoinWarmStartBasis* ws =
972      dynamic_cast<const CoinWarmStartBasis*>(solver->getWarmStart());
973    assert(ws!=NULL); // make sure not volume
974    //int numberArtificials = lastws->getNumArtificial();
975    int numberColumns = solver->getNumCols();
976   
977    const double * lower = solver->getColLower();
978    const double * upper = solver->getColUpper();
979
980    int i;
981/*
982  Create a clone and resize it to hold all the structural constraints, plus
983  all the cuts: old cuts, both active and inactive (currentNumberCuts), and
984  new cuts (numberNewCuts).
985
986  TODO: You'd think that the set of constraints (logicals) in the expanded
987        basis should match the set represented in lastws. At least, that's
988        what I thought. But at the point I first looked hard at this bit of
989        code, it turned out that lastws was the stripped basis produced at
990        the end of addCuts(), rather than the raw basis handed back by
991        addCuts1(). The expanded basis here is equivalent to the raw basis of
992        addCuts1(). I said ``whoa, that's not good, I must have introduced a
993        bug'' and went back to John's code to see where I'd gone wrong.
994        And discovered the same `error' in his code.
995
996        After a bit of thought, my conclusion is that correctness is not
997        affected by whether lastws is the stripped or raw basis. The diffs
998        have no semantics --- just a set of changes that need to be made
999        to convert lastws into expanded. I think the only effect is that we
1000        store a lot more diffs (everything in expanded that's not covered by
1001        the stripped basis). But I need to give this more thought. There
1002        may well be some subtle error cases.
1003
1004        In the mean time, I've twiddled addCuts() to set lastws to the raw
1005        basis. Makes me (Lou) less nervous to compare apples to apples.
1006*/
1007    CoinWarmStartBasis *expanded = 
1008      dynamic_cast<CoinWarmStartBasis *>(ws->clone()) ;
1009    int numberRowsAtContinuous = model->numberRowsAtContinuous();
1010    int iFull = numberRowsAtContinuous+model->currentNumberCuts()+
1011      numberNewCuts;
1012    //int numberArtificialsNow = iFull;
1013    //int maxBasisLength = ((iFull+15)>>4)+((numberColumns+15)>>4);
1014    //printf("l %d full %d\n",maxBasisLength,iFull);
1015    if (expanded) 
1016      expanded->resize(iFull,numberColumns);
1017#ifdef CBC_CHECK_BASIS
1018    printf("Before expansion: orig %d, old %d, new %d, current %d\n",
1019           numberRowsAtContinuous,numberOldActiveCuts,numberNewCuts,
1020           model->currentNumberCuts()) ;
1021    ws->print();
1022#endif
1023/*
1024  Now fill in the expanded basis. Any indices beyond nPartial must
1025  be cuts created while processing this node --- they can be copied directly
1026  into the expanded basis. From nPartial down, pull the status of active cuts
1027  from ws, interleaving with a B entry for the deactivated (loose) cuts.
1028*/
1029    int numberDropped = model->currentNumberCuts()-numberOldActiveCuts;
1030    int iCompact=iFull-numberDropped;
1031    CbcCountRowCut ** cut = model->addedCuts();
1032    int nPartial = model->currentNumberCuts()+numberRowsAtContinuous;
1033    iFull--;
1034    for (;iFull>=nPartial;iFull--) {
1035      CoinWarmStartBasis::Status status = ws->getArtifStatus(--iCompact);
1036      //assert (status != CoinWarmStartBasis::basic); // may be permanent cut
1037      expanded->setArtifStatus(iFull,status);
1038    }
1039    for (;iFull>=numberRowsAtContinuous;iFull--) {
1040      if (cut[iFull-numberRowsAtContinuous]) {
1041        CoinWarmStartBasis::Status status = ws->getArtifStatus(--iCompact);
1042        // If no cut generator being used then we may have basic variables
1043        //if (model->getMaximumCutPasses()&&
1044        //  status == CoinWarmStartBasis::basic)
1045        //printf("cut basic\n");
1046        expanded->setArtifStatus(iFull,status);
1047      } else {
1048        expanded->setArtifStatus(iFull,CoinWarmStartBasis::basic);
1049      }
1050    }
1051#ifdef CBC_CHECK_BASIS
1052    printf("Expanded basis\n");
1053    expanded->print() ;
1054    printf("Diffing against\n") ;
1055    lastws->print() ;
1056#endif   
1057/*
1058  Now that we have two bases in proper positional correspondence, creating
1059  the actual diff is dead easy.
1060*/
1061
1062    CoinWarmStartDiff *basisDiff = expanded->generateDiff(lastws) ;
1063/*
1064  Diff the bound vectors. It's assumed the number of structural variables is
1065  not changing. Assuming that branching objects all involve integer variables,
1066  we should see at least one bound change as a consequence of processing this
1067  subproblem. Different types of branching objects could break this assertion.
1068  Not true at all - we have not applied current branch - JJF.
1069*/
1070    double *boundChanges = new double [2*numberColumns] ;
1071    int *variables = new int [2*numberColumns] ;
1072    int numberChangedBounds=0;
1073    for (i=0;i<numberColumns;i++) {
1074      if (lower[i]!=lastLower[i]) {
1075        variables[numberChangedBounds]=i;
1076        boundChanges[numberChangedBounds++]=lower[i];
1077      }
1078      if (upper[i]!=lastUpper[i]) {
1079        variables[numberChangedBounds]=i|0x80000000;
1080        boundChanges[numberChangedBounds++]=upper[i];
1081      }
1082#ifdef CBC_DEBUG
1083      if (lower[i]!=lastLower[i])
1084        printf("lower on %d changed from %g to %g\n",
1085               i,lastLower[i],lower[i]);
1086      if (upper[i]!=lastUpper[i])
1087        printf("upper on %d changed from %g to %g\n",
1088               i,lastUpper[i],upper[i]);
1089#endif
1090    }
1091#ifdef CBC_DEBUG
1092    printf("%d changed bounds\n",numberChangedBounds) ;
1093#endif
1094    //if (lastNode->branchingObject()->boundBranch())
1095    //assert (numberChangedBounds);
1096/*
1097  Hand the lot over to the CbcPartialNodeInfo constructor, then clean up and
1098  return.
1099*/
1100    if (!strategy)
1101      nodeInfo_ =
1102        new CbcPartialNodeInfo(lastNode->nodeInfo_,this,numberChangedBounds,
1103                               variables,boundChanges,basisDiff) ;
1104    else
1105      nodeInfo_ = strategy->partialNodeInfo(model, lastNode->nodeInfo_,this,numberChangedBounds,
1106                               variables,boundChanges,basisDiff) ;
1107    delete basisDiff ;
1108    delete [] boundChanges;
1109    delete [] variables;
1110    delete expanded ;
1111    delete ws;
1112  }
1113  // Set node number
1114  nodeInfo_->setNodeNumber(model->getNodeCount2());
1115}
1116
1117#endif  // CBC_NEW_CREATEINFO
1118
1119/*
1120  The routine scans through the object list of the model looking for objects
1121  that indicate infeasibility. It tests each object using strong branching
1122  and selects the one with the least objective degradation.  A corresponding
1123  branching object is left attached to lastNode.
1124
1125  If strong branching is disabled, a candidate object is chosen essentially
1126  at random (whatever object ends up in pos'n 0 of the candidate array).
1127
1128  If a branching candidate is found to be monotone, bounds are set to fix the
1129  variable and the routine immediately returns (the caller is expected to
1130  reoptimize).
1131
1132  If a branching candidate is found to result in infeasibility in both
1133  directions, the routine immediately returns an indication of infeasibility.
1134
1135  Returns:  0   both branch directions are feasible
1136           -1   branching variable is monotone
1137           -2   infeasible
1138
1139  Original comments:
1140    Here could go cuts etc etc
1141    For now just fix on objective from strong branching.
1142*/
1143
1144int CbcNode::chooseBranch (CbcModel *model, CbcNode *lastNode,int numberPassesLeft)
1145
1146{ if (lastNode)
1147    depth_ = lastNode->depth_+1;
1148  else
1149    depth_ = 0;
1150  delete branch_;
1151  branch_=NULL;
1152  OsiSolverInterface * solver = model->solver();
1153  double saveObjectiveValue = solver->getObjValue();
1154  double objectiveValue = CoinMax(solver->getObjSense()*saveObjectiveValue,objectiveValue_);
1155  const double * lower = solver->getColLower();
1156  const double * upper = solver->getColUpper();
1157  // See what user thinks
1158  int anyAction=model->problemFeasibility()->feasible(model,0);
1159  if (anyAction) {
1160    // will return -2 if infeasible , 0 if treat as integer
1161    return anyAction-1;
1162  }
1163  double integerTolerance = 
1164    model->getDblParam(CbcModel::CbcIntegerTolerance);
1165  // point to useful information
1166  OsiBranchingInformation usefulInfo = model->usefulInformation();
1167  // and modify
1168  usefulInfo.depth_=depth_;
1169  int i;
1170  bool beforeSolution = model->getSolutionCount()==0;
1171  int numberStrong=model->numberStrong();
1172  // switch off strong if hotstart
1173  if (model->hotstartSolution())
1174    numberStrong=0;
1175  int numberStrongDone=0;
1176  int numberUnfinished=0;
1177  int numberStrongInfeasible=0;
1178  int numberStrongIterations=0;
1179  int saveNumberStrong=numberStrong;
1180  int numberObjects = model->numberObjects();
1181  bool checkFeasibility = numberObjects>model->numberIntegers();
1182  int maximumStrong = CoinMax(CoinMin(model->numberStrong(),numberObjects),1);
1183  int numberColumns = model->getNumCols();
1184  double * saveUpper = new double[numberColumns];
1185  double * saveLower = new double[numberColumns];
1186
1187  // Save solution in case heuristics need good solution later
1188 
1189  double * saveSolution = new double[numberColumns];
1190  memcpy(saveSolution,solver->getColSolution(),numberColumns*sizeof(double));
1191  model->reserveCurrentSolution(saveSolution);
1192  /*
1193    Get a branching decision object. Use the default decision criteria unless
1194    the user has loaded a decision method into the model.
1195  */
1196  CbcBranchDecision *decision = model->branchingMethod();
1197  CbcDynamicPseudoCostBranchingObject * dynamicBranchingObject =
1198    dynamic_cast<CbcDynamicPseudoCostBranchingObject *>(decision);
1199  if (!decision||dynamicBranchingObject)
1200    decision = new CbcBranchDefaultDecision();
1201  decision->initialize(model);
1202  CbcStrongInfo * choice = new CbcStrongInfo[maximumStrong];
1203  for (i=0;i<numberColumns;i++) {
1204    saveLower[i] = lower[i];
1205    saveUpper[i] = upper[i];
1206  }
1207  // May go round twice if strong branching fixes all local candidates
1208  bool finished=false;
1209  double estimatedDegradation=0.0; 
1210  while(!finished) {
1211    finished=true;
1212    // Some objects may compute an estimate of best solution from here
1213    estimatedDegradation=0.0; 
1214    //int numberIntegerInfeasibilities=0; // without odd ones
1215    numberStrongDone=0;
1216    numberUnfinished=0;
1217    numberStrongInfeasible=0;
1218    numberStrongIterations=0;
1219   
1220    // We may go round this loop twice (only if we think we have solution)
1221    for (int iPass=0;iPass<2;iPass++) {
1222     
1223      // compute current state
1224      //int numberObjectInfeasibilities; // just odd ones
1225      //model->feasibleSolution(
1226      //                      numberIntegerInfeasibilities,
1227      //                      numberObjectInfeasibilities);
1228      const double * hotstartSolution = model->hotstartSolution();
1229      const int * hotstartPriorities = model->hotstartPriorities();
1230     
1231      // Some objects may compute an estimate of best solution from here
1232      estimatedDegradation=0.0; 
1233      numberUnsatisfied_ = 0;
1234      // initialize sum of "infeasibilities"
1235      sumInfeasibilities_ = 0.0;
1236      int bestPriority=COIN_INT_MAX;
1237      /*
1238        Scan for branching objects that indicate infeasibility. Choose the best
1239        maximumStrong candidates, using priority as the first criteria, then
1240        integer infeasibility.
1241       
1242        The algorithm is to fill the choice array with a set of good candidates (by
1243        infeasibility) with priority bestPriority.  Finding a candidate with
1244        priority better (less) than bestPriority flushes the choice array. (This
1245        serves as initialization when the first candidate is found.)
1246       
1247        A new candidate is added to choices only if its infeasibility exceeds the
1248        current max infeasibility (mostAway). When a candidate is added, it
1249        replaces the candidate with the smallest infeasibility (tracked by
1250        iSmallest).
1251      */
1252      int iSmallest = 0;
1253      double mostAway = 1.0e-100;
1254      for (i = 0 ; i < maximumStrong ; i++)
1255        choice[i].possibleBranch = NULL ;
1256      numberStrong=0;
1257      bool canDoOneHot=false;
1258      for (i=0;i<numberObjects;i++) {
1259        OsiObject * object = model->modifiableObject(i);
1260        int preferredWay;
1261        double infeasibility = object->infeasibility(&usefulInfo,preferredWay);
1262        int priorityLevel = object->priority();
1263        if (hotstartSolution) {
1264          // we are doing hot start
1265          const CbcSimpleInteger * thisOne = dynamic_cast <const CbcSimpleInteger *> (object);
1266          if (thisOne) {
1267            int iColumn = thisOne->columnNumber();
1268            bool canDoThisHot=true;
1269            double targetValue = hotstartSolution[iColumn];
1270            if (saveUpper[iColumn]>saveLower[iColumn]) {
1271              double value = saveSolution[iColumn];
1272              if (hotstartPriorities)
1273                priorityLevel=hotstartPriorities[iColumn]; 
1274              //double originalLower = thisOne->originalLower();
1275              //double originalUpper = thisOne->originalUpper();
1276              // switch off if not possible
1277              if (targetValue>=saveLower[iColumn]&&targetValue<=saveUpper[iColumn]) {
1278                /* priority outranks rest always if negative
1279                   otherwise can be downgraded if at correct level.
1280                   Infeasibility may be increased to choose 1.0 values first.
1281                   choose one near wanted value
1282                */
1283                if (fabs(value-targetValue)>integerTolerance) {
1284                  infeasibility = 1.0-fabs(value-targetValue);
1285                  if (targetValue==1.0)
1286                    infeasibility += 1.0;
1287                  if (value>targetValue) {
1288                    preferredWay=-1;
1289                  } else {
1290                    preferredWay=1;
1291                  }
1292                  priorityLevel = CoinAbs(priorityLevel);
1293                } else if (priorityLevel<0) {
1294                  priorityLevel = CoinAbs(priorityLevel);
1295                  if (targetValue==saveLower[iColumn]) {
1296                    infeasibility = integerTolerance+1.0e-12;
1297                    preferredWay=-1;
1298                  } else if (targetValue==saveUpper[iColumn]) {
1299                    infeasibility = integerTolerance+1.0e-12;
1300                    preferredWay=1;
1301                  } else {
1302                    // can't
1303                    priorityLevel += 10000000;
1304                    canDoThisHot=false;
1305                  }
1306                } else {
1307                  priorityLevel += 10000000;
1308                  canDoThisHot=false;
1309                }
1310              } else {
1311                // switch off if not possible
1312                canDoThisHot=false;
1313              }
1314              if (canDoThisHot)
1315                canDoOneHot=true;
1316            } else if (targetValue<saveLower[iColumn]||targetValue>saveUpper[iColumn]) {
1317            }
1318          } else {
1319            priorityLevel += 10000000;
1320          }
1321        }
1322        if (infeasibility) {
1323          // Increase estimated degradation to solution
1324          estimatedDegradation += CoinMin(object->upEstimate(),object->downEstimate());
1325          numberUnsatisfied_++;
1326          sumInfeasibilities_ += infeasibility;
1327          // Better priority? Flush choices.
1328          if (priorityLevel<bestPriority) {
1329            int j;
1330            iSmallest=0;
1331            for (j=0;j<maximumStrong;j++) {
1332              choice[j].upMovement=0.0;
1333              delete choice[j].possibleBranch;
1334              choice[j].possibleBranch=NULL;
1335            }
1336            bestPriority = priorityLevel;
1337            mostAway=1.0e-100;
1338            numberStrong=0;
1339          } else if (priorityLevel>bestPriority) {
1340            continue;
1341          }
1342          // Check for suitability based on infeasibility.
1343          if (infeasibility>mostAway) {
1344            //add to list
1345            choice[iSmallest].upMovement=infeasibility;
1346            delete choice[iSmallest].possibleBranch;
1347            CbcSimpleInteger * obj =
1348              dynamic_cast <CbcSimpleInteger *>(object) ;
1349            if (obj) {
1350              choice[iSmallest].possibleBranch=obj->createBranch(solver,&usefulInfo,preferredWay);
1351            } else {
1352              CbcObject * obj =
1353                dynamic_cast <CbcObject *>(object) ;
1354              assert (obj);
1355              choice[iSmallest].possibleBranch=obj->createBranch(preferredWay);
1356            }
1357            numberStrong = CoinMax(numberStrong,iSmallest+1);
1358            // Save which object it was
1359            choice[iSmallest].objectNumber=i;
1360            int j;
1361            iSmallest=-1;
1362            mostAway = 1.0e50;
1363            for (j=0;j<maximumStrong;j++) {
1364              if (choice[j].upMovement<mostAway) {
1365                mostAway=choice[j].upMovement;
1366                iSmallest=j;
1367              }
1368            }
1369          }
1370        }
1371      }
1372      if (!canDoOneHot&&hotstartSolution) {
1373        // switch off as not possible
1374        hotstartSolution=NULL;
1375        model->setHotstartSolution(NULL,NULL);
1376      }
1377      if (numberUnsatisfied_) {
1378        // some infeasibilities - go to next steps
1379        break;
1380      } else if (!iPass) {
1381        // looks like a solution - get paranoid
1382        bool roundAgain=false;
1383        // get basis
1384        CoinWarmStartBasis * ws = dynamic_cast<CoinWarmStartBasis*>(solver->getWarmStart());
1385        if (!ws)
1386          break;
1387        for (i=0;i<numberColumns;i++) {
1388          double value = saveSolution[i];
1389          if (value<lower[i]) {
1390            saveSolution[i]=lower[i];
1391            roundAgain=true;
1392            ws->setStructStatus(i,CoinWarmStartBasis::atLowerBound);
1393          } else if (value>upper[i]) {
1394            saveSolution[i]=upper[i];
1395            roundAgain=true;
1396            ws->setStructStatus(i,CoinWarmStartBasis::atUpperBound);
1397          } 
1398        }
1399        if (roundAgain&&saveNumberStrong) {
1400          // restore basis
1401          solver->setWarmStart(ws);
1402          delete ws;
1403          solver->resolve();
1404          memcpy(saveSolution,solver->getColSolution(),numberColumns*sizeof(double));
1405          model->reserveCurrentSolution(saveSolution);
1406          if (!solver->isProvenOptimal()) {
1407            // infeasible
1408            anyAction=-2;
1409            break;
1410          }
1411        } else {
1412          delete ws;
1413          break;
1414        }
1415      }
1416    }
1417    /* Some solvers can do the strong branching calculations faster if
1418       they do them all at once.  At present only Clp does for ordinary
1419       integers but I think this coding would be easy to modify
1420    */
1421    bool allNormal=true; // to say if we can do fast strong branching
1422    // Say which one will be best
1423    int bestChoice=0;
1424    double worstInfeasibility=0.0;
1425    for (i=0;i<numberStrong;i++) {
1426      choice[i].numIntInfeasUp = numberUnsatisfied_;
1427      choice[i].numIntInfeasDown = numberUnsatisfied_;
1428      choice[i].fix=0; // say not fixed
1429      if (!dynamic_cast <const CbcSimpleInteger *> (model->object(choice[i].objectNumber)))
1430        allNormal=false; // Something odd so lets skip clever fast branching
1431      if ( !model->object(choice[i].objectNumber)->boundBranch())
1432        numberStrong=0; // switch off
1433      if ( choice[i].possibleBranch->numberBranches()>2)
1434        numberStrong=0; // switch off
1435      // Do best choice in case switched off
1436      if (choice[i].upMovement>worstInfeasibility) {
1437        worstInfeasibility=choice[i].upMovement;
1438        bestChoice=i;
1439      }
1440    }
1441    // If we have hit max time don't do strong branching
1442    bool hitMaxTime = ( CoinCpuTime()-model->getDblParam(CbcModel::CbcStartSeconds) > 
1443                        model->getDblParam(CbcModel::CbcMaximumSeconds));
1444    // also give up if we are looping round too much
1445    if (hitMaxTime||numberPassesLeft<=0)
1446      numberStrong=0;
1447    /*
1448      Is strong branching enabled? If so, set up and do it. Otherwise, we'll
1449      fall through to simple branching.
1450     
1451      Setup for strong branching involves saving the current basis (for restoration
1452      afterwards) and setting up for hot starts.
1453    */
1454    if (numberStrong&&saveNumberStrong) {
1455     
1456      bool solveAll=false; // set true to say look at all even if some fixed (experiment)
1457      solveAll=true;
1458      // worth trying if too many times
1459      // Save basis
1460      CoinWarmStart * ws = solver->getWarmStart();
1461      // save limit
1462      int saveLimit;
1463      solver->getIntParam(OsiMaxNumIterationHotStart,saveLimit);
1464      if (beforeSolution&&saveLimit<100)
1465        solver->setIntParam(OsiMaxNumIterationHotStart,100); // go to end
1466#     ifdef COIN_HAS_CLP     
1467      /* If we are doing all strong branching in one go then we create new arrays
1468         to store information.  If clp NULL then doing old way.
1469         Going down -
1470         outputSolution[2*i] is final solution.
1471         outputStuff[2*i] is status (0 - finished, 1 infeas, other unknown
1472         outputStuff[2*i+numberStrong] is number iterations
1473         On entry newUpper[i] is new upper bound, on exit obj change
1474         Going up -
1475         outputSolution[2*i+1] is final solution.
1476         outputStuff[2*i+1] is status (0 - finished, 1 infeas, other unknown
1477         outputStuff[2*i+1+numberStrong] is number iterations
1478       On entry newLower[i] is new lower bound, on exit obj change
1479      */
1480      OsiClpSolverInterface * osiclp = dynamic_cast< OsiClpSolverInterface*> (solver);
1481      ClpSimplex * clp=NULL;
1482      double * newLower = NULL;
1483      double * newUpper = NULL;
1484      double ** outputSolution=NULL;
1485      int * outputStuff=NULL;
1486      // Go back to normal way if user wants it
1487      if (osiclp&&(osiclp->specialOptions()&16)!=0&&osiclp->specialOptions()>0)
1488        allNormal=false;
1489      if (osiclp&&!allNormal) {
1490        // say do fast
1491        int easy=1;
1492        osiclp->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,&easy) ;
1493      }
1494      if (osiclp&& allNormal) {
1495        clp = osiclp->getModelPtr();
1496        // Clp - do a different way
1497        newLower = new double[numberStrong];
1498        newUpper = new double[numberStrong];
1499        outputSolution = new double * [2*numberStrong];
1500        outputStuff = new int [4*numberStrong];
1501        int * which = new int[numberStrong];
1502        int startFinishOptions;
1503        int specialOptions = osiclp->specialOptions();
1504        int clpOptions = clp->specialOptions();
1505        int returnCode=0;
1506#define CRUNCH
1507#ifdef CRUNCH
1508        // Crunch down problem
1509        int numberRows = clp->numberRows();
1510        // Use dual region
1511        double * rhs = clp->dualRowSolution();
1512        int * whichRow = new int[3*numberRows];
1513        int * whichColumn = new int[2*numberColumns];
1514        int nBound;
1515        ClpSimplex * small = ((ClpSimplexOther *) clp)->crunch(rhs,whichRow,whichColumn,nBound,true);
1516        if (!small) {
1517          anyAction=-2;
1518          //printf("XXXX Inf by inspection\n");
1519          delete [] whichColumn;
1520          whichColumn=NULL;
1521          delete [] whichRow;
1522          whichRow=NULL;
1523          break;
1524        } else {
1525          clp = small;
1526        }
1527#else
1528        int saveLogLevel = clp->logLevel();
1529        int saveMaxIts = clp->maximumIterations();
1530#endif
1531        clp->setLogLevel(0);
1532        if((specialOptions&1)==0) {
1533          startFinishOptions=0;
1534          clp->setSpecialOptions(clpOptions|(64|1024));
1535        } else {
1536          startFinishOptions=1+2+4;
1537          //startFinishOptions=1+4; // for moment re-factorize
1538          if((specialOptions&4)==0) 
1539            clp->setSpecialOptions(clpOptions|(64|128|512|1024|4096));
1540          else
1541            clp->setSpecialOptions(clpOptions|(64|128|512|1024|2048|4096));
1542        }
1543        // User may want to clean up before strong branching
1544        if ((clp->specialOptions()&32)!=0) {
1545          clp->primal(1);
1546          if (clp->numberIterations())
1547            model->messageHandler()->message(CBC_ITERATE_STRONG,*model->messagesPointer())
1548              << clp->numberIterations()
1549              <<CoinMessageEol;
1550        }
1551        clp->setMaximumIterations(saveLimit);
1552#ifdef CRUNCH
1553        int * backColumn = whichColumn+numberColumns;
1554#endif
1555        for (i=0;i<numberStrong;i++) {
1556          int iObject = choice[i].objectNumber;
1557          const OsiObject * object = model->object(iObject);
1558          const CbcSimpleInteger * simple = dynamic_cast <const CbcSimpleInteger *> (object);
1559          int iSequence = simple->columnNumber();
1560          newLower[i]= ceil(saveSolution[iSequence]);
1561          newUpper[i]= floor(saveSolution[iSequence]);
1562#ifdef CRUNCH
1563          iSequence = backColumn[iSequence];
1564          assert (iSequence>=0);
1565#endif
1566          which[i]=iSequence;
1567          outputSolution[2*i]= new double [numberColumns];
1568          outputSolution[2*i+1]= new double [numberColumns];
1569        }
1570        //clp->writeMps("bad");
1571        returnCode=clp->strongBranching(numberStrong,which,
1572                                            newLower, newUpper,outputSolution,
1573                                            outputStuff,outputStuff+2*numberStrong,!solveAll,false,
1574                                            startFinishOptions);
1575#ifndef CRUNCH
1576        clp->setSpecialOptions(clpOptions); // restore
1577        clp->setMaximumIterations(saveMaxIts);
1578        clp->setLogLevel(saveLogLevel);
1579#endif
1580        if (returnCode==-2) {
1581          // bad factorization!!!
1582          // Doing normal way
1583          // Mark hot start
1584          solver->markHotStart();
1585          clp = NULL;
1586        } else {
1587#ifdef CRUNCH
1588          // extract solution
1589          //bool checkSol=true;
1590          for (i=0;i<numberStrong;i++) {
1591            int iObject = choice[i].objectNumber;
1592            const OsiObject * object = model->object(iObject);
1593            const CbcSimpleInteger * simple = dynamic_cast <const CbcSimpleInteger *> (object);
1594            int iSequence = simple->columnNumber();
1595            which[i]=iSequence;
1596            double * sol = outputSolution[2*i];
1597            double * sol2 = outputSolution[2*i+1];
1598            //bool x=true;
1599            //bool x2=true;
1600            for (int iColumn=numberColumns-1;iColumn>=0;iColumn--) {
1601              int jColumn = backColumn[iColumn];
1602              if (jColumn>=0) {
1603                sol[iColumn]=sol[jColumn];
1604                sol2[iColumn]=sol2[jColumn];
1605              } else {
1606                sol[iColumn]=saveSolution[iColumn];
1607                sol2[iColumn]=saveSolution[iColumn];
1608              }
1609            }
1610          }
1611#endif
1612        }
1613#ifdef CRUNCH
1614        delete [] whichColumn;
1615        delete [] whichRow;
1616        delete small;
1617#endif
1618        delete [] which;
1619      } else {
1620        // Doing normal way
1621        // Mark hot start
1622        solver->markHotStart();
1623      }
1624#     else      /* COIN_HAS_CLP */
1625
1626      OsiSolverInterface *clp = NULL ;
1627      double **outputSolution = NULL ;
1628      int *outputStuff = NULL ;
1629      double * newLower = NULL ;
1630      double * newUpper = NULL ;
1631
1632      solver->markHotStart();
1633
1634#     endif     /* COIN_HAS_CLP */
1635      /*
1636        Open a loop to do the strong branching LPs. For each candidate variable,
1637        solve an LP with the variable forced down, then up. If a direction turns
1638        out to be infeasible or monotonic (i.e., over the dual objective cutoff),
1639        force the objective change to be big (1.0e100). If we determine the problem
1640        is infeasible, or find a monotone variable, escape the loop.
1641       
1642        TODO: The `restore bounds' part might be better encapsulated as an
1643        unbranch() method. Branching objects more exotic than simple integers
1644        or cliques might not restrict themselves to variable bounds.
1645
1646        TODO: Virtuous solvers invalidate the current solution (or give bogus
1647        results :-) when the bounds are changed out from under them. So we
1648        need to do all the work associated with finding a new solution before
1649        restoring the bounds.
1650      */
1651      for (i = 0 ; i < numberStrong ; i++)
1652        { double objectiveChange ;
1653        double newObjectiveValue=1.0e100;
1654        // status is 0 finished, 1 infeasible and other
1655        int iStatus;
1656        /*
1657          Try the down direction first. (Specify the initial branching alternative as
1658          down with a call to way(-1). Each subsequent call to branch() performs the
1659          specified branch and advances the branch object state to the next branch
1660          alternative.)
1661        */
1662        if (!clp) {
1663          choice[i].possibleBranch->way(-1) ;
1664          choice[i].possibleBranch->branch() ;
1665          bool feasible=true;
1666          if (checkFeasibility) {
1667            // check branching did not make infeasible
1668            int iColumn;
1669            int numberColumns = solver->getNumCols();
1670            const double * columnLower = solver->getColLower();
1671            const double * columnUpper = solver->getColUpper();
1672            for (iColumn= 0;iColumn<numberColumns;iColumn++) {
1673              if (columnLower[iColumn]>columnUpper[iColumn]+1.0e-5)
1674                feasible=false;
1675            }
1676          }
1677          if (feasible) {
1678            solver->solveFromHotStart() ;
1679            numberStrongDone++;
1680            numberStrongIterations += solver->getIterationCount();
1681            /*
1682              We now have an estimate of objective degradation that we can use for strong
1683              branching. If we're over the cutoff, the variable is monotone up.
1684              If we actually made it to optimality, check for a solution, and if we have
1685              a good one, call setBestSolution to process it. Note that this may reduce the
1686              cutoff, so we check again to see if we can declare this variable monotone.
1687            */
1688            if (solver->isProvenOptimal())
1689              iStatus=0; // optimal
1690            else if (solver->isIterationLimitReached()
1691                     &&!solver->isDualObjectiveLimitReached())
1692              iStatus=2; // unknown
1693            else
1694              iStatus=1; // infeasible
1695            newObjectiveValue = solver->getObjSense()*solver->getObjValue();
1696            choice[i].numItersDown = solver->getIterationCount();
1697          } else {
1698            iStatus=1; // infeasible
1699            newObjectiveValue = 1.0e100;
1700            choice[i].numItersDown = 0;
1701          }
1702        } else {
1703          iStatus = outputStuff[2*i];
1704          choice[i].numItersDown = outputStuff[2*numberStrong+2*i];
1705          numberStrongDone++;
1706          numberStrongIterations += choice[i].numItersDown;
1707          newObjectiveValue = objectiveValue+newUpper[i];
1708          solver->setColSolution(outputSolution[2*i]);
1709        }
1710        objectiveChange = CoinMax(newObjectiveValue  - objectiveValue_,0.0);
1711        if (!iStatus) {
1712          choice[i].finishedDown = true ;
1713          if (newObjectiveValue>=model->getCutoff()) {
1714            objectiveChange = 1.0e100; // say infeasible
1715            numberStrongInfeasible++;
1716          } else {
1717            // See if integer solution
1718            if (model->feasibleSolution(choice[i].numIntInfeasDown,
1719                                        choice[i].numObjInfeasDown)
1720                &&model->problemFeasibility()->feasible(model,-1)>=0) {
1721              model->setBestSolution(CBC_STRONGSOL,
1722                                     newObjectiveValue,
1723                                     solver->getColSolution()) ;
1724              // only needed for odd solvers
1725              newObjectiveValue = solver->getObjSense()*solver->getObjValue();
1726              objectiveChange = CoinMax(newObjectiveValue-objectiveValue_,0.0) ;
1727              model->setLastHeuristic(NULL);
1728              model->incrementUsed(solver->getColSolution());
1729              if (newObjectiveValue >= model->getCutoff()) {    //  *new* cutoff
1730                objectiveChange = 1.0e100 ;
1731                numberStrongInfeasible++;
1732              }
1733            }
1734          }
1735        } else if (iStatus==1) {
1736          objectiveChange = 1.0e100 ;
1737          numberStrongInfeasible++;
1738        } else {
1739          // Can't say much as we did not finish
1740          choice[i].finishedDown = false ;
1741          numberUnfinished++;
1742        }
1743        choice[i].downMovement = objectiveChange ;
1744       
1745        // restore bounds
1746        if (!clp)
1747          { for (int j=0;j<numberColumns;j++) {
1748            if (saveLower[j] != lower[j])
1749              solver->setColLower(j,saveLower[j]);
1750            if (saveUpper[j] != upper[j])
1751              solver->setColUpper(j,saveUpper[j]);
1752          }
1753          }
1754        //printf("Down on %d, status is %d, obj %g its %d cost %g finished %d inf %d infobj %d\n",
1755        //     choice[i].objectNumber,iStatus,newObjectiveValue,choice[i].numItersDown,
1756        //     choice[i].downMovement,choice[i].finishedDown,choice[i].numIntInfeasDown,
1757        //     choice[i].numObjInfeasDown);
1758       
1759        // repeat the whole exercise, forcing the variable up
1760        if (!clp) {
1761          bool feasible=true;
1762          // If odd branching then maybe just one possibility
1763          if(choice[i].possibleBranch->numberBranchesLeft()>0) {
1764            choice[i].possibleBranch->branch();
1765            if (checkFeasibility) {
1766              // check branching did not make infeasible
1767              int iColumn;
1768              int numberColumns = solver->getNumCols();
1769              const double * columnLower = solver->getColLower();
1770              const double * columnUpper = solver->getColUpper();
1771              for (iColumn= 0;iColumn<numberColumns;iColumn++) {
1772                if (columnLower[iColumn]>columnUpper[iColumn]+1.0e-5)
1773                  feasible=false;
1774              }
1775            }
1776          } else {
1777            // second branch infeasible
1778            feasible=false;
1779          }
1780          if (feasible) {
1781            solver->solveFromHotStart() ;
1782            numberStrongDone++;
1783            numberStrongIterations += solver->getIterationCount();
1784            /*
1785              We now have an estimate of objective degradation that we can use for strong
1786              branching. If we're over the cutoff, the variable is monotone up.
1787              If we actually made it to optimality, check for a solution, and if we have
1788              a good one, call setBestSolution to process it. Note that this may reduce the
1789              cutoff, so we check again to see if we can declare this variable monotone.
1790            */
1791            if (solver->isProvenOptimal())
1792              iStatus=0; // optimal
1793            else if (solver->isIterationLimitReached()
1794                     &&!solver->isDualObjectiveLimitReached())
1795              iStatus=2; // unknown
1796            else
1797              iStatus=1; // infeasible
1798            newObjectiveValue = solver->getObjSense()*solver->getObjValue();
1799            choice[i].numItersUp = solver->getIterationCount();
1800          } else {
1801            iStatus=1; // infeasible
1802            newObjectiveValue = 1.0e100;
1803            choice[i].numItersDown = 0;
1804          }
1805        } else {
1806          iStatus = outputStuff[2*i+1];
1807          choice[i].numItersUp = outputStuff[2*numberStrong+2*i+1];
1808          numberStrongDone++;
1809          numberStrongIterations += choice[i].numItersUp;
1810          newObjectiveValue = objectiveValue+newLower[i];
1811          solver->setColSolution(outputSolution[2*i+1]);
1812        }
1813        objectiveChange = CoinMax(newObjectiveValue  - objectiveValue_,0.0);
1814        if (!iStatus) {
1815          choice[i].finishedUp = true ;
1816          if (newObjectiveValue>=model->getCutoff()) {
1817            objectiveChange = 1.0e100; // say infeasible
1818            numberStrongInfeasible++;
1819          } else {
1820            // See if integer solution
1821            if (model->feasibleSolution(choice[i].numIntInfeasUp,
1822                                        choice[i].numObjInfeasUp)
1823                &&model->problemFeasibility()->feasible(model,-1)>=0) {
1824              model->setBestSolution(CBC_STRONGSOL,
1825                                     newObjectiveValue,
1826                                     solver->getColSolution()) ;
1827              // only needed for odd solvers
1828              newObjectiveValue = solver->getObjSense()*solver->getObjValue();
1829              objectiveChange = CoinMax(newObjectiveValue-objectiveValue_,0.0) ;
1830              model->setLastHeuristic(NULL);
1831              model->incrementUsed(solver->getColSolution());
1832              if (newObjectiveValue >= model->getCutoff()) {    //  *new* cutoff
1833                objectiveChange = 1.0e100 ;
1834                numberStrongInfeasible++;
1835              }
1836            }
1837          }
1838        } else if (iStatus==1) {
1839          objectiveChange = 1.0e100 ;
1840          numberStrongInfeasible++;
1841        } else {
1842          // Can't say much as we did not finish
1843          choice[i].finishedUp = false ;
1844          numberUnfinished++;
1845        }
1846        choice[i].upMovement = objectiveChange ;
1847       
1848        // restore bounds
1849        if (!clp)
1850          { for (int j=0;j<numberColumns;j++) {
1851            if (saveLower[j] != lower[j])
1852              solver->setColLower(j,saveLower[j]);
1853            if (saveUpper[j] != upper[j])
1854              solver->setColUpper(j,saveUpper[j]);
1855          }
1856          }
1857       
1858        //printf("Up on %d, status is %d, obj %g its %d cost %g finished %d inf %d infobj %d\n",
1859        //     choice[i].objectNumber,iStatus,newObjectiveValue,choice[i].numItersUp,
1860        //     choice[i].upMovement,choice[i].finishedUp,choice[i].numIntInfeasUp,
1861        //     choice[i].numObjInfeasUp);
1862       
1863        /*
1864          End of evaluation for this candidate variable. Possibilities are:
1865          * Both sides below cutoff; this variable is a candidate for branching.
1866          * Both sides infeasible or above the objective cutoff: no further action
1867          here. Break from the evaluation loop and assume the node will be purged
1868          by the caller.
1869          * One side below cutoff: Install the branch (i.e., fix the variable). Break
1870          from the evaluation loop and assume the node will be reoptimised by the
1871          caller.
1872        */
1873        // reset
1874        choice[i].possibleBranch->resetNumberBranchesLeft();
1875        if (choice[i].upMovement<1.0e100) {
1876          if(choice[i].downMovement<1.0e100) {
1877            // feasible - no action
1878          } else {
1879            // up feasible, down infeasible
1880            anyAction=-1;
1881            //printf("Down infeasible for choice %d sequence %d\n",i,
1882            // model->object(choice[i].objectNumber)->columnNumber());
1883            if (!solveAll) {
1884              choice[i].possibleBranch->way(1);
1885              choice[i].possibleBranch->branch();
1886              break;
1887            } else {
1888              choice[i].fix=1;
1889            }
1890          }
1891        } else {
1892          if(choice[i].downMovement<1.0e100) {
1893            // down feasible, up infeasible
1894            anyAction=-1;
1895            //printf("Up infeasible for choice %d sequence %d\n",i,
1896            // model->object(choice[i].objectNumber)->columnNumber());
1897            if (!solveAll) {
1898              choice[i].possibleBranch->way(-1);
1899              choice[i].possibleBranch->branch();
1900              break;
1901            } else {
1902              choice[i].fix=-1;
1903            }
1904          } else {
1905            // neither side feasible
1906            anyAction=-2;
1907            //printf("Both infeasible for choice %d sequence %d\n",i,
1908            // model->object(choice[i].objectNumber)->columnNumber());
1909            break;
1910          }
1911        }
1912        bool hitMaxTime = ( CoinCpuTime()-model->getDblParam(CbcModel::CbcStartSeconds) > 
1913                            model->getDblParam(CbcModel::CbcMaximumSeconds));
1914        if (hitMaxTime) {
1915          numberStrong=i+1;
1916          break;
1917        }
1918        }
1919      if (!clp) {
1920        // Delete the snapshot
1921        solver->unmarkHotStart();
1922      } else {
1923        delete [] newLower;
1924        delete [] newUpper;
1925        delete [] outputStuff;
1926        int i;
1927        for (i=0;i<2*numberStrong;i++)
1928          delete [] outputSolution[i];
1929        delete [] outputSolution;
1930      }
1931      solver->setIntParam(OsiMaxNumIterationHotStart,saveLimit);
1932      // restore basis
1933      solver->setWarmStart(ws);
1934      // Unless infeasible we will carry on
1935      // But we could fix anyway
1936      if (anyAction==-1&&solveAll) {
1937        // apply and take off
1938        for (i = 0 ; i < numberStrong ; i++) {
1939          if (choice[i].fix) {
1940            choice[i].possibleBranch->way(choice[i].fix) ;
1941            choice[i].possibleBranch->branch() ;
1942          }
1943        }
1944        bool feasible=true;
1945        if (checkFeasibility) {
1946          // check branching did not make infeasible
1947          int iColumn;
1948          int numberColumns = solver->getNumCols();
1949          const double * columnLower = solver->getColLower();
1950          const double * columnUpper = solver->getColUpper();
1951          for (iColumn= 0;iColumn<numberColumns;iColumn++) {
1952            if (columnLower[iColumn]>columnUpper[iColumn]+1.0e-5)
1953              feasible=false;
1954          }
1955        }
1956        if (feasible) {
1957          // can do quick optimality check
1958          int easy=2;
1959          solver->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,&easy) ;
1960          solver->resolve() ;
1961          solver->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,NULL) ;
1962          feasible = solver->isProvenOptimal();
1963        }
1964        if (feasible) {
1965          memcpy(saveSolution,solver->getColSolution(),numberColumns*sizeof(double));
1966          model->reserveCurrentSolution(saveSolution);
1967          memcpy(saveLower,solver->getColLower(),numberColumns*sizeof(double));
1968          memcpy(saveUpper,solver->getColUpper(),numberColumns*sizeof(double));
1969          // Clean up all candidates whih are fixed
1970          int numberLeft=0;
1971          for (i = 0 ; i < numberStrong ; i++) {
1972            CbcStrongInfo thisChoice = choice[i];
1973            choice[i].possibleBranch=NULL;
1974            const OsiObject * object = model->object(thisChoice.objectNumber);
1975            int preferredWay;
1976            double infeasibility = object->infeasibility(&usefulInfo,preferredWay);
1977            if (!infeasibility) {
1978              // take out
1979              delete thisChoice.possibleBranch;
1980            } else {
1981              choice[numberLeft++]=thisChoice;
1982            }
1983          }
1984          numberStrong=numberLeft;
1985          for (;i<maximumStrong;i++) {
1986            delete choice[i].possibleBranch;
1987            choice[i].possibleBranch=NULL;
1988          }
1989          // If all fixed then round again
1990          if (!numberLeft) {
1991            finished=false;
1992            numberStrong=0;
1993            saveNumberStrong=0;
1994            maximumStrong=1;
1995          } else {
1996            anyAction=0;
1997          }
1998          // If these two uncommented then different action
1999          anyAction=-1;
2000          finished=true;
2001          //printf("some fixed but continuing %d left\n",numberLeft);
2002        } else {
2003          anyAction=-2; // say infeasible
2004        }
2005      }
2006      delete ws;
2007      int numberNodes = model->getNodeCount();
2008      // update number of strong iterations etc
2009      model->incrementStrongInfo(numberStrongDone,numberStrongIterations,
2010                                 anyAction==-2 ? 0:numberStrongInfeasible,anyAction==-2);
2011     
2012      /*
2013        anyAction >= 0 indicates that strong branching didn't produce any monotone
2014        variables. Sift through the candidates for the best one.
2015       
2016        QUERY: Setting numberNodes looks to be a distributed noop. numberNodes is
2017        local to this code block. Perhaps should be numberNodes_ from model?
2018        Unclear what this calculation is doing.
2019      */
2020      if (anyAction>=0) {
2021       
2022        // get average cost per iteration and assume stopped ones
2023        // would stop after 50% more iterations at average cost??? !!! ???
2024        double averageCostPerIteration=0.0;
2025        double totalNumberIterations=1.0;
2026        int smallestNumberInfeasibilities=COIN_INT_MAX;
2027        for (i=0;i<numberStrong;i++) {
2028          totalNumberIterations += choice[i].numItersDown +
2029            choice[i].numItersUp ;
2030          averageCostPerIteration += choice[i].downMovement +
2031            choice[i].upMovement;
2032          smallestNumberInfeasibilities= 
2033            CoinMin(CoinMin(choice[i].numIntInfeasDown ,
2034                            choice[i].numIntInfeasUp ),
2035                    smallestNumberInfeasibilities);
2036        }
2037        //if (smallestNumberInfeasibilities>=numberIntegerInfeasibilities)
2038        //numberNodes=1000000; // switch off search for better solution
2039        numberNodes=1000000; // switch off anyway
2040        averageCostPerIteration /= totalNumberIterations;
2041        // all feasible - choose best bet
2042       
2043        // New method does all at once so it can be more sophisticated
2044        // in deciding how to balance actions.
2045        // But it does need arrays
2046        double * changeUp = new double [numberStrong];
2047        int * numberInfeasibilitiesUp = new int [numberStrong];
2048        double * changeDown = new double [numberStrong];
2049        int * numberInfeasibilitiesDown = new int [numberStrong];
2050        CbcBranchingObject ** objects = new CbcBranchingObject * [ numberStrong];
2051        for (i = 0 ; i < numberStrong ; i++) {
2052          int iColumn = choice[i].possibleBranch->variable() ;
2053          model->messageHandler()->message(CBC_STRONG,*model->messagesPointer())
2054            << i << iColumn
2055            <<choice[i].downMovement<<choice[i].numIntInfeasDown
2056            <<choice[i].upMovement<<choice[i].numIntInfeasUp
2057            <<choice[i].possibleBranch->value()
2058            <<CoinMessageEol;
2059          changeUp[i]=choice[i].upMovement;
2060          numberInfeasibilitiesUp[i] = choice[i].numIntInfeasUp;
2061          changeDown[i]=choice[i].downMovement;
2062          numberInfeasibilitiesDown[i] = choice[i].numIntInfeasDown;
2063          objects[i] = choice[i].possibleBranch;
2064        }
2065        int whichObject = decision->bestBranch(objects,numberStrong,numberUnsatisfied_,
2066                                               changeUp,numberInfeasibilitiesUp,
2067                                               changeDown,numberInfeasibilitiesDown,
2068                                               objectiveValue_);
2069        // move branching object and make sure it will not be deleted
2070        if (whichObject>=0) {
2071          branch_ = objects[whichObject];
2072          if (model->messageHandler()->logLevel()>3) 
2073            printf("Choosing column %d\n",choice[whichObject].possibleBranch->variable()) ;
2074          choice[whichObject].possibleBranch=NULL;
2075        }
2076        delete [] changeUp;
2077        delete [] numberInfeasibilitiesUp;
2078        delete [] changeDown;
2079        delete [] numberInfeasibilitiesDown;
2080        delete [] objects;
2081      }
2082#     ifdef COIN_HAS_CLP
2083      if (osiclp&&!allNormal) {
2084        // back to normal
2085        osiclp->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,NULL) ;
2086      }
2087#     endif 
2088    }
2089    /*
2090      Simple branching. Probably just one, but we may have got here
2091      because of an odd branch e.g. a cut
2092    */
2093    else {
2094      // not strong
2095      // C) create branching object
2096      branch_ = choice[bestChoice].possibleBranch;
2097      choice[bestChoice].possibleBranch=NULL;
2098    }
2099  }
2100  // Set guessed solution value
2101  guessedObjectiveValue_ = objectiveValue_+estimatedDegradation;
2102/*
2103  Cleanup, then we're outta here.
2104*/
2105  if (!model->branchingMethod()||dynamicBranchingObject)
2106    delete decision;
2107   
2108  for (i=0;i<maximumStrong;i++)
2109    delete choice[i].possibleBranch;
2110  delete [] choice;
2111  delete [] saveLower;
2112  delete [] saveUpper;
2113 
2114  // restore solution
2115  solver->setColSolution(saveSolution);
2116  delete [] saveSolution;
2117  return anyAction;
2118}
2119
2120/*
2121  Version for dynamic pseudo costs.
2122
2123  **** For now just return if anything odd
2124  later allow even if odd
2125
2126  The routine scans through the object list of the model looking for objects
2127  that indicate infeasibility. It tests each object using strong branching
2128  and selects the one with the least objective degradation.  A corresponding
2129  branching object is left attached to lastNode.
2130  This version gives preference in evaluation to variables which
2131  have not been evaluated many times.  It also uses numberStrong
2132  to say give up if last few tries have not changed incumbent.
2133  See Achterberg, Koch and Martin.
2134
2135  If strong branching is disabled, a candidate object is chosen essentially
2136  at random (whatever object ends up in pos'n 0 of the candidate array).
2137
2138  If a branching candidate is found to be monotone, bounds are set to fix the
2139  variable and the routine immediately returns (the caller is expected to
2140  reoptimize).
2141
2142  If a branching candidate is found to result in infeasibility in both
2143  directions, the routine immediately returns an indication of infeasibility.
2144
2145  Returns:  0   both branch directions are feasible
2146           -1   branching variable is monotone
2147           -2   infeasible
2148           -3   Use another method
2149
2150           For now just fix on objective from strong branching.
2151*/
2152
2153int CbcNode::chooseDynamicBranch (CbcModel *model, CbcNode *lastNode,
2154                                  OsiSolverBranch * & branches,int numberPassesLeft)
2155
2156{ if (lastNode)
2157    depth_ = lastNode->depth_+1;
2158  else
2159    depth_ = 0;
2160  delete branch_;
2161  branch_=NULL;
2162  OsiSolverInterface * solver = model->solver();
2163  // get information on solver type
2164  const OsiAuxInfo * auxInfo = solver->getAuxiliaryInfo();
2165  const OsiBabSolver * auxiliaryInfo = dynamic_cast<const OsiBabSolver *> (auxInfo);
2166  if (!auxiliaryInfo) {
2167    // use one from CbcModel
2168    auxiliaryInfo = model->solverCharacteristics();
2169  }
2170  // point to useful information
2171  OsiBranchingInformation usefulInfo = model->usefulInformation();
2172  // and modify
2173  usefulInfo.depth_=depth_;
2174  assert (auxiliaryInfo);
2175  //assert(objectiveValue_ == solver->getObjSense()*solver->getObjValue());
2176  double cutoff =model->getCutoff();
2177  double distanceToCutoff=cutoff-objectiveValue_;
2178  const double * lower = solver->getColLower();
2179  const double * upper = solver->getColUpper();
2180  // See what user thinks
2181  int anyAction=model->problemFeasibility()->feasible(model,0);
2182  if (anyAction) {
2183    // will return -2 if infeasible , 0 if treat as integer
2184    return anyAction-1;
2185  }
2186  int i;
2187  int saveStateOfSearch = model->stateOfSearch();
2188  int numberStrong=model->numberStrong();
2189  if (!auxiliaryInfo->warmStart())
2190    numberStrong=0;
2191  // But make more likely to get out after some times
2192  int changeStrategy=numberStrong;
2193  double changeFactor=1.0;
2194  // Use minimum of this and one stored in objects
2195  //int numberBeforeTrust = model->numberBeforeTrust();
2196  int numberObjects = model->numberObjects();
2197  bool checkFeasibility = numberObjects>model->numberIntegers();
2198  // For now return if not simple
2199  if (checkFeasibility)
2200    return -3;
2201  // Return if doing hot start (in BAB sense)
2202  if (model->hotstartSolution()) 
2203    return -3;
2204#define RANGING
2205#ifdef RANGING
2206  // Pass number
2207  int kPass=0;
2208  int numberRows = solver->getNumRows();
2209#endif
2210  int numberColumns = model->getNumCols();
2211  double * saveUpper = new double[numberColumns];
2212  double * saveLower = new double[numberColumns];
2213
2214  // Save solution in case heuristics need good solution later
2215 
2216  double * saveSolution = new double[numberColumns];
2217  memcpy(saveSolution,solver->getColSolution(),numberColumns*sizeof(double));
2218  model->reserveCurrentSolution(saveSolution);
2219  /*
2220    Get a branching decision object. Use the default dynamic decision criteria unless
2221    the user has loaded a decision method into the model.
2222  */
2223  CbcBranchDecision *decision = model->branchingMethod();
2224  if (!decision)
2225    decision = new CbcBranchDynamicDecision();
2226  int numberMini=0;
2227  int xPen=0;
2228  int xMark=0;
2229  for (i=0;i<numberColumns;i++) {
2230    saveLower[i] = lower[i];
2231    saveUpper[i] = upper[i];
2232  }
2233  // Get arrays to sort
2234  double * sort = new double[numberObjects];
2235  int * whichObject = new int[numberObjects];
2236  int * objectMark = new int[2*numberObjects+1];
2237  // Arrays with movements
2238  double * upEstimate = new double[numberObjects];
2239  double * downEstimate = new double[numberObjects];
2240  CbcStrongInfo * fixObject = new CbcStrongInfo[numberObjects];
2241  double estimatedDegradation=0.0; 
2242  int numberNodes=model->getNodeCount();
2243  int saveLogLevel = model->logLevel();
2244  if ((numberNodes%500)==0&&false) {
2245    model->setLogLevel(6);
2246    // Get average up and down costs
2247    double averageUp=0.0;
2248    double averageDown=0.0;
2249    int numberUp=0;
2250    int numberDown=0;
2251    int i;
2252    for ( i=0;i<numberObjects;i++) {
2253      OsiObject * object = model->modifiableObject(i);
2254      CbcSimpleIntegerDynamicPseudoCost * dynamicObject =
2255        dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(object) ;
2256      assert(dynamicObject);
2257      int  numberUp2=0;
2258      int numberDown2=0;
2259      double up=0.0;
2260      double down=0.0;
2261      if (dynamicObject->numberTimesUp()) {
2262        numberUp++;
2263        averageUp += dynamicObject->upDynamicPseudoCost();
2264        numberUp2 += dynamicObject->numberTimesUp();
2265        up = dynamicObject->upDynamicPseudoCost();
2266      }
2267      if (dynamicObject->numberTimesDown()) {
2268        numberDown++;
2269        averageDown += dynamicObject->downDynamicPseudoCost();
2270        numberDown2 += dynamicObject->numberTimesDown();
2271        down = dynamicObject->downDynamicPseudoCost();
2272      }
2273      if (numberUp2||numberDown2)
2274        printf("col %d - up %d times cost %g, - down %d times cost %g\n",
2275               dynamicObject->columnNumber(),numberUp2,up,numberDown2,down);
2276    }
2277    if (numberUp) 
2278      averageUp /= (double) numberUp;
2279    else
2280      averageUp=1.0;
2281    if (numberDown) 
2282      averageDown /= (double) numberDown;
2283    else
2284      averageDown=1.0;
2285    printf("total - up %d vars average %g, - down %d vars average %g\n",
2286           numberUp,averageUp,numberDown,averageDown);
2287  }
2288  int numberBeforeTrust = model->numberBeforeTrust();
2289  int numberPenalties = model->numberPenalties();
2290  if (numberBeforeTrust>=1000000) {
2291    numberBeforeTrust = numberBeforeTrust % 1000000;
2292    numberPenalties=0;
2293  } else if (numberBeforeTrust<0) {
2294    numberPenalties=numberColumns;
2295    numberBeforeTrust=0;
2296  }
2297  // May go round twice if strong branching fixes all local candidates
2298  bool finished=false;
2299  int numberToFix=0;
2300# ifdef COIN_HAS_CLP
2301  OsiClpSolverInterface * osiclp = dynamic_cast< OsiClpSolverInterface*> (solver);
2302  int saveClpOptions=0;
2303  if (osiclp) {
2304    // for faster hot start
2305    saveClpOptions = osiclp->specialOptions();
2306    osiclp->setSpecialOptions(saveClpOptions|8192);
2307  }
2308# else
2309  OsiSolverInterface *osiclp = 0 ;
2310# endif
2311  const CglTreeProbingInfo * probingInfo = model->probingInfo();
2312  int saveSearchStrategy2 = model->searchStrategy();
2313  if (saveSearchStrategy2<999) {
2314    // Get average up and down costs
2315    double averageUp=0.0;
2316    double averageDown=0.0;
2317    {
2318      int numberUp=0;
2319      int numberDown=0;
2320      int i;
2321      for ( i=0;i<numberObjects;i++) {
2322        OsiObject * object = model->modifiableObject(i);
2323        CbcSimpleIntegerDynamicPseudoCost * dynamicObject =
2324          dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(object) ;
2325        assert(dynamicObject);
2326        if (dynamicObject->numberTimesUp()) {
2327          numberUp++;
2328          averageUp += dynamicObject->upDynamicPseudoCost();
2329        }
2330        if (dynamicObject->numberTimesDown()) {
2331          numberDown++;
2332          averageDown += dynamicObject->downDynamicPseudoCost();
2333        }
2334      }
2335      if (numberUp) 
2336        averageUp /= (double) numberUp;
2337      else
2338        averageUp=1.0;
2339      if (numberDown) 
2340        averageDown /= (double) numberDown;
2341      else
2342        averageDown=1.0;
2343      for ( i=0;i<numberObjects;i++) {
2344        OsiObject * object = model->modifiableObject(i);
2345        CbcSimpleIntegerDynamicPseudoCost * dynamicObject =
2346          dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(object) ;
2347        assert(dynamicObject);
2348        if (!dynamicObject->numberTimesUp()) 
2349          dynamicObject->setUpDynamicPseudoCost(averageUp);
2350      if (!dynamicObject->numberTimesDown()) 
2351        dynamicObject->setDownDynamicPseudoCost(averageDown);
2352      }
2353    }
2354  } else if (saveSearchStrategy2<1999) {
2355    // pseudo shadow prices
2356    model->pseudoShadow(NULL,NULL);
2357  } else if (saveSearchStrategy2<2999) {
2358    // leave old ones
2359  } else if (saveSearchStrategy2<3999) {
2360    // pseudo shadow prices at root
2361    if (!numberNodes)
2362      model->pseudoShadow(NULL,NULL);
2363  } else {
2364    abort();
2365  }
2366  if (saveSearchStrategy2>=0)
2367    saveSearchStrategy2 = saveSearchStrategy2 % 1000;
2368  if (saveSearchStrategy2==999)
2369    saveSearchStrategy2=-1;
2370  int px[4]={-1,-1,-1,-1};
2371  int saveSearchStrategy = saveSearchStrategy2<99 ? saveSearchStrategy2 : saveSearchStrategy2-100;
2372  bool newWay = saveSearchStrategy2>98;
2373  int numberNotTrusted=0;
2374  int numberStrongDone=0;
2375  int numberUnfinished=0;
2376  int numberStrongInfeasible=0;
2377  int numberStrongIterations=0;
2378  while(!finished) {
2379    finished=true;
2380    decision->initialize(model);
2381    // Some objects may compute an estimate of best solution from here
2382    estimatedDegradation=0.0; 
2383    numberToFix=0;
2384    int numberIntegerInfeasibilities=0; // without odd ones
2385    int numberToDo=0;
2386    int iBestNot=-1;
2387    int iBestGot=-1;
2388    double best=0.0;
2389    numberNotTrusted=0;
2390    numberStrongDone=0;
2391    numberUnfinished=0;
2392    numberStrongInfeasible=0;
2393    numberStrongIterations=0;
2394    int * which = objectMark+numberObjects+1;
2395    int neededPenalties;
2396    int branchingMethod=-1;
2397    // We may go round this loop three times (only if we think we have solution)
2398    for (int iPass=0;iPass<3;iPass++) {
2399     
2400      // compute current state
2401      int numberObjectInfeasibilities; // just odd ones
2402      model->feasibleSolution(
2403                              numberIntegerInfeasibilities,
2404                              numberObjectInfeasibilities);
2405     
2406      // Some objects may compute an estimate of best solution from here
2407      estimatedDegradation=0.0; 
2408      numberUnsatisfied_ = 0;
2409      // initialize sum of "infeasibilities"
2410      sumInfeasibilities_ = 0.0;
2411      int bestPriority=COIN_INT_MAX;
2412      int number01 = 0;
2413      const fixEntry * entry = NULL;
2414      const int * toZero = NULL;
2415      const int * toOne = NULL;
2416      const int * backward = NULL;
2417      int numberUnsatisProbed=0;
2418      int numberUnsatisNotProbed=0; // 0-1
2419      if (probingInfo) {
2420        number01 = probingInfo->numberIntegers();
2421        entry = probingInfo->fixEntries();
2422        toZero = probingInfo->toZero();
2423        toOne = probingInfo->toOne();
2424        backward = probingInfo->backward();
2425        if (!toZero[number01]) {
2426          // no info
2427          probingInfo=NULL;
2428        }
2429      }
2430      /*
2431        Scan for branching objects that indicate infeasibility. Choose candidates
2432        using priority as the first criteria, then integer infeasibility.
2433       
2434        The algorithm is to fill the array with a set of good candidates (by
2435        infeasibility) with priority bestPriority.  Finding a candidate with
2436        priority better (less) than bestPriority flushes the choice array. (This
2437        serves as initialization when the first candidate is found.)
2438       
2439      */
2440      numberToDo=0;
2441      neededPenalties=0;
2442      iBestNot=-1;
2443      double bestNot=0.0;
2444      iBestGot=-1;
2445      best=0.0;
2446      /* Problem type as set by user or found by analysis.  This will be extended
2447         0 - not known
2448         1 - Set partitioning <=
2449         2 - Set partitioning ==
2450         3 - Set covering
2451         4 - all +- 1 or all +1 and odd
2452      */
2453      int problemType = model->problemType();
2454#define PRINT_STUFF -1
2455      for (i=0;i<numberObjects;i++) {
2456        OsiObject * object = model->modifiableObject(i);
2457        CbcSimpleIntegerDynamicPseudoCost * dynamicObject =
2458          dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(object) ;
2459        assert(dynamicObject);
2460        int preferredWay;
2461        double infeasibility = object->infeasibility(&usefulInfo,preferredWay);
2462        int priorityLevel = object->priority();
2463#define ZERO_ONE 0
2464#define ZERO_FAKE 1.0e20;
2465#if ZERO_ONE==1
2466        // branch on 0-1 first (temp)
2467        if (fabs(saveSolution[dynamicObject->columnNumber()])<1.0)
2468          priorityLevel--;
2469#endif
2470#if ZERO_ONE==2
2471        if (fabs(saveSolution[dynamicObject->columnNumber()])<1.0)
2472          infeasibility *= ZERO_FAKE;
2473#endif
2474        if (infeasibility) {
2475          // check branching method
2476          if (branchingMethod!=dynamicObject->method()) {
2477            if (branchingMethod==-1)
2478              branchingMethod = dynamicObject->method();
2479            else
2480              branchingMethod = 100;
2481          }
2482          int iColumn = dynamicObject->columnNumber();
2483          if (probingInfo) {
2484            int iSeq = backward[iColumn];
2485            if (iSeq>=0) {
2486              if (toZero[iSeq+1]>toZero[iSeq]) {
2487                numberUnsatisProbed++;
2488              } else {
2489                numberUnsatisNotProbed++;
2490              }
2491            }
2492          }
2493          //double gap = saveUpper[iColumn]-saveLower[iColumn];
2494          // Give precedence to ones with gap of 1.0
2495          //assert(gap>0.0);
2496          //infeasibility /= CoinMin(gap,100.0);
2497          if (!depth_&&false) {
2498            // try closest to 0.5
2499            double part =saveSolution[iColumn]-floor(saveSolution[iColumn]);
2500            infeasibility = fabs(0.5-part);
2501          }
2502          if (problemType>0&&problemType<4) {
2503            // try closest to 0.5
2504            double part =saveSolution[iColumn]-floor(saveSolution[iColumn]);
2505            infeasibility = 0.5-fabs(0.5-part);
2506          }
2507          bool gotDown=false;
2508          int numberThisDown = dynamicObject->numberTimesDown();
2509          if (numberThisDown>=numberBeforeTrust)
2510            gotDown=true;
2511          bool gotUp=false;
2512          int numberThisUp = dynamicObject->numberTimesUp();
2513          if (numberThisUp>=numberBeforeTrust)
2514            gotUp=true;
2515          if ((numberNodes%PRINT_STUFF)==0&&PRINT_STUFF>0)
2516            printf("%d down %d %g up %d %g - infeas %g\n",
2517                   i,numberThisDown,object->downEstimate(),numberThisUp,object->upEstimate(),
2518                   infeasibility);
2519          // Increase estimated degradation to solution
2520          estimatedDegradation += CoinMin(object->upEstimate(),object->downEstimate());
2521          downEstimate[i]=object->downEstimate();
2522          upEstimate[i]=object->upEstimate();
2523          numberUnsatisfied_++;
2524          sumInfeasibilities_ += infeasibility;
2525          // Better priority? Flush choices.
2526          if (priorityLevel<bestPriority) {
2527            numberToDo=0;
2528            bestPriority = priorityLevel;
2529            iBestGot=-1;
2530            best=0.0;
2531            numberNotTrusted=0;
2532          } else if (priorityLevel>bestPriority) {
2533            continue;
2534          }
2535          if (!gotUp||!gotDown)
2536            numberNotTrusted++;
2537          // Check for suitability based on infeasibility.
2538          if ((gotDown&&gotUp)&&numberStrong>0) {
2539            sort[numberToDo]=-infeasibility;
2540            if (infeasibility>best) {
2541              best=infeasibility;
2542              iBestGot=numberToDo;
2543            }
2544          } else {
2545            objectMark[neededPenalties]=numberToDo;
2546            which[neededPenalties++]=dynamicObject->columnNumber();
2547            int iColumn = dynamicObject->columnNumber();
2548            double part =saveSolution[iColumn]-floor(saveSolution[iColumn]);
2549            sort[numberToDo]=-10.0*infeasibility;
2550            if (!(numberThisUp+numberThisDown))
2551              sort[numberToDo] *= 100.0; // make even more likely
2552            if (1.0-fabs(part-0.5)>bestNot) {
2553              iBestNot=numberToDo;
2554              bestNot = 1.0-fabs(part-0.5);
2555            }
2556          }
2557          whichObject[numberToDo++]=i;
2558        } else {
2559          // for debug
2560          downEstimate[i]=-1.0;
2561          upEstimate[i]=-1.0;
2562        }
2563      }
2564      if (numberUnsatisfied_) {
2565        if (probingInfo&&false)
2566          printf("nunsat %d, %d probed, %d other 0-1\n",numberUnsatisfied_,
2567                 numberUnsatisProbed,numberUnsatisNotProbed);
2568        // some infeasibilities - go to next steps
2569        break;
2570      } else if (!iPass) {
2571        // may just need resolve
2572        solver->resolve();
2573        memcpy(saveSolution,solver->getColSolution(),numberColumns*sizeof(double));
2574        model->reserveCurrentSolution(saveSolution);
2575        if (!solver->isProvenOptimal()) {
2576          // infeasible
2577          anyAction=-2;
2578          break;
2579        }
2580      } else if (iPass==1) {
2581        // looks like a solution - get paranoid
2582        bool roundAgain=false;
2583        // get basis
2584        CoinWarmStartBasis * ws = dynamic_cast<CoinWarmStartBasis*>(solver->getWarmStart());
2585        if (!ws)
2586          break;
2587        double tolerance;
2588        solver->getDblParam(OsiPrimalTolerance,tolerance);
2589        for (i=0;i<numberColumns;i++) {
2590          double value = saveSolution[i];
2591          if (value<lower[i]-tolerance) {
2592            saveSolution[i]=lower[i];
2593            roundAgain=true;
2594            ws->setStructStatus(i,CoinWarmStartBasis::atLowerBound);
2595          } else if (value>upper[i]+tolerance) {
2596            saveSolution[i]=upper[i];
2597            roundAgain=true;
2598            ws->setStructStatus(i,CoinWarmStartBasis::atUpperBound);
2599          } 
2600        }
2601        if (roundAgain) {
2602          // restore basis
2603          solver->setWarmStart(ws);
2604          solver->setColSolution(saveSolution);
2605          delete ws;
2606          bool takeHint;
2607          OsiHintStrength strength;
2608          solver->getHintParam(OsiDoDualInResolve,takeHint,strength);
2609          solver->setHintParam(OsiDoDualInResolve,false,OsiHintDo) ;
2610          solver->resolve();
2611          solver->setHintParam(OsiDoDualInResolve,takeHint,strength) ;
2612          memcpy(saveSolution,solver->getColSolution(),numberColumns*sizeof(double));
2613          model->reserveCurrentSolution(saveSolution);
2614          if (!solver->isProvenOptimal()) {
2615            // infeasible
2616            anyAction=-2;
2617            break;
2618          }
2619        } else {
2620          delete ws;
2621          break;
2622        }
2623      }
2624    }
2625    if (anyAction==-2) {
2626      break;
2627    }
2628    bool solveAll=false; // set true to say look at all even if some fixed (experiment)
2629    solveAll=true;
2630    // skip if solution
2631    if (!numberUnsatisfied_)
2632      break;
2633    //bool skipAll = (numberBeforeTrust>20&&numberNodes>20000&&numberNotTrusted==0);
2634    bool skipAll = numberNotTrusted==0||numberToDo==1;
2635    bool doneHotStart=false;
2636    int searchStrategy = saveSearchStrategy>=0 ? (saveSearchStrategy%10) : -1;
2637#ifndef CBC_WEAK_STRONG
2638    if (((numberNodes%20)==0&&searchStrategy!=2)||(model->specialOptions()&8)!=0)
2639      skipAll=false;
2640#endif
2641    if (!newWay) {
2642    // 10 up always use %10, 20 up as 10 and allow penalties
2643    // But adjust depending on ratio of iterations
2644    if (searchStrategy>0&&saveSearchStrategy<10) {
2645      if (numberBeforeTrust>=5&&numberBeforeTrust<=10) {
2646        if (searchStrategy!=2) {
2647          if (depth_>5) {
2648            int numberIterations = model->getIterationCount();
2649            int numberStrongIterations = model->numberStrongIterations();
2650            if (numberStrongIterations>numberIterations+10000) {
2651              searchStrategy=2;
2652              //skipAll=true;
2653            } else if (numberStrongIterations*4+1000<numberIterations||depth_<5) {
2654              searchStrategy=3;
2655              skipAll=false;
2656            }
2657          } else {
2658            searchStrategy=3;
2659            skipAll=false;
2660          }
2661        } else {
2662          //skipAll=true;
2663        }
2664      }
2665    }
2666    } else {
2667    // But adjust depending on ratio of iterations
2668    if (saveSearchStrategy<0) {
2669      // unset
2670      if ((numberNodes%20)==0||(model->specialOptions()&8)!=0) {
2671        // Do numberStrong
2672        searchStrategy=3;
2673      } else if (depth_<5) {
2674        // Do numberStrong
2675        searchStrategy=2;
2676      } else {
2677        int numberIterations = model->getIterationCount();
2678        int numberStrongIterations = model->numberStrongIterations();
2679        int numberRows = solver->getNumRows();
2680        if (numberStrongIterations>numberIterations+CoinMin(10000,10*numberRows)) {
2681          // off
2682          searchStrategy=0;
2683        } else if (numberStrongIterations*4+1000<numberIterations) {
2684          // Do numberStrong if not trusted
2685          searchStrategy=2;
2686        } else {
2687          searchStrategy=1;
2688        }
2689      }
2690    }
2691    if (searchStrategy<3&&(!numberNotTrusted||!searchStrategy))
2692      skipAll=true;
2693    else
2694      skipAll=false;
2695    }
2696    // worth trying if too many times
2697    // Save basis
2698    CoinWarmStart * ws = NULL;
2699    // save limit
2700    int saveLimit=0;
2701    solver->getIntParam(OsiMaxNumIterationHotStart,saveLimit);
2702    if (!skipAll) {
2703      ws = solver->getWarmStart();
2704      int limit=100;
2705#if 0
2706      int averageBranchIterations = model->getIterationCount()/(model->getNodeCount()+1);
2707      if (numberNodes)
2708        limit = CoinMin(CoinMax(limit,2*averageBranchIterations),500);
2709      else
2710        limit = 500;
2711#endif
2712      if ((!saveStateOfSearch||searchStrategy>3)&&saveLimit<limit&&saveLimit==100)
2713        solver->setIntParam(OsiMaxNumIterationHotStart,limit); 
2714    }
2715    // Say which one will be best
2716    int whichChoice=0;
2717    int bestChoice;
2718    if (iBestGot>=0)
2719      bestChoice=iBestGot;
2720    else
2721      bestChoice=iBestNot;
2722    assert (bestChoice>=0);
2723    // If we have hit max time don't do strong branching
2724    bool hitMaxTime = ( CoinCpuTime()-model->getDblParam(CbcModel::CbcStartSeconds) > 
2725                        model->getDblParam(CbcModel::CbcMaximumSeconds));
2726    // also give up if we are looping round too much
2727    if (hitMaxTime||numberPassesLeft<=0||(!numberNotTrusted&&false)||branchingMethod==11) {
2728      int iObject = whichObject[bestChoice];
2729      OsiObject * object = model->modifiableObject(iObject);
2730      int preferredWay;
2731      object->infeasibility(&usefulInfo,preferredWay);
2732      CbcSimpleInteger * obj =
2733        dynamic_cast <CbcSimpleInteger *>(object) ;
2734      if (obj) {
2735        branch_=obj->createBranch(solver,&usefulInfo,preferredWay);
2736      } else {
2737        CbcObject * obj =
2738          dynamic_cast <CbcObject *>(object) ;
2739        assert (obj);
2740        branch_=obj->createBranch(preferredWay);
2741      }
2742      {
2743        CbcBranchingObject * branchObj =
2744          dynamic_cast <CbcBranchingObject *>(branch_) ;
2745        assert (branchObj);
2746        branchObj->way(preferredWay);
2747      }
2748      delete ws;
2749      ws=NULL;
2750      break;
2751    } else {
2752      // say do fast
2753      int easy=1;
2754      if (!skipAll)
2755        solver->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,&easy) ;
2756      int iDo;
2757#ifdef RANGING
2758      if ((skipAll&&numberBeforeTrust&&saveSearchStrategy<20)||saveSearchStrategy<10)
2759        numberPenalties=0;
2760      {
2761        // off penalties if too much
2762        double needed = neededPenalties;
2763        needed *= numberRows;
2764        if (needed>1.0e6&&numberNodes&&saveSearchStrategy<20) {
2765          numberPenalties=0;
2766          neededPenalties=0;
2767        }
2768      }
2769#     ifdef COIN_HAS_CLP
2770      if (osiclp&&numberPenalties&&neededPenalties) {
2771        xPen += neededPenalties;
2772        which--;
2773        which[0]=neededPenalties;
2774        osiclp->passInRanges(which);
2775        // Mark hot start and get ranges
2776        if (kPass) {
2777          // until can work out why solution can go funny
2778          int save = osiclp->specialOptions();
2779          osiclp->setSpecialOptions(save|256);
2780          solver->markHotStart();
2781          osiclp->setSpecialOptions(save);
2782        } else {
2783          solver->markHotStart();
2784        }
2785        assert (auxiliaryInfo->warmStart());
2786        doneHotStart=true;
2787        xMark++;
2788        kPass++;
2789        osiclp->passInRanges(NULL);
2790        const double * downCost=osiclp->upRange();
2791        const double * upCost=osiclp->downRange();
2792        //printf("numberTodo %d needed %d numberpenalties %d\n",numberToDo,neededPenalties,numberPenalties);
2793        double invTrust = 1.0/((double) numberBeforeTrust);
2794        for (int i=0;i<neededPenalties;i++) {
2795          int j = objectMark[i];
2796          int iObject = whichObject[j];
2797          OsiObject * object = model->modifiableObject(iObject);
2798          CbcSimpleIntegerDynamicPseudoCost * dynamicObject =
2799            dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(object) ;
2800          int iSequence=dynamicObject->columnNumber();
2801          double value = saveSolution[iSequence];
2802          value -= floor(value);
2803          double upPenalty = CoinMin(upCost[i],1.0e110)*(1.0-value);
2804          double downPenalty = CoinMin(downCost[i],1.0e110)*value;
2805          if (!numberBeforeTrust) {
2806            // override
2807            downEstimate[iObject]=downPenalty;
2808            upEstimate[iObject]=upPenalty;
2809          } else {
2810            int numberThisDown = dynamicObject->numberTimesDown();
2811            if (numberThisDown<numberBeforeTrust) {
2812              double fraction = ((double) numberThisDown)*invTrust;
2813              downEstimate[iObject] = fraction*downEstimate[iObject]+(1.0-fraction)*downPenalty;
2814            }
2815            int numberThisUp = dynamicObject->numberTimesUp();
2816            if (numberThisUp<numberBeforeTrust) {
2817              double fraction = ((double) numberThisUp)*invTrust;
2818              upEstimate[iObject] = fraction*upEstimate[iObject]+(1.0-fraction)*upPenalty;
2819            }
2820          }
2821          sort[j] = - CoinMin(downEstimate[iObject],upEstimate[iObject]);
2822#ifdef CBC_WEAK_STRONG
2823          sort[j] -= 1.0e10; // make more likely to be chosen
2824#endif
2825          //if ((numberNodes%PRINT_STUFF)==0&&PRINT_STUFF>0)
2826          if (!numberNodes)
2827            printf("%d pen down ps %g -> %g up ps %g -> %g\n",
2828                   iObject,downCost[i],downPenalty,upCost[i],upPenalty);
2829        }
2830      } else
2831#     endif     /* COIN_HAS_CLP */
2832      {
2833        if (!skipAll) {
2834          // Mark hot start
2835          solver->markHotStart();
2836          doneHotStart=true;
2837          assert (auxiliaryInfo->warmStart());
2838          xMark++;
2839          //if (solver->isProvenPrimalInfeasible())
2840          //printf("**** Hot start says node infeasible\n");
2841        }
2842        // make sure best will be first
2843        if (iBestGot>=0)
2844          sort[iBestGot]=-1.0e120;
2845      }
2846#else           /* RANGING */
2847      if (!skipAll) {
2848        // Mark hot start
2849        doneHotStart=true;
2850        assert (auxiliaryInfo->warmStart());
2851        solver->markHotStart();
2852        xMark++;
2853      }
2854      // make sure best will be first
2855      if (iBestGot>=0)
2856        sort[iBestGot]=-COIN_DBL_MAX;
2857#endif          /* RANGING */
2858      // Actions 0 - exit for repeat, 1 resolve and try old choice,2 exit for continue
2859#define ACTION 0
2860#if ACTION<2
2861      if (anyAction)
2862        numberToDo=0; // skip as we will be trying again
2863#endif
2864      // Sort
2865      CoinSort_2(sort,sort+numberToDo,whichObject);
2866      // Change in objective opposite infeasible
2867      double worstFeasible=0.0;
2868      // Just first if strong off
2869      if (!numberStrong)
2870        numberToDo=CoinMin(numberToDo,1);
2871      iDo=0;
2872      int saveLimit2;
2873      solver->getIntParam(OsiMaxNumIterationHotStart,saveLimit2);
2874      bool doQuickly = false; // numberToDo>2*numberStrong;
2875      if (searchStrategy==2)
2876        doQuickly=true;
2877      //printf("todo %d, strong %d\n",numberToDo,numberStrong);
2878      int numberTest=numberNotTrusted>0 ? numberStrong : (numberStrong+1)/2;
2879      int numberTest2 = 2*numberStrong;
2880      double distanceToCutoff2 = model->getCutoff()-objectiveValue_;
2881      if (!newWay) {
2882      if (searchStrategy==3) {
2883        // Previously decided we need strong
2884        doQuickly=false;
2885        numberTest = numberStrong;
2886        //numberTest2 = 1000000;
2887      }
2888      //if (searchStrategy<0||searchStrategy==1)
2889        //numberTest2 = 1000000;
2890#if 0
2891      if (numberBeforeTrust>20&&(numberNodes>20000||(numberNodes>200&&numberNotTrusted==0))) {
2892        if ((numberNodes%20)!=0) {
2893          numberTest=0;
2894          doQuickly=true;
2895        }
2896      }
2897#else
2898      // Try nearly always off
2899      if (searchStrategy<2) {
2900        if ((numberNodes%20)!=0) {
2901          if ((model->specialOptions()&8)==0) {
2902            numberTest=0;
2903            doQuickly=true;
2904          }
2905        } else {
2906          doQuickly=false;
2907          numberTest=2*numberStrong;
2908          skipAll=false;
2909        }
2910      } else if (searchStrategy!=3) {
2911        doQuickly=true;
2912        numberTest=numberStrong;
2913      }
2914#endif
2915      if (depth_<8&&numberStrong) {
2916        if (searchStrategy!=2) {
2917          doQuickly=false;
2918          int numberRows = solver->getNumRows();
2919          // whether to do this or not is important - think
2920          if (numberRows<300||numberRows+numberColumns<2500) {
2921            if (depth_<7)
2922              numberStrong = CoinMin(3*numberStrong,numberToDo);
2923            if (!depth_) 
2924              numberStrong=CoinMin(6*numberStrong,numberToDo);
2925          }
2926          numberTest=numberStrong;
2927          skipAll=false;
2928        }
2929        model->setStateOfSearch(2); // use min min
2930      }
2931      // could adjust using average iterations per branch
2932      // double average = ((double)model->getIterationCount())/
2933      //((double) model->getNodeCount()+1.0);
2934      // if too many and big then just do 10 its
2935      if (!skipAll&&saveStateOfSearch) {
2936        //if (numberNotTrusted>3*numberStrong&&numberRows>250&&numberColumns>1000&&saveLimit==100)
2937          // off solver->setIntParam(OsiMaxNumIterationHotStart,10);
2938      }
2939      // make negative for test
2940      distanceToCutoff = - distanceToCutoff;
2941      if (numberObjects>-100) {
2942        // larger
2943        distanceToCutoff *= 100.0;
2944      }
2945        distanceToCutoff = -COIN_DBL_MAX;
2946      // Do at least 5 strong
2947      if (numberColumns<1000&&(depth_<15||numberNodes<1000000))
2948        numberTest = CoinMax(numberTest,5);
2949      if ((model->specialOptions()&8)==0) {
2950        if (skipAll) {
2951          numberTest=0;
2952          doQuickly=true;
2953        }
2954      } else {
2955        // do 5 as strong is fixing
2956        numberTest = CoinMax(numberTest,5);
2957      }
2958      } else {
2959      int numberTest=numberNotTrusted>0 ? numberStrong : (numberStrong+1)/2;
2960      int numberTest2 = 2*numberStrong;
2961      if (searchStrategy>=3) {
2962        // Previously decided we need strong
2963        doQuickly=false;
2964        if (depth_<7)
2965          numberStrong *=3;
2966        if (!depth_) 
2967          numberStrong=CoinMin(6*numberStrong,numberToDo);
2968        numberTest = numberStrong;
2969        numberTest2 *= 2;
2970      } else if (searchStrategy==2||(searchStrategy==1&&depth_<6)) {
2971        numberStrong *=2;
2972        if (!depth_) 
2973          numberStrong=CoinMin(2*numberStrong,numberToDo);
2974        numberTest = numberStrong;
2975      } else if (searchStrategy==1&&numberNotTrusted) {
2976        numberTest = numberStrong;
2977      } else {
2978        numberTest=0;
2979        skipAll=true;
2980      }
2981      distanceToCutoff=model->getCutoff()-objectiveValue_;
2982      // make negative for test
2983      distanceToCutoff = - distanceToCutoff;
2984      if (numberObjects>-100) {
2985        // larger
2986        distanceToCutoff *= 100.0;
2987      }
2988      distanceToCutoff = -COIN_DBL_MAX;
2989      if (skipAll) {
2990        numberTest=0;
2991        doQuickly=true;
2992      }
2993      }
2994#if 0
2995      // temp - always switch off
2996      if (0) {
2997        int numberIterations = model->getIterationCount();
2998        int numberStrongIterations = model->numberStrongIterations();
2999        if (numberStrongIterations>numberIterations+10000&&depth_>=5) {
3000          skipAll=true;
3001          newWay=false;
3002          numberTest=0;
3003          doQuickly=true;
3004        }
3005      }
3006      // temp - always switch on
3007      if (0) {
3008        int numberIterations = model->getIterationCount();
3009        int numberStrongIterations = model->numberStrongIterations();
3010        if (2*numberStrongIterations<numberIterations||depth_<=5) {
3011          skipAll=false;
3012          newWay=false;
3013          numberTest=CoinMax(numberTest,numberStrong);
3014          doQuickly=false;
3015        }
3016      }
3017#endif
3018      px[0]=numberTest;
3019      px[1]=numberTest2;
3020      px[2]= doQuickly ? 1 : -1;
3021      px[3]=numberStrong;
3022      if (!newWay) {
3023        if (numberColumns>8*solver->getNumRows()&&false) {
3024          printf("skipAll %c doQuickly %c numberTest %d numberTest2 %d numberNot %d\n",
3025                 skipAll ? 'Y' : 'N',doQuickly ? 'Y' : 'N',numberTest,numberTest2,numberNotTrusted);
3026          numberTest = CoinMin(numberTest,model->numberStrong());
3027          numberTest2 = CoinMin(numberTest2,model->numberStrong());
3028          printf("new test,test2 %d %d\n",numberTest,numberTest2);
3029        }
3030      }
3031      //printf("skipAll %c doQuickly %c numberTest %d numberTest2 %d numberNot %d\n",
3032      //   skipAll ? 'Y' : 'N',doQuickly ? 'Y' : 'N',numberTest,numberTest2,numberNotTrusted);
3033      // See if we want mini tree
3034      bool wantMiniTree=false;
3035      if (model->sizeMiniTree()&&depth_>7&&saveStateOfSearch>0)
3036        wantMiniTree=true;
3037      numberMini=0;
3038      //if (skipAll&&numberTest==0&&doQuickly)
3039      //numberToDo = 1; // trust previous stuff
3040      bool couldChooseFirst = false ; //(skipAll&&numberTest==0&&doQuickly);
3041      //skipAll=false;
3042      for ( iDo=0;iDo<numberToDo;iDo++) {
3043        CbcStrongInfo choice;
3044        int iObject = whichObject[iDo];
3045        OsiObject * object = model->modifiableObject(iObject);
3046        CbcSimpleIntegerDynamicPseudoCost * dynamicObject =
3047          dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(object) ;
3048        int iColumn = dynamicObject->columnNumber();
3049        int preferredWay;
3050        double infeasibility = object->infeasibility(&usefulInfo,preferredWay);
3051        // may have become feasible
3052        if (!infeasibility)
3053          continue;
3054        CbcSimpleInteger * obj =
3055          dynamic_cast <CbcSimpleInteger *>(object) ;
3056        if (obj) {
3057          choice.possibleBranch=obj->createBranch(solver,&usefulInfo,preferredWay);
3058        } else {
3059          CbcObject * obj =
3060            dynamic_cast <CbcObject *>(object) ;
3061          assert (obj);
3062          choice.possibleBranch=obj->createBranch(preferredWay);
3063        }
3064        // Save which object it was
3065        choice.objectNumber=iObject;
3066        choice.numIntInfeasUp = numberUnsatisfied_;
3067        choice.numIntInfeasDown = numberUnsatisfied_;
3068        choice.upMovement = upEstimate[iObject];
3069        choice.downMovement = downEstimate[iObject];
3070        assert (choice.upMovement>=0.0);
3071        assert (choice.downMovement>=0.0);
3072        choice.fix=0; // say not fixed
3073        double maxChange = 0.5*(choice.upMovement+choice.downMovement);
3074        maxChange = CoinMin(choice.upMovement,choice.downMovement);
3075        maxChange = CoinMax(choice.upMovement,choice.downMovement);
3076        if (searchStrategy==2)
3077          maxChange = COIN_DBL_MAX;
3078        //maxChange *= 5.0;
3079        if (dynamicObject->method()==1)
3080          maxChange *= 0.1; // probing
3081        // see if can skip strong branching
3082        int canSkip = choice.possibleBranch->fillStrongInfo(choice);
3083        if (!newWay) {
3084          if ((maxChange>distanceToCutoff2)&&(!doQuickly||(numberTest>0&&searchStrategy!=2)))
3085          canSkip=0;
3086        } else {
3087        if (skipAll)
3088          canSkip=1;
3089        else if (numberTest>0&&searchStrategy>=3)
3090          canSkip=0;
3091        }
3092        if (!numberBeforeTrust) {
3093          canSkip=1;
3094        }
3095        if (sort[iDo]<distanceToCutoff)
3096          canSkip=0;
3097        if (((numberTest2<=0&&numberTest<=0)||skipAll)&&sort[iDo]>distanceToCutoff) {
3098          canSkip=1; // always skip
3099          if (iDo>20) {
3100            delete choice.possibleBranch;
3101            choice.possibleBranch=NULL;
3102            break; // give up anyway
3103          }
3104        }
3105        if (model->messageHandler()->logLevel()>3&&numberBeforeTrust) 
3106          dynamicObject->print(1,choice.possibleBranch->value());
3107        // was if (!canSkip)
3108        if (newWay)
3109        numberTest2--;
3110        if (!canSkip) {
3111          //#ifndef RANGING
3112          if (!doneHotStart) {
3113            // Mark hot start
3114            doneHotStart=true;
3115            assert (auxiliaryInfo->warmStart());
3116            solver->markHotStart();
3117            xMark++;
3118          }
3119          //#endif
3120          assert (!couldChooseFirst);
3121          numberTest--;
3122          if (!newWay)
3123          numberTest2--;
3124          // just do a few
3125          //if (canSkip)
3126          //solver->setIntParam(OsiMaxNumIterationHotStart,10);
3127          double objectiveChange ;
3128          double newObjectiveValue=1.0e100;
3129          int j;
3130          // status is 0 finished, 1 infeasible and other
3131          int iStatus;
3132          if (0) {
3133            CbcDynamicPseudoCostBranchingObject * cbcobj = dynamic_cast<CbcDynamicPseudoCostBranchingObject *> (choice.possibleBranch);
3134            if (cbcobj) {
3135              CbcSimpleIntegerDynamicPseudoCost * object = cbcobj->object();
3136              printf("strong %d ",iDo);
3137              object->print(1,0.5);
3138            }
3139          }
3140          /*
3141            Try the down direction first. (Specify the initial branching alternative as
3142            down with a call to way(-1). Each subsequent call to branch() performs the
3143            specified branch and advances the branch object state to the next branch
3144            alternative.)
3145          */
3146          choice.possibleBranch->way(-1) ;
3147#if NEW_UPDATE_OBJECT==0
3148          decision->saveBranchingObject( choice.possibleBranch);
3149#endif
3150          choice.possibleBranch->branch() ;
3151          solver->solveFromHotStart() ;
3152          bool needHotStartUpdate=false;
3153          numberStrongDone++;
3154          numberStrongIterations += solver->getIterationCount();
3155          /*
3156            We now have an estimate of objective degradation that we can use for strong
3157            branching. If we're over the cutoff, the variable is monotone up.
3158            If we actually made it to optimality, check for a solution, and if we have
3159            a good one, call setBestSolution to process it. Note that this may reduce the
3160            cutoff, so we check again to see if we can declare this variable monotone.
3161          */
3162          if (solver->isProvenOptimal())
3163            iStatus=0; // optimal
3164          else if (solver->isIterationLimitReached()
3165                   &&!solver->isDualObjectiveLimitReached())
3166            iStatus=2; // unknown
3167          else
3168            iStatus=1; // infeasible
3169          newObjectiveValue = solver->getObjSense()*solver->getObjValue();
3170          choice.numItersDown = solver->getIterationCount();
3171          objectiveChange = CoinMax(newObjectiveValue  - objectiveValue_,0.0);
3172          // Update branching information if wanted
3173#if NEW_UPDATE_OBJECT==0
3174          decision->updateInformation( solver,this);
3175#elif NEW_UPDATE_OBJECT<2
3176          CbcBranchingObject * cbcobj = dynamic_cast<CbcBranchingObject *> (choice.possibleBranch);
3177          if (cbcobj) {
3178            CbcObject * object = cbcobj->object();
3179            CbcObjectUpdateData update = object->createUpdateInformation(solver,this,cbcobj);
3180            object->updateInformation(update);
3181          } else {
3182            decision->updateInformation( solver,this);
3183          }
3184#else
3185          CbcBranchingObject * cbcobj = dynamic_cast<CbcBranchingObject *> (choice.possibleBranch);
3186          if (cbcobj) {
3187            CbcObject * object = cbcobj->object();
3188            CbcObjectUpdateData update = object->createUpdateInformation(solver,this,cbcobj);
3189            update.objectNumber_ = choice.objectNumber;
3190            model->addUpdateInformation(update);
3191          } else {
3192            decision->updateInformation( solver,this);
3193          }
3194#endif
3195          if (!iStatus) {
3196            choice.finishedDown = true ;
3197            if (newObjectiveValue>=cutoff) {
3198              objectiveChange = 1.0e100; // say infeasible
3199              numberStrongInfeasible++;
3200            } else {
3201              // See if integer solution
3202              if (model->feasibleSolution(choice.numIntInfeasDown,
3203                                          choice.numObjInfeasDown)
3204                  &&model->problemFeasibility()->feasible(model,-1)>=0) {
3205                if (auxiliaryInfo->solutionAddsCuts()) {
3206                  needHotStartUpdate=true;
3207                  solver->unmarkHotStart();
3208                }
3209                model->setBestSolution(CBC_STRONGSOL,
3210                                       newObjectiveValue,
3211                                       solver->getColSolution()) ;
3212                if (needHotStartUpdate) {
3213                  solver->resolve();
3214                  newObjectiveValue = solver->getObjSense()*solver->getObjValue();
3215                  objectiveChange = CoinMax(newObjectiveValue  - objectiveValue_,0.0);
3216                  model->feasibleSolution(choice.numIntInfeasDown,
3217                                          choice.numObjInfeasDown);
3218                }
3219                model->setLastHeuristic(NULL);
3220                model->incrementUsed(solver->getColSolution());
3221                cutoff =model->getCutoff();
3222                if (newObjectiveValue >= cutoff) {      //  *new* cutoff
3223                  objectiveChange = 1.0e100 ;
3224                  numberStrongInfeasible++;
3225                }
3226              }
3227            }
3228          } else if (iStatus==1) {
3229            objectiveChange = 1.0e100 ;
3230            numberStrongInfeasible++;
3231          } else {
3232            // Can't say much as we did not finish
3233            choice.finishedDown = false ;
3234            numberUnfinished++;
3235          }
3236          choice.downMovement = objectiveChange ;
3237         
3238          // restore bounds
3239          for ( j=0;j<numberColumns;j++) {
3240            if (saveLower[j] != lower[j])
3241              solver->setColLower(j,saveLower[j]);
3242            if (saveUpper[j] != upper[j])
3243              solver->setColUpper(j,saveUpper[j]);
3244          }
3245          if(needHotStartUpdate) {
3246            needHotStartUpdate = false;
3247            solver->resolve();
3248            //we may again have an integer feasible solution
3249            int numberIntegerInfeasibilities;
3250            int numberObjectInfeasibilities;
3251            if (model->feasibleSolution(
3252                                        numberIntegerInfeasibilities,
3253                                        numberObjectInfeasibilities)) {
3254#ifdef BONMIN
3255              //In this case node has become integer feasible, let us exit the loop
3256              std::cout<<"Node has become integer feasible"<<std::endl;
3257              numberUnsatisfied_ = 0;
3258              break;
3259#endif
3260              double objValue = solver->getObjValue();
3261              model->setBestSolution(CBC_STRONGSOL,
3262                                     objValue,
3263                                     solver->getColSolution()) ;
3264              solver->resolve();
3265              cutoff =model->getCutoff();
3266            }
3267            solver->markHotStart();
3268          }
3269          //printf("Down on %d, status is %d, obj %g its %d cost %g finished %d inf %d infobj %d\n",
3270          //printf("Down on %d, status is %d, obj %g its %d cost %g finished %d inf %d infobj %d\n",
3271          //     choice.objectNumber,iStatus,newObjectiveValue,choice.numItersDown,
3272          //     choice.downMovement,choice.finishedDown,choice.numIntInfeasDown,
3273          //     choice.numObjInfeasDown);
3274         
3275          // repeat the whole exercise, forcing the variable up
3276#if NEW_UPDATE_OBJECT==0
3277          decision->saveBranchingObject( choice.possibleBranch);
3278#endif
3279          choice.possibleBranch->branch();
3280          solver->solveFromHotStart() ;
3281          numberStrongDone++;
3282          numberStrongIterations += solver->getIterationCount();
3283          /*
3284            We now have an estimate of objective degradation that we can use for strong
3285            branching. If we're over the cutoff, the variable is monotone up.
3286            If we actually made it to optimality, check for a solution, and if we have
3287            a good one, call setBestSolution to process it. Note that this may reduce the
3288            cutoff, so we check again to see if we can declare this variable monotone.
3289          */
3290          if (solver->isProvenOptimal())
3291            iStatus=0; // optimal
3292          else if (solver->isIterationLimitReached()
3293                   &&!solver->isDualObjectiveLimitReached())
3294            iStatus=2; // unknown
3295          else
3296            iStatus=1; // infeasible
3297          newObjectiveValue = solver->getObjSense()*solver->getObjValue();
3298          choice.numItersUp = solver->getIterationCount();
3299          objectiveChange = CoinMax(newObjectiveValue  - objectiveValue_,0.0);
3300          // Update branching information if wanted
3301#if NEW_UPDATE_OBJECT==0
3302          decision->updateInformation( solver,this);
3303#elif NEW_UPDATE_OBJECT<2
3304          cbcobj = dynamic_cast<CbcBranchingObject *> (choice.possibleBranch);
3305          if (cbcobj) {
3306            CbcObject * object = cbcobj->object();
3307            CbcObjectUpdateData update = object->createUpdateInformation(solver,this,cbcobj);
3308            object->updateInformation(update);
3309          } else {
3310            decision->updateInformation( solver,this);
3311          }
3312#else
3313          cbcobj = dynamic_cast<CbcBranchingObject *> (choice.possibleBranch);
3314          if (cbcobj) {
3315            CbcObject * object = cbcobj->object();
3316            CbcObjectUpdateData update = object->createUpdateInformation(solver,this,cbcobj);
3317            update.objectNumber_ = choice.objectNumber;
3318            model->addUpdateInformation(update);
3319          } else {
3320            decision->updateInformation( solver,this);
3321          }
3322#endif
3323          if (!iStatus) {
3324            choice.finishedUp = true ;
3325            if (newObjectiveValue>=cutoff) {
3326              objectiveChange = 1.0e100; // say infeasible
3327              numberStrongInfeasible++;
3328            } else {
3329              // See if integer solution
3330              if (model->feasibleSolution(choice.numIntInfeasUp,
3331                                          choice.numObjInfeasUp)
3332                  &&model->problemFeasibility()->feasible(model,-1)>=0) {
3333#ifdef BONMIN
3334                std::cout<<"Node has become integer feasible"<<std::endl;
3335                numberUnsatisfied_ = 0;
3336                break;
3337#endif
3338                if (auxiliaryInfo->solutionAddsCuts()) {
3339                  needHotStartUpdate=true;
3340                  solver->unmarkHotStart();
3341                }
3342                model->setBestSolution(CBC_STRONGSOL,
3343                                       newObjectiveValue,
3344                                       solver->getColSolution()) ;
3345                if (needHotStartUpdate) {
3346                  solver->resolve();
3347                  newObjectiveValue = solver->getObjSense()*solver->getObjValue();
3348                  objectiveChange = CoinMax(newObjectiveValue  - objectiveValue_,0.0);
3349                  model->feasibleSolution(choice.numIntInfeasDown,
3350                                          choice.numObjInfeasDown);
3351                }
3352                model->setLastHeuristic(NULL);
3353                model->incrementUsed(solver->getColSolution());
3354                cutoff =model->getCutoff();
3355                if (newObjectiveValue >= cutoff) {      //  *new* cutoff
3356                  objectiveChange = 1.0e100 ;
3357                  numberStrongInfeasible++;
3358                }
3359              }
3360            }
3361          } else if (iStatus==1) {
3362            objectiveChange = 1.0e100 ;
3363            numberStrongInfeasible++;
3364          } else {
3365            // Can't say much as we did not finish
3366            choice.finishedUp = false ;
3367            numberUnfinished++;
3368          }
3369          choice.upMovement = objectiveChange ;
3370         
3371          // restore bounds
3372          for ( j=0;j<numberColumns;j++) {
3373            if (saveLower[j] != lower[j])
3374              solver->setColLower(j,saveLower[j]);
3375            if (saveUpper[j] != upper[j])
3376              solver->setColUpper(j,saveUpper[j]);
3377          }
3378          if(needHotStartUpdate) {
3379            needHotStartUpdate = false;
3380            solver->resolve();
3381            //we may again have an integer feasible solution
3382            int numberIntegerInfeasibilities;
3383            int numberObjectInfeasibilities;
3384            if (model->feasibleSolution(
3385                                        numberIntegerInfeasibilities,
3386                                        numberObjectInfeasibilities)) {
3387              double objValue = solver->getObjValue();
3388              model->setBestSolution(CBC_STRONGSOL,
3389                                     objValue,
3390                                     solver->getColSolution()) ;
3391              solver->resolve();
3392              cutoff =model->getCutoff();
3393            }
3394            solver->markHotStart();
3395          }
3396         
3397          //printf("Up on %d, status is %d, obj %g its %d cost %g finished %d inf %d infobj %d\n",
3398          //     choice.objectNumber,iStatus,newObjectiveValue,choice.numItersUp,
3399          //     choice.upMovement,choice.finishedUp,choice.numIntInfeasUp,
3400          //     choice.numObjInfeasUp);
3401        }
3402   
3403        solver->setIntParam(OsiMaxNumIterationHotStart,saveLimit2); 
3404        /*
3405          End of evaluation for this candidate variable. Possibilities are:
3406          * Both sides below cutoff; this variable is a candidate for branching.
3407          * Both sides infeasible or above the objective cutoff: no further action
3408          here. Break from the evaluation loop and assume the node will be purged
3409          by the caller.
3410          * One side below cutoff: Install the branch (i.e., fix the variable). Break
3411          from the evaluation loop and assume the node will be reoptimised by the
3412          caller.
3413        */
3414        // reset
3415        choice.possibleBranch->resetNumberBranchesLeft();
3416        if (choice.upMovement<1.0e100) {
3417          if(choice.downMovement<1.0e100) {
3418            // In case solution coming in was odd
3419            choice.upMovement = CoinMax(0.0,choice.upMovement);
3420            choice.downMovement = CoinMax(0.0,choice.downMovement);
3421            if (couldChooseFirst)
3422              printf("candidate %d up %g down %g sort %g\n",iDo,choice.upMovement,choice.downMovement,sort[iDo]);
3423#if ZERO_ONE==2
3424            // branch on 0-1 first (temp)
3425            if (fabs(choice.possibleBranch->value())<1.0) {
3426              choice.upMovement *= ZERO_FAKE;
3427              choice.downMovement *= ZERO_FAKE;
3428            }
3429#endif
3430            // feasible - see which best
3431            if (!canSkip) {
3432              if (iColumn==-46) {
3433                printf("sort %g downest %g upest %g ",sort[iDo],downEstimate[iObject],
3434                     upEstimate[iObject]);
3435                printf("downMove %g upMove %g value %g current pseudo %g %g\n",
3436                       choice.downMovement,choice.upMovement,choice.possibleBranch->value(),
3437                       dynamicObject->downDynamicPseudoCost(),dynamicObject->upDynamicPseudoCost());
3438              }
3439              if (model->messageHandler()->logLevel()>3) 
3440                printf("sort %g downest %g upest %g ",sort[iDo],downEstimate[iObject],
3441                     upEstimate[iObject]);
3442              model->messageHandler()->message(CBC_STRONG,*model->messagesPointer())
3443                << iObject << iColumn
3444                <<choice.downMovement<<choice.numIntInfeasDown
3445                <<choice.upMovement<<choice.numIntInfeasUp
3446                <<choice.possibleBranch->value()
3447                <<CoinMessageEol;
3448            }
3449            //if (!stateOfSearch)
3450            //choice.numIntInfeasDown=99999; // temp fudge
3451            if (wantMiniTree)
3452              decision->setBestCriterion(-1.0);
3453            double bestCriterion = -1.0;
3454            //double gap = saveUpper[iColumn]-saveLower[iColumn];
3455            // Give precedence to ones with gap of 1.0
3456            //assert(gap>0.0);
3457            double factor = 1.0; //changeFactor/CoinMin(gap,100.0);
3458            int betterWay;
3459            {
3460              CbcBranchingObject * branchObj =
3461                dynamic_cast <CbcBranchingObject *>(branch_) ;
3462              if (branch_)
3463                assert (branchObj);
3464              betterWay = decision->betterBranch(choice.possibleBranch,
3465                                                     branchObj,
3466                                                     choice.upMovement*factor,
3467                                                     choice.numIntInfeasUp ,
3468                                                     choice.downMovement*factor,
3469                                                     choice.numIntInfeasDown );
3470            }
3471            if (wantMiniTree) {
3472              double criterion = decision->getBestCriterion();
3473              sort[numberMini]=-criterion;
3474              whichObject[numberMini++]=whichObject[iDo];
3475              assert (betterWay);
3476              if (criterion>bestCriterion) 
3477                bestCriterion=criterion;
3478              else
3479                betterWay=0;
3480            }
3481            if (iDo>=changeStrategy) {
3482              // make less likely
3483              changeStrategy+=numberStrong;
3484              changeFactor *= 0.9;
3485            }
3486            if (betterWay) {
3487              delete branch_;
3488              // C) create branching object
3489              branch_ = choice.possibleBranch;
3490              choice.possibleBranch=NULL;
3491              {
3492                CbcBranchingObject * branchObj =
3493                  dynamic_cast <CbcBranchingObject *>(branch_) ;
3494                assert (branchObj);
3495                //branchObj->way(preferredWay);
3496                branchObj->way(betterWay);
3497              }
3498              if (couldChooseFirst)
3499                printf("choosing %d way %d\n",iDo,betterWay);
3500              bestChoice = choice.objectNumber;
3501              whichChoice = iDo;
3502              if (numberStrong<=1) {
3503                delete ws;
3504                ws=NULL;
3505                break;
3506              }
3507            } else {
3508              delete choice.possibleBranch;
3509              choice.possibleBranch=NULL;
3510              if (iDo>=2*numberStrong) {
3511                delete ws;
3512                ws=NULL;
3513                break;
3514              }
3515              if (!dynamicObject||dynamicObject->numberTimesUp()>1) {
3516                if (iDo-whichChoice>=numberStrong) {
3517                  delete choice.possibleBranch;
3518                  choice.possibleBranch=NULL;
3519                  break; // give up
3520                }
3521              } else {
3522                if (iDo-whichChoice>=2*numberStrong) {
3523                  delete ws;
3524                  ws=NULL;
3525                  delete choice.possibleBranch;
3526                  choice.possibleBranch=NULL;
3527                  break; // give up
3528                }
3529              }
3530            }
3531          } else {
3532            // up feasible, down infeasible
3533            anyAction=-1;
3534            worstFeasible = CoinMax(worstFeasible,choice.upMovement);
3535            model->messageHandler()->message(CBC_STRONG,*model->messagesPointer())
3536              << iObject << iColumn
3537              <<choice.downMovement<<choice.numIntInfeasDown
3538              <<choice.upMovement<<choice.numIntInfeasUp
3539              <<choice.possibleBranch->value()
3540              <<CoinMessageEol;
3541            //printf("Down infeasible for choice %d sequence %d\n",i,
3542            // model->object(choice.objectNumber)->columnNumber());
3543            if (!solveAll) {
3544              choice.possibleBranch->way(1);
3545              choice.possibleBranch->branch();
3546              delete choice.possibleBranch;
3547              choice.possibleBranch=NULL;
3548              delete ws;
3549              ws=NULL;
3550              break;
3551            } else {
3552              choice.fix=1;
3553              fixObject[numberToFix++]=choice;
3554              choice.possibleBranch=NULL;
3555#define FIXNOW
3556#ifdef FIXNOW
3557              double value = ceil(saveSolution[iColumn]);
3558              saveLower[iColumn]=value;
3559              solver->setColLower(iColumn,value);
3560              assert(doneHotStart);
3561              solver->unmarkHotStart();
3562              solver->resolve();
3563              solver->markHotStart();
3564              // may be infeasible (if other way stopped on iterations)
3565              if (!solver->isProvenOptimal()) {
3566                // neither side feasible
3567                anyAction=-2;
3568                delete choice.possibleBranch;
3569                choice.possibleBranch=NULL;
3570                //printf("Both infeasible for choice %d sequence %d\n",i,
3571                // model->object(choice.objectNumber)->columnNumber());
3572                delete ws;
3573                ws=NULL;
3574                break;
3575              }
3576#endif
3577            }
3578          }
3579        } else {
3580          if(choice.downMovement<1.0e100) {
3581            // down feasible, up infeasible
3582            anyAction=-1;
3583            worstFeasible = CoinMax(worstFeasible,choice.downMovement);
3584            model->messageHandler()->message(CBC_STRONG,*model->messagesPointer())
3585              << iObject << iColumn
3586              <<choice.downMovement<<choice.numIntInfeasDown
3587              <<choice.upMovement<<choice.numIntInfeasUp
3588              <<choice.possibleBranch->value()
3589              <<CoinMessageEol;
3590            //printf("Up infeasible for choice %d sequence %d\n",i,
3591            // model->object(choice.objectNumber)->columnNumber());
3592            if (!solveAll) {
3593              choice.possibleBranch->way(-1);
3594              choice.possibleBranch->branch();
3595              delete choice.possibleBranch;
3596              choice.possibleBranch=NULL;
3597              delete ws;
3598              ws=NULL;
3599              break;
3600            } else {
3601              choice.fix=-1;
3602              fixObject[numberToFix++]=choice;
3603              choice.possibleBranch=NULL;
3604#ifdef FIXNOW
3605              double value = floor(saveSolution[iColumn]);
3606              saveUpper[iColumn]=value;
3607              solver->setColUpper(iColumn,value);
3608              assert(doneHotStart);
3609              solver->unmarkHotStart();
3610              solver->resolve();
3611              solver->markHotStart();
3612              // may be infeasible (if other way stopped on iterations)
3613              if (!solver->isProvenOptimal()) {
3614                // neither side feasible
3615                anyAction=-2;
3616                delete choice.possibleBranch;
3617                choice.possibleBranch=NULL;
3618                //printf("Both infeasible for choice %d sequence %d\n",i,
3619                // model->object(choice.objectNumber)->columnNumber());
3620                delete ws;
3621                ws=NULL;
3622                break;
3623              }
3624#endif
3625            }
3626          } else {
3627            // neither side feasible
3628            anyAction=-2;
3629            delete choice.possibleBranch;
3630            choice.possibleBranch=NULL;
3631            //printf("Both infeasible for choice %d sequence %d\n",i,
3632            // model->object(choice.objectNumber)->columnNumber());
3633            delete ws;
3634            ws=NULL;
3635            break;
3636          }
3637        }
3638        // Check max time
3639        hitMaxTime = ( CoinCpuTime()-model->getDblParam(CbcModel::CbcStartSeconds) > 
3640                       model->getDblParam(CbcModel::CbcMaximumSeconds));
3641        if (hitMaxTime) {
3642          // make sure rest are fast
3643          doQuickly=true;
3644          for ( int jDo=iDo+1;jDo<numberToDo;jDo++) {
3645            int iObject = whichObject[iDo];
3646            OsiObject * object = model->modifiableObject(iObject);
3647            CbcSimpleIntegerDynamicPseudoCost * dynamicObject =
3648              dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(object) ;
3649            dynamicObject->setNumberBeforeTrust(0);
3650          }
3651          numberTest=0;
3652          distanceToCutoff=-COIN_DBL_MAX;
3653        }
3654        delete choice.possibleBranch;
3655      }
3656      double averageChange = model->sumChangeObjective()/((double) model->getNodeCount());
3657      if (depth_<10||worstFeasible>0.2*averageChange) 
3658        solveAll=false;
3659      if (model->messageHandler()->logLevel()>3||false) { 
3660        if (anyAction==-2) {
3661          printf("infeasible\n");
3662        } else if(anyAction==-1) {
3663          if (!solveAll)
3664            printf("%d fixed\n",numberToFix);
3665          else
3666            printf("%d fixed AND choosing %d iDo %d iChosenWhen %d numberToDo %d\n",numberToFix,bestChoice,
3667                   iDo,whichChoice,numberToDo);
3668        } else {
3669          printf("choosing %d  iDo %d iChosenWhen %d numberToDo %d\n",bestChoice,
3670                 iDo,whichChoice,numberToDo);
3671        }
3672      }
3673      if (doneHotStart) {
3674        // Delete the snapshot
3675        solver->unmarkHotStart();
3676        // back to normal
3677        solver->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,NULL) ;
3678        // restore basis
3679        solver->setWarmStart(ws);
3680      }
3681      solver->setIntParam(OsiMaxNumIterationHotStart,saveLimit);
3682      // Unless infeasible we will carry on
3683      // But we could fix anyway
3684      if (numberToFix&&!hitMaxTime) {
3685        if (anyAction==-2) {
3686          // take off
3687          for (i = 0 ; i < numberToFix ; i++) {
3688            delete fixObject[i].possibleBranch;
3689          }
3690        } else {
3691          // apply and take off
3692          for (i = 0 ; i < numberToFix ; i++) {
3693#ifndef FIXNOW
3694            fixObject[i].possibleBranch->way(fixObject[i].fix) ;
3695            fixObject[i].possibleBranch->branch() ;
3696#endif
3697            delete fixObject[i].possibleBranch;
3698          }
3699          bool feasible=true;
3700#if ACTION <2
3701          if (solveAll) {
3702            // can do quick optimality check
3703            int easy=2;
3704            solver->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,&easy) ;
3705            solver->resolve() ;
3706            solver->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,NULL) ;
3707            feasible = solver->isProvenOptimal();
3708            if (feasible) {
3709              anyAction=0;
3710              numberMini=0;
3711              memcpy(saveSolution,solver->getColSolution(),numberColumns*sizeof(double));
3712              model->reserveCurrentSolution(saveSolution);
3713              memcpy(saveLower,solver->getColLower(),numberColumns*sizeof(double));
3714              memcpy(saveUpper,solver->getColUpper(),numberColumns*sizeof(double));
3715              model->setPointers(solver);
3716              // See if candidate still possible
3717              if (branch_) {
3718                const OsiObject * object = model->object(bestChoice);
3719                int preferredWay;
3720                double infeasibility = object->infeasibility(&usefulInfo,preferredWay);
3721                if (!infeasibility) {
3722                  // take out
3723                  delete branch_;
3724                  branch_=NULL;
3725                } else {
3726                  CbcBranchingObject * branchObj =
3727                    dynamic_cast <CbcBranchingObject *>(branch_) ;
3728                  assert (branchObj);
3729                  branchObj->way(preferredWay);
3730                }
3731              }
3732            } else {
3733              anyAction=-2;
3734              finished=true;
3735            }
3736          }
3737#endif
3738          // If  fixed then round again
3739          if (!branch_&&anyAction!=-2) {
3740            finished=false;
3741          }
3742          // If these in then different action
3743#if ACTION == 1
3744          if (!anyAction)
3745            anyAction=-1;
3746          finished=true;
3747#endif
3748        }
3749      }
3750      delete ws;
3751    }
3752  }
3753  if (model->messageHandler()->logLevel()>2) 
3754    printf("%d strong, %d iters, %d pen, %d mark, %d fixed, action %d nnott %d nt %d, %d dq %s ns %d\n",
3755         numberStrongDone,numberStrongIterations,xPen,xMark,
3756           numberToFix,anyAction,numberNotTrusted,px[0],px[1],px[2]>0 ? "y" : "n",px[3]);
3757  // update number of strong iterations etc
3758  model->incrementStrongInfo(numberStrongDone,numberStrongIterations,
3759                             anyAction==-2 ? 0:numberToFix,anyAction==-2);
3760  if (!newWay) {
3761  if (((model->searchStrategy()+1)%1000)==0) {
3762    if (solver->messageHandler()->logLevel()>1)
3763      printf("%d strong, %d iters, %d inf, %d not finished, %d not trusted\n",
3764             numberStrongDone,numberStrongIterations,numberStrongInfeasible,numberUnfinished,
3765             numberNotTrusted);
3766    // decide what to do
3767    int strategy=1;
3768    if (numberUnfinished*4>numberStrongDone&&numberStrongInfeasible*10<numberStrongDone) {
3769      strategy=2;
3770      if (model->logLevel()>1)
3771        printf("going to strategy 2\n");
3772    }
3773    if (numberNodes)
3774      strategy=1;  // should only happen after hot start
3775    model->setSearchStrategy(strategy);
3776  }
3777  }
3778  //if (numberToFix&&depth_<5)
3779  //printf("%d fixed by strong at depth %d\n",numberToFix,depth_);
3780  // Set guessed solution value
3781  guessedObjectiveValue_ = objectiveValue_+estimatedDegradation;
3782 
3783  // Get collection of branches if mini tree wanted
3784  if (anyAction==0&&numberMini&&numberMini>1) {
3785    // Sort
3786    CoinSort_2(sort,sort+numberMini,whichObject);
3787    delete branch_;
3788    branch_=NULL;
3789    numberMini = CoinMin(numberMini,model->sizeMiniTree());
3790    anyAction=numberMini;
3791    branches = new OsiSolverBranch[numberMini];
3792    for (int iDo=0;iDo<numberMini;iDo++) {
3793      int iObject = whichObject[iDo];
3794      OsiObject * object = model->modifiableObject(iObject);
3795      CbcSimpleInteger * obj =
3796        dynamic_cast <CbcSimpleInteger *>(object) ;
3797      OsiSolverBranch * oneBranch;
3798      if (obj) {
3799        oneBranch = obj->solverBranch(solver,&usefulInfo);
3800      } else {
3801        CbcObject * obj =
3802          dynamic_cast <CbcObject *>(object) ;
3803        assert (obj);
3804        oneBranch = obj->solverBranch();
3805      }
3806      branches[iDo]=*oneBranch;
3807      delete oneBranch;
3808    }
3809  }
3810/*
3811  Cleanup, then we're finished
3812*/
3813  if (!model->branchingMethod())
3814    delete decision;
3815   
3816  delete [] fixObject;
3817  delete [] sort;
3818  delete [] whichObject;
3819  delete [] objectMark;
3820  delete [] saveLower;
3821  delete [] saveUpper;
3822  delete [] upEstimate;
3823  delete [] downEstimate;
3824# ifdef COIN_HAS_CLP
3825  if (osiclp) 
3826    osiclp->setSpecialOptions(saveClpOptions);
3827# endif
3828  // restore solution
3829  solver->setColSolution(saveSolution);
3830  model->reserveCurrentSolution(saveSolution);
3831  delete [] saveSolution;
3832  model->setStateOfSearch(saveStateOfSearch);
3833  model->setLogLevel(saveLogLevel);
3834  return anyAction;
3835}
3836int CbcNode::analyze (CbcModel *model, double * results)
3837{
3838  int i;
3839  int numberIterationsAllowed = model->numberAnalyzeIterations();
3840  OsiSolverInterface * solver = model->solver();
3841  objectiveValue_ = solver->getObjSense()*solver->getObjValue();
3842  double cutoff =model->getCutoff();
3843  const double * lower = solver->getColLower();
3844  const double * upper = solver->getColUpper();
3845  const double * dj = solver->getReducedCost();
3846  int numberObjects = model->numberObjects();
3847  int numberColumns = model->getNumCols();
3848  // Initialize arrays
3849  int numberIntegers = model->numberIntegers();
3850  int * back = new int[numberColumns];
3851  const int * integerVariable = model->integerVariable();
3852  for (i=0;i<numberColumns;i++) 
3853    back[i]=-1;
3854  // What results is
3855  double * newLower = results;
3856  double * objLower = newLower+numberIntegers;
3857  double * newUpper = objLower+numberIntegers;
3858  double * objUpper = newUpper+numberIntegers;
3859  for (i=0;i<numberIntegers;i++) {
3860    int iColumn = integerVariable[i];
3861    back[iColumn]=i;
3862    newLower[i]=0.0;
3863    objLower[i]=-COIN_DBL_MAX;
3864    newUpper[i]=0.0;
3865    objUpper[i]=-COIN_DBL_MAX;
3866  }
3867  double * saveUpper = new double[numberColumns];
3868  double * saveLower = new double[numberColumns];
3869  int anyAction=0;
3870  // Save solution in case heuristics need good solution later
3871 
3872  double * saveSolution = new double[numberColumns];
3873  memcpy(saveSolution,solver->getColSolution(),numberColumns*sizeof(double));
3874  model->reserveCurrentSolution(saveSolution);
3875  for (i=0;i<numberColumns;i++) {
3876    saveLower[i] = lower[i];
3877    saveUpper[i] = upper[i];
3878  }
3879  // Get arrays to sort
3880  double * sort = new double[numberObjects];
3881  int * whichObject = new int[numberObjects];
3882  int numberToFix=0;
3883  int numberToDo=0;
3884  double integerTolerance = 
3885    model->getDblParam(CbcModel::CbcIntegerTolerance);
3886  // point to useful information
3887  OsiBranchingInformation usefulInfo = model->usefulInformation();
3888  // and modify
3889  usefulInfo.depth_=depth_;
3890     
3891  // compute current state
3892  int numberObjectInfeasibilities; // just odd ones
3893  int numberIntegerInfeasibilities;
3894  model->feasibleSolution(
3895                          numberIntegerInfeasibilities,
3896                          numberObjectInfeasibilities);
3897# ifdef COIN_HAS_CLP
3898  OsiClpSolverInterface * osiclp = dynamic_cast< OsiClpSolverInterface*> (solver);
3899  int saveClpOptions=0;
3900  bool fastIterations = (model->specialOptions()&8)!=0;
3901  if (osiclp&&fastIterations) {
3902    // for faster hot start
3903    saveClpOptions = osiclp->specialOptions();
3904    osiclp->setSpecialOptions(saveClpOptions|8192);
3905  }
3906# else
3907  bool fastIterations = false ;
3908# endif
3909  /*
3910    Scan for branching objects that indicate infeasibility. Choose candidates
3911    using priority as the first criteria, then integer infeasibility.
3912   
3913    The algorithm is to fill the array with a set of good candidates (by
3914    infeasibility) with priority bestPriority.  Finding a candidate with
3915    priority better (less) than bestPriority flushes the choice array. (This
3916    serves as initialization when the first candidate is found.)
3917   
3918  */
3919  numberToDo=0;
3920  for (i=0;i<numberObjects;i++) {
3921    OsiObject * object = model->modifiableObject(i);
3922    CbcSimpleIntegerDynamicPseudoCost * dynamicObject =
3923      dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(object) ;
3924    if(!dynamicObject)
3925      continue;
3926    int preferredWay;
3927    double infeasibility = object->infeasibility(&usefulInfo,preferredWay);
3928    int iColumn = dynamicObject->columnNumber();
3929    if (saveUpper[iColumn]==saveLower[iColumn])
3930      continue;
3931    if (infeasibility)
3932      sort[numberToDo]=-1.0e10-infeasibility;
3933    else
3934      sort[numberToDo]=-fabs(dj[iColumn]);
3935    whichObject[numberToDo++]=i;
3936  }
3937  // Save basis
3938  CoinWarmStart * ws = solver->getWarmStart();
3939  int saveLimit;
3940  solver->getIntParam(OsiMaxNumIterationHotStart,saveLimit);
3941  int targetIterations = CoinMax(500,numberIterationsAllowed/numberObjects);
3942  if (saveLimit<targetIterations)
3943    solver->setIntParam(OsiMaxNumIterationHotStart,targetIterations); 
3944  // Mark hot start
3945  solver->markHotStart();
3946  // Sort
3947  CoinSort_2(sort,sort+numberToDo,whichObject);
3948  //double distanceToCutoff=model->getCutoff()-objectiveValue_;
3949  double * currentSolution = model->currentSolution();
3950  double objMin = 1.0e50;
3951  double objMax = -1.0e50;
3952  bool needResolve=false;
3953  int iDo;
3954  for (iDo=0;iDo<numberToDo;iDo++) {
3955    CbcStrongInfo choice;
3956    int iObject = whichObject[iDo];
3957    OsiObject * object = model->modifiableObject(iObject);
3958    CbcSimpleIntegerDynamicPseudoCost * dynamicObject =
3959      dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(object) ;
3960    int iColumn = dynamicObject->columnNumber();
3961    int preferredWay;
3962    object->infeasibility(&usefulInfo,preferredWay);
3963    double value = currentSolution[iColumn];
3964    double nearest = floor(value+0.5);
3965    double lowerValue = floor(value);
3966    bool satisfied=false;
3967    if (fabs(value-nearest)<=integerTolerance||value<saveLower[iColumn]||value>saveUpper[iColumn]) {
3968      satisfied=true;
3969      double newValue;
3970      if (nearest<saveUpper[iColumn]) {
3971        newValue = nearest + 1.0001*integerTolerance;
3972        lowerValue = nearest;
3973      } else {
3974        newValue = nearest - 1.0001*integerTolerance;
3975        lowerValue = nearest-1;
3976      }
3977      currentSolution[iColumn]=newValue;
3978    }
3979    double upperValue = lowerValue+1.0;
3980    CbcSimpleInteger * obj =
3981      dynamic_cast <CbcSimpleInteger *>(object) ;
3982    if (obj) {
3983      choice.possibleBranch=obj->createBranch(solver,&usefulInfo,preferredWay);
3984    } else {
3985      CbcObject * obj =
3986        dynamic_cast <CbcObject *>(object) ;
3987      assert (obj);
3988      choice.possibleBranch=obj->createBranch(preferredWay);
3989    }
3990    currentSolution[iColumn]=value;
3991    // Save which object it was
3992    choice.objectNumber=iObject;
3993    choice.numIntInfeasUp = numberUnsatisfied_;
3994    choice.numIntInfeasDown = numberUnsatisfied_;
3995    choice.downMovement = 0.0;
3996    choice.upMovement = 0.0;
3997    choice.numItersDown = 0;
3998    choice.numItersUp = 0;
3999    choice.fix=0; // say not fixed
4000    double objectiveChange ;
4001    double newObjectiveValue=1.0e100;
4002    int j;
4003    // status is 0 finished, 1 infeasible and other
4004    int iStatus;
4005    /*
4006      Try the down direction first. (Specify the initial branching alternative as
4007      down with a call to way(-1). Each subsequent call to branch() performs the
4008      specified branch and advances the branch object state to the next branch
4009      alternative.)
4010    */
4011    choice.possibleBranch->way(-1) ;
4012    choice.possibleBranch->branch() ;
4013    if (fabs(value-lowerValue)>integerTolerance) {
4014      solver->solveFromHotStart() ;
4015      /*
4016        We now have an estimate of objective degradation that we can use for strong
4017        branching. If we're over the cutoff, the variable is monotone up.
4018        If we actually made it to optimality, check for a solution, and if we have
4019        a good one, call setBestSolution to process it. Note that this may reduce the
4020        cutoff, so we check again to see if we can declare this variable monotone.
4021      */
4022      if (solver->isProvenOptimal())
4023        iStatus=0; // optimal
4024      else if (solver->isIterationLimitReached()
4025               &&!solver->isDualObjectiveLimitReached())
4026        iStatus=2; // unknown
4027      else
4028        iStatus=1; // infeasible
4029      newObjectiveValue = solver->getObjSense()*solver->getObjValue();
4030      choice.numItersDown = solver->getIterationCount();
4031      numberIterationsAllowed -= choice.numItersDown;
4032      objectiveChange = newObjectiveValue  - objectiveValue_;
4033      if (!iStatus) {
4034        choice.finishedDown = true ;
4035        if (newObjectiveValue>=cutoff) {
4036          objectiveChange = 1.0e100; // say infeasible
4037        } else {
4038          // See if integer solution
4039          if (model->feasibleSolution(choice.numIntInfeasDown,
4040                                      choice.numObjInfeasDown)
4041              &&model->problemFeasibility()->feasible(model,-1)>=0) {
4042            model->setBestSolution(CBC_STRONGSOL,
4043                                   newObjectiveValue,
4044                                   solver->getColSolution()) ;
4045            model->setLastHeuristic(NULL);
4046            model->incrementUsed(solver->getColSolution());
4047            cutoff =model->getCutoff();
4048            if (newObjectiveValue >= cutoff)    //  *new* cutoff
4049              objectiveChange = 1.0e100 ;
4050          }
4051        }
4052      } else if (iStatus==1) {
4053        objectiveChange = 1.0e100 ;
4054      } else {
4055        // Can't say much as we did not finish
4056        choice.finishedDown = false ;
4057      }
4058      choice.downMovement = objectiveChange ;
4059    }
4060    // restore bounds
4061    for ( j=0;j<numberColumns;j++) {
4062      if (saveLower[j] != lower[j])
4063        solver->setColLower(j,saveLower[j]);
4064      if (saveUpper[j] != upper[j])
4065        solver->setColUpper(j,saveUpper[j]);
4066    }
4067    // repeat the whole exercise, forcing the variable up
4068    choice.possibleBranch->branch();
4069    if (fabs(value-upperValue)>integerTolerance) {
4070      solver->solveFromHotStart() ;
4071      /*
4072        We now have an estimate of objective degradation that we can use for strong
4073        branching. If we're over the cutoff, the variable is monotone up.
4074        If we actually made it to optimality, check for a solution, and if we have
4075        a good one, call setBestSolution to process it. Note that this may reduce the
4076        cutoff, so we check again to see if we can declare this variable monotone.
4077      */
4078      if (solver->isProvenOptimal())
4079        iStatus=0; // optimal
4080      else if (solver->isIterationLimitReached()
4081               &&!solver->isDualObjectiveLimitReached())
4082        iStatus=2; // unknown
4083      else
4084        iStatus=1; // infeasible
4085      newObjectiveValue = solver->getObjSense()*solver->getObjValue();
4086      choice.numItersUp = solver->getIterationCount();
4087      numberIterationsAllowed -= choice.numItersUp;
4088      objectiveChange = newObjectiveValue  - objectiveValue_;
4089      if (!iStatus) {
4090        choice.finishedUp = true ;
4091        if (newObjectiveValue>=cutoff) {
4092          objectiveChange = 1.0e100; // say infeasible
4093        } else {
4094          // See if integer solution
4095          if (model->feasibleSolution(choice.numIntInfeasUp,
4096                                      choice.numObjInfeasUp)
4097              &&model->problemFeasibility()->feasible(model,-1)>=0) {
4098            model->setBestSolution(CBC_STRONGSOL,
4099                                   newObjectiveValue,
4100                                   solver->getColSolution()) ;
4101            model->setLastHeuristic(NULL);
4102            model->incrementUsed(solver->getColSolution());
4103            cutoff =model->getCutoff();
4104            if (newObjectiveValue >= cutoff)    //  *new* cutoff
4105              objectiveChange = 1.0e100 ;
4106          }
4107        }
4108      } else if (iStatus==1) {
4109        objectiveChange = 1.0e100 ;
4110      } else {
4111        // Can't say much as we did not finish
4112        choice.finishedUp = false ;
4113      }
4114      choice.upMovement = objectiveChange ;
4115     
4116      // restore bounds
4117      for ( j=0;j<numberColumns;j++) {
4118        if (saveLower[j] != lower[j])
4119          solver->setColLower(j,saveLower[j]);
4120        if (saveUpper[j] != upper[j])
4121          solver->setColUpper(j,saveUpper[j]);
4122      }
4123    }
4124    // If objective goes above certain amount we can set bound
4125    int jInt = back[iColumn];
4126    newLower[jInt]=upperValue;
4127    if (choice.finishedDown||!fastIterations)
4128      objLower[jInt]=choice.downMovement+objectiveValue_;
4129    else
4130      objLower[jInt]=objectiveValue_;
4131    newUpper[jInt]=lowerValue;
4132    if (choice.finishedUp||!fastIterations)
4133      objUpper[jInt]=choice.upMovement+objectiveValue_;
4134    else
4135      objUpper[jInt]=objectiveValue_;
4136    objMin = CoinMin(CoinMin(objLower[jInt],objUpper[jInt]),objMin);
4137    /*
4138      End of evaluation for this candidate variable. Possibilities are:
4139      * Both sides below cutoff; this variable is a candidate for branching.
4140      * Both sides infeasible or above the objective cutoff: no further action
4141      here. Break from the evaluation loop and assume the node will be purged
4142      by the caller.
4143      * One side below cutoff: Install the branch (i.e., fix the variable). Break
4144      from the evaluation loop and assume the node will be reoptimised by the
4145      caller.
4146    */
4147    if (choice.upMovement<1.0e100) {
4148      if(choice.downMovement<1.0e100) {
4149        objMax = CoinMax(CoinMax(objLower[jInt],objUpper[jInt]),objMax);
4150        // In case solution coming in was odd
4151        choice.upMovement = CoinMax(0.0,choice.upMovement);
4152        choice.downMovement = CoinMax(0.0,choice.downMovement);
4153        // feasible -
4154        model->messageHandler()->message(CBC_STRONG,*model->messagesPointer())
4155          << iObject << iColumn
4156          <<choice.downMovement<<choice.numIntInfeasDown
4157          <<choice.upMovement<<choice.numIntInfeasUp
4158          <<value
4159          <<CoinMessageEol;
4160      } else {
4161        // up feasible, down infeasible
4162        anyAction=-1;
4163        if (!satisfied)
4164          needResolve=true;
4165        choice.fix=1;
4166        numberToFix++;
4167        saveLower[iColumn]=upperValue;
4168        solver->setColLower(iColumn,upperValue);
4169      }
4170    } else {
4171      if(choice.downMovement<1.0e100) {
4172        // down feasible, up infeasible
4173        anyAction=-1;
4174        if (!satisfied)
4175          needResolve=true;
4176        choice.fix=-1;
4177        numberToFix++;
4178        saveUpper[iColumn]=lowerValue;
4179        solver->setColUpper(iColumn,lowerValue);
4180      } else {
4181        // neither side feasible
4182        anyAction=-2;
4183        printf("Both infeasible for choice %d sequence %d\n",i,
4184               model->object(choice.objectNumber)->columnNumber());
4185        delete ws;
4186        ws=NULL;
4187        //solver->writeMps("bad");
4188        numberToFix=-1;
4189        delete choice.possibleBranch;
4190        choice.possibleBranch=NULL;
4191        break;
4192      }
4193    }
4194    delete choice.possibleBranch;
4195    if (numberIterationsAllowed<=0)
4196      break;
4197    //printf("obj %d, col %d, down %g up %g value %g\n",iObject,iColumn,
4198    //     choice.downMovement,choice.upMovement,value);
4199  }
4200  printf("Best possible solution %g, can fix more if solution of %g found - looked at %d variables in %d iterations\n",
4201         objMin,objMax,iDo,model->numberAnalyzeIterations()-numberIterationsAllowed);
4202  model->setNumberAnalyzeIterations(numberIterationsAllowed);
4203  // Delete the snapshot
4204  solver->unmarkHotStart();
4205  // back to normal
4206  solver->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,NULL) ;
4207  solver->setIntParam(OsiMaxNumIterationHotStart,saveLimit);
4208  // restore basis
4209  solver->setWarmStart(ws);
4210  delete ws;
4211   
4212  delete [] sort;
4213  delete [] whichObject;
4214  delete [] saveLower;
4215  delete [] saveUpper;
4216  delete [] back;
4217  // restore solution
4218  solver->setColSolution(saveSolution);
4219# ifdef COIN_HAS_CLP
4220  if (osiclp) 
4221    osiclp->setSpecialOptions(saveClpOptions);
4222# endif
4223  model->reserveCurrentSolution(saveSolution);
4224  delete [] saveSolution;
4225  if (needResolve)
4226    solver->resolve();
4227  return numberToFix;
4228}
4229
4230
4231CbcNode::CbcNode(const CbcNode & rhs) 
4232{ 
4233#ifdef CHECK_NODE
4234  printf("CbcNode %x Constructor from rhs %x\n",this,&rhs);
4235#endif
4236  if (rhs.nodeInfo_)
4237    nodeInfo_ = rhs.nodeInfo_->clone();
4238  else
4239    nodeInfo_=NULL;
4240  objectiveValue_=rhs.objectiveValue_;
4241  guessedObjectiveValue_ = rhs.guessedObjectiveValue_;
4242  sumInfeasibilities_ = rhs.sumInfeasibilities_;
4243  if (rhs.branch_)
4244    branch_=rhs.branch_->clone();
4245  else
4246    branch_=NULL;
4247  depth_ = rhs.depth_;
4248  numberUnsatisfied_ = rhs.numberUnsatisfied_;
4249}
4250
4251CbcNode &
4252CbcNode::operator=(const CbcNode & rhs)
4253{
4254  if (this != &rhs) {
4255    delete nodeInfo_;
4256    if (rhs.nodeInfo_)
4257      nodeInfo_ = rhs.nodeInfo_->clone();
4258    else
4259      nodeInfo_ = NULL;
4260    objectiveValue_=rhs.objectiveValue_;
4261    guessedObjectiveValue_ = rhs.guessedObjectiveValue_;
4262    sumInfeasibilities_ = rhs.sumInfeasibilities_;
4263    if (rhs.branch_)
4264      branch_=rhs.branch_->clone();
4265    else
4266      branch_=NULL,
4267    depth_ = rhs.depth_;
4268    numberUnsatisfied_ = rhs.numberUnsatisfied_;
4269  }
4270  return *this;
4271}
4272CbcNode::~CbcNode ()
4273{
4274#ifdef CHECK_NODE
4275  if (nodeInfo_) 
4276    printf("CbcNode %x Destructor nodeInfo %x (%d)\n",
4277         this,nodeInfo_,nodeInfo_->numberPointingToThis());
4278  else
4279    printf("CbcNode %x Destructor nodeInfo %x (?)\n",
4280         this,nodeInfo_);
4281#endif
4282  if (nodeInfo_) {
4283    nodeInfo_->nullOwner();
4284    int numberToDelete=nodeInfo_->numberBranchesLeft();
4285    //    CbcNodeInfo * parent = nodeInfo_->parent();
4286    //assert (nodeInfo_->numberPointingToThis()>0);
4287    if (nodeInfo_->decrement(numberToDelete)==0) {
4288      delete nodeInfo_;
4289    } else {
4290      //printf("node %x nodeinfo %x parent %x\n",this,nodeInfo_,nodeInfo_->parent());
4291      // anyway decrement parent
4292      //if (parent)
4293      ///parent->decrement(1);
4294    }
4295  }
4296  delete branch_;
4297}
4298// Decrement  active cut counts
4299void 
4300CbcNode::decrementCuts(int change)
4301{
4302  if(nodeInfo_) {
4303    nodeInfo_->decrementCuts(change);
4304  }
4305}
4306void 
4307CbcNode::decrementParentCuts(int change)
4308{
4309  if(nodeInfo_) {
4310    nodeInfo_->decrementParentCuts(change);
4311  }
4312}
4313
4314/*
4315  Initialize reference counts (numberPointingToThis, numberBranchesLeft_)
4316  in the attached nodeInfo_.
4317*/
4318void
4319CbcNode::initializeInfo()
4320{
4321  assert(nodeInfo_ && branch_) ;
4322  nodeInfo_->initializeInfo(branch_->numberBranches());
4323}
4324// Nulls out node info
4325void 
4326CbcNode::nullNodeInfo()
4327{
4328  nodeInfo_=NULL;
4329}
4330
4331int
4332CbcNode::branch(OsiSolverInterface * solver)
4333{
4334  double changeInGuessed;
4335  if (!solver)
4336    changeInGuessed=branch_->branch();
4337  else
4338    changeInGuessed=branch_->branch(solver);
4339  guessedObjectiveValue_+= changeInGuessed;
4340  //#define PRINTIT
4341#ifdef PRINTIT
4342  int numberLeft = nodeInfo_->numberBranchesLeft();
4343  CbcNodeInfo * parent = nodeInfo_->parent();
4344  int parentNodeNumber = -1;
4345  //CbcBranchingObject * object1 = branch_->object_;
4346  //OsiObject * object = object1->
4347  //int sequence = object->columnNumber);
4348  int id=-1;
4349  double value=0.0;
4350  if (branch_) {
4351    id = branch_->variable();
4352    value = branch_->value();
4353  }
4354  printf("id %d value %g objvalue %g\n",id,value,objectiveValue_);
4355  if (parent)
4356    parentNodeNumber = parent->nodeNumber();
4357  printf("Node number %d, %s, way %d, depth %d, parent node number %d\n",
4358         nodeInfo_->nodeNumber(),(numberLeft==2) ? "leftBranch" : "rightBranch",
4359         way(),depth_,parentNodeNumber);
4360#endif
4361  return nodeInfo_->branchedOn();
4362}
4363/* Active arm of the attached OsiBranchingObject.
4364 
4365   In the simplest instance, coded -1 for the down arm of the branch, +1 for
4366   the up arm. But see OsiBranchingObject::way()
4367     Use nodeInfo--.numberBranchesLeft_ to see how active
4368*/
4369int 
4370CbcNode::way() const
4371{
4372  if (branch_) {
4373    CbcBranchingObject * obj =
4374      dynamic_cast <CbcBranchingObject *>(branch_) ;
4375    assert (obj);
4376    return obj->way();
4377  } else {
4378    return 0;
4379  }
4380}
4381/* Create a branching object for the node
4382
4383    The routine scans the object list of the model and selects a set of
4384    unsatisfied objects as candidates for branching. The candidates are
4385    evaluated, and an appropriate branch object is installed.
4386
4387    The numberPassesLeft is decremented to stop fixing one variable each time
4388    and going on and on (e.g. for stock cutting, air crew scheduling)
4389
4390    If evaluation determines that an object is monotone or infeasible,
4391    the routine returns immediately. In the case of a monotone object,
4392    the branch object has already been called to modify the model.
4393
4394    Return value:
4395    <ul>
4396      <li>  0: A branching object has been installed
4397      <li> -1: A monotone object was discovered
4398      <li> -2: An infeasible object was discovered
4399    </ul>
4400    Branch state:
4401    <ul>
4402      <li> -1: start
4403      <li> -1: A monotone object was discovered
4404      <li> -2: An infeasible object was discovered
4405    </ul>
4406*/
4407int 
4408CbcNode::chooseOsiBranch (CbcModel * model,
4409                          CbcNode * lastNode,
4410                          OsiBranchingInformation * usefulInfo,
4411                          int branchState)
4412{
4413  int returnStatus=0;
4414  if (lastNode)
4415    depth_ = lastNode->depth_+1;
4416  else
4417    depth_ = 0;
4418  OsiSolverInterface * solver = model->solver();
4419  objectiveValue_ = solver->getObjValue()*solver->getObjSense();
4420  usefulInfo->objectiveValue_ = objectiveValue_;
4421  usefulInfo->depth_ = depth_;
4422  const double * saveInfoSol = usefulInfo->solution_;
4423  double * saveSolution = new double[solver->getNumCols()];
4424  memcpy(saveSolution,solver->getColSolution(),solver->getNumCols()*sizeof(double));
4425  usefulInfo->solution_ = saveSolution;
4426  OsiChooseVariable * choose = model->branchingMethod()->chooseMethod();
4427  int numberUnsatisfied=-1;
4428  if (branchState<0) {
4429    // initialize
4430    // initialize sum of "infeasibilities"
4431    sumInfeasibilities_ = 0.0;
4432    numberUnsatisfied = choose->setupList(usefulInfo,true);
4433    numberUnsatisfied_ = numberUnsatisfied;
4434    branchState=0;
4435    if (numberUnsatisfied_<0) {
4436      // infeasible
4437      delete [] saveSolution;
4438      return -2;
4439    }
4440  }
4441  // unset best
4442  int best=-1;
4443  choose->setBestObjectIndex(-1);
4444  if (numberUnsatisfied) {
4445    if (branchState>0||!choose->numberOnList()) {
4446      // we need to return at once - don't do strong branching or anything
4447      if (choose->numberOnList()||!choose->numberStrong()) {
4448        best = choose->candidates()[0];
4449        choose->setBestObjectIndex(best);
4450      } else {
4451        // nothing on list - need to try again - keep any solution
4452        numberUnsatisfied = choose->setupList(usefulInfo, false);
4453        numberUnsatisfied_ = numberUnsatisfied;
4454        if (numberUnsatisfied) {
4455          best = choose->candidates()[0];
4456          choose->setBestObjectIndex(best);
4457        }
4458      }
4459    } else {
4460      // carry on with strong branching or whatever
4461      int returnCode = choose->chooseVariable(solver, usefulInfo,true);
4462      // update number of strong iterations etc
4463      model->incrementStrongInfo(choose->numberStrongDone(),choose->numberStrongIterations(),
4464                                 returnCode==-1 ? 0:choose->numberStrongFixed(),returnCode==-1);
4465      if (returnCode>1) {
4466        // has fixed some
4467        returnStatus=-1;
4468      } else if (returnCode==-1) {
4469        // infeasible
4470        returnStatus=-2;
4471      } else if (returnCode==0) {
4472        // normal
4473        returnStatus=0;
4474        numberUnsatisfied=1;
4475      } else {
4476        // ones on list satisfied - double check
4477        numberUnsatisfied = choose->setupList(usefulInfo, false);
4478        numberUnsatisfied_ = numberUnsatisfied;
4479        if (numberUnsatisfied) {
4480          best = choose->candidates()[0];
4481          choose->setBestObjectIndex(best);
4482        }
4483      }
4484    }
4485  } 
4486  delete branch_;
4487  branch_ = NULL;
4488  guessedObjectiveValue_ = COIN_DBL_MAX;//objectiveValue_; // for now
4489  if (!returnStatus) {
4490    if (numberUnsatisfied) {
4491      // create branching object
4492      const OsiObject * obj = model->solver()->object(choose->bestObjectIndex());
4493      //const OsiSolverInterface * solver = usefulInfo->solver_;
4494      branch_ = obj->createBranch(model->solver(),usefulInfo,obj->whichWay());
4495    }
4496  }
4497  usefulInfo->solution_=saveInfoSol;
4498  delete [] saveSolution;
4499  // may have got solution
4500  if (choose->goodSolution()
4501      &&model->problemFeasibility()->feasible(model,-1)>=0) {
4502    // yes
4503    double objValue = choose->goodObjectiveValue();
4504    model->setBestSolution(CBC_STRONGSOL,
4505                                     objValue,
4506                                     choose->goodSolution()) ;
4507    model->setLastHeuristic(NULL);
4508    model->incrementUsed(choose->goodSolution());
4509    choose->clearGoodSolution();
4510  }
4511  return returnStatus;
4512}
Note: See TracBrowser for help on using the repository browser.