source: trunk/Cbc/src/CbcModel.cpp @ 871

Last change on this file since 871 was 871, checked in by forrest, 11 years ago

add diving heuristics

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 418.2 KB
Line 
1// Copyright (C) 2002, International Business Machines
2// Corporation and others.  All Rights Reserved.
3#if defined(_MSC_VER)
4// Turn off compiler warning about long names
5#  pragma warning(disable:4786)
6#endif
7
8#include "CbcConfig.h"
9//static int nXXXXXX=0;
10
11#include <string>
12//#define CBC_DEBUG 1
13//#define CHECK_CUT_COUNTS
14//#define CHECK_NODE_FULL
15//#define NODE_LOG
16//#define GLOBAL_CUTS_JUST_POINTERS
17#ifndef CLP_FAST_CODE
18#ifdef NDEBUG
19#undef NDEBUG
20#endif
21#endif
22#include <cassert>
23#include <cmath>
24#include <cfloat>
25
26#ifdef COIN_HAS_CLP
27// include Presolve from Clp
28#include "ClpPresolve.hpp"
29#include "OsiClpSolverInterface.hpp"
30#endif
31
32#include "CbcEventHandler.hpp"
33
34#include "OsiSolverInterface.hpp"
35#include "OsiAuxInfo.hpp"
36#include "OsiSolverBranch.hpp"
37#include "OsiChooseVariable.hpp"
38#include "CoinWarmStartBasis.hpp"
39#include "CoinPackedMatrix.hpp"
40#include "CoinHelperFunctions.hpp"
41#include "CbcBranchActual.hpp"
42#include "CbcBranchDynamic.hpp"
43#include "CbcHeuristic.hpp"
44#include "CbcHeuristicFPump.hpp"
45#include "CbcModel.hpp"
46#include "CbcTreeLocal.hpp"
47#include "CbcStatistics.hpp"
48#include "CbcStrategy.hpp"
49#include "CbcMessage.hpp"
50#include "OsiRowCut.hpp"
51#include "OsiColCut.hpp"
52#include "OsiRowCutDebugger.hpp"
53#include "OsiCuts.hpp"
54#include "CbcCountRowCut.hpp"
55#include "CbcCutGenerator.hpp"
56#include "CbcFeasibilityBase.hpp"
57#include "CbcFathom.hpp"
58// include Probing
59#include "CglProbing.hpp"
60// include preprocessing
61#include "CglPreProcess.hpp"
62#include "CglDuplicateRow.hpp"
63#include "CglStored.hpp"
64#include "CglClique.hpp"
65
66#include "CoinTime.hpp"
67#include "CoinMpsIO.hpp"
68
69#include "CbcCompareActual.hpp"
70#include "CbcTree.hpp"
71//#define CBC_DETERMINISTIC_THREAD
72#ifdef CBC_THREAD
73#ifdef CBC_DETERMINISTIC_THREAD
74//#define DELETE_OUTSIDE
75#else
76#define CBC_NORMAL_THREAD
77#endif
78#include <pthread.h>
79#ifndef CLP_FAST_CODE
80#define CBC_THREAD_DEBUG 1
81#endif
82#ifdef CBC_THREAD_DEBUG
83#ifdef NDEBUG
84#undef NDEBUG
85#undef assert
86#         define assert(expression) {                              \
87             if (!(expression)) {                                          \
88                throw CoinError(__STRING(expression), __PRETTY_FUNCTION__, \
89                                "", __FILE__, __LINE__);                   \
90             }                                                             \
91          }
92#endif
93#endif
94// To Pass across to doOneNode
95typedef struct {
96  CbcModel * baseModel;
97  CbcModel * thisModel;
98  CbcNode * node; // filled in every time
99  CbcNode * createdNode; // filled in every time on return
100  pthread_t threadIdOfBase;
101  pthread_mutex_t * mutex; // for locking data
102  pthread_mutex_t * mutex2; // for waking up threads
103  pthread_cond_t * condition2; // for waking up thread
104  int returnCode; // -1 available, 0 busy, 1 finished , 2??
105  double timeLocked;
106  double timeWaitingToLock;
107  double timeWaitingToStart;
108  double timeInThread;
109  int numberTimesLocked;
110  int numberTimesUnlocked;
111  int numberTimesWaitingToStart;
112  int saveStuff[2];
113  struct timespec absTime;
114  bool locked;
115#if CBC_THREAD_DEBUG
116  int threadNumber;
117#endif
118#ifdef CBC_DETERMINISTIC_THREAD
119  CbcNode ** delNode;
120  int maxDeleteNode;
121  int nDeleteNode;
122  int nodesThisTime;
123  int iterationsThisTime;
124#endif
125} threadStruct;
126static void * doNodesThread(void * voidInfo);
127static void * doCutsThread(void * voidInfo);
128#endif
129/* Various functions local to CbcModel.cpp */
130
131namespace {
132
133//-------------------------------------------------------------------
134// Returns the greatest common denominator of two
135// positive integers, a and b, found using Euclid's algorithm
136//-------------------------------------------------------------------
137static int gcd(int a, int b) 
138{
139  int remainder = -1;
140  // make sure a<=b (will always remain so)
141  if(a > b) {
142    // Swap a and b
143    int temp = a;
144    a = b;
145    b = temp;
146  }
147  // if zero then gcd is nonzero (zero may occur in rhs of packed)
148  if (!a) {
149    if (b) {
150      return b;
151    } else {
152      printf("**** gcd given two zeros!!\n");
153      abort();
154    }
155  }
156  while (remainder) {
157    remainder = b % a;
158    b = a;
159    a = remainder;
160  }
161  return b;
162}
163
164
165
166#ifdef CHECK_NODE_FULL
167
168/*
169  Routine to verify that tree linkage is correct. The invariant that is tested
170  is
171
172  reference count = (number of actual references) + (number of branches left)
173
174  The routine builds a set of paired arrays, info and count, by traversing the
175  tree. Each CbcNodeInfo is recorded in info, and the number of times it is
176  referenced (via the parent field) is recorded in count. Then a final check is
177  made to see if the numberPointingToThis_ field agrees.
178*/
179
180void verifyTreeNodes (const CbcTree * branchingTree, const CbcModel &model)
181
182{if (model.getNodeCount()==661) return;  printf("*** CHECKING tree after %d nodes\n",model.getNodeCount()) ;
183 
184  int j ;
185  int nNodes = branchingTree->size() ;
186# define MAXINFO 1000
187  int *count = new int [MAXINFO] ;
188  CbcNodeInfo **info = new CbcNodeInfo*[MAXINFO] ;
189  int nInfo = 0 ;
190/*
191  Collect all CbcNodeInfo objects in info, by starting from each live node and
192  traversing back to the root. Nodes in the live set should have unexplored
193  branches remaining.
194
195  TODO: The `while (nodeInfo)' loop could be made to break on reaching a
196        common ancester (nodeInfo is found in info[k]). Alternatively, the
197        check could change to signal an error if nodeInfo is not found above a
198        common ancestor.
199*/
200  for (j = 0 ; j < nNodes ; j++)
201  { CbcNode *node = branchingTree->nodePointer(j) ;
202  if (!node)
203    continue;
204    CbcNodeInfo *nodeInfo = node->nodeInfo() ; 
205    int change = node->nodeInfo()->numberBranchesLeft() ;
206    assert(change) ;
207    while (nodeInfo)
208    { int k ;
209      for (k = 0 ; k < nInfo ; k++)
210      { if (nodeInfo == info[k]) break ; }
211      if (k == nInfo)
212      { assert(nInfo < MAXINFO) ;
213        nInfo++ ;
214        info[k] = nodeInfo ;
215        count[k] = 0 ; }
216      nodeInfo = nodeInfo->parent() ; } }
217/*
218  Walk the info array. For each nodeInfo, look up its parent in info and
219  increment the corresponding count.
220*/
221  for (j = 0 ; j < nInfo ; j++)
222  { CbcNodeInfo *nodeInfo = info[j] ;
223    nodeInfo = nodeInfo->parent() ;
224    if (nodeInfo)
225    { int k ;
226      for (k = 0 ; k < nInfo ; k++)
227      { if (nodeInfo == info[k]) break ; }
228      assert (k < nInfo) ;
229      count[k]++ ; } }
230/*
231  Walk the info array one more time and check that the invariant holds. The
232  number of references (numberPointingToThis()) should equal the sum of the
233  number of actual references (held in count[]) plus the number of potential
234  references (unexplored branches, numberBranchesLeft()).
235*/
236  for (j = 0;j < nInfo;j++) {
237    CbcNodeInfo * nodeInfo = info[j] ;
238    if (nodeInfo) {
239      int k ;
240      for (k = 0;k < nInfo;k++)
241        if (nodeInfo == info[k])
242          break ;
243      printf("Nodeinfo %x - %d left, %d count\n",
244             nodeInfo,
245             nodeInfo->numberBranchesLeft(),
246             nodeInfo->numberPointingToThis()) ;
247      assert(nodeInfo->numberPointingToThis() ==
248             count[k]+nodeInfo->numberBranchesLeft()) ; } }
249
250  delete [] count ;
251  delete [] info ;
252 
253  return ; }
254
255#endif  /* CHECK_NODE_FULL */
256
257
258
259#ifdef CHECK_CUT_COUNTS
260
261/*
262  Routine to verify that cut reference counts are correct.
263*/
264void verifyCutCounts (const CbcTree * branchingTree, CbcModel &model)
265
266{ printf("*** CHECKING cuts after %d nodes\n",model.getNodeCount()) ;
267
268  int j ;
269  int nNodes = branchingTree->size() ;
270
271/*
272  cut.tempNumber_ exists for the purpose of doing this verification. Clear it
273  in all cuts. We traverse the tree by starting from each live node and working
274  back to the root. At each CbcNodeInfo, check for cuts.
275*/
276  for (j = 0 ; j < nNodes ; j++)
277  { CbcNode *node = branchingTree->nodePointer(j) ;
278    CbcNodeInfo * nodeInfo = node->nodeInfo() ;
279    assert (node->nodeInfo()->numberBranchesLeft()) ;
280    while (nodeInfo)
281    { int k ;
282      for (k = 0 ; k < nodeInfo->numberCuts() ; k++)
283      { CbcCountRowCut *cut = nodeInfo->cuts()[k] ;
284        if (cut) cut->tempNumber_ = 0; }
285      nodeInfo = nodeInfo->parent() ; } }
286/*
287  Walk the live set again, this time collecting the list of cuts in use at each
288  node. addCuts1 will collect the cuts in model.addedCuts_. Take into account
289  that when we recreate the basis for a node, we compress out the slack cuts.
290*/
291  for (j = 0 ; j < nNodes ; j++)
292  { CoinWarmStartBasis *debugws = model.getEmptyBasis() ;
293    CbcNode *node = branchingTree->nodePointer(j) ;
294    CbcNodeInfo *nodeInfo = node->nodeInfo(); 
295    int change = node->nodeInfo()->numberBranchesLeft() ;
296    printf("Node %d %x (info %x) var %d way %d obj %g",j,node,
297           node->nodeInfo(),node->columnNumber(),node->way(),
298           node->objectiveValue()) ;
299
300    model.addCuts1(node,debugws) ;
301
302    int i ;
303    int numberRowsAtContinuous = model.numberRowsAtContinuous() ;
304    CbcCountRowCut **addedCuts = model.addedCuts() ;
305    for (i = 0 ; i < model.currentNumberCuts() ; i++)
306    { CoinWarmStartBasis::Status status = 
307        debugws->getArtifStatus(i+numberRowsAtContinuous) ;
308      if (status != CoinWarmStartBasis::basic && addedCuts[i])
309      { addedCuts[i]->tempNumber_ += change ; } }
310
311    while (nodeInfo)
312    { nodeInfo = nodeInfo->parent() ;
313      if (nodeInfo) printf(" -> %x",nodeInfo); }
314    printf("\n") ;
315    delete debugws ; }
316/*
317  The moment of truth: We've tallied up the references by direct scan of the
318  search tree. Check for agreement with the count in the cut.
319
320  TODO: Rewrite to check and print mismatch only when tempNumber_ == 0?
321*/
322  for (j = 0 ; j < nNodes ; j++)
323  { CbcNode *node = branchingTree->nodePointer(j) ;
324    CbcNodeInfo *nodeInfo = node->nodeInfo(); 
325    while (nodeInfo)
326    { int k ;
327      for (k = 0 ; k < nodeInfo->numberCuts() ; k++)
328      { CbcCountRowCut *cut = nodeInfo->cuts()[k] ;
329        if (cut && cut->tempNumber_ >= 0)
330        { if (cut->tempNumber_ != cut->numberPointingToThis()) 
331            printf("mismatch %x %d %x %d %d\n",nodeInfo,k,
332                    cut,cut->tempNumber_,cut->numberPointingToThis()) ;
333          else
334            printf("   match %x %d %x %d %d\n", nodeInfo,k,
335                   cut,cut->tempNumber_,cut->numberPointingToThis()) ;
336          cut->tempNumber_ = -1 ; } }
337      nodeInfo = nodeInfo->parent() ; } }
338
339  return ; }
340
341#endif /* CHECK_CUT_COUNTS */
342
343
344//#define CHECK_CUT_SIZE
345#ifdef CHECK_CUT_SIZE
346
347/*
348  Routine to verify that cut reference counts are correct.
349*/
350void verifyCutSize (const CbcTree * branchingTree, CbcModel &model)
351{ 
352
353  int j ;
354  int nNodes = branchingTree->size() ;
355  int totalCuts=0;
356
357/*
358  cut.tempNumber_ exists for the purpose of doing this verification. Clear it
359  in all cuts. We traverse the tree by starting from each live node and working
360  back to the root. At each CbcNodeInfo, check for cuts.
361*/
362  for (j = 0 ; j < nNodes ; j++) {
363    CbcNode *node = branchingTree->nodePointer(j) ;
364    CbcNodeInfo * nodeInfo = node->nodeInfo() ;
365    assert (node->nodeInfo()->numberBranchesLeft()) ;
366    while (nodeInfo) {
367      totalCuts += nodeInfo->numberCuts();
368      nodeInfo = nodeInfo->parent() ;
369    }
370  }
371  printf("*** CHECKING cuts (size) after %d nodes - %d cuts\n",model.getNodeCount(),totalCuts) ;
372  return ;
373}
374
375#endif /* CHECK_CUT_SIZE */
376
377}
378
379 /* End unnamed namespace for CbcModel.cpp */
380
381
382static double trueIncrement=0.0;
383void 
384CbcModel::analyzeObjective ()
385/*
386  Try to find a minimum change in the objective function. The first scan
387  checks that there are no continuous variables with non-zero coefficients,
388  and grabs the largest objective coefficient associated with an unfixed
389  integer variable. The second scan attempts to scale up the objective
390  coefficients to a point where they are sufficiently close to integer that
391  we can pretend they are integer, and calculate a gcd over the coefficients
392  of interest. This will be the minimum increment for the scaled coefficients.
393  The final action is to scale the increment back for the original coefficients
394  and install it, if it's better than the existing value.
395
396  John's note: We could do better than this.
397
398  John's second note - apologies for changing s to z
399*/
400{ const double *objective = getObjCoefficients() ;
401  const double *lower = getColLower() ;
402  const double *upper = getColUpper() ;
403  /*
404    Scan continuous and integer variables to see if continuous
405    are cover or network with integral rhs.
406  */
407  double continuousMultiplier = 1.0;
408  double * coeffMultiplier=NULL;
409  {
410    const double *rowLower = getRowLower() ;
411    const double *rowUpper = getRowUpper() ;
412    int numberRows = solver_->getNumRows() ;
413    double * rhs = new double [numberRows];
414    memset(rhs,0,numberRows*sizeof(double));
415    int iColumn;
416    int numberColumns = solver_->getNumCols() ;
417    // Column copy of matrix
418    bool allPlusOnes=true;
419    bool allOnes=true;
420    int problemType=-1;
421    const double * element = solver_->getMatrixByCol()->getElements();
422    const int * row = solver_->getMatrixByCol()->getIndices();
423    const CoinBigIndex * columnStart = solver_->getMatrixByCol()->getVectorStarts();
424    const int * columnLength = solver_->getMatrixByCol()->getVectorLengths();
425    for (iColumn=0;iColumn<numberColumns;iColumn++) {
426      if (upper[iColumn]==lower[iColumn]) {
427        CoinBigIndex start = columnStart[iColumn];
428        CoinBigIndex end = start + columnLength[iColumn];
429        for (CoinBigIndex j=start;j<end;j++) {
430          int iRow = row[j];
431          rhs[iRow] += lower[iColumn]*element[j];
432        }
433      }
434    }
435    int iRow;
436    for (iRow=0;iRow<numberRows;iRow++) {
437      if (rowLower[iRow]>-1.0e20&&
438          fabs(rowLower[iRow]-rhs[iRow]-floor(rowLower[iRow]-rhs[iRow]+0.5))>1.0e-10) {
439        continuousMultiplier=0.0;
440        break;
441      }
442      if (rowUpper[iRow]<1.0e20&&
443          fabs(rowUpper[iRow]-rhs[iRow]-floor(rowUpper[iRow]-rhs[iRow]+0.5))>1.0e-10) {
444        continuousMultiplier=0.0;
445        break;
446      }
447      // set rhs to limiting value
448      if (rowLower[iRow]!=rowUpper[iRow]) {
449        if(rowLower[iRow]>-1.0e20) {
450          if (rowUpper[iRow]<1.0e20) {
451            // no good
452            continuousMultiplier=0.0;
453            break;
454          } else {
455            rhs[iRow] = rowLower[iRow]-rhs[iRow];
456            if (problemType<0)
457              problemType=3; // set cover
458            else if (problemType!=3)
459              problemType=4;
460          }
461        } else {
462          rhs[iRow] = rowUpper[iRow]-rhs[iRow];
463            if (problemType<0)
464              problemType=1; // set partitioning <=
465            else if (problemType!=1)
466              problemType=4;
467        }
468      } else {
469        rhs[iRow] = rowUpper[iRow]-rhs[iRow];
470        if (problemType<0)
471          problemType=3; // set partitioning ==
472        else if (problemType!=2)
473          problemType=2;
474      }
475      if (fabs(rhs[iRow]-1.0)>1.0e-12)
476        problemType=4;
477    }
478    if (continuousMultiplier) {
479      // 1 network, 2 cover, 4 negative cover
480      int possible=7;
481      bool unitRhs=true;
482      // See which rows could be set cover
483      for (iColumn=0;iColumn<numberColumns;iColumn++) {
484        if (upper[iColumn] > lower[iColumn]+1.0e-8) {
485          CoinBigIndex start = columnStart[iColumn];
486          CoinBigIndex end = start + columnLength[iColumn];
487          for (CoinBigIndex j=start;j<end;j++) {
488            double value = element[j];
489            if (value==1.0) {
490            } else if (value==-1.0) {
491              rhs[row[j]]=-0.5;
492              allPlusOnes=false;
493            } else {
494              rhs[row[j]]=-COIN_DBL_MAX;
495              allOnes=false;
496            }
497          }
498        }
499      }
500      for (iColumn=0;iColumn<numberColumns;iColumn++) {
501        if (upper[iColumn] > lower[iColumn]+1.0e-8) {
502          if (!isInteger(iColumn)) {
503            CoinBigIndex start = columnStart[iColumn];
504            CoinBigIndex end = start + columnLength[iColumn];
505            double rhsValue=0.0;
506            // 1 all ones, -1 all -1s, 2 all +- 1, 3 no good
507            int type=0;
508            for (CoinBigIndex j=start;j<end;j++) {
509              double value = element[j];
510              if (fabs(value)!=1.0) {
511                type=3;
512                break;
513              } else if (value==1.0) {
514                if (!type) 
515                  type=1;
516                else if (type!=1)
517                  type=2;
518              } else {
519                if (!type) 
520                  type=-1;
521                else if (type!=-1)
522                  type=2;
523              }
524              int iRow = row[j];
525              if (rhs[iRow]==-COIN_DBL_MAX) {
526                type=3;
527                break;
528              } else if (rhs[iRow]==-0.5) {
529                // different values
530                unitRhs=false;
531              } else if (rhsValue) {
532                if (rhsValue!=rhs[iRow])
533                  unitRhs=false;
534              } else {
535                rhsValue=rhs[iRow];
536              }
537            }
538            // if no elements OK
539            if (type==3) {
540              // no good
541              possible=0;
542              break;
543            } else if (type==2) {
544              if (end-start>2) {
545                // no good
546                possible=0;
547                break;
548              } else {
549                // only network
550                possible &= 1;
551                if (!possible)
552                  break;
553              }
554            } else if (type==1) {
555              // only cover
556              possible &= 2;
557              if (!possible)
558                break;
559            } else if (type==-1) {
560              // only negative cover
561              possible &= 4;
562              if (!possible)
563                break;
564            }
565          }
566        }
567      }
568      if ((possible==2||possible==4)&&!unitRhs) {
569#ifdef COIN_DEVELOP
570        printf("XXXXXX Continuous all +1 but different rhs\n");
571#endif
572        possible=0;
573      }
574      // may be all integer
575      if (possible!=7) {
576        if (!possible)
577          continuousMultiplier=0.0;
578        else if (possible==1)
579          continuousMultiplier=1.0;
580        else 
581          continuousMultiplier=0.5;
582#ifdef COIN_DEVELOP
583        if (continuousMultiplier)
584          printf("XXXXXX multiplier of %g\n",continuousMultiplier);
585#endif
586        if (continuousMultiplier==0.5) {
587          coeffMultiplier=new double [numberColumns];
588          bool allOne=true;
589          for (iColumn=0;iColumn<numberColumns;iColumn++) {
590            coeffMultiplier[iColumn]=1.0;
591            if (upper[iColumn] > lower[iColumn]+1.0e-8) {
592              if (!isInteger(iColumn)) {
593                CoinBigIndex start = columnStart[iColumn];
594                int iRow = row[start];
595                double value = rhs[iRow];
596                assert (value>=0.0);
597                if (value!=0.0&&value!=1.0)
598                  allOne=false;
599                coeffMultiplier[iColumn]=0.5*value;
600              }
601            }
602          }
603          if (allOne) {
604            // back to old way
605            delete [] coeffMultiplier;
606            coeffMultiplier=NULL;
607          }
608        }
609      } else {
610        // all integer
611        problemType_= problemType;
612#ifdef COIN_DEVELOP
613        printf("Problem type is %d\n",problemType_);
614#endif
615      }
616    }
617    // But try again
618    if (continuousMultiplier<1.0) {
619      memset(rhs,0,numberRows*sizeof(double));
620      int * count = new int [numberRows];
621      memset(count,0,numberRows*sizeof(int));
622      for (iColumn=0;iColumn<numberColumns;iColumn++) {
623        CoinBigIndex start = columnStart[iColumn];
624        CoinBigIndex end = start + columnLength[iColumn];
625        if (upper[iColumn]==lower[iColumn]) {
626          for (CoinBigIndex j=start;j<end;j++) {
627            int iRow = row[j];
628            rhs[iRow] += lower[iColumn]*element[j];
629          }
630        } else if (solver_->isInteger(iColumn)) {
631          for (CoinBigIndex j=start;j<end;j++) {
632            int iRow = row[j];
633            if (fabs(element[j]-floor(element[j]+0.5))>1.0e-10) 
634              rhs[iRow]  = COIN_DBL_MAX;
635          }
636        } else {
637          for (CoinBigIndex j=start;j<end;j++) {
638            int iRow = row[j];
639            count[iRow]++;
640            if (fabs(element[j])!=1.0)
641              rhs[iRow]  = COIN_DBL_MAX;
642          }
643        }
644      }
645      // now look at continuous
646      bool allGood=true;
647      double direction = solver_->getObjSense() ;
648      int numberObj=0;
649      for (iColumn=0;iColumn<numberColumns;iColumn++) {
650        if (upper[iColumn]>lower[iColumn]) {
651          double objValue = objective[iColumn]*direction;
652          if (objValue&&!solver_->isInteger(iColumn)) {
653            numberObj++;
654            CoinBigIndex start = columnStart[iColumn];
655            CoinBigIndex end = start + columnLength[iColumn];
656            if (objValue>0.0) {
657              // wants to be as low as possible
658              if (lower[iColumn]<-1.0e10||fabs(lower[iColumn]-floor(lower[iColumn]+0.5))>1.0e-10) {
659                allGood=false;
660                break;
661              } else if (upper[iColumn]<1.0e10&&fabs(upper[iColumn]-floor(upper[iColumn]+0.5))>1.0e-10) {
662                allGood=false;
663                break;
664              }
665              bool singletonRow=true;
666              bool equality=false;
667              for (CoinBigIndex j=start;j<end;j++) {
668                int iRow = row[j];
669                if (count[iRow]>1)
670                  singletonRow=false;
671                else if (rowLower[iRow]==rowUpper[iRow])
672                  equality=true;
673                if (fabs(rhs[iRow])>1.0e20||fabs(rhs[iRow]-floor(rhs[iRow]+0.5))>1.0e-10
674                    ||fabs(element[j])!=1.0) {
675                  // no good
676                  allGood=false;
677                  break;
678                }
679                if (element[j]>0.0) {
680                  if (rowLower[iRow]>-1.0e20&&fabs(rowLower[iRow]-floor(rowLower[iRow]+0.5))>1.0e-10) {
681                    // no good
682                    allGood=false;
683                    break;
684                  }
685                } else {
686                  if (rowUpper[iRow]<1.0e20&&fabs(rowUpper[iRow]-floor(rowUpper[iRow]+0.5))>1.0e-10) {
687                    // no good
688                    allGood=false;
689                    break;
690                  }
691                }
692              }
693              if (!singletonRow&&end>start+1&&!equality)
694                allGood=false;
695              if (!allGood)
696                break;
697            } else {
698              // wants to be as high as possible
699              if (upper[iColumn]>1.0e10||fabs(upper[iColumn]-floor(upper[iColumn]+0.5))>1.0e-10) {
700                allGood=false;
701                break;
702              } else if (lower[iColumn]>-1.0e10&&fabs(lower[iColumn]-floor(lower[iColumn]+0.5))>1.0e-10) {
703                allGood=false;
704                break;
705              }
706              bool singletonRow=true;
707              bool equality=false;
708              for (CoinBigIndex j=start;j<end;j++) {
709                int iRow = row[j];
710                if (count[iRow]>1)
711                  singletonRow=false;
712                else if (rowLower[iRow]==rowUpper[iRow])
713                  equality=true;
714                if (fabs(rhs[iRow])>1.0e20||fabs(rhs[iRow]-floor(rhs[iRow]+0.5))>1.0e-10
715                    ||fabs(element[j])!=1.0) {
716                  // no good
717                  allGood=false;
718                  break;
719                }
720                if (element[j]<0.0) {
721                  if (rowLower[iRow]>-1.0e20&&fabs(rowLower[iRow]-floor(rowLower[iRow]+0.5))>1.0e-10) {
722                    // no good
723                    allGood=false;
724                    break;
725                  }
726                } else {
727                  if (rowUpper[iRow]<1.0e20&&fabs(rowUpper[iRow]-floor(rowUpper[iRow]+0.5))>1.0e-10) {
728                    // no good
729                    allGood=false;
730                    break;
731                  }
732                }
733              }
734              if (!singletonRow&&end>start+1&&!equality)
735                allGood=false;
736              if (!allGood)
737                break;
738            }
739          }
740        }
741      }
742      delete [] count;
743      if (allGood) {
744#ifdef COIN_DEVELOP
745        if (numberObj)
746          printf("YYYY analysis says all continuous with costs will be integer\n");
747#endif
748        continuousMultiplier=1.0;
749      }
750    }
751    delete [] rhs;
752  }
753/*
754  Take a first scan to see if there are unfixed continuous variables in the
755  objective.  If so, the minimum objective change could be arbitrarily small.
756  Also pick off the maximum coefficient of an unfixed integer variable.
757
758  If the objective is found to contain only integer variables, set the
759  fathoming discipline to strict.
760*/
761  double maximumCost = 0.0 ;
762  trueIncrement=0.0;
763  bool possibleMultiple = continuousMultiplier!=0.0 ;
764  int iColumn ;
765  int numberColumns = getNumCols() ;
766  if (possibleMultiple) {
767    for (iColumn = 0 ; iColumn < numberColumns ; iColumn++)
768      { if (upper[iColumn] > lower[iColumn]+1.0e-8)
769          { maximumCost = CoinMax(maximumCost,fabs(objective[iColumn])) ; } }
770  }
771  setIntParam(CbcModel::CbcFathomDiscipline,possibleMultiple) ;
772/*
773  If a nontrivial increment is possible, try and figure it out. We're looking
774  for gcd(c<j>) for all c<j> that are coefficients of unfixed integer
775  variables. Since the c<j> might not be integers, try and inflate them
776  sufficiently that they look like integers (and we'll deflate the gcd
777  later).
778
779  2520.0 is used as it is a nice multiple of 2,3,5,7
780*/
781    if (possibleMultiple&&maximumCost)
782    { int increment = 0 ;
783      double multiplier = 2520.0 ;
784      while (10.0*multiplier*maximumCost < 1.0e8)
785        multiplier *= 10.0 ;
786    int bigIntegers = 0; // Count of large costs which are integer
787    for (iColumn = 0 ; iColumn < numberColumns ; iColumn++) {
788      if (upper[iColumn] > lower[iColumn]+1.0e-8) {
789        double objValue = fabs(objective[iColumn]);
790        if (!isInteger(iColumn)) {
791          if (!coeffMultiplier)
792            objValue *= continuousMultiplier;
793          else
794            objValue *= coeffMultiplier[iColumn];
795        }
796        if (objValue) {
797          double value = objValue*multiplier ;
798          if (value <2.1e9) {
799            int nearest = (int) floor(value+0.5) ;
800            if (fabs(value-floor(value+0.5)) > 1.0e-8)
801              { increment = 0 ;
802              break ; }
803            else if (!increment)
804              { increment = nearest ; }
805            else
806              { increment = gcd(increment,nearest) ; }
807          } else {
808            // large value - may still be multiple of 1.0
809            if (fabs(objValue-floor(objValue+0.5)) > 1.0e-8) {
810              increment=0;
811              break;
812            } else {
813              bigIntegers++;
814            }
815          }
816        }
817      }
818    }
819    delete [] coeffMultiplier;
820/*
821  If the increment beats the current value for objective change, install it.
822*/
823      if (increment)
824      { double value = increment ;
825        double cutoff = getDblParam(CbcModel::CbcCutoffIncrement) ;
826        if (bigIntegers) {
827          // allow for 1.0
828          increment = gcd(increment,(int) multiplier);
829          value = increment;
830        }
831        value /= multiplier ;
832        trueIncrement=CoinMax(cutoff,value);;
833        if (value*0.999 > cutoff)
834        { messageHandler()->message(CBC_INTEGERINCREMENT,
835                                          messages())
836            << value << CoinMessageEol ;
837          setDblParam(CbcModel::CbcCutoffIncrement,value*0.999) ; } } }
838
839  return ; 
840}
841
842
843/**
844  \todo
845  Normally, it looks like we enter here from command dispatch in the main
846  routine, after calling the solver for an initial solution
847  (CbcModel::initialSolve, which simply calls the solver's initialSolve
848  routine.) The first thing we do is call resolve. Presumably there are
849  circumstances where this is nontrivial? There's also a call from
850  CbcModel::originalModel (tied up with integer presolve), which should be
851  checked.
852
853*/
854
855/*
856  The overall flow can be divided into three stages:
857    * Prep: Check that the lp relaxation remains feasible at the root. If so,
858      do all the setup for B&C.
859    * Process the root node: Generate cuts, apply heuristics, and in general do
860      the best we can to resolve the problem without B&C.
861    * Do B&C search until we hit a limit or exhaust the search tree.
862 
863  Keep in mind that in general there is no node in the search tree that
864  corresponds to the active subproblem. The active subproblem is represented
865  by the current state of the model,  of the solver, and of the constraint
866  system held by the solver.
867*/
868void CbcModel::branchAndBound(int doStatistics) 
869
870{
871/*
872  Capture a time stamp before we start.
873*/
874  dblParam_[CbcStartSeconds] = CoinCpuTime();
875  strongInfo_[0]=0;
876  strongInfo_[1]=0;
877  strongInfo_[2]=0;
878  numberStrongIterations_ = 0;
879  CoinThreadRandom randomGenerator(1234567);
880#ifdef COIN_HAS_CLP
881 {
882   OsiClpSolverInterface * clpSolver
883     = dynamic_cast<OsiClpSolverInterface *> (solver_);
884   if (clpSolver) {
885     // Initialise solvers seed
886     clpSolver->getModelPtr()->setRandomSeed(1234567);
887   }
888 }
889#endif
890#ifndef NDEBUG
891  {
892#ifdef COIN_DEVELOP
893    double big = 1.0e10;
894#else
895    double big = 1.0e20;
896#endif
897    int i;
898    int n = solver_->getNumCols();
899    const double *lower = solver_->getColLower() ;
900    const double *upper = solver_->getColUpper() ;
901    for (i=0;i<n;i++) {
902      assert (lower[i]<big);
903      assert (upper[i]>-big);
904    }
905    n = solver_->getNumRows();
906    lower = solver_->getRowLower() ;
907    upper = solver_->getRowUpper() ;
908    for (i=0;i<n;i++) {
909      assert (lower[i]<big);
910      assert (upper[i]>-big);
911    }
912  }
913#endif
914  // original solver (only set if pre-processing)
915  OsiSolverInterface * originalSolver=NULL;
916  int numberOriginalObjects=numberObjects_;
917  OsiObject ** originalObject = NULL;
918  // Set up strategies
919#if 0
920  std::string problemName ;
921  solver_->getStrParam(OsiProbName,problemName) ;
922  if (!strcmp(problemName.c_str(),"EGOUT")) solver_->activateRowCutDebugger(problemName.c_str()) ;
923#endif
924  if (strategy_) {
925    // May do preprocessing
926    originalSolver = solver_;
927    strategy_->setupOther(*this);
928    if (strategy_->preProcessState()) {
929      // pre-processing done
930      if (strategy_->preProcessState()<0) {
931        // infeasible
932        handler_->message(CBC_INFEAS,messages_)<< CoinMessageEol ;
933        status_ = 0 ;
934        secondaryStatus_ = 1;
935        originalContinuousObjective_ = COIN_DBL_MAX;
936        return ; 
937      } else if (numberObjects_&&object_) {
938        numberOriginalObjects=numberObjects_;
939        // redo sequence
940        numberIntegers_=0;
941        int numberColumns = getNumCols();
942        int nOrig = originalSolver->getNumCols();
943        CglPreProcess * process = strategy_->process();
944        assert (process);
945        const int * originalColumns = process->originalColumns();
946        // allow for cliques etc
947        nOrig = CoinMax(nOrig,originalColumns[numberColumns-1]+1);
948        // try and redo debugger
949        OsiRowCutDebugger * debugger = const_cast<OsiRowCutDebugger *> (solver_->getRowCutDebuggerAlways());
950        if (debugger)
951          debugger->redoSolution(numberColumns,originalColumns);
952        originalObject = object_;
953        // object number or -1
954        int * temp = new int[nOrig];
955        int iColumn;
956        for (iColumn=0;iColumn<nOrig;iColumn++) 
957          temp[iColumn]=-1;
958        int iObject;
959        int nNonInt=0;
960        for (iObject=0;iObject<numberOriginalObjects;iObject++) {
961          iColumn = originalObject[iObject]->columnNumber();
962          if (iColumn<0) {
963            nNonInt++;
964          } else {
965            temp[iColumn]=iObject;
966          }
967        }
968        int numberNewIntegers=0;
969        int numberOldIntegers=0;
970        int numberOldOther=0;
971        for (iColumn=0;iColumn<numberColumns;iColumn++) {
972          int jColumn = originalColumns[iColumn];
973          if (temp[jColumn]>=0) {
974            int iObject= temp[jColumn];
975            CbcSimpleInteger * obj =
976              dynamic_cast <CbcSimpleInteger *>(originalObject[iObject]) ;
977            if (obj) 
978              numberOldIntegers++;
979            else
980              numberOldOther++;
981          } else if (isInteger(iColumn)) {
982            numberNewIntegers++;
983          }
984        }
985        /*
986          Allocate an array to hold the indices of the integer variables.
987          Make a large enough array for all objects
988        */
989        numberObjects_= numberNewIntegers+numberOldIntegers+numberOldOther+nNonInt;
990        object_ = new OsiObject * [numberObjects_];
991        delete [] integerVariable_;
992        integerVariable_ = new int [numberNewIntegers+numberOldIntegers];
993        /*
994          Walk the variables again, filling in the indices and creating objects for
995          the integer variables. Initially, the objects hold the index and upper &
996          lower bounds.
997        */
998        numberIntegers_=0;
999        int n=originalColumns[numberColumns-1]+1;
1000        int * backward = new int[n];
1001        int i;
1002        for ( i=0;i<n;i++)
1003          backward[i]=-1;
1004        for (i=0;i<numberColumns;i++)
1005          backward[originalColumns[i]]=i;
1006        for (iColumn=0;iColumn<numberColumns;iColumn++) {
1007          int jColumn = originalColumns[iColumn];
1008          if (temp[jColumn]>=0) {
1009            int iObject= temp[jColumn];
1010            CbcSimpleInteger * obj =
1011              dynamic_cast <CbcSimpleInteger *>(originalObject[iObject]) ;
1012            if (obj) {
1013              object_[numberIntegers_] = originalObject[iObject]->clone();
1014              // redo ids etc
1015              //object_[numberIntegers_]->resetSequenceEtc(numberColumns,originalColumns);
1016              object_[numberIntegers_]->resetSequenceEtc(numberColumns,backward);
1017              integerVariable_[numberIntegers_++]=iColumn;
1018            }
1019          } else if (isInteger(iColumn)) {
1020            object_[numberIntegers_] =
1021              new CbcSimpleInteger(this,iColumn);
1022            integerVariable_[numberIntegers_++]=iColumn;
1023          }
1024        }
1025        delete [] backward;
1026        numberObjects_=numberIntegers_;
1027        // Now append other column stuff
1028        for (iColumn=0;iColumn<numberColumns;iColumn++) {
1029          int jColumn = originalColumns[iColumn];
1030          if (temp[jColumn]>=0) {
1031            int iObject= temp[jColumn];
1032            CbcSimpleInteger * obj =
1033              dynamic_cast <CbcSimpleInteger *>(originalObject[iObject]) ;
1034            if (!obj) {
1035              object_[numberObjects_] = originalObject[iObject]->clone();
1036              // redo ids etc
1037              CbcObject * obj =
1038              dynamic_cast <CbcObject *>(object_[numberObjects_]) ;
1039              assert (obj);
1040              obj->redoSequenceEtc(this,numberColumns,originalColumns);
1041              numberObjects_++;
1042            }
1043          }
1044        }
1045        // now append non column stuff
1046        for (iObject=0;iObject<numberOriginalObjects;iObject++) {
1047          iColumn = originalObject[iObject]->columnNumber();
1048          if (iColumn<0) {
1049            object_[numberObjects_] = originalObject[iObject]->clone();
1050            // redo ids etc
1051            CbcObject * obj =
1052              dynamic_cast <CbcObject *>(object_[numberObjects_]) ;
1053            assert (obj);
1054            obj->redoSequenceEtc(this,numberColumns,originalColumns);
1055            numberObjects_++;
1056          }
1057        }
1058        delete [] temp;
1059        if (!numberObjects_)
1060          handler_->message(CBC_NOINT,messages_) << CoinMessageEol ;
1061      } else {
1062        int numberColumns = getNumCols();
1063        CglPreProcess * process = strategy_->process();
1064        assert (process);
1065        const int * originalColumns = process->originalColumns();
1066        // try and redo debugger
1067        OsiRowCutDebugger * debugger = const_cast<OsiRowCutDebugger *> (solver_->getRowCutDebuggerAlways());
1068        if (debugger)
1069          debugger->redoSolution(numberColumns,originalColumns);
1070      }
1071    } else {
1072      //no preprocessing
1073      originalSolver=NULL;
1074    }
1075    strategy_->setupCutGenerators(*this);
1076    strategy_->setupHeuristics(*this);
1077    // Set strategy print level to models
1078    strategy_->setupPrinting(*this,handler_->logLevel());
1079  }
1080  eventHappened_=false;
1081  CbcEventHandler *eventHandler = getEventHandler() ;
1082  if (eventHandler)
1083    eventHandler->setModel(this);
1084#ifdef CLIQUE_ANALYSIS
1085  // set up for probing
1086  probingInfo_ = new CglTreeProbingInfo(solver_);
1087#else
1088  probingInfo_=NULL;
1089#endif
1090
1091  // Try for dominated columns
1092  if ((specialOptions_&64)!=0) {
1093    CglDuplicateRow dupcuts(solver_);
1094    dupcuts.setMode(2);
1095    CglStored * storedCuts = dupcuts.outDuplicates(solver_);
1096    addCutGenerator(storedCuts,1,"StoredCuts from dominated");
1097  }
1098  if (!nodeCompare_)
1099    nodeCompare_=new CbcCompareDefault();;
1100  // See if hot start wanted
1101  CbcCompareBase * saveCompare = NULL;
1102  if (hotstartSolution_) {
1103    if (strategy_&&strategy_->preProcessState()>0) {
1104      CglPreProcess * process = strategy_->process();
1105      assert (process);
1106      int n = solver_->getNumCols();
1107      const int * originalColumns = process->originalColumns();
1108      // columns should be in order ... but
1109      double * tempS = new double[n];
1110      for (int i=0;i<n;i++) {
1111        int iColumn = originalColumns[i];
1112        tempS[i]=hotstartSolution_[iColumn];
1113      }
1114      delete [] hotstartSolution_;
1115      hotstartSolution_=tempS;
1116      if (hotstartPriorities_) {
1117        int * tempP = new int [n];
1118        for (int i=0;i<n;i++) {
1119          int iColumn = originalColumns[i];
1120          tempP[i]=hotstartPriorities_[iColumn];
1121        }
1122        delete [] hotstartPriorities_;
1123        hotstartPriorities_=tempP;
1124      }
1125    }
1126    saveCompare = nodeCompare_;
1127    // depth first
1128    nodeCompare_ = new CbcCompareDepth();
1129  }
1130  if (!problemFeasibility_)
1131    problemFeasibility_=new CbcFeasibilityBase();
1132# ifdef CBC_DEBUG
1133  std::string problemName ;
1134  solver_->getStrParam(OsiProbName,problemName) ;
1135  printf("Problem name - %s\n",problemName.c_str()) ;
1136  solver_->setHintParam(OsiDoReducePrint,false,OsiHintDo,0) ;
1137# endif
1138/*
1139  Assume we're done, and see if we're proven wrong.
1140*/
1141  status_ = 0 ;
1142  secondaryStatus_ = 0;
1143  phase_=0;
1144/*
1145  Scan the variables, noting the integer variables. Create an
1146  CbcSimpleInteger object for each integer variable.
1147*/
1148  findIntegers(false) ;
1149  // Say not dynamic pseudo costs
1150  ownership_ &= ~0x40000000;
1151  // If dynamic pseudo costs then do
1152  if (numberBeforeTrust_)
1153    convertToDynamic();
1154  // Set up char array to say if integer
1155  delete [] integerInfo_;
1156  {
1157    int n = solver_->getNumCols();
1158    integerInfo_ = new char [n];
1159    for (int i=0;i<n;i++) {
1160      if (solver_->isInteger(i))
1161        integerInfo_[i]=1;
1162      else
1163        integerInfo_[i]=0;
1164    }
1165  }
1166  if (preferredWay_) {
1167    // set all unset ones
1168    for (int iObject = 0 ; iObject < numberObjects_ ; iObject++) {
1169      CbcObject * obj =
1170        dynamic_cast <CbcObject *>(object_[iObject]) ;
1171      if (obj&&!obj->preferredWay())
1172        obj->setPreferredWay(preferredWay_);
1173    }
1174  } 
1175/*
1176  Ensure that objects on the lists of OsiObjects, heuristics, and cut
1177  generators attached to this model all refer to this model.
1178*/
1179  synchronizeModel() ;
1180  if (!solverCharacteristics_) {
1181    OsiBabSolver * solverCharacteristics = dynamic_cast<OsiBabSolver *> (solver_->getAuxiliaryInfo());
1182    if (solverCharacteristics) {
1183      solverCharacteristics_ = solverCharacteristics;
1184    } else {
1185      // replace in solver
1186      OsiBabSolver defaultC;
1187      solver_->setAuxiliaryInfo(&defaultC);
1188      solverCharacteristics_ = dynamic_cast<OsiBabSolver *> (solver_->getAuxiliaryInfo());
1189    }
1190  }
1191
1192  solverCharacteristics_->setSolver(solver_);
1193  // Set so we can tell we are in initial phase in resolve
1194  continuousObjective_ = -COIN_DBL_MAX ;
1195/*
1196  Solve the relaxation.
1197
1198  Apparently there are circumstances where this will be non-trivial --- i.e.,
1199  we've done something since initialSolve that's trashed the solution to the
1200  continuous relaxation.
1201*/
1202  bool feasible;
1203  // If NLP then we assume already solved outside branchAndbound
1204  if (!solverCharacteristics_->solverType()||solverCharacteristics_->solverType()==4) {
1205    feasible=resolve(NULL,0) != 0 ;
1206  } else {
1207    // pick up given status
1208    feasible = (solver_->isProvenOptimal() &&
1209                !solver_->isDualObjectiveLimitReached()) ;
1210  }
1211  if (problemFeasibility_->feasible(this,0)<0) {
1212    feasible=false; // pretend infeasible
1213  }
1214/*
1215  If the linear relaxation of the root is infeasible, bail out now. Otherwise,
1216  continue with processing the root node.
1217*/
1218  if (!feasible) {
1219    status_ = 0 ;
1220    if (!solver_->isProvenDualInfeasible()) {
1221      handler_->message(CBC_INFEAS,messages_)<< CoinMessageEol ;
1222      secondaryStatus_ = 1;
1223    } else {
1224      handler_->message(CBC_UNBOUNDED,messages_)<< CoinMessageEol ;
1225      secondaryStatus_ = 7;
1226    }
1227    originalContinuousObjective_ = COIN_DBL_MAX;
1228    solverCharacteristics_ = NULL;
1229    return ;
1230  }
1231  // Convert to Osi if wanted
1232  bool useOsiBranching=false;
1233  //OsiBranchingInformation * persistentInfo = NULL;
1234  if (branchingMethod_&&branchingMethod_->chooseMethod()) {
1235    useOsiBranching=true;
1236    //persistentInfo = new OsiBranchingInformation(solver_);
1237    if (numberOriginalObjects) {
1238      for (int iObject = 0 ; iObject < numberObjects_ ; iObject++) {
1239        CbcObject * obj =
1240          dynamic_cast <CbcObject *>(object_[iObject]) ;
1241        if (obj) {
1242          CbcSimpleInteger * obj2 =
1243            dynamic_cast <CbcSimpleInteger *>(obj) ;
1244          if (obj2) {
1245            // back to Osi land
1246            object_[iObject]=obj2->osiObject();
1247            delete obj;
1248          } else {
1249            OsiSimpleInteger * obj3 =
1250              dynamic_cast <OsiSimpleInteger *>(obj) ;
1251            if (!obj3) {
1252              OsiSOS * obj4 =
1253                dynamic_cast <OsiSOS *>(obj) ;
1254              if (!obj4) {
1255                CbcSOS * obj5 =
1256                  dynamic_cast <CbcSOS *>(obj) ;
1257                if (obj5) {
1258                  // back to Osi land
1259                  object_[iObject]=obj5->osiObject(solver_);
1260                } else {
1261                  printf("Code up CbcObject type in Osi land\n");
1262                  abort();
1263                }
1264              }
1265            }
1266          }
1267        }
1268      }
1269      // and add to solver
1270      //if (!solver_->numberObjects()) {
1271        solver_->addObjects(numberObjects_,object_);
1272        //} else {
1273        //if (solver_->numberObjects()!=numberOriginalObjects) {
1274        //printf("should have trapped that solver has objects before\n");
1275        //abort();
1276        //}
1277        //}
1278    } else {
1279      // do from solver
1280      deleteObjects(false);
1281      solver_->findIntegersAndSOS(false);
1282      numberObjects_=solver_->numberObjects();
1283      object_ = solver_->objects();
1284      ownObjects_ = false;
1285    }
1286    branchingMethod_->chooseMethod()->setSolver(solver_);
1287  }
1288  // take off heuristics if have to
1289  if (numberHeuristics_) {
1290    int numberOdd=0;
1291    for (int i=0;i<numberObjects_;i++) {
1292      if (!object_[i]->canDoHeuristics()) 
1293        numberOdd++;
1294    }
1295    if (numberOdd) {
1296      int k=0;
1297      for (int i=0;i<numberHeuristics_;i++) {
1298        if (!heuristic_[i]->canDealWithOdd())
1299          delete heuristic_[i];
1300        else
1301          heuristic_[k++]=heuristic_[i];
1302      }
1303      if (!k) {
1304        delete [] heuristic_;
1305        heuristic_=NULL;
1306      }
1307      numberHeuristics_=k;
1308      handler_->message(CBC_HEURISTICS_OFF,messages_)<< numberOdd<<CoinMessageEol ;
1309    }
1310  }
1311  // Save objective (just so user can access it)
1312  originalContinuousObjective_ = solver_->getObjValue();
1313  bestPossibleObjective_=originalContinuousObjective_;
1314  sumChangeObjective1_=0.0;
1315  sumChangeObjective2_=0.0;
1316/*
1317  OsiRowCutDebugger knows an optimal answer for a subset of MIP problems.
1318  Assuming it recognises the problem, when called upon it will check a cut to
1319  see if it cuts off the optimal answer.
1320*/
1321  // If debugger exists set specialOptions_ bit
1322  if (solver_->getRowCutDebuggerAlways())
1323    specialOptions_ |= 1;
1324
1325# ifdef CBC_DEBUG
1326  if ((specialOptions_&1)==0)
1327    solver_->activateRowCutDebugger(problemName.c_str()) ;
1328  if (solver_->getRowCutDebuggerAlways())
1329    specialOptions_ |= 1;
1330# endif
1331
1332/*
1333  Begin setup to process a feasible root node.
1334*/
1335  bestObjective_ = CoinMin(bestObjective_,1.0e50) ;
1336  if (!bestSolution_) {
1337    numberSolutions_ = 0 ;
1338    numberHeuristicSolutions_ = 0 ;
1339  } 
1340  stateOfSearch_ = 0; 
1341  // Everything is minimization
1342  { 
1343    // needed to sync cutoffs
1344    double value ;
1345    solver_->getDblParam(OsiDualObjectiveLimit,value) ;
1346    dblParam_[CbcCurrentCutoff]= value * solver_->getObjSense();
1347  }
1348  double cutoff=getCutoff() ;
1349  double direction = solver_->getObjSense() ;
1350  dblParam_[CbcOptimizationDirection]=direction;
1351  if (cutoff < 1.0e20&&direction<0.0)
1352    messageHandler()->message(CBC_CUTOFF_WARNING1,
1353                                    messages())
1354                                      << cutoff << -cutoff << CoinMessageEol ;
1355  if (cutoff > bestObjective_)
1356    cutoff = bestObjective_ ;
1357  setCutoff(cutoff) ;
1358/*
1359  We probably already have a current solution, but just in case ...
1360*/
1361  int numberColumns = getNumCols() ;
1362  if (!currentSolution_)
1363    currentSolution_ = new double[numberColumns] ;
1364  testSolution_ = currentSolution_;
1365  /* Tell solver we are in Branch and Cut
1366     Could use last parameter for subtle differences */
1367  solver_->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,NULL) ;
1368#ifdef COIN_HAS_CLP
1369 {
1370   OsiClpSolverInterface * clpSolver
1371     = dynamic_cast<OsiClpSolverInterface *> (solver_);
1372   if (clpSolver) {
1373     //#define CLP_QUICK_OPTIONS
1374#ifdef CLP_QUICK_OPTIONS
1375     // Try and re-use regions   
1376     ClpSimplex * simplex = clpSolver->getModelPtr();
1377     simplex->setPersistenceFlag(1);
1378#if 0
1379     clpSolver->deleteScaleFactors();
1380     int value=131072;
1381     clpSolver->setSpecialOptions(clpSolver->specialOptions()|value);
1382     if ((clpSolver->specialOptions()&value)!=0)
1383       simplex->setSpecialOptions(simplex->specialOptions()|value);
1384#else
1385#undef CLP_QUICK_OPTIONS
1386     //if (simplex->numberRows()<50)
1387     //simplex->setAlphaAccuracy(1.0);
1388     //clpSolver->setSpecialOptions((clpSolver->specialOptions()&~128)|65536);
1389     //simplex->setMoreSpecialOptions(simplex->moreSpecialOptions()|4);
1390     //simplex->setSpecialOptions(simplex->specialOptions()|65536);
1391     //simplex->startPermanentArrays();
1392#endif
1393#endif
1394     if ((specialOptions_&32)==0) {
1395       ClpSimplex * clpSimplex = clpSolver->getModelPtr();
1396       // take off names
1397       clpSimplex->dropNames();
1398     }
1399     // no crunch if mostly continuous
1400     //int numberColumns = solver_->getNumCols()+1000000; // fake for testing
1401     int numberColumns = solver_->getNumCols();
1402     if (numberColumns>1000&&numberIntegers_*4<numberColumns)
1403       clpSolver->setSpecialOptions(clpSolver->specialOptions()&(~1));
1404   }
1405 }
1406#endif
1407/*
1408  Create a copy of the solver, thus capturing the original (root node)
1409  constraint system (aka the continuous system).
1410*/
1411  continuousSolver_ = solver_->clone() ;
1412
1413  numberRowsAtContinuous_ = getNumRows() ;
1414  solver_->saveBaseModel();
1415/*
1416  Check the objective to see if we can deduce a nontrivial increment. If
1417  it's better than the current value for CbcCutoffIncrement, it'll be
1418  installed.
1419*/
1420  if(solverCharacteristics_->reducedCostsAccurate())
1421    analyzeObjective() ;
1422/*
1423  Set up for cut generation. addedCuts_ holds the cuts which are relevant for
1424  the active subproblem. whichGenerator will be used to record the generator
1425  that produced a given cut.
1426*/
1427  maximumWhich_ = 1000 ;
1428  delete [] whichGenerator_;
1429  whichGenerator_ = new int[maximumWhich_] ;
1430  memset(whichGenerator_,0,maximumWhich_*sizeof(int));
1431  maximumNumberCuts_ = 0 ;
1432  currentNumberCuts_ = 0 ;
1433  delete [] addedCuts_ ;
1434  addedCuts_ = NULL ;
1435  OsiObject ** saveObjects=NULL;
1436  maximumRows_ = numberRowsAtContinuous_;
1437  workingBasis_.resize(maximumRows_,numberColumns);
1438/*
1439  Set up an empty heap and associated data structures to hold the live set
1440  (problems which require further exploration).
1441*/
1442  tree_->setComparison(*nodeCompare_) ;
1443/*
1444  Used to record the path from a node to the root of the search tree, so that
1445  we can then traverse from the root to the node when restoring a subproblem.
1446*/
1447  maximumDepth_ = 10 ;
1448  delete [] walkback_ ;
1449  walkback_ = new CbcNodeInfo * [maximumDepth_] ;
1450/*
1451  Used to generate bound edits for CbcPartialNodeInfo.
1452*/
1453  double * lowerBefore = new double [numberColumns] ;
1454  double * upperBefore = new double [numberColumns] ;
1455/*
1456 
1457  Generate cuts at the root node and reoptimise. solveWithCuts does the heavy
1458  lifting. It will iterate a generate/reoptimise loop (including reduced cost
1459  fixing) until no cuts are generated, the change in objective falls off,  or
1460  the limit on the number of rounds of cut generation is exceeded.
1461
1462  At the end of all this, any cuts will be recorded in cuts and also
1463  installed in the solver's constraint system. We'll have reoptimised, and
1464  removed any slack cuts (numberOldActiveCuts_ and numberNewCuts_ have been
1465  adjusted accordingly).
1466
1467  Tell cut generators they can be a bit more aggressive at root node
1468
1469  TODO: Why don't we make a copy of the solution after solveWithCuts?
1470  TODO: If numberUnsatisfied == 0, don't we have a solution?
1471*/
1472  phase_=1;
1473  int iCutGenerator;
1474  for (iCutGenerator = 0;iCutGenerator<numberCutGenerators_;iCutGenerator++) {
1475    CglCutGenerator * generator = generator_[iCutGenerator]->generator();
1476    generator->setAggressiveness(generator->getAggressiveness()+100);
1477  }
1478  OsiCuts cuts ;
1479  int anyAction = -1 ;
1480  numberOldActiveCuts_ = 0 ;
1481  numberNewCuts_ = 0 ;
1482  // Array to mark solution
1483  delete [] usedInSolution_;
1484  usedInSolution_ = new int[numberColumns];
1485  CoinZeroN(usedInSolution_,numberColumns);
1486/*
1487  For printing totals and for CbcNode (numberNodes_)
1488*/
1489  numberIterations_ = 0 ;
1490  numberNodes_ = 0 ;
1491  numberNodes2_ = 0 ;
1492  maximumStatistics_=0;
1493  maximumDepthActual_=0;
1494  numberDJFixed_=0.0;
1495  // Do heuristics
1496  doHeuristicsAtRoot();
1497  if ( intParam_[CbcMaxNumNode] < 0)
1498    eventHappened_=true; // stop as fast as possible
1499  statistics_ = NULL;
1500  // Do on switch
1501  if (doStatistics>0&&doStatistics<100) {
1502    maximumStatistics_=10000;
1503    statistics_ = new CbcStatistics * [maximumStatistics_];
1504    memset(statistics_,0,maximumStatistics_*sizeof(CbcStatistics *));
1505  }
1506
1507  { int iObject ;
1508    int preferredWay ;
1509    int numberUnsatisfied = 0 ;
1510    delete [] currentSolution_;
1511    currentSolution_ = new double [numberColumns];
1512    testSolution_ = currentSolution_;
1513    memcpy(currentSolution_,solver_->getColSolution(),
1514           numberColumns*sizeof(double)) ;
1515    // point to useful information
1516    OsiBranchingInformation usefulInfo=usefulInformation();
1517
1518    for (iObject = 0 ; iObject < numberObjects_ ; iObject++)
1519    { double infeasibility =
1520          object_[iObject]->infeasibility(&usefulInfo,preferredWay) ;
1521      if (infeasibility ) numberUnsatisfied++ ; }
1522    // replace solverType
1523    if(solverCharacteristics_->tryCuts())  {
1524
1525      if (numberUnsatisfied)   {
1526        // User event
1527        if (!eventHappened_)
1528          feasible = solveWithCuts(cuts,maximumCutPassesAtRoot_,
1529                                   NULL);
1530        else
1531          feasible=false;
1532      } else if (solverCharacteristics_->solutionAddsCuts()||
1533                 solverCharacteristics_->alwaysTryCutsAtRootNode()) {
1534        // may generate cuts and turn the solution
1535        //to an infeasible one
1536        feasible = solveWithCuts(cuts, 1,
1537                                 NULL);
1538      }
1539    }
1540    // check extra info on feasibility
1541    if (!solverCharacteristics_->mipFeasible())
1542      feasible = false;
1543  }
1544  // make cut generators less aggressive
1545  for (iCutGenerator = 0;iCutGenerator<numberCutGenerators_;iCutGenerator++) {
1546    CglCutGenerator * generator = generator_[iCutGenerator]->generator();
1547    generator->setAggressiveness(generator->getAggressiveness()-100);
1548  }
1549  currentNumberCuts_ = numberNewCuts_ ;
1550  // See if can stop on gap
1551  stoppedOnGap_ = false ;
1552  bestPossibleObjective_ = solver_->getObjValue()*solver_->getObjSense();
1553  double testGap = CoinMax(dblParam_[CbcAllowableGap],
1554                           CoinMax(fabs(bestObjective_),fabs(bestPossibleObjective_))
1555                           *dblParam_[CbcAllowableFractionGap]);
1556  if (bestObjective_-bestPossibleObjective_ < testGap && getCutoffIncrement()>=0.0) {
1557    if (bestPossibleObjective_<getCutoff())
1558      stoppedOnGap_ = true ;
1559    feasible = false;
1560  }
1561  // User event
1562  if (eventHappened_)
1563    feasible=false;
1564/*
1565  We've taken the continuous relaxation as far as we can. Time to branch.
1566  The first order of business is to actually create a node. chooseBranch
1567  currently uses strong branching to evaluate branch object candidates,
1568  unless forced back to simple branching. If chooseBranch concludes that a
1569  branching candidate is monotone (anyAction == -1) or infeasible (anyAction
1570  == -2) when forced to integer values, it returns here immediately.
1571
1572  Monotone variables trigger a call to resolve(). If the problem remains
1573  feasible, try again to choose a branching variable. At the end of the loop,
1574  resolved == true indicates that some variables were fixed.
1575
1576  Loss of feasibility will result in the deletion of newNode.
1577*/
1578
1579  bool resolved = false ;
1580  CbcNode *newNode = NULL ;
1581  numberFixedAtRoot_=0;
1582  numberFixedNow_=0;
1583  int numberIterationsAtContinuous = numberIterations_;
1584  //solverCharacteristics_->setSolver(solver_);
1585  if (feasible) {
1586    if (probingInfo_) {
1587      int number01 = probingInfo_->numberIntegers();
1588      //const fixEntry * entry = probingInfo_->fixEntries();
1589      const int * toZero = probingInfo_->toZero();
1590      //const int * toOne = probingInfo_->toOne();
1591      //const int * integerVariable = probingInfo_->integerVariable();
1592      if (toZero[number01]) {
1593        for (int i = 0;i<numberCutGenerators_;i++) {
1594          CglFakeClique * clique = dynamic_cast<CglFakeClique*>(generator_[i]->generator());
1595          if (clique) {
1596            OsiSolverInterface * fakeSolver = probingInfo_->analyze(*solver_,1);
1597            if (fakeSolver) {
1598              printf("Probing fake solver has %d rows\n",fakeSolver->getNumRows());
1599              //if (fakeSolver)
1600              //fakeSolver->writeMps("bad");
1601              if (generator_[i]->numberCutsInTotal())
1602                generator_[i]->setHowOften(1);
1603            }
1604            clique->assignSolver(fakeSolver);
1605            //stored->setProbingInfo(probingInfo_);
1606            break;
1607          }
1608        }
1609      }
1610      delete probingInfo_;
1611      probingInfo_=NULL;
1612    }
1613    newNode = new CbcNode ;
1614    // Set objective value (not so obvious if NLP etc)
1615    setObjectiveValue(newNode,NULL);
1616    anyAction = -1 ;
1617    // To make depth available we may need a fake node
1618    CbcNode fakeNode;
1619    if (!currentNode_) {
1620      // Not true if sub trees assert (!numberNodes_);
1621      currentNode_=&fakeNode;
1622    }
1623    phase_=3;
1624    // only allow 1000 passes
1625    int numberPassesLeft=1000;
1626    // This is first crude step
1627    if (numberAnalyzeIterations_) {
1628      delete [] analyzeResults_;
1629      analyzeResults_ = new double [4*numberIntegers_];
1630      numberFixedAtRoot_=newNode->analyze(this,analyzeResults_);
1631      if (numberFixedAtRoot_>0) {
1632        printf("%d fixed by analysis\n",numberFixedAtRoot_);
1633        setPointers(solver_);
1634        numberFixedNow_ = numberFixedAtRoot_;
1635      } else if (numberFixedAtRoot_<0) {
1636        printf("analysis found to be infeasible\n");
1637        anyAction=-2;
1638        delete newNode ;
1639        newNode = NULL ;
1640        feasible = false ;
1641      }
1642    }
1643    OsiSolverBranch * branches = NULL;
1644    anyAction = chooseBranch(newNode, numberPassesLeft, NULL, cuts,resolved,
1645                             NULL,NULL,NULL,branches);
1646    if (anyAction == -2||newNode->objectiveValue() >= cutoff) {
1647      if (anyAction != -2) {
1648        // zap parent nodeInfo
1649#ifdef COIN_DEVELOP
1650        printf("zapping CbcNodeInfo %x\n",newNode->nodeInfo()->parent());
1651#endif
1652        if (newNode->nodeInfo())
1653          newNode->nodeInfo()->nullParent();
1654      }
1655      delete newNode ;
1656      newNode = NULL ;
1657      feasible = false ;
1658    }
1659  }
1660/*
1661  At this point, the root subproblem is infeasible or fathomed by bound
1662  (newNode == NULL), or we're live with an objective value that satisfies the
1663  current objective cutoff.
1664*/
1665  assert (!newNode || newNode->objectiveValue() <= cutoff) ;
1666  // Save address of root node as we don't want to delete it
1667  // initialize for print out
1668  int lastDepth=0;
1669  int lastUnsatisfied=0;
1670  if (newNode)
1671    lastUnsatisfied=newNode->numberUnsatisfied();
1672/*
1673  The common case is that the lp relaxation is feasible but doesn't satisfy
1674  integrality (i.e., newNode->branchingObject(), indicating we've been able to
1675  select a branching variable). Remove any cuts that have gone slack due to
1676  forcing monotone variables. Then tack on an CbcFullNodeInfo object and full
1677  basis (via createInfo()) and stash the new cuts in the nodeInfo (via
1678  addCuts()). If, by some miracle, we have an integral solution at the root
1679  (newNode->branchingObject() is NULL), takeOffCuts() will ensure that the solver holds
1680  a valid solution for use by setBestSolution().
1681*/
1682  CoinWarmStartBasis *lastws = NULL ;
1683  if (feasible && newNode->branchingObject())
1684  { if (resolved)
1685    { takeOffCuts(cuts,false,NULL) ;
1686#     ifdef CHECK_CUT_COUNTS
1687      { printf("Number of rows after chooseBranch fix (root)"
1688               "(active only) %d\n",
1689                numberRowsAtContinuous_+numberNewCuts_+numberOldActiveCuts_) ;
1690        const CoinWarmStartBasis* debugws =
1691          dynamic_cast <const CoinWarmStartBasis*>(solver_->getWarmStart()) ;
1692        debugws->print() ;
1693        delete debugws ; }
1694#     endif
1695    }
1696  //newNode->createInfo(this,NULL,NULL,NULL,NULL,0,0) ;
1697    newNode->nodeInfo()->addCuts(cuts,
1698                                 newNode->numberBranches(),whichGenerator_) ;
1699    if (lastws) delete lastws ;
1700    lastws = dynamic_cast<CoinWarmStartBasis*>(solver_->getWarmStart()) ;
1701  }
1702/*
1703  Continuous data to be used later
1704*/
1705  continuousObjective_ = solver_->getObjValue()*solver_->getObjSense();
1706  continuousInfeasibilities_ = 0 ;
1707  if (newNode)
1708  { continuousObjective_ = newNode->objectiveValue() ;
1709    delete [] continuousSolution_;
1710    continuousSolution_ = CoinCopyOfArray(solver_->getColSolution(),
1711                                             numberColumns);
1712    continuousInfeasibilities_ = newNode->numberUnsatisfied() ; }
1713/*
1714  Bound may have changed so reset in objects
1715*/
1716  { int i ;
1717    for (i = 0;i < numberObjects_;i++)
1718      object_[i]->resetBounds(solver_) ; }
1719/*
1720  Feasible? Then we should have either a live node prepped for future
1721  expansion (indicated by variable() >= 0), or (miracle of miracles) an
1722  integral solution at the root node.
1723
1724  initializeInfo sets the reference counts in the nodeInfo object.  Since
1725  this node is still live, push it onto the heap that holds the live set.
1726*/
1727  double bestValue = 0.0 ;
1728  if (newNode) {
1729    bestValue = newNode->objectiveValue();
1730    if (newNode->branchingObject()) {
1731      newNode->initializeInfo() ;
1732      tree_->push(newNode) ;
1733      if (statistics_) {
1734        if (numberNodes2_==maximumStatistics_) {
1735          maximumStatistics_ = 2*maximumStatistics_;
1736          CbcStatistics ** temp = new CbcStatistics * [maximumStatistics_];
1737          memset(temp,0,maximumStatistics_*sizeof(CbcStatistics *));
1738          memcpy(temp,statistics_,numberNodes2_*sizeof(CbcStatistics *));
1739          delete [] statistics_;
1740          statistics_=temp;
1741        }
1742        assert (!statistics_[numberNodes2_]);
1743        statistics_[numberNodes2_]=new CbcStatistics(newNode);
1744      }
1745      numberNodes2_++;
1746#     ifdef CHECK_NODE
1747      printf("Node %x on tree\n",newNode) ;
1748#     endif
1749    } else {
1750      // continuous is integer
1751      double objectiveValue = newNode->objectiveValue();
1752      setBestSolution(CBC_SOLUTION,objectiveValue,
1753                      solver_->getColSolution()) ;
1754      delete newNode ;
1755      newNode = NULL ;
1756    }
1757  }
1758
1759  if (printFrequency_ <= 0) {
1760    printFrequency_ = 1000 ;
1761    if (getNumCols() > 2000)
1762      printFrequency_ = 100 ;
1763  }
1764  /*
1765    It is possible that strong branching fixes one variable and then the code goes round
1766    again and again.  This can take too long.  So we need to warn user - just once.
1767  */
1768  numberLongStrong_=0;
1769  double totalTime = 0.0;
1770#ifdef CBC_THREAD
1771  CbcNode * createdNode=NULL;
1772  CbcModel ** threadModel = NULL;
1773  pthread_t * threadId = NULL;
1774  int * threadCount = NULL;
1775  pthread_mutex_t mutex;
1776  pthread_cond_t condition_main;
1777  pthread_mutex_t condition_mutex;
1778  pthread_mutex_t * mutex2 = NULL;
1779  pthread_cond_t * condition2 = NULL;
1780  threadStruct * threadInfo = NULL;
1781#ifdef CBC_NORMAL_THREAD
1782  bool locked=false;
1783#endif
1784  int threadStats[6];
1785#ifdef CBC_DETERMINISTIC_THREAD
1786  int defaultParallelIterations=500;
1787  int defaultParallelNodes=10;
1788#endif
1789  memset(threadStats,0,sizeof(threadStats));
1790  double timeWaiting=0.0;
1791  // For now just one model
1792  if (numberThreads_) {
1793    nodeCompare_->sayThreaded(); // need to use addresses
1794    threadId = new pthread_t [numberThreads_];
1795    threadCount = new int [numberThreads_];
1796    CoinZeroN(threadCount,numberThreads_);
1797    pthread_mutex_init(&mutex,NULL);
1798    pthread_cond_init(&condition_main,NULL);
1799    pthread_mutex_init(&condition_mutex,NULL);
1800    threadModel = new CbcModel * [numberThreads_+1];
1801    threadInfo = new threadStruct [numberThreads_+1];
1802    mutex2 = new pthread_mutex_t [numberThreads_];
1803    condition2 = new pthread_cond_t [numberThreads_];
1804#ifdef CBC_DETERMINISTIC_THREAD
1805    // May need for deterministic
1806    saveObjects=new OsiObject * [numberObjects_];
1807    for (int i=0;i<numberObjects_;i++) {
1808      saveObjects[i] = object_[i]->clone();
1809    }
1810#endif
1811    // we don't want a strategy object
1812    CbcStrategy * saveStrategy = strategy_;
1813    strategy_ = NULL;
1814    for (int i=0;i<numberThreads_;i++) {
1815      pthread_mutex_init(mutex2+i,NULL);
1816      pthread_cond_init(condition2+i,NULL);
1817      threadId[i]=0;
1818      threadInfo[i].baseModel=this;
1819      threadModel[i]=new CbcModel(*this);
1820#ifdef COIN_HAS_CLP
1821      // Solver may need to know about model
1822      CbcModel * thisModel = threadModel[i];
1823      CbcOsiSolver * solver =
1824              dynamic_cast<CbcOsiSolver *>(thisModel->solver()) ;
1825      if (solver)
1826        solver->setCbcModel(thisModel);
1827#endif
1828      mutex_ = (void *) (threadInfo+i);
1829      threadModel[i]->moveToModel(this,-1);
1830      threadInfo[i].thisModel=threadModel[i];
1831      threadInfo[i].node=NULL;
1832      threadInfo[i].createdNode=NULL;
1833      threadInfo[i].threadIdOfBase=pthread_self();
1834      threadInfo[i].mutex=&mutex;
1835      threadInfo[i].mutex2=mutex2+i;
1836      threadInfo[i].condition2=condition2+i;
1837      threadInfo[i].returnCode=-1;
1838      threadInfo[i].timeLocked=0.0;
1839      threadInfo[i].timeWaitingToLock=0.0;
1840      threadInfo[i].timeWaitingToStart=0.0;
1841      threadInfo[i].timeInThread=0.0;
1842      threadInfo[i].numberTimesLocked=0;
1843      threadInfo[i].numberTimesUnlocked=0;
1844      threadInfo[i].numberTimesWaitingToStart=0;
1845      threadInfo[i].locked=false;
1846#if CBC_THREAD_DEBUG
1847      threadInfo[i].threadNumber=i+2;
1848#endif
1849#ifdef CBC_DETERMINISTIC_THREAD
1850      threadInfo[i].delNode = NULL;
1851      threadInfo[i].maxDeleteNode=0;
1852      threadInfo[i].nDeleteNode=0;
1853      threadInfo[i].nodesThisTime=0;
1854      threadInfo[i].iterationsThisTime=0;
1855#endif
1856      pthread_create(threadId+i,NULL,doNodesThread,threadInfo+i);
1857    }
1858    strategy_ = saveStrategy;
1859    // Do a partial one for base model
1860    threadInfo[numberThreads_].baseModel=this;
1861    threadModel[numberThreads_]=this;
1862    mutex_ = (void *) (threadInfo+numberThreads_);
1863    threadInfo[numberThreads_].node=NULL;
1864    threadInfo[numberThreads_].mutex=&mutex;
1865    threadInfo[numberThreads_].condition2=&condition_main;
1866    threadInfo[numberThreads_].mutex2=&condition_mutex;
1867    threadInfo[numberThreads_].timeLocked=0.0;
1868    threadInfo[numberThreads_].timeWaitingToLock=0.0;
1869    threadInfo[numberThreads_].numberTimesLocked=0;
1870    threadInfo[numberThreads_].numberTimesUnlocked=0;
1871    threadInfo[numberThreads_].locked=false;
1872#if CBC_THREAD_DEBUG
1873    threadInfo[numberThreads_].threadNumber=1;
1874#endif
1875  }
1876#endif
1877/*
1878  At last, the actual branch-and-cut search loop, which will iterate until
1879  the live set is empty or we hit some limit (integrality gap, time, node
1880  count, etc.). The overall flow is to rebuild a subproblem, reoptimise using
1881  solveWithCuts(), choose a branching pattern with chooseBranch(), and finally
1882  add the node to the live set.
1883
1884  The first action is to winnow the live set to remove nodes which are worse
1885  than the current objective cutoff.
1886*/
1887  if (solver_->getRowCutDebuggerAlways()) {
1888    OsiRowCutDebugger * debuggerX = const_cast<OsiRowCutDebugger *> (solver_->getRowCutDebuggerAlways());
1889    const OsiRowCutDebugger *debugger = solver_->getRowCutDebugger() ;
1890    if (!debugger) {
1891      // infeasible!!
1892      printf("before search\n");
1893      const double * lower = solver_->getColLower();
1894      const double * upper = solver_->getColUpper();
1895      const double * solution = debuggerX->optimalSolution();
1896      int numberColumns = solver_->getNumCols();
1897      for (int i=0;i<numberColumns;i++) {
1898        if (solver_->isInteger(i)) {
1899          if (solution[i]<lower[i]-1.0e-6||solution[i]>upper[i]+1.0e-6)
1900            printf("**** ");
1901          printf("%d %g <= %g <= %g\n",
1902                 i,lower[i],solution[i],upper[i]);
1903        }
1904      }
1905      //abort();
1906    }
1907  }
1908#ifdef CBC_DETERMINISTIC_THREAD
1909#define MAX_DEL_NODE 1
1910  CbcNode * delNode[MAX_DEL_NODE+1];
1911  int nDeleteNode=0;
1912  bool goneParallel=false;
1913#endif
1914  // For Printing etc when parallel
1915  int lastEvery1000=0;
1916  int lastPrintEvery=0;
1917  while (true) {
1918#ifdef CBC_NORMAL_THREAD
1919    if (!locked) {
1920      lockThread();
1921      locked=true;
1922    }
1923#endif
1924    if (tree_->empty()) {
1925#ifdef CBC_NORMAL_THREAD
1926      if (numberThreads_) {
1927#ifdef COIN_DEVELOP
1928        printf("empty\n");
1929#endif
1930        // may still be outstanding nodes
1931        int iThread;
1932        for (iThread=0;iThread<numberThreads_;iThread++) {
1933          if (threadId[iThread]) {
1934            if (threadInfo[iThread].returnCode==0) 
1935              break;
1936          }
1937        }
1938        if (iThread<numberThreads_) {
1939#ifdef COIN_DEVELOP
1940          printf("waiting for thread %d code 0\n",iThread);
1941#endif
1942#ifndef CBC_DETERMINISTIC_THREAD
1943          unlockThread();
1944#endif
1945          locked = false;
1946          pthread_cond_signal(threadInfo[iThread].condition2); // unlock in case
1947          while (true) {
1948            pthread_mutex_lock(&condition_mutex);
1949            struct timespec absTime;
1950            clock_gettime(CLOCK_REALTIME,&absTime);
1951            double time = absTime.tv_sec+1.0e-9*absTime.tv_nsec;
1952            absTime.tv_nsec += 1000000; // millisecond
1953            if (absTime.tv_nsec>=1000000000) {
1954              absTime.tv_nsec -= 1000000000;
1955              absTime.tv_sec++;
1956            }
1957            pthread_cond_timedwait(&condition_main,&condition_mutex,&absTime);
1958            clock_gettime(CLOCK_REALTIME,&absTime);
1959            double time2 = absTime.tv_sec+1.0e-9*absTime.tv_nsec;
1960            timeWaiting += time2-time;
1961            pthread_mutex_unlock(&condition_mutex);
1962            if (threadInfo[iThread].returnCode!=0) 
1963              break;
1964            pthread_cond_signal(threadInfo[iThread].condition2); // unlock
1965          }
1966          threadModel[iThread]->moveToModel(this,1);
1967          assert (threadInfo[iThread].returnCode==1);
1968          // say available
1969          threadInfo[iThread].returnCode=-1;
1970          threadStats[4]++;
1971#ifdef COIN_DEVELOP
1972          printf("thread %d code now -1\n",iThread);
1973#endif
1974          continue;
1975        } else {
1976#ifdef COIN_DEVELOP
1977          printf("no threads at code 0 \n");
1978#endif
1979          // now check if any have just finished
1980          for (iThread=0;iThread<numberThreads_;iThread++) {
1981            if (threadId[iThread]) {
1982              if (threadInfo[iThread].returnCode==1) 
1983                break;
1984            }
1985          }
1986          if (iThread<numberThreads_) {
1987#ifndef CBC_DETERMINISTIC_THREAD
1988            unlockThread();
1989#endif
1990            locked = false;
1991            threadModel[iThread]->moveToModel(this,1);
1992            assert (threadInfo[iThread].returnCode==1);
1993            // say available
1994            threadInfo[iThread].returnCode=-1;
1995            threadStats[4]++;
1996#ifdef COIN_DEVELOP
1997            printf("thread %d code now -1\n",iThread);
1998#endif
1999            continue;
2000          }
2001        }
2002        if (!tree_->empty()) {
2003#ifdef COIN_DEVELOP
2004          printf("tree not empty!!!!!!\n");
2005#endif
2006          continue;
2007        }
2008        for (iThread=0;iThread<numberThreads_;iThread++) {
2009          if (threadId[iThread]) {
2010            if (threadInfo[iThread].returnCode!=-1) { 
2011              printf("bad end of tree\n");
2012              abort();
2013            }
2014          }
2015        }
2016#ifdef COIN_DEVELOP
2017        printf("finished ************\n");
2018#endif
2019      }
2020#ifndef CBC_DETERMINISTIC_THREAD
2021      unlockThread();
2022#endif
2023      locked=false; // not needed as break
2024#endif
2025      break;
2026    }
2027#ifdef CBC_NORMAL_THREAD
2028    unlockThread();
2029    locked = false;
2030#endif
2031/*
2032  Check for abort on limits: node count, solution count, time, integrality gap.
2033*/
2034    totalTime = getCurrentSeconds() ;
2035    double maxSeconds = getMaximumSeconds();
2036    if (parentModel_)
2037      maxSeconds=CoinMin(maxSeconds,parentModel_->getMaximumSeconds());
2038    if (!(numberNodes_ < intParam_[CbcMaxNumNode] &&
2039          numberSolutions_ < intParam_[CbcMaxNumSol] &&
2040          totalTime < maxSeconds &&
2041          !stoppedOnGap_&&!eventHappened_)) {
2042      // out of loop
2043      break;
2044    }
2045#ifdef BONMIN
2046    assert(!solverCharacteristics_->solutionAddsCuts() || solverCharacteristics_->mipFeasible());
2047#endif
2048    if (cutoff > getCutoff()) {
2049      double newCutoff = getCutoff();
2050      if (analyzeResults_) {
2051        // see if we could fix any (more)
2052        int n=0;
2053        double * newLower = analyzeResults_;
2054        double * objLower = newLower+numberIntegers_;
2055        double * newUpper = objLower+numberIntegers_;
2056        double * objUpper = newUpper+numberIntegers_;
2057        for (int i=0;i<numberIntegers_;i++) {
2058          if (objLower[i]>newCutoff) {
2059            n++;
2060            if (objUpper[i]>newCutoff) {
2061              newCutoff = -COIN_DBL_MAX;
2062              break;
2063            }
2064          } else if (objUpper[i]>newCutoff) {
2065            n++;
2066          }
2067        }
2068        if (newCutoff==-COIN_DBL_MAX) {
2069          printf("Root analysis says finished\n");
2070        } else if (n>numberFixedNow_) {
2071          printf("%d more fixed by analysis - now %d\n",n-numberFixedNow_,n);
2072          numberFixedNow_=n;
2073        }
2074      }
2075      if (eventHandler) {
2076        if (!eventHandler->event(CbcEventHandler::solution)) {
2077          eventHappened_=true; // exit
2078        }
2079      }
2080#ifndef CBC_DETERMINISTIC_THREAD
2081      lockThread();
2082#endif
2083      // Do from deepest
2084      tree_->cleanTree(this, newCutoff,bestPossibleObjective_) ;
2085      nodeCompare_->newSolution(this) ;
2086      nodeCompare_->newSolution(this,continuousObjective_,
2087                                continuousInfeasibilities_) ;
2088      tree_->setComparison(*nodeCompare_) ;
2089      if (tree_->empty()) {
2090#ifndef CBC_DETERMINISTIC_THREAD
2091        unlockThread();
2092#endif
2093        // For threads we need to check further
2094        //break; // finished
2095        continue;
2096      }
2097#ifndef CBC_DETERMINISTIC_THREAD
2098      unlockThread();
2099#endif
2100    }
2101    cutoff = getCutoff() ;
2102/*
2103    Periodic activities: Opportunities to
2104    + tweak the nodeCompare criteria,
2105    + check if we've closed the integrality gap enough to quit,
2106    + print a summary line to let the user know we're working
2107*/
2108    if (numberNodes_>=lastEvery1000) {
2109#ifndef CBC_DETERMINISTIC_THREAD
2110      lockThread();
2111#endif
2112      lastEvery1000 = numberNodes_ + 1000;
2113      bool redoTree=nodeCompare_->every1000Nodes(this, numberNodes_) ;
2114#ifdef CHECK_CUT_SIZE
2115      verifyCutSize (tree_, *this);
2116#endif
2117      // redo tree if wanted
2118      if (redoTree)
2119        tree_->setComparison(*nodeCompare_) ;
2120#ifndef CBC_DETERMINISTIC_THREAD
2121      unlockThread();
2122#endif
2123    }
2124    if (saveCompare&&!hotstartSolution_) {
2125      // hotstart switched off
2126      delete nodeCompare_; // off depth first
2127      nodeCompare_=saveCompare;
2128      saveCompare=NULL;
2129      // redo tree
2130#ifndef CBC_DETERMINISTIC_THREAD
2131      lockThread();
2132#endif
2133      tree_->setComparison(*nodeCompare_) ;
2134#ifndef CBC_DETERMINISTIC_THREAD
2135      unlockThread();
2136#endif
2137    }
2138    if (numberNodes_>=lastPrintEvery) {
2139      lastPrintEvery = numberNodes_ + printFrequency_;
2140#ifdef CBC_INSTRUMENT
2141      if (0) {
2142        printf("==Start instrument\n");
2143        for (int iObject=0;iObject<numberObjects_;iObject++) {
2144          CbcSimpleIntegerDynamicPseudoCost * obj =
2145            dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(object_[iObject]) ;
2146          if (obj)
2147            obj->print();
2148        }
2149        printf("==End instrument\n");
2150      }
2151#endif
2152#ifndef CBC_DETERMINISTIC_THREAD
2153      lockThread();
2154#endif
2155      int nNodes = tree_->size() ;
2156
2157      //MODIF PIERRE
2158      bestPossibleObjective_ = tree_->getBestPossibleObjective();
2159#ifndef CBC_DETERMINISTIC_THREAD
2160      unlockThread();
2161#endif
2162      if (!intParam_[CbcPrinting]) {
2163        messageHandler()->message(CBC_STATUS,messages())
2164          << numberNodes_<< nNodes<< bestObjective_<< bestPossibleObjective_
2165          <<getCurrentSeconds()
2166          << CoinMessageEol ;
2167      } else {
2168        messageHandler()->message(CBC_STATUS2,messages())
2169          << numberNodes_<< nNodes<< bestObjective_<< bestPossibleObjective_
2170          <<lastDepth<<lastUnsatisfied<<numberIterations_
2171          <<getCurrentSeconds()
2172          << CoinMessageEol ;
2173      }
2174      if (!eventHandler->event(CbcEventHandler::treeStatus)) {
2175        eventHappened_=true; // exit
2176      }
2177    }
2178    // See if can stop on gap
2179    double testGap = CoinMax(dblParam_[CbcAllowableGap],
2180                             CoinMax(fabs(bestObjective_),fabs(bestPossibleObjective_))
2181                             *dblParam_[CbcAllowableFractionGap]);
2182    if (bestObjective_-bestPossibleObjective_ < testGap && getCutoffIncrement()>=0.0) {
2183      stoppedOnGap_ = true ;
2184    }
2185   
2186#   ifdef CHECK_NODE_FULL
2187    verifyTreeNodes(tree_,*this) ;
2188#   endif
2189#   ifdef CHECK_CUT_COUNTS
2190    verifyCutCounts(tree_,*this) ;
2191#   endif
2192/*
2193  Now we come to the meat of the loop. To create the active subproblem, we'll
2194  pop the most promising node in the live set, rebuild the subproblem it
2195  represents, and then execute the current arm of the branch to create the
2196  active subproblem.
2197*/
2198#ifndef CBC_THREAD
2199    CbcNode *node = tree_->bestNode(cutoff) ;
2200    // Possible one on tree worse than cutoff
2201    if (!node||node->objectiveValue()>cutoff)
2202      continue;
2203    int currentNumberCuts = 0 ;
2204    currentNode_=node; // so can be accessed elsewhere
2205#ifdef CBC_DEBUG
2206    printf("%d unsat, way %d, obj %g est %g\n",
2207           node->numberUnsatisfied(),node->way(),node->objectiveValue(),
2208           node->guessedObjectiveValue());
2209#endif
2210#if NEW_UPDATE_OBJECT==0
2211    // Save clone in branching decision
2212    if(branchingMethod_)
2213      branchingMethod_->saveBranchingObject(node->modifiableBranchingObject());
2214#endif
2215    // Say not on optimal path
2216    bool onOptimalPath=false;
2217#   ifdef CHECK_NODE
2218    printf("Node %x popped from tree - %d left, %d count\n",node,
2219           node->nodeInfo()->numberBranchesLeft(),
2220           node->nodeInfo()->numberPointingToThis()) ;
2221    printf("\tdepth = %d, z =  %g, unsat = %d, var = %d.\n",
2222           node->depth(),node->objectiveValue(),
2223           node->numberUnsatisfied(),
2224           node->columnNumber()) ;
2225#   endif
2226    lastDepth=node->depth();
2227    lastUnsatisfied=node->numberUnsatisfied();
2228
2229/*
2230  Rebuild the subproblem for this node:  Call addCuts() to adjust the model
2231  to recreate the subproblem for this node (set proper variable bounds, add
2232  cuts, create a basis).  This may result in the problem being fathomed by
2233  bound or infeasibility. Returns 1 if node is fathomed.
2234  Execute the current arm of the branch: If the problem survives, save the
2235  resulting variable bounds and call branch() to modify variable bounds
2236  according to the current arm of the branching object. If we're processing
2237  the final arm of the branching object, flag the node for removal from the
2238  live set.
2239*/
2240    CbcNodeInfo * nodeInfo = node->nodeInfo() ;
2241    newNode = NULL ;
2242    int branchesLeft=0;
2243    if (!addCuts(node,lastws,numberFixedNow_>numberFixedAtRoot_))
2244    { int i ;
2245      const double * lower = getColLower() ;
2246      const double * upper = getColUpper() ;
2247      for (i = 0 ; i < numberColumns ; i++)
2248      { lowerBefore[i]= lower[i] ;
2249        upperBefore[i]= upper[i] ; }
2250      if ((solverCharacteristics_->extraCharacteristics()&2)!=0) {
2251        solverCharacteristics_->setBeforeLower(lowerBefore);
2252        solverCharacteristics_->setBeforeUpper(upperBefore);
2253      }
2254      if (messageHandler()->logLevel()>2)
2255        node->modifiableBranchingObject()->print();
2256      if (!useOsiBranching) 
2257        branchesLeft = node->branch(NULL); // old way
2258      else
2259        branchesLeft = node->branch(solver_); // new way
2260      if (branchesLeft) {
2261        // set nodenumber correctly
2262        node->nodeInfo()->setNodeNumber(numberNodes2_);
2263        tree_->push(node) ;
2264        if (statistics_) {
2265          if (numberNodes2_==maximumStatistics_) {
2266            maximumStatistics_ = 2*maximumStatistics_;
2267            CbcStatistics ** temp = new CbcStatistics * [maximumStatistics_];
2268            memset(temp,0,maximumStatistics_*sizeof(CbcStatistics *));
2269            memcpy(temp,statistics_,numberNodes2_*sizeof(CbcStatistics *));
2270            delete [] statistics_;
2271            statistics_=temp;
2272          }
2273          assert (!statistics_[numberNodes2_]);
2274          statistics_[numberNodes2_]=new CbcStatistics(node);
2275        }
2276        numberNodes2_++;
2277        //nodeOnTree=true; // back on tree
2278        //deleteNode = false ;
2279#       ifdef CHECK_NODE
2280        printf("Node %x pushed back on tree - %d left, %d count\n",node,
2281               nodeInfo->numberBranchesLeft(),
2282               nodeInfo->numberPointingToThis()) ;
2283#       endif
2284      } else {
2285        //deleteNode = true ;
2286        if (!nodeInfo->numberBranchesLeft())
2287          nodeInfo->allBranchesGone(); // can clean up
2288      }
2289      if ((specialOptions_&1)!=0) {
2290        /*
2291          This doesn't work as intended --- getRowCutDebugger will return null
2292          unless the current feasible solution region includes the optimal solution
2293          that RowCutDebugger knows. There's no way to tell inactive from off the
2294          optimal path.
2295        */
2296        const OsiRowCutDebugger *debugger = solver_->getRowCutDebugger() ;
2297        if (debugger) {
2298          onOptimalPath=true;
2299          printf("On optimal path\n") ;
2300        }
2301      }
2302     
2303/*
2304  Reoptimize, possibly generating cuts and/or using heuristics to find
2305  solutions.  Cut reference counts are unaffected unless we lose feasibility,
2306  in which case solveWithCuts() will make the adjustment.
2307*/
2308      phase_=2;
2309      cuts = OsiCuts() ;
2310      currentNumberCuts = solver_->getNumRows()-numberRowsAtContinuous_ ;
2311      int saveNumber = numberIterations_;
2312      if(solverCharacteristics_->solutionAddsCuts()) {
2313        int returnCode=resolve(node ? node->nodeInfo() : NULL,1);
2314        feasible = returnCode != 0;
2315        if (feasible) {
2316          int iObject ;
2317          int preferredWay ;
2318          int numberUnsatisfied = 0 ;
2319          memcpy(currentSolution_,solver_->getColSolution(),
2320                 numberColumns*sizeof(double)) ;
2321          // point to useful information
2322          OsiBranchingInformation usefulInfo=usefulInformation();
2323         
2324          for (iObject = 0 ; iObject < numberObjects_ ; iObject++) {
2325            double infeasibility =
2326              object_[iObject]->infeasibility(&usefulInfo,preferredWay) ;
2327            if (infeasibility ) numberUnsatisfied++ ;
2328          }
2329          if (returnCode>0) {
2330            if (numberUnsatisfied)   {
2331              feasible = solveWithCuts(cuts,maximumCutPasses_,node);
2332            } else {
2333              // may generate cuts and turn the solution
2334              //to an infeasible one
2335              feasible = solveWithCuts(cuts, 1,
2336                                       node);
2337#if 0
2338              currentNumberCuts_ = cuts.sizeRowCuts();
2339              if (currentNumberCuts_ >= maximumNumberCuts_) {
2340                maximumNumberCuts_ = currentNumberCuts;
2341                delete [] addedCuts_;
2342                addedCuts_ = new CbcCountRowCut * [maximumNumberCuts_];
2343              }
2344#endif
2345            }
2346          }
2347          // check extra info on feasibility
2348          if (!solverCharacteristics_->mipFeasible()) {
2349            feasible = false;
2350            solverCharacteristics_->setMipBound(-COIN_DBL_MAX);
2351          }
2352        }
2353      } else {
2354        // normal
2355        //int zzzzzz=0;
2356        //if (zzzzzz)
2357        //solver_->writeMps("before");
2358        feasible = solveWithCuts(cuts,maximumCutPasses_,node);
2359      }
2360      if ((specialOptions_&1)!=0&&onOptimalPath) {
2361        if (!solver_->getRowCutDebugger()) {
2362          // dj fix did something???
2363          solver_->writeMps("infeas2");
2364          assert (solver_->getRowCutDebugger()) ;
2365        }
2366      }
2367      if (statistics_) {
2368        assert (numberNodes2_);
2369        assert (statistics_[numberNodes2_-1]);
2370        assert (statistics_[numberNodes2_-1]->node()==numberNodes2_-1);
2371        statistics_[numberNodes2_-1]->endOfBranch(numberIterations_-saveNumber,
2372                                               feasible ? solver_->getObjValue()
2373                                               : COIN_DBL_MAX);
2374      }
2375/*
2376  Are we still feasible? If so, create a node and do the work to attach a
2377  branching object, reoptimising as needed if chooseBranch() identifies
2378  monotone objects.
2379
2380  Finally, attach a partial nodeInfo object and store away any cuts that we
2381  created back in solveWithCuts. addCuts() will initialise the reference
2382  counts for these new cuts.
2383
2384  This next test can be problematic if we've discovered an
2385  alternate equivalent answer and subsequently fathom the solution
2386  known to the row cut debugger due to bounds.
2387*/
2388        if (onOptimalPath) {
2389          bool objLim = solver_->isDualObjectiveLimitReached() ;
2390          if (!feasible && !objLim) {
2391            printf("infeas2\n");
2392            solver_->writeMps("infeas");
2393            CoinWarmStartBasis *slack =
2394              dynamic_cast<CoinWarmStartBasis *>(solver_->getEmptyWarmStart()) ;
2395            solver_->setWarmStart(slack);
2396            delete slack ;
2397            solver_->setHintParam(OsiDoReducePrint,false,OsiHintDo,0) ;
2398            solver_->initialSolve();
2399            assert (!solver_->isProvenOptimal());
2400          }
2401          assert (feasible || objLim);
2402        }
2403        bool checkingNode=false;
2404        if (feasible) {
2405          newNode = new CbcNode ;//Regular node of the tree
2406          // Set objective value (not so obvious if NLP etc)
2407          setObjectiveValue(newNode,node);
2408          anyAction =-1 ;
2409          resolved = false ;
2410          if (newNode->objectiveValue() >= getCutoff()) 
2411            anyAction=-2;
2412          // only allow at most a few passes
2413          int numberPassesLeft=5;
2414          checkingNode=true;
2415        OsiSolverBranch * branches=NULL;
2416        // point to useful information
2417        anyAction = chooseBranch(newNode, numberPassesLeft,node, cuts,resolved,
2418                                 lastws, lowerBefore, upperBefore, branches);
2419/*
2420  If we end up infeasible, we can delete the new node immediately. Since this
2421  node won't be needing the cuts we collected, decrement the reference counts.
2422  If we are feasible, then we'll be placing this node into the live set, so
2423  increment the reference count in the current (parent) nodeInfo.
2424*/
2425        if (anyAction == -2)
2426          { delete newNode ;
2427          newNode = NULL ;
2428          // say strong doing well
2429          if (checkingNode)
2430            setSpecialOptions(specialOptions_|8);
2431          for (i = 0 ; i < currentNumberCuts_ ; i++)
2432            { if (addedCuts_[i])
2433              { if (!addedCuts_[i]->decrement(1))
2434                delete addedCuts_[i] ; } } }
2435        else
2436          { nodeInfo->increment() ;
2437          if ((numberNodes_%20)==0) {
2438            // say strong not doing as well
2439            setSpecialOptions(specialOptions_&~8);
2440          }
2441        }
2442        }
2443/*
2444  At this point, there are three possibilities:
2445    * newNode is live and will require further branching to resolve
2446      (variable() >= 0). Increment the cut reference counts by
2447      numberBranches() to allow for use by children of this node, and
2448      decrement by 1 because we've executed one arm of the branch of our
2449      parent (consuming one reference). Before we push newNode onto the
2450      search tree, try for a heuristic solution.
2451    * We have a solution, in which case newNode is non-null but we have no
2452      branching variable. Decrement the cut counts and save the solution.
2453    * The node was found to be infeasible, in which case it's already been
2454      deleted, and newNode is null.
2455*/
2456        if (!eventHandler->event(CbcEventHandler::node)) {
2457          eventHappened_=true; // exit
2458        }
2459        assert (!newNode || newNode->objectiveValue() <= getCutoff()) ;
2460        if (statistics_) {
2461          assert (numberNodes2_);
2462          assert (statistics_[numberNodes2_-1]);
2463          assert (statistics_[numberNodes2_-1]->node()==numberNodes2_-1);
2464          if (newNode)
2465            statistics_[numberNodes2_-1]->updateInfeasibility(newNode->numberUnsatisfied());
2466          else
2467            statistics_[numberNodes2_-1]->sayInfeasible();
2468        }
2469        if (newNode) {
2470          if (newNode->branchingObject() == NULL&&solverCharacteristics_->solverType()==4) {
2471            // need to check if any cuts would do anything
2472            OsiCuts theseCuts;
2473            // reset probing info
2474            //if (probingInfo_)
2475            //probingInfo_->initializeFixing();
2476            for (int i = 0;i<numberCutGenerators_;i++) {
2477              bool generate = generator_[i]->normal();
2478              // skip if not optimal and should be (maybe a cut generator has fixed variables)
2479              if (generator_[i]->needsOptimalBasis()&&!solver_->basisIsAvailable())
2480                generate=false;
2481              if (!generator_[i]->mustCallAgain())
2482                generate=false; // only special cuts
2483              if (generate) {
2484                generator_[i]->generateCuts(theseCuts,true,solver_,NULL) ;
2485                int numberRowCutsAfter = theseCuts.sizeRowCuts() ;
2486                if (numberRowCutsAfter) {
2487                  // need dummy branch
2488                  newNode->setBranchingObject(new CbcDummyBranchingObject(this));
2489                  newNode->nodeInfo()->initializeInfo(1);
2490                  break;
2491                }
2492              }
2493            }
2494          }
2495          if (newNode->branchingObject())
2496          { handler_->message(CBC_BRANCH,messages_)
2497               << numberNodes_<< newNode->objectiveValue()
2498               << newNode->numberUnsatisfied()<< newNode->depth()
2499               << CoinMessageEol ;
2500            // Increment cut counts (taking off current)
2501            int numberLeft = newNode->numberBranches() ;
2502            for (i = 0;i < currentNumberCuts_;i++)
2503            { if (addedCuts_[i])
2504              {
2505#               ifdef CHECK_CUT_COUNTS
2506                printf("Count on cut %x increased by %d\n",addedCuts_[i],
2507                        numberLeft-1) ;
2508#               endif
2509                addedCuts_[i]->increment(numberLeft-1) ; } }
2510
2511            double estValue = newNode->guessedObjectiveValue() ;
2512            int found = -1 ;
2513            // no - overhead on small problems solver_->resolve() ;     // double check current optimal
2514            // assert (!solver_->getIterationCount());
2515            double * newSolution = new double [numberColumns] ;
2516            double heurValue = getCutoff() ;
2517            int iHeur ;
2518            for (iHeur = 0 ; iHeur < numberHeuristics_ ; iHeur++) {
2519              double saveValue = heurValue ;
2520              int ifSol = heuristic_[iHeur]->solution(heurValue,newSolution) ;
2521              if (ifSol > 0) {
2522                // new solution found
2523                found = iHeur ;
2524                incrementUsed(newSolution);
2525                lastHeuristic_ = heuristic_[found];
2526                setBestSolution(CBC_ROUNDING,heurValue,newSolution) ;
2527              } else if (ifSol < 0) {
2528                // just returning an estimate
2529                estValue = CoinMin(heurValue,estValue) ;
2530                heurValue = saveValue ;
2531              }
2532            }
2533            delete [] newSolution ;
2534            newNode->setGuessedObjectiveValue(estValue) ;
2535            tree_->push(newNode) ;
2536            if (statistics_) {
2537              if (numberNodes2_==maximumStatistics_) {
2538                maximumStatistics_ = 2*maximumStatistics_;
2539                CbcStatistics ** temp = new CbcStatistics * [maximumStatistics_];
2540                memset(temp,0,maximumStatistics_*sizeof(CbcStatistics *));
2541                memcpy(temp,statistics_,numberNodes2_*sizeof(CbcStatistics *));
2542                delete [] statistics_;
2543                statistics_=temp;
2544              }
2545              assert (!statistics_[numberNodes2_]);
2546              statistics_[numberNodes2_]=new CbcStatistics(newNode);
2547            }
2548            numberNodes2_++;
2549#           ifdef CHECK_NODE
2550            printf("Node %x pushed on tree c\n",newNode) ;
2551#           endif
2552          }
2553          else
2554          { 
2555            if(solverCharacteristics_ && //we may be in a non standard bab
2556               solverCharacteristics_->solutionAddsCuts()// we are in some kind of OA based bab.
2557               )
2558              {
2559                std::cerr<<"You should never get here"<<std::endl;
2560                throw CoinError("Nodes should not be fathomed on integer infeasibility in this setting",
2561                                "branchAndBound","CbcModel") ;
2562              }
2563            for (i = 0 ; i < currentNumberCuts_ ; i++)
2564            { if (addedCuts_[i])
2565              { if (!addedCuts_[i]->decrement(1))
2566                  delete addedCuts_[i] ; } }
2567          double objectiveValue = newNode->objectiveValue();
2568            setBestSolution(CBC_SOLUTION,objectiveValue,
2569                            solver_->getColSolution()) ;
2570            lastHeuristic_ = NULL;
2571            incrementUsed(solver_->getColSolution());
2572            //assert(nodeInfo->numberPointingToThis() <= 2) ;
2573            // avoid accidental pruning, if newNode was final branch arm
2574            nodeInfo->increment();
2575            delete newNode ;
2576            nodeInfo->decrement() ; } }
2577/*
2578  This node has been completely expanded and can be removed from the live
2579  set.
2580*/
2581      if (branchesLeft)
2582      { 
2583      }
2584      else
2585      { 
2586        if (!nodeInfo->numberBranchesLeft())
2587          nodeInfo->allBranchesGone(); // can clean up
2588        delete node ; }
2589    } else {
2590      // add cuts found to be infeasible (on bound)!
2591      abort();
2592      delete node;
2593    }
2594/*
2595  Delete cuts to get back to the original system.
2596
2597  I'm thinking this is redundant --- the call to addCuts that conditions entry
2598  to this code block also performs this action.
2599*/
2600      int numberToDelete = getNumRows()-numberRowsAtContinuous_ ;
2601      if (numberToDelete)
2602      { int * delRows = new int[numberToDelete] ;
2603        int i ;
2604        for (i = 0 ; i < numberToDelete ; i++)
2605        { delRows[i] = i+numberRowsAtContinuous_ ; }
2606        solver_->deleteRows(numberToDelete,delRows) ;
2607        delete [] delRows ; }
2608#else // end of not CBC_THREAD
2609#ifndef CBC_DETERMINISTIC_THREAD
2610      CbcNode *node = tree_->bestNode(cutoff) ;
2611      // Possible one on tree worse than cutoff
2612      if (!node||node->objectiveValue()>cutoff)
2613        continue;
2614    if (!numberThreads_) {
2615#else
2616      if (!numberThreads_||(tree_->size()<5*numberThreads_&&!goneParallel)) {
2617      CbcNode *node = tree_->bestNode(cutoff) ;
2618      // Possible one on tree worse than cutoff
2619      if (!node||node->objectiveValue()>cutoff)
2620        continue;
2621#endif
2622        doOneNode(this,node,createdNode);
2623#ifdef CBC_DETERMINISTIC_THREAD
2624        assert (createdNode);
2625        if (!createdNode->active()) {
2626          //if (createdNode->nodeInfo()) {
2627          //createdNode->nodeInfo()->throwAway();
2628          //}
2629          delete createdNode;
2630          createdNode=NULL;
2631        } else {
2632          // Say one more pointing to this
2633          node->nodeInfo()->increment() ;
2634          tree_->push(createdNode) ;
2635        }
2636        //if (node) {
2637        //assert (node->active());
2638        if (node->active()) {
2639          assert (node->nodeInfo());
2640          if (node->nodeInfo()->numberBranchesLeft()) {
2641            tree_->push(node) ;
2642          } else {
2643            node->setActive(false);
2644          }
2645        } else {
2646          if (node->nodeInfo()) {
2647            if (!node->nodeInfo()->numberBranchesLeft())
2648              node->nodeInfo()->allBranchesGone(); // can clean up
2649            // So will delete underlying stuff
2650            node->setActive(true);
2651          }
2652          delNode[nDeleteNode++]=node;
2653          node=NULL;
2654        } 
2655        if (nDeleteNode>=MAX_DEL_NODE) {
2656          for (int i=0;i<nDeleteNode;i++) {
2657            //printf("trying to del %d %x\n",i,delNode[i]);
2658            delete delNode[i];
2659            //printf("done to del %d %x\n",i,delNode[i]);
2660          }
2661          nDeleteNode=0;
2662        }
2663#endif
2664      } else {
2665#ifdef CBC_NORMAL_THREAD
2666        threadStats[0]++;
2667        //need to think
2668        int iThread;
2669        // Start one off if any available
2670        for (iThread=0;iThread<numberThreads_;iThread++) {
2671          if (threadInfo[iThread].returnCode==-1) 
2672            break;
2673        }
2674        if (iThread<numberThreads_) {
2675          threadInfo[iThread].node=node;
2676          assert (threadInfo[iThread].returnCode==-1);
2677          // say in use
2678          threadInfo[iThread].returnCode=0;
2679          threadModel[iThread]->moveToModel(this,0);
2680          pthread_cond_signal(threadInfo[iThread].condition2); // unlock
2681          threadCount[iThread]++;
2682        }
2683#ifndef CBC_DETERMINISTIC_THREAD
2684        lockThread();
2685#endif
2686        locked=true;
2687        // see if any finished
2688        for (iThread=0;iThread<numberThreads_;iThread++) {
2689          if (threadInfo[iThread].returnCode>0) 
2690            break;
2691        }
2692#ifndef CBC_DETERMINISTIC_THREAD
2693        unlockThread();
2694#endif
2695        locked=false;
2696        if (iThread<numberThreads_) {
2697          threadModel[iThread]->moveToModel(this,1);
2698          assert (threadInfo[iThread].returnCode==1);
2699          // say available
2700          threadInfo[iThread].returnCode=-1;
2701          // carry on
2702          threadStats[3]++;
2703        } else {
2704          // Start one off if any available
2705          for (iThread=0;iThread<numberThreads_;iThread++) {
2706            if (threadInfo[iThread].returnCode==-1) 
2707              break;
2708          }
2709          if (iThread<numberThreads_) {
2710#ifndef CBC_DETERMINISTIC_THREAD
2711            lockThread();
2712#endif
2713            locked=true;
2714            // If any on tree get
2715            if (!tree_->empty()) {
2716              //node = tree_->bestNode(cutoff) ;
2717              //assert (node);
2718              threadStats[1]++;
2719              continue; // ** get another node
2720            }
2721#ifndef CBC_DETERMINISTIC_THREAD
2722            unlockThread();
2723#endif
2724            locked=false;
2725          }
2726          // wait (for debug could sleep and use test)
2727          bool finished=false;
2728          while (!finished) {
2729            pthread_mutex_lock(&condition_mutex);
2730            struct timespec absTime;
2731            clock_gettime(CLOCK_REALTIME,&absTime);
2732            double time = absTime.tv_sec+1.0e-9*absTime.tv_nsec;
2733            absTime.tv_nsec += 1000000; // millisecond
2734            if (absTime.tv_nsec>=1000000000) {
2735              absTime.tv_nsec -= 1000000000;
2736              absTime.tv_sec++;
2737            }
2738            pthread_cond_timedwait(&condition_main,&condition_mutex,&absTime);
2739            clock_gettime(CLOCK_REALTIME,&absTime);
2740            double time2 = absTime.tv_sec+1.0e-9*absTime.tv_nsec;
2741            timeWaiting += time2-time;
2742            pthread_mutex_unlock(&condition_mutex);
2743            for (iThread=0;iThread<numberThreads_;iThread++) {
2744              if (threadInfo[iThread].returnCode>0) {
2745                finished=true;
2746                break;
2747              } else if (threadInfo[iThread].returnCode==0) {
2748                pthread_cond_signal(threadInfo[iThread].condition2); // unlock
2749              }
2750            }
2751          }
2752          assert (iThread<numberThreads_);
2753          threadModel[iThread]->moveToModel(this,1);
2754          node = threadInfo[iThread].node;
2755          threadInfo[iThread].node=NULL;
2756          assert (threadInfo[iThread].returnCode==1);
2757          // say available
2758          threadInfo[iThread].returnCode=-1;
2759          // carry on
2760          threadStats[2]++;
2761        }
2762#else
2763        // Deterministic parallel
2764#ifndef CBC_DETERMINISTIC_THREAD
2765        abort();
2766#endif
2767        int saveTreeSize = tree_->size();
2768        goneParallel=true;
2769        int nAffected=splitModel(numberThreads_,threadModel,defaultParallelNodes);
2770        int saveTreeSize2 = tree_->size();
2771        int iThread;
2772        // do all until finished
2773        for (iThread=0;iThread<numberThreads_;iThread++) {
2774          // obviously tune
2775          threadInfo[iThread].nDeleteNode=defaultParallelIterations;
2776        }
2777        // Save current state
2778        int iObject;
2779        for (iObject=0;iObject<numberObjects_;iObject++) {
2780          saveObjects[iObject]->updateBefore(object_[iObject]);
2781        }
2782        for (iThread=0;iThread<numberThreads_;iThread++) {
2783          threadInfo[iThread].returnCode=0;
2784          pthread_cond_signal(threadInfo[iThread].condition2); // unlock
2785#if 0
2786          //wait!!
2787          bool finished=false;
2788          while (!finished) {
2789            pthread_mutex_lock(&condition_mutex);
2790            struct timespec absTime;
2791            clock_gettime(CLOCK_REALTIME,&absTime);
2792            double time = absTime.tv_sec+1.0e-9*absTime.tv_nsec;
2793            absTime.tv_nsec += 1000000; // millisecond
2794            if (absTime.tv_nsec>=1000000000) {
2795              absTime.tv_nsec -= 1000000000;
2796              absTime.tv_sec++;
2797            }
2798            pthread_cond_timedwait(&condition_main,&condition_mutex,&absTime);
2799            clock_gettime(CLOCK_REALTIME,&absTime);
2800            double time2 = absTime.tv_sec+1.0e-9*absTime.tv_nsec;
2801            timeWaiting += time2-time;
2802            pthread_mutex_unlock(&condition_mutex);
2803            finished=true;
2804            if (threadInfo[iThread].returnCode<=0) {
2805              finished=false;
2806            }
2807          }
2808#endif
2809        }
2810        // wait
2811        bool finished=false;
2812        while (!finished) {
2813          pthread_mutex_lock(&condition_mutex);
2814          struct timespec absTime;
2815          clock_gettime(CLOCK_REALTIME,&absTime);
2816          double time = absTime.tv_sec+1.0e-9*absTime.tv_nsec;
2817          absTime.tv_nsec += 1000000; // millisecond
2818          if (absTime.tv_nsec>=1000000000) {
2819            absTime.tv_nsec -= 1000000000;
2820            absTime.tv_sec++;
2821          }
2822          pthread_cond_timedwait(&condition_main,&condition_mutex,&absTime);
2823          clock_gettime(CLOCK_REALTIME,&absTime);
2824          double time2 = absTime.tv_sec+1.0e-9*absTime.tv_nsec;
2825          timeWaiting += time2-time;
2826          pthread_mutex_unlock(&condition_mutex);
2827          finished=true;
2828          for (iThread=0;iThread<numberThreads_;iThread++) {
2829            if (threadInfo[iThread].returnCode<=0) {
2830              finished=false;
2831            }
2832          }
2833        }
2834        // Unmark marked
2835        for (int i=0;i<nAffected;i++) {
2836          walkback_[i]->unmark();
2837        }
2838        assert (saveTreeSize2 == tree_->size());
2839        if (0) { 
2840          // put back cut counts
2841          for (int i=0;i<nAffected;i++) {
2842            walkback_[i]->decrementCuts(1000000);
2843          }
2844        }
2845#ifndef NDEBUG
2846        for (iObject=0;iObject<numberObjects_;iObject++) {
2847          CbcSimpleIntegerDynamicPseudoCost * obj =
2848            dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(object_[iObject]) ;
2849          CbcSimpleIntegerDynamicPseudoCost * obj2 =
2850            dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(saveObjects[iObject]) ;
2851          assert (obj->same(obj2));
2852        }
2853#endif
2854        int iModel;
2855        double scaleFactor=1.0;
2856        for (iModel=0;iModel<numberThreads_;iModel++) {
2857          //printf("model %d tree size %d\n",iModel,threadModel[iModel]->tree_->size());
2858          if (saveTreeSize>4*numberThreads_*defaultParallelNodes) {
2859            if (!threadModel[iModel]->tree_->size()) {
2860              scaleFactor *= 1.05;
2861            }
2862          }
2863          threadModel[iModel]->moveToModel(this,11);
2864          // Update base model
2865          OsiObject ** threadObject = threadModel[iModel]->object_;
2866          for (iObject=0;iObject<numberObjects_;iObject++) {
2867            object_[iObject]->updateAfter(threadObject[iObject],saveObjects[iObject]);
2868          }
2869        }
2870        if (scaleFactor!=1.0) {
2871          int newNumber = (int) (defaultParallelNodes * scaleFactor+0.5001);
2872          if (newNumber*2<defaultParallelIterations) {
2873            printf("Changing tree size from %d to %d\n",
2874                   defaultParallelNodes,newNumber);
2875            defaultParallelNodes = newNumber;
2876          }
2877        }
2878        printf("Tree sizes %d %d %d - affected %d\n",saveTreeSize,saveTreeSize2,tree_->size(),nAffected);
2879        // later remember random may not be thread neutral
2880#endif
2881      }
2882      //lastDepth=node->depth();
2883      //lastUnsatisfied=node->numberUnsatisfied();
2884#endif // end of CBC_THREAD
2885  }
2886#ifdef CBC_DETERMINISTIC_THREAD
2887  if (nDeleteNode) {
2888    for (int i=0;i<nDeleteNode;i++) {
2889      delete delNode[i];
2890    }
2891    nDeleteNode=0;
2892  }
2893#endif
2894#ifdef CBC_THREAD
2895  if (numberThreads_) {
2896    //printf("stats ");
2897    //for (unsigned int j=0;j<sizeof(threadStats)/sizeof(int);j++)
2898    //printf("%d ",threadStats[j]);
2899    //printf("\n");
2900    int i;
2901    // Seems to be bug in CoinCpu on Linux - does threads as well despite documentation
2902    double time=0.0;
2903    for (i=0;i<numberThreads_;i++) 
2904      time += threadInfo[i].timeInThread;
2905    bool goodTimer = time<(getCurrentSeconds());
2906    //bool stopped = (!(numberNodes_ < intParam_[CbcMaxNumNode] &&
2907    //        numberSolutions_ < intParam_[CbcMaxNumSol] &&
2908    //        totalTime < dblParam_[CbcMaximumSeconds] &&
2909    //        !stoppedOnGap_&&!eventHappened_));
2910    for (i=0;i<numberThreads_;i++) {
2911      while (threadInfo[i].returnCode==0) {
2912        pthread_cond_signal(threadInfo[i].condition2); // unlock
2913        pthread_mutex_lock(&condition_mutex);
2914        struct timespec absTime;
2915        clock_gettime(CLOCK_REALTIME,&absTime);
2916        absTime.tv_nsec += 1000000; // millisecond
2917        if (absTime.tv_nsec>=1000000000) {
2918          absTime.tv_nsec -= 1000000000;
2919          absTime.tv_sec++;
2920        }
2921        pthread_cond_timedwait(&condition_main,&condition_mutex,&absTime);
2922        clock_gettime(CLOCK_REALTIME,&absTime);
2923        pthread_mutex_unlock(&condition_mutex);
2924      }
2925      pthread_cond_signal(threadInfo[i].condition2); // unlock
2926      pthread_mutex_lock(&condition_mutex); // not sure necessary but have had one hang on interrupt
2927      threadModel[i]->numberThreads_=0; // say exit
2928#ifdef CBC_DETERMINISTIC_THREAD
2929      delete [] threadInfo[i].delNode;
2930#endif
2931      threadInfo[i].returnCode=0;
2932      pthread_mutex_unlock(&condition_mutex);
2933      pthread_cond_signal(threadInfo[i].condition2); // unlock
2934      //if (!stopped)
2935      //pthread_join(threadId[i],NULL);
2936      int returnCode;
2937      returnCode=pthread_join(threadId[i],NULL);
2938      assert (!returnCode);
2939        //else
2940        //pthread_kill(threadId[i]); // kill rather than try and synchronize
2941      threadModel[i]->moveToModel(this,2);
2942      pthread_mutex_destroy (threadInfo[i].mutex2);
2943      pthread_cond_destroy (threadInfo[i].condition2);
2944      assert (threadInfo[i].numberTimesLocked==threadInfo[i].numberTimesUnlocked);
2945      handler_->message(CBC_THREAD_STATS,messages_)
2946        <<"Thread";
2947      handler_->printing(true)
2948        <<i<<threadCount[i]<<threadInfo[i].timeWaitingToStart;
2949      handler_->printing(goodTimer)<<threadInfo[i].timeInThread;
2950      handler_->printing(false)<<0.0;
2951      handler_->printing(true)<<threadInfo[i].numberTimesLocked
2952        <<threadInfo[i].timeLocked<<threadInfo[i].timeWaitingToLock
2953        <<CoinMessageEol;
2954    }
2955    assert (threadInfo[numberThreads_].numberTimesLocked==threadInfo[numberThreads_].numberTimesUnlocked);
2956    handler_->message(CBC_THREAD_STATS,messages_)
2957      <<"Main thread";
2958    handler_->printing(false)<<0<<0<<0.0;
2959    handler_->printing(false)<<0.0;
2960    handler_->printing(true)<<timeWaiting;
2961    handler_->printing(true)<<threadInfo[numberThreads_].numberTimesLocked
2962      <<threadInfo[numberThreads_].timeLocked<<threadInfo[numberThreads_].timeWaitingToLock
2963      <<CoinMessageEol;
2964    pthread_mutex_destroy (&mutex);
2965    pthread_cond_destroy (&condition_main);
2966    pthread_mutex_destroy (&condition_mutex);
2967    // delete models (here in case some point to others)
2968    for (i=0;i<numberThreads_;i++) {
2969      delete threadModel[i];
2970    }
2971    delete [] mutex2;
2972    delete [] condition2;
2973    delete [] threadId;
2974    delete [] threadInfo;
2975    delete [] threadModel;
2976    delete [] threadCount;
2977    mutex_=NULL;
2978    // adjust time to allow for children on some systems
2979    dblParam_[CbcStartSeconds] -= CoinCpuTimeJustChildren();
2980  }
2981#endif
2982/*
2983  End of the non-abort actions. The next block of code is executed if we've
2984  aborted because we hit one of the limits. Clean up by deleting the live set
2985  and break out of the node processing loop. Note that on an abort, node may
2986  have been pushed back onto the tree for further processing, in which case
2987  it'll be deleted in cleanTree. We need to check.
2988*/
2989    if (!(numberNodes_ < intParam_[CbcMaxNumNode] &&
2990        numberSolutions_ < intParam_[CbcMaxNumSol] &&
2991        totalTime < dblParam_[CbcMaximumSeconds] &&
2992        !stoppedOnGap_&&!eventHappened_)) {
2993      if (tree_->size())
2994        tree_->cleanTree(this,-COIN_DBL_MAX,bestPossibleObjective_) ;
2995      delete nextRowCut_;
2996      if (stoppedOnGap_)
2997        { messageHandler()->message(CBC_GAP,messages())
2998          << bestObjective_-bestPossibleObjective_
2999          << dblParam_[CbcAllowableGap]
3000          << dblParam_[CbcAllowableFractionGap]*100.0
3001          << CoinMessageEol ;
3002        secondaryStatus_ = 2;
3003        status_ = 0 ; }
3004        else
3005          if (isNodeLimitReached())
3006            { handler_->message(CBC_MAXNODES,messages_) << CoinMessageEol ;
3007            secondaryStatus_ = 3;
3008            status_ = 1 ; }
3009          else
3010        if (totalTime >= dblParam_[CbcMaximumSeconds])
3011          { handler_->message(CBC_MAXTIME,messages_) << CoinMessageEol ; 
3012          secondaryStatus_ = 4;
3013          status_ = 1 ; }
3014        else
3015          if (eventHappened_)
3016            { handler_->message(CBC_EVENT,messages_) << CoinMessageEol ; 
3017            secondaryStatus_ = 5;
3018            status_ = 5 ; }
3019          else
3020            { handler_->message(CBC_MAXSOLS,messages_) << CoinMessageEol ;
3021            secondaryStatus_ = 6;
3022            status_ = 1 ; }
3023    }
3024/*
3025  That's it, we've exhausted the search tree, or broken out of the loop because
3026  we hit some limit on evaluation.
3027
3028  We may have got an intelligent tree so give it one more chance
3029*/
3030  // Tell solver we are not in Branch and Cut
3031  solver_->setHintParam(OsiDoInBranchAndCut,false,OsiHintDo,NULL) ;
3032  tree_->endSearch();
3033  //  If we did any sub trees - did we give up on any?
3034  if ( numberStoppedSubTrees_)
3035    status_=1;
3036  if (!status_) {
3037    // Set best possible unless stopped on gap
3038    if(secondaryStatus_ != 2)
3039      bestPossibleObjective_=bestObjective_;
3040    handler_->message(CBC_END_GOOD,messages_)
3041      << bestObjective_ << numberIterations_ << numberNodes_<<getCurrentSeconds()
3042      << CoinMessageEol ;
3043  } else {
3044    handler_->message(CBC_END,messages_)
3045      << bestObjective_ <<bestPossibleObjective_
3046      << numberIterations_ << numberNodes_<<getCurrentSeconds()
3047      << CoinMessageEol ;
3048  }
3049  if (numberStrongIterations_)
3050    handler_->message(CBC_STRONG_STATS,messages_)
3051      << strongInfo_[0] << numberStrongIterations_ << strongInfo_[2]
3052      << strongInfo_[1] << CoinMessageEol ;
3053  handler_->message(CBC_OTHER_STATS,messages_)
3054      << maximumDepthActual_
3055      << numberDJFixed_ << CoinMessageEol ;
3056  if (doStatistics==100) {
3057    for (int i=0;i<numberObjects_;i++) {
3058      CbcSimpleIntegerDynamicPseudoCost * obj =
3059        dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(object_[i]) ;
3060      if (obj)
3061        obj->print();
3062    }
3063  }
3064  if (statistics_) {
3065    // report in some way
3066    int * lookup = new int[numberObjects_];
3067    int i;
3068    for (i=0;i<numberObjects_;i++) 
3069      lookup[i]=-1;
3070    bool goodIds=true;
3071    for (i=0;i<numberObjects_;i++) {
3072      int iColumn = object_[i]->columnNumber();
3073      if(iColumn>=0&&iColumn<numberColumns) {
3074        if (lookup[i]==-1) {
3075          lookup[i]=iColumn;
3076        } else {
3077          goodIds=false;
3078          break;
3079        }
3080      } else {
3081        goodIds=false;
3082        break;
3083      }
3084    }
3085    if (!goodIds) {
3086      delete [] lookup;
3087      lookup=NULL;
3088    }
3089    if (doStatistics==3) {
3090      printf("  node parent depth column   value                    obj      inf\n");
3091      for ( i=0;i<numberNodes2_;i++) {
3092        statistics_[i]->print(lookup);
3093      }
3094    }
3095    if (doStatistics>1) {
3096      // Find last solution
3097      int k;
3098      for (k=numberNodes2_-1;k>=0;k--) {
3099        if (statistics_[k]->endingObjective()!=COIN_DBL_MAX&&
3100            !statistics_[k]->endingInfeasibility())
3101          break;
3102      }
3103      if (k>=0) {
3104        int depth=statistics_[k]->depth();
3105        int * which = new int[depth+1];
3106        for (i=depth;i>=0;i--) {
3107          which[i]=k;
3108          k=statistics_[k]->parentNode();
3109        }
3110        printf("  node parent depth column   value                    obj      inf\n");
3111        for (i=0;i<=depth;i++) {
3112          statistics_[which[i]]->print(lookup);
3113        }
3114        delete [] which;
3115      }
3116    }
3117    // now summary
3118    int maxDepth=0;
3119    double averageSolutionDepth=0.0;
3120    int numberSolutions=0;
3121    double averageCutoffDepth=0.0;
3122    double averageSolvedDepth=0.0;
3123    int numberCutoff=0;
3124    int numberDown=0;
3125    int numberFirstDown=0;
3126    double averageInfDown=0.0;
3127    double averageObjDown=0.0;
3128    int numberCutoffDown=0;
3129    int numberUp=0;
3130    int numberFirstUp=0;
3131    double averageInfUp=0.0;
3132    double averageObjUp=0.0;
3133    int numberCutoffUp=0;
3134    double averageNumberIterations1=0.0;
3135    double averageValue=0.0;
3136    for ( i=0;i<numberNodes2_;i++) {
3137      int depth =  statistics_[i]->depth(); 
3138      int way =  statistics_[i]->way(); 
3139      double value = statistics_[i]->value(); 
3140      double startingObjective =  statistics_[i]->startingObjective(); 
3141      int startingInfeasibility = statistics_[i]->startingInfeasibility(); 
3142      double endingObjective = statistics_[i]->endingObjective(); 
3143      int endingInfeasibility = statistics_[i]->endingInfeasibility(); 
3144      maxDepth = CoinMax(depth,maxDepth);
3145      // Only for completed
3146      averageNumberIterations1 += statistics_[i]->numberIterations();
3147      averageValue += value;
3148      if (endingObjective!=COIN_DBL_MAX&&!endingInfeasibility) {
3149        numberSolutions++;
3150        averageSolutionDepth += depth;
3151      }
3152      if (endingObjective==COIN_DBL_MAX) {
3153        numberCutoff++;
3154        averageCutoffDepth += depth;
3155        if (way<0) {
3156          numberDown++;
3157          numberCutoffDown++;
3158          if (way==-1)
3159            numberFirstDown++;
3160        } else {
3161          numberUp++;
3162          numberCutoffUp++;
3163          if (way==1)
3164            numberFirstUp++;
3165        }
3166      } else {
3167        averageSolvedDepth += depth;
3168        if (way<0) {
3169          numberDown++;
3170          averageInfDown += startingInfeasibility-endingInfeasibility;
3171          averageObjDown += endingObjective-startingObjective;
3172          if (way==-1)
3173            numberFirstDown++;
3174        } else {
3175          numberUp++;
3176          averageInfUp += startingInfeasibility-endingInfeasibility;
3177          averageObjUp += endingObjective-startingObjective;
3178          if (way==1)
3179            numberFirstUp++;
3180        }
3181      }
3182    }
3183    // Now print
3184    if (numberSolutions)
3185      averageSolutionDepth /= (double) numberSolutions;
3186    int numberSolved = numberNodes2_-numberCutoff;
3187    double averageNumberIterations2=numberIterations_-averageNumberIterations1
3188      -numberIterationsAtContinuous;
3189    if(numberCutoff) {
3190      averageCutoffDepth /= (double) numberCutoff;
3191      averageNumberIterations2 /= (double) numberCutoff;
3192    }
3193    if (numberNodes2_) 
3194      averageValue /= (double) numberNodes2_;
3195    if (numberSolved) {
3196      averageNumberIterations1 /= (double) numberSolved;
3197      averageSolvedDepth /= (double) numberSolved;
3198    }
3199    printf("%d solution(s) were found (by branching) at an average depth of %g\n",
3200           numberSolutions,averageSolutionDepth);
3201    printf("average value of variable being branched on was %g\n",
3202           averageValue);
3203    printf("%d nodes were cutoff at an average depth of %g with iteration count of %g\n",
3204           numberCutoff,averageCutoffDepth,averageNumberIterations2);
3205    printf("%d nodes were solved at an average depth of %g with iteration count of %g\n",
3206           numberSolved,averageSolvedDepth,averageNumberIterations1);
3207    if (numberDown) {
3208      averageInfDown /= (double) numberDown;
3209      averageObjDown /= (double) numberDown;
3210    }
3211    printf("Down %d nodes (%d first, %d second) - %d cutoff, rest decrease numinf %g increase obj %g\n",
3212           numberDown,numberFirstDown,numberDown-numberFirstDown,numberCutoffDown,
3213           averageInfDown,averageObjDown);
3214    if (numberUp) {
3215      averageInfUp /= (double) numberUp;
3216      averageObjUp /= (double) numberUp;
3217    }
3218    printf("Up %d nodes (%d first, %d second) - %d cutoff, rest decrease numinf %g increase obj %g\n",
3219           numberUp,numberFirstUp,numberUp-numberFirstUp,numberCutoffUp,
3220           averageInfUp,averageObjUp);
3221    for ( i=0;i<numberNodes2_;i++) 
3222      delete statistics_[i];
3223    delete [] statistics_;
3224    statistics_=NULL;
3225    maximumStatistics_=0;
3226    delete [] lookup;
3227  }
3228/*
3229  If we think we have a solution, restore and confirm it with a call to
3230  setBestSolution().  We need to reset the cutoff value so as not to fathom
3231  the solution on bounds.  Note that calling setBestSolution( ..., true)
3232  leaves the continuousSolver_ bounds vectors fixed at the solution value.
3233
3234  Running resolve() here is a failsafe --- setBestSolution has already
3235  reoptimised using the continuousSolver_. If for some reason we fail to
3236  prove optimality, run the problem again after instructing the solver to
3237  tell us more.
3238
3239  If all looks good, replace solver_ with continuousSolver_, so that the
3240  outside world will be able to obtain information about the solution using
3241  public methods.
3242*/
3243  if (bestSolution_&&(solverCharacteristics_->solverType()<2||solverCharacteristics_->solverType()==4)) 
3244  { setCutoff(1.0e50) ; // As best solution should be worse than cutoff
3245    phase_=5;
3246    double increment = getDblParam(CbcModel::CbcCutoffIncrement) ;
3247    if ((specialOptions_&4)==0)
3248      bestObjective_ += 100.0*increment+1.0e-3; // only set if we are going to solve
3249    setBestSolution(CBC_END_SOLUTION,bestObjective_,bestSolution_,true) ;
3250    continuousSolver_->resolve() ;
3251    if (!continuousSolver_->isProvenOptimal())
3252    { continuousSolver_->messageHandler()->setLogLevel(2) ;
3253      continuousSolver_->initialSolve() ; }
3254    delete solver_ ;
3255    // above deletes solverCharacteristics_
3256    solverCharacteristics_ = NULL;
3257    solver_ = continuousSolver_ ;
3258    setPointers(solver_);
3259    continuousSolver_ = NULL ; }
3260/*
3261  Clean up dangling objects. continuousSolver_ may already be toast.
3262*/
3263  delete lastws ;
3264  if (saveObjects) {
3265    for (int i=0;i<numberObjects_;i++)
3266      delete saveObjects[i];
3267    delete [] saveObjects;
3268  }
3269  delete [] whichGenerator_ ;
3270  whichGenerator_=NULL;
3271  delete [] lowerBefore ;
3272  delete [] upperBefore ;
3273  delete [] walkback_ ;
3274  walkback_ = NULL ;
3275  delete [] addedCuts_ ;
3276  addedCuts_ = NULL ;
3277  //delete persistentInfo;
3278  // Get rid of characteristics
3279  solverCharacteristics_=NULL;
3280  if (continuousSolver_)
3281  { delete continuousSolver_ ;
3282    continuousSolver_ = NULL ; }
3283/*
3284  Destroy global cuts by replacing with an empty OsiCuts object.
3285*/
3286  globalCuts_= OsiCuts() ;
3287  if (!bestSolution_) {
3288    // make sure lp solver is infeasible
3289    int numberColumns = solver_->getNumCols();
3290    const double * columnLower = solver_->getColLower();
3291    int iColumn;
3292    for (iColumn=0;iColumn<numberColumns;iColumn++) {
3293      if (solver_->isInteger(iColumn)) 
3294        solver_->setColUpper(iColumn,columnLower[iColumn]);
3295    }
3296    solver_->initialSolve();
3297  }
3298  if (strategy_&&strategy_->preProcessState()>0) {
3299    // undo preprocessing
3300    CglPreProcess * process = strategy_->process();
3301    assert (process);
3302    int n = originalSolver->getNumCols();
3303    if (bestSolution_) {
3304      delete [] bestSolution_;
3305      bestSolution_ = new double [n];
3306      process->postProcess(*solver_);
3307    }
3308    strategy_->deletePreProcess();
3309    // Solution now back in originalSolver
3310    delete solver_;
3311    solver_=originalSolver;
3312    if (bestSolution_)
3313      memcpy(bestSolution_,solver_->getColSolution(),n*sizeof(double));
3314    // put back original objects if there were any
3315    if (originalObject) {
3316      int iColumn;
3317      assert (ownObjects_);
3318      for (iColumn=0;iColumn<numberObjects_;iColumn++) 
3319        delete object_[iColumn];
3320      delete [] object_;
3321      numberObjects_ = numberOriginalObjects;
3322      object_=originalObject;
3323      delete [] integerVariable_;
3324      numberIntegers_=0;
3325      for (iColumn=0;iColumn<n;iColumn++) {
3326        if (solver_->isInteger(iColumn))
3327          numberIntegers_++;
3328      }
3329      integerVariable_ = new int[numberIntegers_];
3330      numberIntegers_=0;
3331      for (iColumn=0;iColumn<n;iColumn++) {
3332        if (solver_->isInteger(iColumn))
3333            integerVariable_[numberIntegers_++]=iColumn;
3334      }
3335    }
3336  }
3337#ifdef CLP_QUICK_OPTIONS
3338  {
3339    OsiClpSolverInterface * clpSolver
3340      = dynamic_cast<OsiClpSolverInterface *> (solver_);
3341    if (clpSolver) {
3342      // Try and re-use regions   
3343      ClpSimplex * simplex = clpSolver->getModelPtr();
3344      simplex->setPersistenceFlag(0);
3345      clpSolver->deleteScaleFactors();
3346      clpSolver->setSpecialOptions(clpSolver->specialOptions()&(~131072));
3347      simplex->setSpecialOptions(simplex->specialOptions()&(~131072));
3348      simplex->setAlphaAccuracy(-1.0);
3349      //clpSolver->setSpecialOptions((clpSolver->specialOptions()&~128)|65536);
3350    }
3351  }
3352#endif
3353  return ;
3354 }
3355
3356
3357// Solve the initial LP relaxation
3358void 
3359CbcModel::initialSolve() 
3360{
3361  assert (solver_);
3362  assert (!solverCharacteristics_);
3363  OsiBabSolver * solverCharacteristics = dynamic_cast<OsiBabSolver *> (solver_->getAuxiliaryInfo());
3364  if (solverCharacteristics) {
3365    solverCharacteristics_ = solverCharacteristics;
3366  } else {
3367    // replace in solver
3368    OsiBabSolver defaultC;
3369    solver_->setAuxiliaryInfo(&defaultC);
3370    solverCharacteristics_ = dynamic_cast<OsiBabSolver *> (solver_->getAuxiliaryInfo());
3371  }
3372  solverCharacteristics_->setSolver(solver_);
3373  solver_->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,NULL) ;
3374  solver_->initialSolve();
3375  solver_->setHintParam(OsiDoInBranchAndCut,false,OsiHintDo,NULL) ;
3376  // But set up so Jon Lee will be happy
3377  status_=-1;
3378  secondaryStatus_ = -1;
3379  originalContinuousObjective_ = solver_->getObjValue()*solver_->getObjSense();
3380  delete [] continuousSolution_;
3381  continuousSolution_ = CoinCopyOfArray(solver_->getColSolution(),
3382                                             solver_->getNumCols());
3383  setPointers(solver_);
3384  solverCharacteristics_ = NULL;
3385}
3386
3387/*! \brief Get an empty basis object
3388
3389  Return an empty CoinWarmStartBasis object with the requested capacity,
3390  appropriate for the current solver. The object is cloned from the object
3391  cached as emptyWarmStart_. If there is no cached object, the routine
3392  queries the solver for a warm start object, empties it, and caches the
3393  result.
3394*/
3395
3396CoinWarmStartBasis *CbcModel::getEmptyBasis (int ns, int na) const
3397
3398{ CoinWarmStartBasis *emptyBasis ;
3399/*
3400  Acquire an empty basis object, if we don't yet have one.
3401*/
3402  if (emptyWarmStart_ == 0)
3403  { if (solver_ == 0)
3404    { throw CoinError("Cannot construct basis without solver!",
3405                      "getEmptyBasis","CbcModel") ; }
3406    emptyBasis =
3407        dynamic_cast<CoinWarmStartBasis *>(solver_->getEmptyWarmStart()) ;
3408    if (emptyBasis == 0)
3409    { throw CoinError(
3410        "Solver does not appear to use a basis-oriented warm start.",
3411        "getEmptyBasis","CbcModel") ; }
3412    emptyBasis->setSize(0,0) ;
3413    emptyWarmStart_ = dynamic_cast<CoinWarmStart *>(emptyBasis) ; }
3414/*
3415  Clone the empty basis object, resize it as requested, and return.
3416*/
3417  emptyBasis = dynamic_cast<CoinWarmStartBasis *>(emptyWarmStart_->clone()) ;
3418  assert(emptyBasis) ;
3419  if (ns != 0 || na != 0) emptyBasis->setSize(ns,na) ;
3420
3421  return (emptyBasis) ; }
3422   
3423
3424/** Default Constructor
3425
3426  Creates an empty model without an associated solver.
3427*/
3428CbcModel::CbcModel() 
3429
3430:
3431  solver_(NULL),
3432  ownership_(0x80000000),
3433  continuousSolver_(NULL),
3434  referenceSolver_(NULL),
3435  defaultHandler_(true),
3436  emptyWarmStart_(NULL),
3437  bestObjective_(COIN_DBL_MAX),
3438  bestPossibleObjective_(COIN_DBL_MAX),
3439  sumChangeObjective1_(0.0),
3440  sumChangeObjective2_(0.0),
3441  bestSolution_(NULL),
3442  currentSolution_(NULL),
3443  testSolution_(NULL),
3444  minimumDrop_(1.0e-4),
3445  numberSolutions_(0),
3446  stateOfSearch_(0),
3447  hotstartSolution_(NULL),
3448  hotstartPriorities_(NULL),
3449  numberHeuristicSolutions_(0),
3450  numberNodes_(0),
3451  numberNodes2_(0),
3452  numberIterations_(0),
3453  status_(-1),
3454  secondaryStatus_(-1),
3455  numberIntegers_(0),
3456  numberRowsAtContinuous_(0),
3457  maximumNumberCuts_(0),
3458  phase_(0),
3459  currentNumberCuts_(0),
3460  maximumDepth_(0),
3461  walkback_(NULL),
3462  addedCuts_(NULL),
3463  nextRowCut_(NULL),
3464  currentNode_(NULL),
3465  integerVariable_(NULL),
3466  integerInfo_(NULL),
3467  continuousSolution_(NULL),
3468  usedInSolution_(NULL),
3469  specialOptions_(0),
3470  subTreeModel_(NULL),
3471  numberStoppedSubTrees_(0),
3472  mutex_(NULL),
3473  presolve_(0),
3474  numberStrong_(5),
3475  numberBeforeTrust_(10),
3476  numberPenalties_(20),
3477  stopNumberIterations_(-1),
3478  penaltyScaleFactor_(3.0),
3479  numberAnalyzeIterations_(0),
3480  analyzeResults_(NULL),
3481  numberInfeasibleNodes_(0),
3482  problemType_(0),
3483  printFrequency_(0),
3484  numberCutGenerators_(0),
3485  generator_(NULL),
3486  virginGenerator_(NULL),
3487  numberHeuristics_(0),
3488  heuristic_(NULL),
3489  lastHeuristic_(NULL),
3490  eventHandler_(0),
3491  numberObjects_(0),
3492  object_(NULL),
3493  ownObjects_(true),
3494  originalColumns_(NULL),
3495  howOftenGlobalScan_(1),
3496  numberGlobalViolations_(0),
3497  continuousObjective_(COIN_DBL_MAX),
3498  originalContinuousObjective_(COIN_DBL_MAX),
3499  continuousInfeasibilities_(COIN_INT_MAX),
3500  maximumCutPassesAtRoot_(20),
3501  maximumCutPasses_(10),
3502  preferredWay_(0),
3503  currentPassNumber_(0),
3504  maximumWhich_(1000),
3505  maximumRows_(0),
3506  whichGenerator_(NULL),
3507  maximumStatistics_(0),
3508  statistics_(NULL),
3509  maximumDepthActual_(0),
3510  numberDJFixed_(0.0),
3511  probingInfo_(NULL),
3512  numberFixedAtRoot_(0),
3513  numberFixedNow_(0),
3514  stoppedOnGap_(false),
3515  eventHappened_(false),
3516  numberLongStrong_(0),
3517  numberOldActiveCuts_(0),
3518  numberNewCuts_(0),
3519  sizeMiniTree_(0),
3520  searchStrategy_(-1),
3521  numberStrongIterations_(0),
3522  resolveAfterTakeOffCuts_(true),
3523#if NEW_UPDATE_OBJECT>1
3524  numberUpdateItems_(0),
3525  maximumNumberUpdateItems_(0),
3526  updateItems_(NULL),
3527#endif
3528  numberThreads_(0),
3529  threadMode_(0)
3530{
3531  memset(intParam_,0,sizeof(intParam_));
3532  intParam_[CbcMaxNumNode] = 2147483647;
3533  intParam_[CbcMaxNumSol] = 9999999;
3534  intParam_[CbcFathomDiscipline] = 0;
3535
3536  dblParam_[CbcIntegerTolerance] = 1e-6;
3537  dblParam_[CbcInfeasibilityWeight] = 0.0;
3538  dblParam_[CbcCutoffIncrement] = 1e-5;
3539  dblParam_[CbcAllowableGap] = 1.0e-10;
3540  dblParam_[CbcAllowableFractionGap] = 0.0;
3541  dblParam_[CbcMaximumSeconds] = 1.0e100;
3542  dblParam_[CbcCurrentCutoff] = 1.0e100;
3543  dblParam_[CbcOptimizationDirection] = 1.0;
3544  dblParam_[CbcCurrentObjectiveValue] = 1.0e100;
3545  dblParam_[CbcCurrentMinimizationObjectiveValue] = 1.0e100;
3546  dblParam_[CbcStartSeconds] = 0.0;
3547  strongInfo_[0]=0;
3548  strongInfo_[1]=0;
3549  strongInfo_[2]=0;
3550  solverCharacteristics_ = NULL;
3551  nodeCompare_=new CbcCompareDefault();;
3552  problemFeasibility_=new CbcFeasibilityBase();
3553  tree_= new CbcTree();
3554  branchingMethod_=NULL;
3555  cutModifier_=NULL;
3556  strategy_=NULL;
3557  parentModel_=NULL;
3558  cbcColLower_ = NULL;
3559  cbcColUpper_ = NULL;
3560  cbcRowLower_ = NULL;
3561  cbcRowUpper_ = NULL;
3562  cbcColSolution_ = NULL;
3563  cbcRowPrice_ = NULL;
3564  cbcReducedCost_ = NULL;
3565  cbcRowActivity_ = NULL;
3566  appData_=NULL;
3567  handler_ = new CoinMessageHandler();
3568  handler_->setLogLevel(2);
3569  messages_ = CbcMessage();
3570  eventHandler_ = new CbcEventHandler() ;
3571}
3572
3573/** Constructor from solver.
3574
3575  Creates a model complete with a clone of the solver passed as a parameter.
3576*/
3577
3578CbcModel::CbcModel(const OsiSolverInterface &rhs)
3579:
3580  continuousSolver_(NULL),
3581  referenceSolver_(NULL),
3582  defaultHandler_(true),
3583  emptyWarmStart_(NULL),
3584  bestObjective_(COIN_DBL_MAX),
3585  bestPossibleObjective_(COIN_DBL_MAX),
3586  sumChangeObjective1_(0.0),
3587  sumChangeObjective2_(0.0),
3588  minimumDrop_(1.0e-4),
3589  numberSolutions_(0),
3590  stateOfSearch_(0),
3591  hotstartSolution_(NULL),
3592  hotstartPriorities_(NULL),
3593  numberHeuristicSolutions_(0),
3594  numberNodes_(0),
3595  numberNodes2_(0),
3596  numberIterations_(0),
3597  status_(-1),
3598  secondaryStatus_(-1),
3599  numberRowsAtContinuous_(0),
3600  maximumNumberCuts_(0),
3601  phase_(0),
3602  currentNumberCuts_(0),
3603  maximumDepth_(0),
3604  walkback_(NULL),
3605  addedCuts_(NULL),
3606  nextRowCut_(NULL),
3607  currentNode_(NULL),
3608  integerInfo_(NULL),
3609  specialOptions_(0),
3610  subTreeModel_(NULL),
3611  numberStoppedSubTrees_(0),
3612  mutex_(NULL),
3613  presolve_(0),
3614  numberStrong_(5),
3615  numberBeforeTrust_(10),
3616  numberPenalties_(20),
3617  stopNumberIterations_(-1),
3618  penaltyScaleFactor_(3.0),
3619  numberAnalyzeIterations_(0),
3620  analyzeResults_(NULL),
3621  numberInfeasibleNodes_(0),
3622  problemType_(0),
3623  printFrequency_(0),
3624  numberCutGenerators_(0),
3625  generator_(NULL),
3626  virginGenerator_(NULL),
3627  numberHeuristics_(0),
3628  heuristic_(NULL),
3629  lastHeuristic_(NULL),
3630  eventHandler_(0),
3631  numberObjects_(0),
3632  object_(NULL),
3633  ownObjects_(true),
3634  originalColumns_(NULL),
3635  howOftenGlobalScan_(1),
3636  numberGlobalViolations_(0),
3637  continuousObjective_(COIN_DBL_MAX),
3638  originalContinuousObjective_(COIN_DBL_MAX),
3639  continuousInfeasibilities_(COIN_INT_MAX),
3640  maximumCutPassesAtRoot_(20),
3641  maximumCutPasses_(10),
3642  preferredWay_(0),
3643  currentPassNumber_(0),
3644  maximumWhich_(1000),
3645  maximumRows_(0),
3646  whichGenerator_(NULL),
3647  maximumStatistics_(0),
3648  statistics_(NULL),
3649  maximumDepthActual_(0),
3650  numberDJFixed_(0.0),
3651  probingInfo_(NULL),
3652  numberFixedAtRoot_(0),
3653  numberFixedNow_(0),
3654  stoppedOnGap_(false),
3655  eventHappened_(false),
3656  numberLongStrong_(0),
3657  numberOldActiveCuts_(0),
3658  numberNewCuts_(0),
3659  sizeMiniTree_(0),
3660  searchStrategy_(-1),
3661  numberStrongIterations_(0),
3662  resolveAfterTakeOffCuts_(true),
3663#if NEW_UPDATE_OBJECT>1
3664  numberUpdateItems_(0),
3665  maximumNumberUpdateItems_(0),
3666  updateItems_(NULL),
3667#endif
3668  numberThreads_(0),
3669  threadMode_(0)
3670{
3671  memset(intParam_,0,sizeof(intParam_));
3672  intParam_[CbcMaxNumNode] = 2147483647;
3673  intParam_[CbcMaxNumSol] = 9999999;
3674  intParam_[CbcFathomDiscipline] = 0;
3675
3676  dblParam_[CbcIntegerTolerance] = 1e-6;
3677  dblParam_[CbcInfeasibilityWeight] = 0.0;
3678  dblParam_[CbcCutoffIncrement] = 1e-5;
3679  dblParam_[CbcAllowableGap] = 1.0e-10;
3680  dblParam_[CbcAllowableFractionGap] = 0.0;
3681  dblParam_[CbcMaximumSeconds] = 1.0e100;
3682  dblParam_[CbcCurrentCutoff] = 1.0e100;
3683  dblParam_[CbcOptimizationDirection] = 1.0;
3684  dblParam_[CbcCurrentObjectiveValue] = 1.0e100;
3685  dblParam_[CbcCurrentMinimizationObjectiveValue] = 1.0e100;
3686  dblParam_[CbcStartSeconds] = 0.0;
3687  strongInfo_[0]=0;
3688  strongInfo_[1]=0;
3689  strongInfo_[2]=0;
3690  solverCharacteristics_ = NULL;
3691
3692  nodeCompare_=new CbcCompareDefault();;
3693  problemFeasibility_=new CbcFeasibilityBase();
3694  tree_= new CbcTree();
3695  branchingMethod_=NULL;
3696  cutModifier_=NULL;
3697  strategy_=NULL;
3698  parentModel_=NULL;
3699  appData_=NULL;
3700  handler_ = new CoinMessageHandler();
3701  handler_->setLogLevel(2);
3702  messages_ = CbcMessage();
3703  eventHandler_ = new CbcEventHandler() ;
3704  solver_ = rhs.clone();
3705  referenceSolver_ = solver_->clone();
3706  ownership_ = 0x80000000;
3707  cbcColLower_ = NULL;
3708  cbcColUpper_ = NULL;
3709  cbcRowLower_ = NULL;
3710  cbcRowUpper_ = NULL;
3711  cbcColSolution_ = NULL;
3712  cbcRowPrice_ = NULL;
3713  cbcReducedCost_ = NULL;
3714  cbcRowActivity_ = NULL;
3715
3716  // Initialize solution and integer variable vectors
3717  bestSolution_ = NULL; // to say no solution found
3718  numberIntegers_=0;
3719  int numberColumns = solver_->getNumCols();
3720  int iColumn;
3721  if (numberColumns) {
3722    // Space for current solution
3723    currentSolution_ = new double[numberColumns];
3724    continuousSolution_ = new double[numberColumns];
3725    usedInSolution_ = new int[numberColumns];
3726    CoinZeroN(usedInSolution_,numberColumns);
3727    for (iColumn=0;iColumn<numberColumns;iColumn++) {
3728      if( solver_->isInteger(iColumn)) 
3729        numberIntegers_++;
3730    }
3731  } else {
3732    // empty model
3733    currentSolution_=NULL;
3734    continuousSolution_=NULL;
3735    usedInSolution_=NULL;
3736  }
3737  testSolution_=currentSolution_;
3738  if (numberIntegers_) {
3739    integerVariable_ = new int [numberIntegers_];
3740    numberIntegers_=0;
3741    for (iColumn=0;iColumn<numberColumns;iColumn++) {
3742      if( solver_->isInteger(iColumn)) 
3743        integerVariable_[numberIntegers_++]=iColumn;
3744    }
3745  } else {
3746    integerVariable_ = NULL;
3747  }
3748}
3749
3750/*
3751  Assign a solver to the model (model assumes ownership)
3752
3753  The integer variable vector is initialized if it's not already present.
3754  If deleteSolver then current solver deleted (if model owned)
3755
3756  Assuming ownership matches usage in OsiSolverInterface
3757  (cf. assignProblem, loadProblem).
3758
3759  TODO: What to do about solver parameters? A simple copy likely won't do it,
3760        because the SI must push the settings into the underlying solver. In
3761        the context of switching solvers in cbc, this means that command line
3762        settings will get lost. Stash the command line somewhere and reread it
3763        here, maybe?
3764 
3765  TODO: More generally, how much state should be transferred from the old
3766        solver to the new solver? Best perhaps to see how usage develops.
3767        What's done here mimics the CbcModel(OsiSolverInterface) constructor.
3768*/
3769void
3770CbcModel::assignSolver(OsiSolverInterface *&solver, bool deleteSolver)
3771
3772{
3773  // resize best solution if exists
3774  if (bestSolution_&&solver&&solver_) {
3775    int nOld = solver_->getNumCols();
3776    int nNew = solver->getNumCols();
3777    if (nNew>nOld) {
3778      double * temp = new double[nNew];
3779      memcpy(temp,bestSolution_,nOld*sizeof(double));
3780      memset(temp+nOld,0,(nNew-nOld)*sizeof(double));
3781      delete [] bestSolution_;
3782      bestSolution_=temp;
3783    }
3784  }
3785  // Keep the current message level for solver (if solver exists)
3786  if (solver_)
3787    solver->messageHandler()->setLogLevel(solver_->messageHandler()->logLevel()) ;
3788
3789  if (modelOwnsSolver()&&deleteSolver) delete solver_ ;
3790  solver_ = solver;
3791  solver = NULL ;
3792  setModelOwnsSolver(true) ;
3793/*
3794  Basis information is solver-specific.
3795*/
3796  if (emptyWarmStart_)
3797  { delete emptyWarmStart_  ;
3798    emptyWarmStart_ = 0 ; }
3799  bestSolutionBasis_ = CoinWarmStartBasis();
3800/*
3801  Initialize integer variable vector.
3802*/
3803  numberIntegers_=0;
3804  int numberColumns = solver_->getNumCols();
3805  int iColumn;
3806  for (iColumn=0;iColumn<numberColumns;iColumn++) {
3807    if( solver_->isInteger(iColumn)) 
3808      numberIntegers_++;
3809  }
3810  delete [] integerVariable_;
3811  if (numberIntegers_) {
3812    integerVariable_ = new int [numberIntegers_];
3813    numberIntegers_=0;
3814    for (iColumn=0;iColumn<numberColumns;iColumn++) {
3815      if( solver_->isInteger(iColumn)) 
3816        integerVariable_[numberIntegers_++]=iColumn;
3817    }
3818  } else {
3819    integerVariable_ = NULL;
3820  }
3821
3822  return ;
3823}
3824
3825// Copy constructor.
3826
3827CbcModel::CbcModel(const CbcModel & rhs, bool noTree)
3828:
3829  continuousSolver_(NULL),
3830  referenceSolver_(NULL),
3831  defaultHandler_(rhs.defaultHandler_),
3832  emptyWarmStart_(NULL),
3833  bestObjective_(rhs.bestObjective_),
3834  bestPossibleObjective_(rhs.bestPossibleObjective_),
3835  sumChangeObjective1_(rhs.sumChangeObjective1_),
3836  sumChangeObjective2_(rhs.sumChangeObjective2_),
3837  minimumDrop_(rhs.minimumDrop_),
3838  numberSolutions_(rhs.numberSolutions_),
3839  stateOfSearch_(rhs.stateOfSearch_),
3840  numberHeuristicSolutions_(rhs.numberHeuristicSolutions_),
3841  numberNodes_(rhs.numberNodes_),
3842  numberNodes2_(rhs.numberNodes2_),
3843  numberIterations_(rhs.numberIterations_),
3844  status_(rhs.status_),
3845  secondaryStatus_(rhs.secondaryStatus_),
3846  specialOptions_(rhs.specialOptions_),
3847  subTreeModel_(rhs.subTreeModel_),
3848  numberStoppedSubTrees_(rhs.numberStoppedSubTrees_),
3849  mutex_(NULL),
3850  presolve_(rhs.presolve_),
3851  numberStrong_(rhs.numberStrong_),
3852  numberBeforeTrust_(rhs.numberBeforeTrust_),
3853  numberPenalties_(rhs.numberPenalties_),
3854  stopNumberIterations_(rhs.stopNumberIterations_),
3855  penaltyScaleFactor_(rhs.penaltyScaleFactor_),
3856  numberAnalyzeIterations_(rhs.numberAnalyzeIterations_),
3857  analyzeResults_(NULL),
3858  numberInfeasibleNodes_(rhs.numberInfeasibleNodes_),
3859  problemType_(rhs.problemType_),
3860  printFrequency_(rhs.printFrequency_),
3861  howOftenGlobalScan_(rhs.howOftenGlobalScan_),
3862  numberGlobalViolations_(rhs.numberGlobalViolations_),
3863  continuousObjective_(rhs.continuousObjective_),
3864  originalContinuousObjective_(rhs.originalContinuousObjective_),
3865  continuousInfeasibilities_(rhs.continuousInfeasibilities_),
3866  maximumCutPassesAtRoot_(rhs.maximumCutPassesAtRoot_),
3867  maximumCutPasses_( rhs.maximumCutPasses_),
3868  preferredWay_(rhs.preferredWay_),
3869  currentPassNumber_(rhs.currentPassNumber_),
3870  maximumWhich_(rhs.maximumWhich_),
3871  maximumRows_(0),
3872  whichGenerator_(NULL),
3873  maximumStatistics_(0),
3874  statistics_(NULL),
3875  maximumDepthActual_(0),
3876  numberDJFixed_(0.0),
3877  probingInfo_(NULL),
3878  numberFixedAtRoot_(rhs.numberFixedAtRoot_),
3879  numberFixedNow_(rhs.numberFixedNow_),
3880  stoppedOnGap_(rhs.stoppedOnGap_),
3881  eventHappened_(rhs.eventHappened_),
3882  numberLongStrong_(rhs.numberLongStrong_),
3883  numberOldActiveCuts_(rhs.numberOldActiveCuts_),
3884  numberNewCuts_(rhs.numberNewCuts_),
3885  sizeMiniTree_(rhs.sizeMiniTree_),
3886  searchStrategy_(rhs.searchStrategy_),
3887  numberStrongIterations_(rhs.numberStrongIterations_),
3888  resolveAfterTakeOffCuts_(rhs.resolveAfterTakeOffCuts_),
3889#if NEW_UPDATE_OBJECT>1
3890  numberUpdateItems_(rhs.numberUpdateItems_),
3891  maximumNumberUpdateItems_(rhs.maximumNumberUpdateItems_),
3892  updateItems_(NULL),
3893#endif
3894  numberThreads_(rhs.numberThreads_),
3895  threadMode_(rhs.threadMode_)
3896{
3897  memcpy(intParam_,rhs.intParam_,sizeof(intParam_));
3898  memcpy(dblParam_,rhs.dblParam_,sizeof(dblParam_));
3899  strongInfo_[0]=rhs.strongInfo_[0];
3900  strongInfo_[1]=rhs.strongInfo_[1];
3901  strongInfo_[2]=rhs.strongInfo_[2];
3902  solverCharacteristics_ = NULL;
3903  if (rhs.emptyWarmStart_) emptyWarmStart_ = rhs.emptyWarmStart_->clone() ;
3904  if (defaultHandler_) {
3905    handler_ = new CoinMessageHandler();
3906    handler_->setLogLevel(2);
3907  } else {
3908    handler_ = rhs.handler_;
3909  }
3910  messageHandler()->setLogLevel(rhs.messageHandler()->logLevel());
3911  numberCutGenerators_ = rhs.numberCutGenerators_;
3912  if (numberCutGenerators_) {
3913    generator_ = new CbcCutGenerator * [numberCutGenerators_];
3914    virginGenerator_ = new CbcCutGenerator * [numberCutGenerators_];
3915    int i;
3916    for (i=0;i<numberCutGenerators_;i++) {
3917      generator_[i]=new CbcCutGenerator(*rhs.generator_[i]);
3918      virginGenerator_[i]=new CbcCutGenerator(*rhs.virginGenerator_[i]);
3919    }
3920  } else {
3921    generator_=NULL;
3922    virginGenerator_=NULL;
3923  }
3924  if (!noTree)
3925    globalCuts_ = rhs.globalCuts_;
3926  numberHeuristics_ = rhs.numberHeuristics_;
3927  if (numberHeuristics_) {
3928    heuristic_ = new CbcHeuristic * [numberHeuristics_];
3929    int i;
3930    for (i=0;i<numberHeuristics_;i++) {
3931      heuristic_[i]=rhs.heuristic_[i]->clone();
3932    }
3933  } else {
3934    heuristic_=NULL;
3935  }
3936  lastHeuristic_ = NULL;
3937  if (rhs.eventHandler_)
3938    { eventHandler_ = rhs.eventHandler_->clone() ; }
3939  else
3940  { eventHandler_ = NULL ; }
3941  ownObjects_ = rhs.ownObjects_;
3942  if (ownObjects_) {
3943    numberObjects_=rhs.numberObjects_;
3944    if (numberObjects_) {
3945      object_ = new OsiObject * [numberObjects_];
3946      int i;
3947      for (i=0;i<numberObjects_;i++) {
3948        object_[i]=(rhs.object_[i])->clone();
3949        CbcObject * obj = dynamic_cast <CbcObject *>(object_[i]) ;
3950        // Could be OsiObjects
3951        if (obj)
3952          obj->setModel(this);
3953      }
3954    } else {
3955      object_=NULL;
3956    }
3957  } else {
3958    // assume will be redone
3959    numberObjects_=0;
3960    object_=NULL;
3961  }
3962  if (rhs.referenceSolver_)
3963    referenceSolver_ = rhs.referenceSolver_->clone();
3964  else
3965    referenceSolver_=NULL;
3966  if (!noTree||!rhs.continuousSolver_)
3967    solver_ = rhs.solver_->clone();
3968  else
3969    solver_ = rhs.continuousSolver_->clone();
3970  if (rhs.originalColumns_) {
3971    int numberColumns = solver_->getNumCols();
3972    originalColumns_= new int [numberColumns];
3973    memcpy(originalColumns_,rhs.originalColumns_,numberColumns*sizeof(int));
3974  } else {
3975    originalColumns_=NULL;
3976  }
3977#if NEW_UPDATE_OBJECT>1
3978  if (maximumNumberUpdateItems_) {
3979    updateItems_ = new CbcObjectUpdateData [maximumNumberUpdateItems_];
3980    for (int i=0;i<maximumNumberUpdateItems_;i++)
3981      updateItems_[i] = rhs.updateItems_[i];
3982  }
3983#endif
3984  if (maximumWhich_&&rhs.whichGenerator_)
3985    whichGenerator_ = CoinCopyOfArray(rhs.whichGenerator_,maximumWhich_);
3986  nodeCompare_=rhs.nodeCompare_->clone();
3987  problemFeasibility_=rhs.problemFeasibility_->clone();
3988  tree_= rhs.tree_->clone();
3989  if (rhs.branchingMethod_)
3990    branchingMethod_=rhs.branchingMethod_->clone();
3991  else
3992    branchingMethod_=NULL;
3993  if (rhs.cutModifier_)
3994    cutModifier_=rhs.cutModifier_->clone();
3995  else
3996    cutModifier_=NULL;
3997  cbcColLower_ = NULL;
3998  cbcColUpper_ = NULL;
3999  cbcRowLower_ = NULL;
4000  cbcRowUpper_ = NULL;
4001  cbcColSolution_ = NULL;
4002  cbcRowPrice_ = NULL;
4003  cbcReducedCost_ = NULL;
4004  cbcRowActivity_ = NULL;
4005  if (rhs.strategy_)
4006    strategy_=rhs.strategy_->clone();
4007  else
4008    strategy_=NULL;
4009  parentModel_=rhs.parentModel_;
4010  appData_=rhs.appData_;
4011  messages_ = rhs.messages_;
4012  ownership_ = 0x80000000;
4013  messageHandler()->setLogLevel(rhs.messageHandler()->logLevel());
4014  numberIntegers_=rhs.numberIntegers_;
4015  if (numberIntegers_) {
4016    integerVariable_ = new int [numberIntegers_];
4017    memcpy(integerVariable_,rhs.integerVariable_,numberIntegers_*sizeof(int));
4018    integerInfo_ = CoinCopyOfArray(rhs.integerInfo_,solver_->getNumCols());
4019  } else {
4020    integerVariable_ = NULL;
4021    integerInfo_=NULL;
4022  }
4023  if (rhs.hotstartSolution_) {
4024    int numberColumns = solver_->getNumCols();
4025    hotstartSolution_ = CoinCopyOfArray(rhs.hotstartSolution_,numberColumns);
4026    hotstartPriorities_ = CoinCopyOfArray(rhs.hotstartPriorities_,numberColumns);
4027  } else {
4028    hotstartSolution_ = NULL;
4029    hotstartPriorities_ =NULL;
4030  }
4031  if (rhs.bestSolution_&&!noTree) {
4032    int numberColumns = solver_->getNumCols();
4033    bestSolution_ = new double[numberColumns];
4034    memcpy(bestSolution_,rhs.bestSolution_,numberColumns*sizeof(double));
4035  } else {
4036    bestSolution_=NULL;
4037  }
4038  if (!noTree) {
4039    int numberColumns = solver_->getNumCols();
4040    // Space for current solution
4041    currentSolution_ = new double[numberColumns];
4042    continuousSolution_ = new double[numberColumns];
4043    usedInSolution_ = new int[numberColumns];
4044    CoinZeroN(usedInSolution_,numberColumns);
4045  } else {
4046    currentSolution_=NULL;
4047    continuousSolution_=NULL;
4048    usedInSolution_=NULL;
4049  }
4050  testSolution_=currentSolution_;
4051  numberRowsAtContinuous_ = rhs.numberRowsAtContinuous_;
4052  maximumNumberCuts_=rhs.maximumNumberCuts_;
4053  phase_ = rhs.phase_;
4054  currentNumberCuts_=rhs.currentNumberCuts_;
4055  maximumDepth_= rhs.maximumDepth_;
4056  if (noTree) {
4057    bestObjective_ = COIN_DBL_MAX;
4058    numberSolutions_ =0;
4059    stateOfSearch_= 0;
4060    numberHeuristicSolutions_=0;
4061    numberNodes_=0;
4062    numberNodes2_=0;
4063    numberIterations_=0;
4064    status_=0;
4065    subTreeModel_=NULL;
4066    numberStoppedSubTrees_=0;
4067    continuousObjective_=COIN_DBL_MAX;
4068    originalContinuousObjective_=COIN_DBL_MAX;
4069    continuousInfeasibilities_=COIN_INT_MAX;
4070    maximumNumberCuts_=0;
4071    tree_->cleanTree(this,-COIN_DBL_MAX,bestPossibleObjective_);
4072    bestPossibleObjective_ = COIN_DBL_MAX;
4073  }
4074  // These are only used as temporary arrays so need not be filled
4075  if (maximumNumberCuts_) {
4076    addedCuts_ = new CbcCountRowCut * [maximumNumberCuts_];
4077  } else {
4078    addedCuts_ = NULL;
4079  }
4080  bestSolutionBasis_ = rhs.bestSolutionBasis_;
4081  nextRowCut_ = NULL;
4082  currentNode_ = NULL;
4083  if (maximumDepth_)
4084    walkback_ = new CbcNodeInfo * [maximumDepth_];
4085  else
4086    walkback_ = NULL;
4087  synchronizeModel();
4088}
4089 
4090// Assignment operator
4091CbcModel & 
4092CbcModel::operator=(const CbcModel& rhs)
4093{
4094  if (this!=&rhs) {
4095    if (modelOwnsSolver()) {
4096      delete solver_;
4097      solver_=NULL;
4098    }
4099    gutsOfDestructor();
4100    if (defaultHandler_)
4101    { delete handler_;
4102      handler_ = NULL; }
4103    defaultHandler_ = rhs.defaultHandler_;
4104    if (defaultHandler_)
4105    { handler_ = new CoinMessageHandler();
4106      handler_->setLogLevel(2); }
4107    else
4108    { handler_ = rhs.handler_; }
4109    messages_ = rhs.messages_;
4110    messageHandler()->setLogLevel(rhs.messageHandler()->logLevel());
4111    if (rhs.solver_)
4112    { solver_ = rhs.solver_->clone() ; }
4113    else
4114    { solver_ = 0 ; }
4115    ownership_ = 0x80000000;
4116    delete continuousSolver_ ;
4117    if (rhs.continuousSolver_)
4118    { continuousSolver_ = rhs.continuousSolver_->clone() ; }
4119    else
4120    { continuousSolver_ = 0 ; }
4121    delete referenceSolver_;
4122    if (rhs.referenceSolver_)
4123    { referenceSolver_ = rhs.referenceSolver_->clone() ; }
4124    else
4125    { referenceSolver_ = NULL ; }
4126
4127    delete emptyWarmStart_ ;
4128    if (rhs.emptyWarmStart_)
4129    { emptyWarmStart_ = rhs.emptyWarmStart_->clone() ; }
4130    else
4131    { emptyWarmStart_ = 0 ; }
4132
4133    bestObjective_ = rhs.bestObjective_;
4134    bestPossibleObjective_=rhs.bestPossibleObjective_;
4135    sumChangeObjective1_=rhs.sumChangeObjective1_;
4136    sumChangeObjective2_=rhs.sumChangeObjective2_;
4137    delete [] bestSolution_;
4138    if (rhs.bestSolution_) {
4139      int numberColumns = rhs.getNumCols();
4140      bestSolution_ = new double[numberColumns];
4141      memcpy(bestSolution_,rhs.bestSolution_,numberColumns*sizeof(double));
4142    } else {
4143      bestSolution_=NULL;
4144    }
4145    int numberColumns = rhs.getNumCols();
4146    if (numberColumns) {
4147      // Space for current solution
4148      currentSolution_ = new double[numberColumns];
4149      continuousSolution_ = new double[numberColumns];
4150      usedInSolution_ = new int[numberColumns];
4151      CoinZeroN(usedInSolution_,numberColumns);
4152    } else {
4153      currentSolution_=NULL;
4154      continuousSolution_=NULL;
4155      usedInSolution_=NULL;
4156    }
4157    testSolution_=currentSolution_;
4158    minimumDrop_ = rhs.minimumDrop_;
4159    numberSolutions_=rhs.numberSolutions_;
4160    stateOfSearch_= rhs.stateOfSearch_;
4161    numberHeuristicSolutions_=rhs.numberHeuristicSolutions_;
4162    numberNodes_ = rhs.numberNodes_;
4163    numberNodes2_ = rhs.numberNodes2_;
4164    numberIterations_ = rhs.numberIterations_;
4165    status_ = rhs.status_;
4166    secondaryStatus_ = rhs.secondaryStatus_;
4167    specialOptions_ = rhs.specialOptions_;
4168    subTreeModel_ = rhs.subTreeModel_;
4169    numberStoppedSubTrees_ = rhs.numberStoppedSubTrees_;
4170    mutex_ = NULL;
4171    presolve_ = rhs.presolve_;
4172    numberStrong_ = rhs.numberStrong_;
4173    numberBeforeTrust_ = rhs.numberBeforeTrust_;
4174    numberPenalties_ = rhs.numberPenalties_;
4175    stopNumberIterations_ = rhs.stopNumberIterations_;
4176    penaltyScaleFactor_ = rhs.penaltyScaleFactor_;
4177    numberAnalyzeIterations_ = rhs.numberAnalyzeIterations_;
4178    delete [] analyzeResults_;
4179    analyzeResults_ = NULL;
4180    numberInfeasibleNodes_ = rhs.numberInfeasibleNodes_;
4181    problemType_ = rhs.problemType_;
4182    printFrequency_ = rhs.printFrequency_;
4183    howOftenGlobalScan_=rhs.howOftenGlobalScan_;
4184    numberGlobalViolations_=rhs.numberGlobalViolations_;
4185    continuousObjective_=rhs.continuousObjective_;
4186    originalContinuousObjective_ = rhs.originalContinuousObjective_;
4187    continuousInfeasibilities_ = rhs.continuousInfeasibilities_;
4188    maximumCutPassesAtRoot_ = rhs.maximumCutPassesAtRoot_;
4189    maximumCutPasses_ = rhs.maximumCutPasses_;
4190    preferredWay_ = rhs.preferredWay_;
4191    currentPassNumber_ = rhs.currentPassNumber_;
4192    memcpy(intParam_,rhs.intParam_,sizeof(intParam_));
4193    memcpy(dblParam_,rhs.dblParam_,sizeof(dblParam_));
4194    globalCuts_ = rhs.globalCuts_;
4195    int i;
4196    for (i=0;i<numberCutGenerators_;i++) {
4197      delete generator_[i];
4198      delete virginGenerator_[i];
4199    }
4200    delete [] generator_;
4201    delete [] virginGenerator_;
4202    delete [] heuristic_;
4203    maximumWhich_ = rhs.maximumWhich_;
4204    delete [] whichGenerator_;
4205    whichGenerator_ = NULL;
4206    if (maximumWhich_&&rhs.whichGenerator_)
4207      whichGenerator_ = CoinCopyOfArray(rhs.whichGenerator_,maximumWhich_);
4208    maximumRows_=0;
4209    workingBasis_ = CoinWarmStartBasis();
4210    for (i=0;i<maximumStatistics_;i++)
4211      delete statistics_[i];
4212    delete [] statistics_;
4213    maximumStatistics_ = 0;
4214    statistics_ = NULL;
4215    delete probingInfo_;
4216    probingInfo_=NULL;
4217    numberFixedAtRoot_ = rhs.numberFixedAtRoot_;
4218    numberFixedNow_ = rhs.numberFixedNow_;
4219    stoppedOnGap_ = rhs.stoppedOnGap_;
4220    eventHappened_ = rhs.eventHappened_;
4221    numberLongStrong_ = rhs.numberLongStrong_;
4222    numberOldActiveCuts_ = rhs.numberOldActiveCuts_;
4223    numberNewCuts_ = rhs.numberNewCuts_;
4224    resolveAfterTakeOffCuts_=rhs.resolveAfterTakeOffCuts_;
4225#if NEW_UPDATE_OBJECT>1
4226    numberUpdateItems_ = rhs.numberUpdateItems_;
4227    maximumNumberUpdateItems_ = rhs.maximumNumberUpdateItems_;
4228    delete [] updateItems_;
4229    if (maximumNumberUpdateItems_) {
4230      updateItems_ = new CbcObjectUpdateData [maximumNumberUpdateItems_];
4231      for (i=0;i<maximumNumberUpdateItems_;i++)
4232        updateItems_[i] = rhs.updateItems_[i];
4233    } else {
4234      updateItems_ = NULL;
4235    }
4236#endif
4237    numberThreads_ = rhs.numberThreads_;
4238    threadMode_ = rhs.threadMode_;
4239    sizeMiniTree_ = rhs.sizeMiniTree_;
4240    searchStrategy_ = rhs.searchStrategy_;
4241    numberStrongIterations_ = rhs.numberStrongIterations_;
4242    strongInfo_[0]=rhs.strongInfo_[0];
4243    strongInfo_[1]=rhs.strongInfo_[1];
4244    strongInfo_[2]=rhs.strongInfo_[2];
4245    solverCharacteristics_ = NULL;
4246    lastHeuristic_ = NULL;
4247    numberCutGenerators_ = rhs.numberCutGenerators_;
4248    if (numberCutGenerators_) {
4249      generator_ = new CbcCutGenerator * [numberCutGenerators_];
4250      virginGenerator_ = new CbcCutGenerator * [numberCutGenerators_];
4251      int i;
4252      for (i=0;i<numberCutGenerators_;i++) {
4253        generator_[i]=new CbcCutGenerator(*rhs.generator_[i]);
4254        virginGenerator_[i]=new CbcCutGenerator(*rhs.virginGenerator_[i]);
4255      }
4256    } else {
4257      generator_=NULL;
4258      virginGenerator_=NULL;
4259    }
4260    numberHeuristics_ = rhs.numberHeuristics_;
4261    if (numberHeuristics_) {
4262      heuristic_ = new CbcHeuristic * [numberHeuristics_];
4263      memcpy(heuristic_,rhs.heuristic_,
4264             numberHeuristics_*sizeof(CbcHeuristic *));
4265    } else {
4266      heuristic_=NULL;
4267    }
4268    lastHeuristic_ = NULL;
4269    if (eventHandler_)
4270      delete eventHandler_ ;
4271    if (rhs.eventHandler_)
4272      { eventHandler_ = rhs.eventHandler_->clone() ; }
4273    else
4274    { eventHandler_ = NULL ; }
4275    if (ownObjects_) {
4276      for (i=0;i<numberObjects_;i++)
4277        delete object_[i];
4278      delete [] object_;
4279      numberObjects_=rhs.numberObjects_;
4280      if (numberObjects_) {
4281        object_ = new OsiObject * [numberObjects_];
4282        int i;
4283        for (i=0;i<numberObjects_;i++) 
4284          object_[i]=(rhs.object_[i])->clone();
4285      } else {
4286        object_=NULL;
4287    }
4288    } else {
4289      // assume will be redone
4290      numberObjects_=0;
4291      object_=NULL;
4292    }
4293    delete [] originalColumns_;
4294    if (rhs.originalColumns_) {
4295      int numberColumns = rhs.getNumCols();
4296      originalColumns_= new int [numberColumns];
4297      memcpy(originalColumns_,rhs.originalColumns_,numberColumns*sizeof(int));
4298    } else {
4299      originalColumns_=NULL;
4300    }
4301    nodeCompare_=rhs.nodeCompare_->clone();
4302    problemFeasibility_=rhs.problemFeasibility_->clone();
4303    delete tree_;
4304    tree_= rhs.tree_->clone();
4305    if (rhs.branchingMethod_)
4306      branchingMethod_=rhs.branchingMethod_->clone();
4307    else
4308      branchingMethod_=NULL;
4309    if (rhs.cutModifier_)
4310      cutModifier_=rhs.cutModifier_->clone();
4311    else
4312      cutModifier_=NULL;
4313    delete strategy_;
4314    if (rhs.strategy_)
4315      strategy_=rhs.strategy_->clone();
4316    else
4317      strategy_=NULL;
4318    parentModel_=rhs.parentModel_;
4319    appData_=rhs.appData_;
4320
4321    delete [] integerVariable_;
4322    numberIntegers_=rhs.numberIntegers_;
4323    if (numberIntegers_) {
4324      integerVariable_ = new int [numberIntegers_];
4325      memcpy(integerVariable_,rhs.integerVariable_,
4326             numberIntegers_*sizeof(int));
4327      integerInfo_ = CoinCopyOfArray(rhs.integerInfo_,rhs.getNumCols());
4328    } else {
4329      integerVariable_ = NULL;
4330      integerInfo_=NULL;
4331    }
4332    if (rhs.hotstartSolution_) {
4333      int numberColumns = solver_->getNumCols();
4334      hotstartSolution_ = CoinCopyOfArray(rhs.hotstartSolution_,numberColumns);
4335      hotstartPriorities_ = CoinCopyOfArray(rhs.hotstartPriorities_,numberColumns);
4336    } else {
4337      hotstartSolution_ = NULL;
4338      hotstartPriorities_ =NULL;
4339    }
4340    numberRowsAtContinuous_ = rhs.numberRowsAtContinuous_;
4341    maximumNumberCuts_=rhs.maximumNumberCuts_;
4342    phase_ = rhs.phase_;
4343    currentNumberCuts_=rhs.currentNumberCuts_;
4344    maximumDepth_= rhs.maximumDepth_;
4345    delete [] addedCuts_;
4346    delete [] walkback_;
4347    // These are only used as temporary arrays so need not be filled
4348    if (maximumNumberCuts_) {
4349      addedCuts_ = new CbcCountRowCut * [maximumNumberCuts_];
4350    } else {
4351      addedCuts_ = NULL;
4352    }
4353    bestSolutionBasis_ = rhs.bestSolutionBasis_;
4354    nextRowCut_ = NULL;
4355    currentNode_ = NULL;
4356    if (maximumDepth_)
4357      walkback_ = new CbcNodeInfo * [maximumDepth_];
4358    else
4359      walkback_ = NULL;
4360    synchronizeModel();
4361    cbcColLower_ = NULL;
4362    cbcColUpper_ = NULL;
4363    cbcRowLower_ = NULL;
4364    cbcRowUpper_ = NULL;
4365    cbcColSolution_ = NULL;
4366    cbcRowPrice_ = NULL;
4367    cbcReducedCost_ = NULL;
4368    cbcRowActivity_ = NULL;
4369  }
4370  return *this;
4371}
4372// Destructor
4373CbcModel::~CbcModel ()
4374{
4375  if (defaultHandler_) {
4376    delete handler_;
4377    handler_ = NULL;
4378  }
4379  delete tree_;
4380  tree_=NULL;
4381  if (modelOwnsSolver()) {
4382    delete solver_;
4383    solver_ = NULL;
4384  }
4385  gutsOfDestructor();
4386  delete eventHandler_ ;
4387  eventHandler_ = NULL ;
4388}
4389// Clears out as much as possible (except solver)
4390void 
4391CbcModel::gutsOfDestructor()
4392{
4393  delete referenceSolver_;
4394  referenceSolver_=NULL;
4395  int i;
4396  for (i=0;i<numberCutGenerators_;i++) {
4397    delete generator_[i];
4398    delete virginGenerator_[i];
4399  }
4400  delete [] generator_;
4401  delete [] virginGenerator_;
4402  generator_=NULL;
4403  virginGenerator_=NULL;
4404  for (i=0;i<numberHeuristics_;i++)
4405    delete heuristic_[i];
4406  delete [] heuristic_;
4407  heuristic_=NULL;
4408  delete nodeCompare_;
4409  nodeCompare_=NULL;
4410  delete problemFeasibility_;
4411  problemFeasibility_=NULL;
4412  delete [] originalColumns_;
4413  originalColumns_=NULL;
4414  delete strategy_;
4415#if NEW_UPDATE_OBJECT>1
4416  delete [] updateItems_;
4417  updateItems_=NULL;
4418  numberUpdateItems_=0;
4419  maximumNumberUpdateItems_=0;
4420#endif
4421  gutsOfDestructor2();
4422}
4423// Clears out enough to reset CbcModel
4424void 
4425CbcModel::gutsOfDestructor2()
4426{
4427  delete [] integerInfo_;
4428  integerInfo_=NULL;
4429  delete [] integerVariable_;
4430  integerVariable_=NULL;
4431  int i;
4432  if (ownObjects_) {
4433    for (i=0;i<numberObjects_;i++)
4434      delete object_[i];
4435    delete [] object_;
4436  }
4437  ownObjects_=true;
4438  object_=NULL;
4439  numberIntegers_=0;
4440  numberObjects_=0;
4441  // Below here is whatever consensus is
4442  ownership_ = 0x80000000;
4443  delete branchingMethod_;
4444  branchingMethod_=NULL;
4445  delete cutModifier_;
4446  cutModifier_=NULL;
4447  resetModel();
4448}
4449// Clears out enough to reset CbcModel
4450void 
4451CbcModel::resetModel()
4452{
4453  delete emptyWarmStart_ ;
4454  emptyWarmStart_ =NULL;
4455  delete continuousSolver_;
4456  continuousSolver_=NULL;
4457  delete [] bestSolution_;
4458  bestSolution_=NULL;
4459  delete [] currentSolution_;
4460  currentSolution_=NULL;
4461  delete [] continuousSolution_;
4462  continuousSolution_=NULL;
4463  solverCharacteristics_=NULL;
4464  delete [] usedInSolution_;
4465  usedInSolution_ = NULL;
4466  testSolution_=NULL;
4467  lastHeuristic_ = NULL;
4468  delete [] addedCuts_;
4469  addedCuts_=NULL;
4470  nextRowCut_ = NULL;
4471  currentNode_ = NULL;
4472  delete [] walkback_;
4473  walkback_=NULL;
4474  delete [] whichGenerator_;
4475  whichGenerator_ = NULL;
4476  for (int i=0;i<maximumStatistics_;i++)
4477    delete statistics_[i];
4478  delete [] statistics_;
4479  statistics_=NULL;
4480  maximumDepthActual_ = 0;
4481  numberDJFixed_ =0.0;
4482  delete probingInfo_;
4483  probingInfo_ = NULL;
4484  maximumStatistics_=0;
4485  delete [] analyzeResults_;
4486  analyzeResults_=NULL;
4487  bestObjective_=COIN_DBL_MAX;
4488  bestPossibleObjective_=COIN_DBL_MAX;
4489  sumChangeObjective1_=0.0;
4490  sumChangeObjective2_=0.0;
4491  numberSolutions_=0;
4492  stateOfSearch_=0;
4493  delete [] hotstartSolution_;
4494  hotstartSolution_=NULL;
4495  delete [] hotstartPriorities_;
4496  hotstartPriorities_=NULL;
4497  numberHeuristicSolutions_=0;
4498  numberNodes_=0;
4499  numberNodes2_=0;
4500  numberIterations_=0;
4501  status_=-1;
4502  secondaryStatus_=-1;
4503  maximumNumberCuts_=0;
4504  phase_=0;
4505  currentNumberCuts_=0;
4506  maximumDepth_=0;
4507  nextRowCut_=NULL;
4508  currentNode_=NULL;
4509  // clear out tree
4510  if (tree_&&tree_->size())
4511    tree_->cleanTree(this, -1.0e100,bestPossibleObjective_) ;
4512  subTreeModel_=NULL;
4513  numberStoppedSubTrees_=0;
4514  numberInfeasibleNodes_=0;
4515  numberGlobalViolations_=0;
4516  continuousObjective_=0.0;
4517  originalContinuousObjective_=0.0;
4518  continuousInfeasibilities_=0;
4519  numberFixedAtRoot_=0;
4520  numberFixedNow_=0;
4521  stoppedOnGap_=false;
4522  eventHappened_=false;
4523  numberLongStrong_=0;
4524  numberOldActiveCuts_=0;
4525  numberNewCuts_=0;
4526  searchStrategy_=-1;
4527  numberStrongIterations_=0;
4528  // Parameters which need to be reset
4529  setCutoff(COIN_DBL_MAX);
4530  dblParam_[CbcCutoffIncrement] = 1e-5;
4531  dblParam_[CbcCurrentCutoff] = 1.0e100;
4532  dblParam_[CbcCurrentObjectiveValue] = 1.0e100;
4533  dblParam_[CbcCurrentMinimizationObjectiveValue] = 1.0e100;
4534}
4535// Move status, nodes etc etc across
4536void 
4537CbcModel::moveInfo(const CbcModel & rhs)
4538{
4539  bestObjective_ = rhs.bestObjective_;
4540  bestPossibleObjective_=rhs.bestPossibleObjective_;
4541  numberSolutions_=rhs.numberSolutions_;
4542  numberHeuristicSolutions_=rhs.numberHeuristicSolutions_;
4543  numberNodes_ = rhs.numberNodes_;
4544  numberNodes2_ = rhs.numberNodes2_;
4545  numberIterations_ = rhs.numberIterations_;
4546  status_ = rhs.status_;
4547  secondaryStatus_ = rhs.secondaryStatus_;
4548  numberStoppedSubTrees_ = rhs.numberStoppedSubTrees_;
4549  numberInfeasibleNodes_ = rhs.numberInfeasibleNodes_;
4550  continuousObjective_=rhs.continuousObjective_;
4551  originalContinuousObjective_ = rhs.originalContinuousObjective_;
4552  continuousInfeasibilities_ = rhs.continuousInfeasibilities_;
4553  numberFixedAtRoot_ = rhs.numberFixedAtRoot_;
4554  numberFixedNow_ = rhs.numberFixedNow_;
4555  stoppedOnGap_ = rhs.stoppedOnGap_;
4556  eventHappened_ = rhs.eventHappened_;
4557  numberLongStrong_ = rhs.numberLongStrong_;
4558  numberStrongIterations_ = rhs.numberStrongIterations_;
4559  strongInfo_[0]=rhs.strongInfo_[0];
4560  strongInfo_[1]=rhs.strongInfo_[1];
4561  strongInfo_[2]=rhs.strongInfo_[2];
4562  numberRowsAtContinuous_ = rhs.numberRowsAtContinuous_;
4563  maximumDepth_= rhs.maximumDepth_;
4564}
4565// Save a copy of the current solver so can be reset to
4566void 
4567CbcModel::saveReferenceSolver()
4568{
4569  delete referenceSolver_;
4570  referenceSolver_= solver_->clone();
4571}
4572
4573// Uses a copy of reference solver to be current solver
4574void 
4575CbcModel::resetToReferenceSolver()
4576{
4577  delete solver_;
4578  solver_ = referenceSolver_->clone();
4579  // clear many things
4580  gutsOfDestructor2();
4581  // Reset cutoff
4582  // Solvers know about direction
4583  double direction = solver_->getObjSense();
4584  double value;
4585  solver_->getDblParam(OsiDualObjectiveLimit,value); 
4586  setCutoff(value*direction);
4587}
4588
4589// Are there a numerical difficulties?
4590bool 
4591CbcModel::isAbandoned() const
4592{
4593  return status_ == 2;
4594}
4595// Is optimality proven?
4596bool 
4597CbcModel::isProvenOptimal() const
4598{
4599  if (!status_ && bestObjective_<1.0e30)
4600    return true;
4601  else
4602    return false;
4603}
4604// Is  infeasiblity proven (or none better than cutoff)?
4605bool 
4606CbcModel::isProvenInfeasible() const
4607{
4608  if (!status_ && bestObjective_>=1.0e30)
4609    return true;
4610  else
4611    return false;
4612}
4613// Was continuous solution unbounded
4614bool 
4615CbcModel::isContinuousUnbounded() const
4616{
4617  if (!status_ && secondaryStatus_==7)
4618    return true;
4619  else
4620    return false;
4621}
4622// Was continuous solution unbounded
4623bool 
4624CbcModel::isProvenDualInfeasible() const
4625{
4626  if (!status_ && secondaryStatus_==7)
4627    return true;
4628  else
4629    return false;
4630}
4631// Node limit reached?
4632bool 
4633CbcModel::isNodeLimitReached() const
4634{
4635  return numberNodes_ >= intParam_[CbcMaxNumNode];
4636}
4637// Time limit reached?
4638bool 
4639CbcModel::isSecondsLimitReached() const
4640{
4641  if (status_==1&&secondaryStatus_==4)
4642    return true;
4643  else
4644    return false;
4645}
4646// Solution limit reached?
4647bool 
4648CbcModel::isSolutionLimitReached() const
4649{
4650  return numberSolutions_ >= intParam_[CbcMaxNumSol];
4651}
4652// Set language
4653void 
4654CbcModel::newLanguage(CoinMessages::Language language)
4655{
4656  messages_ = CbcMessage(language);
4657}
4658void 
4659CbcModel::setNumberStrong(int number)
4660{
4661  if (number<0)
4662    numberStrong_=0;
4663   else
4664    numberStrong_=number;
4665}
4666void 
4667CbcModel::setNumberBeforeTrust(int number)
4668{
4669  if (number<-3) {
4670    numberBeforeTrust_=0;
4671  } else {
4672    numberBeforeTrust_=number;
4673    //numberStrong_ = CoinMax(numberStrong_,1);
4674  }
4675}
4676void 
4677CbcModel::setNumberPenalties(int number)
4678{
4679  if (number<=0) {
4680    numberPenalties_=0;
4681  } else {
4682    numberPenalties_=number;
4683  }
4684}
4685void 
4686CbcModel::setPenaltyScaleFactor(double value)
4687{
4688  if (value<=0) {
4689    penaltyScaleFactor_=3.0;
4690  } else {
4691    penaltyScaleFactor_=value;
4692  }
4693}
4694void 
4695CbcModel::setHowOftenGlobalScan(int number)
4696{
4697  if (number<-1)
4698    howOftenGlobalScan_=0;
4699   else
4700    howOftenGlobalScan_=number;
4701}
4702
4703// Add one generator
4704void 
4705CbcModel::addCutGenerator(CglCutGenerator * generator,
4706                          int howOften, const char * name,
4707                          bool normal, bool atSolution,
4708                          bool whenInfeasible,int howOftenInSub,
4709                          int whatDepth, int whatDepthInSub)
4710{
4711  CbcCutGenerator ** temp = generator_;
4712  generator_ = new CbcCutGenerator * [numberCutGenerators_+1];
4713  memcpy(generator_,temp,numberCutGenerators_*sizeof(CbcCutGenerator *));
4714  delete[] temp ;
4715  generator_[numberCutGenerators_]= 
4716    new CbcCutGenerator(this,generator, howOften, name,
4717                        normal,atSolution,whenInfeasible,howOftenInSub,
4718                        whatDepth, whatDepthInSub);
4719  // and before any cahnges
4720  temp = virginGenerator_;
4721  virginGenerator_ = new CbcCutGenerator * [numberCutGenerators_+1];
4722  memcpy(virginGenerator_,temp,numberCutGenerators_*sizeof(CbcCutGenerator *));
4723  delete[] temp ;
4724  virginGenerator_[numberCutGenerators_++]= 
4725    new CbcCutGenerator(this,generator, howOften, name,
4726                        normal,atSolution,whenInfeasible,howOftenInSub,
4727                        whatDepth, whatDepthInSub);
4728                                                         
4729}
4730// Add one heuristic
4731void 
4732CbcModel::addHeuristic(CbcHeuristic * generator, const char *name)
4733{
4734  CbcHeuristic ** temp = heuristic_;
4735  heuristic_ = new CbcHeuristic * [numberHeuristics_+1];
4736  memcpy(heuristic_,temp,numberHeuristics_*sizeof(CbcHeuristic *));
4737  delete [] temp;
4738  heuristic_[numberHeuristics_]=generator->clone();
4739  if (name)
4740  { heuristic_[numberHeuristics_]->setHeuristicName(name) ; }
4741  heuristic_[numberHeuristics_]->setSeed(987654321+numberHeuristics_);
4742  numberHeuristics_++ ;
4743}
4744
4745/*
4746  The last subproblem handled by the solver is not necessarily related to the
4747  one being recreated, so the first action is to remove all cuts from the
4748  constraint system.  Next, traverse the tree from node to the root to
4749  determine the basis size required for this subproblem and create an empty
4750  basis with the right capacity.  Finally, traverse the tree from root to
4751  node, adjusting bounds in the constraint system, adjusting the basis, and
4752  collecting the cuts that must be added to the constraint system.
4753  applyToModel does the heavy lifting.
4754
4755  addCuts1 is used in contexts where all that's desired is the list of cuts:
4756  the node is already fathomed, and we're collecting cuts so that we can
4757  adjust reference counts as we prune nodes. Arguably the two functions
4758  should be separated. The culprit is applyToModel, which performs cut
4759  collection and model adjustment.
4760
4761  Certainly in the contexts where all we need is a list of cuts, there's no
4762  point in passing in a valid basis --- an empty basis will do just fine.
4763*/
4764void CbcModel::addCuts1 (CbcNode * node, CoinWarmStartBasis *&lastws)
4765{ int i;
4766  int nNode=0;
4767  int numberColumns = getNumCols();
4768  CbcNodeInfo * nodeInfo = node->nodeInfo();
4769
4770/*
4771  Remove all cuts from the constraint system.
4772  (original comment includes ``see note below for later efficiency'', but
4773  the reference isn't clear to me).
4774*/
4775  solver_->restoreBaseModel(numberRowsAtContinuous_);
4776#if 0
4777  int currentNumberCuts = solver_->getNumRows()-numberRowsAtContinuous_;
4778  int *which = new int[currentNumberCuts];
4779  for (i = 0 ; i < currentNumberCuts ; i++)
4780    which[i] = i+numberRowsAtContinuous_;
4781  solver_->deleteRows(currentNumberCuts,which);
4782  delete [] which;
4783#endif
4784/*
4785  Accumulate the path from node to the root in walkback_, and accumulate a
4786  cut count in currentNumberCuts.
4787
4788  original comment: when working then just unwind until where new node joins
4789  old node (for cuts?)
4790*/
4791  int currentNumberCuts = 0;
4792  while (nodeInfo) {
4793    //printf("nNode = %d, nodeInfo = %x\n",nNode,nodeInfo);
4794    walkback_[nNode++]=nodeInfo;
4795    currentNumberCuts += nodeInfo->numberCuts() ;
4796    nodeInfo = nodeInfo->parent() ;
4797    if (nNode==maximumDepth_) {
4798      maximumDepth_ *= 2;
4799      CbcNodeInfo ** temp = new CbcNodeInfo * [maximumDepth_];
4800      for (i=0;i<nNode;i++) 
4801        temp[i] = walkback_[i];
4802      delete [] walkback_;
4803      walkback_ = temp;
4804    }
4805  }
4806/*
4807  Create an empty basis with sufficient capacity for the constraint system
4808  we'll construct: original system plus cuts. Make sure we have capacity to
4809  record those cuts in addedCuts_.
4810
4811  The method of adjusting the basis at a FullNodeInfo object (the root, for
4812  example) is to use a copy constructor to duplicate the basis held in the
4813  nodeInfo, then resize it and return the new basis object. Guaranteed,
4814  lastws will point to a different basis when it returns. We pass in a basis
4815  because we need the parameter to return the allocated basis, and it's an
4816  easy way to pass in the size. But we take a hit for memory allocation.
4817*/
4818  currentNumberCuts_=currentNumberCuts;
4819  if (currentNumberCuts > maximumNumberCuts_) {
4820    maximumNumberCuts_ = currentNumberCuts;
4821    delete [] addedCuts_;
4822    addedCuts_ = new CbcCountRowCut * [maximumNumberCuts_];
4823  }
4824  lastws->setSize(numberColumns,numberRowsAtContinuous_+currentNumberCuts);
4825/*
4826  This last bit of code traverses the path collected in walkback_ from the
4827  root back to node. At the end of the loop,
4828   * lastws will be an appropriate basis for node;
4829   * variable bounds in the constraint system will be set to be correct for
4830     node; and
4831   * addedCuts_ will be set to a list of cuts that need to be added to the
4832     constraint system at node.
4833  applyToModel does all the heavy lifting.
4834*/
4835  currentNumberCuts=0;
4836  //#define CBC_PRINT2
4837#ifdef CBC_PRINT2
4838  printf("Starting bounds at node %d\n",numberNodes_);
4839#endif
4840  while (nNode) {
4841    --nNode;
4842    walkback_[nNode]->applyToModel(this,lastws,addedCuts_,currentNumberCuts);
4843  }
4844  if (0) {
4845    int numberDebugValues=18;
4846    double * debugValues = new double[numberDebugValues];
4847    CoinZeroN(debugValues,numberDebugValues);
4848    debugValues[1]=6.0;
4849    debugValues[3]=60.0;
4850    debugValues[4]=6.0;
4851    debugValues[6]=60.0;
4852    debugValues[7]=16.0;
4853    debugValues[9]=70.0;
4854    debugValues[10]=7.0;
4855    debugValues[12]=70.0;
4856    debugValues[13]=12.0;
4857    debugValues[15]=75.0;
4858    int nBad=0;
4859    for (int j=0;j<numberColumns;j++) {
4860      if (integerInfo_[j]) {
4861        if(solver_->getColLower()[j]>debugValues[j]||
4862           solver_->getColUpper()[j]<debugValues[j]) {
4863          printf("** (%g) ** ",debugValues[j]);
4864          nBad++;
4865        }
4866        printf("%d bounds %g %g\n",j,solver_->getColLower()[j],solver_->getColUpper()[j]);
4867      }
4868    }
4869    if (nBad)
4870      printf("%d BAD\n",nBad);
4871    else
4872      printf("OKAY\n");
4873    delete [] debugValues;
4874  }
4875}
4876
4877/*
4878  adjustCuts might be a better name: If the node is feasible, we sift through
4879  the cuts collected by addCuts1, add the ones that are tight and omit the
4880  ones that are loose. If the node is infeasible, we just adjust the
4881  reference counts to reflect that we're about to prune this node and its
4882  descendants.
4883*/
4884int CbcModel::addCuts (CbcNode *node, CoinWarmStartBasis *&lastws,bool canFix)
4885{
4886/*
4887  addCuts1 performs step 1 of restoring the subproblem at this node; see the
4888  comments there.
4889*/
4890  addCuts1(node,lastws);
4891  int i;
4892  int numberColumns = getNumCols();
4893  if (solver_->getNumRows()>maximumRows_) {
4894    maximumRows_ = solver_->getNumRows();
4895    workingBasis_.resize(maximumRows_,numberColumns);
4896  }
4897  CbcNodeInfo * nodeInfo = node->nodeInfo();
4898  double cutoff = getCutoff() ;
4899  int currentNumberCuts=currentNumberCuts_;
4900  if (canFix) {
4901    bool feasible=true;
4902    const double *lower = solver_->getColLower() ;
4903    const double *upper = solver_->getColUpper() ;
4904    double * newLower = analyzeResults_;
4905    double * objLower = newLower+numberIntegers_;
4906    double * newUpper = objLower+numberIntegers_;
4907    double * objUpper = newUpper+numberIntegers_;
4908    int n=0;
4909    for (i=0;i<numberIntegers_;i++) {
4910      int iColumn = integerVariable_[i];
4911      bool changed=false;
4912      double lo = 0.0;
4913      double up = 0.0;
4914      if (objLower[i]>cutoff) {
4915        lo = lower[iColumn];
4916        up = upper[iColumn];
4917        if (lo<newLower[i]) {
4918          lo = newLower[i];
4919          solver_->setColLower(iColumn,lo);
4920          changed=true;
4921          n++;
4922        }
4923        if (objUpper[i]>cutoff) {
4924          if (up>newUpper[i]) {
4925            up = newUpper[i];
4926            solver_->setColUpper(iColumn,up);
4927            changed=true;
4928            n++;
4929          }
4930        }
4931      } else if (objUpper[i]>cutoff) {
4932        lo = lower[iColumn];
4933        up = upper[iColumn];
4934        if (up>newUpper[i]) {
4935          up = newUpper[i];
4936          solver_->setColUpper(iColumn,up);
4937          changed=true;
4938          n++;
4939        }
4940      }
4941      if (changed&&lo>up) {
4942        feasible=false;
4943        break;
4944      }
4945    }
4946    if (!feasible) {
4947      printf("analysis says node infeas\n");
4948      cutoff=-COIN_DBL_MAX;
4949    }
4950  }
4951/*
4952  If the node can't be fathomed by bound, reinstall tight cuts in the
4953  constraint system. Even if there are no cuts, we'll want to set the
4954  reconstructed basis in the solver.
4955*/
4956  if (node->objectiveValue() < cutoff||numberThreads_)
4957  { 
4958#   ifdef CBC_CHECK_BASIS
4959    printf("addCuts: expanded basis; rows %d+%d\n",
4960           numberRowsAtContinuous_,currentNumberCuts);
4961    lastws->print();
4962#   endif
4963/*
4964  Adjust the basis and constraint system so that we retain only active cuts.
4965  There are three steps:
4966    1) Scan the basis. Sort the cuts into effective cuts to be kept and
4967       loose cuts to be dropped.
4968    2) Drop the loose cuts and resize the basis to fit.
4969    3) Install the tight cuts in the constraint system (applyRowCuts) and
4970       and install the basis (setWarmStart).
4971  Use of compressRows conveys we're compressing the basis and not just
4972  tweaking the artificialStatus_ array.
4973*/
4974    if (currentNumberCuts > 0) {
4975      int numberToAdd = 0;
4976      const OsiRowCut **addCuts;
4977      int numberToDrop = 0 ;
4978      int *cutsToDrop ;
4979      addCuts = new const OsiRowCut* [currentNumberCuts];
4980      cutsToDrop = new int[currentNumberCuts] ;
4981      assert (currentNumberCuts+numberRowsAtContinuous_<=lastws->getNumArtificial());
4982      for (i=0;i<currentNumberCuts;i++) {
4983        CoinWarmStartBasis::Status status = 
4984          lastws->getArtifStatus(i+numberRowsAtContinuous_);
4985        if (addedCuts_[i] &&
4986            (status != CoinWarmStartBasis::basic ||
4987             addedCuts_[i]->effectiveness()==COIN_DBL_MAX)) {
4988#         ifdef CHECK_CUT_COUNTS
4989          printf("Using cut %d %x as row %d\n",i,addedCuts_[i],
4990                 numberRowsAtContinuous_+numberToAdd);
4991#         endif
4992          addCuts[numberToAdd++] = addedCuts_[i];
4993        } else {
4994#         ifdef CHECK_CUT_COUNTS
4995          printf("Dropping cut %d %x\n",i,addedCuts_[i]);
4996#         endif
4997          addedCuts_[i]=NULL;
4998          cutsToDrop[numberToDrop++] = numberRowsAtContinuous_+i ;
4999        }
5000      }
5001      int numberRowsNow=numberRowsAtContinuous_+numberToAdd;
5002      lastws->compressRows(numberToDrop,cutsToDrop) ;
5003      lastws->resize(numberRowsNow,numberColumns);
5004      solver_->applyRowCuts(numberToAdd,addCuts);
5005#     ifdef CBC_CHECK_BASIS
5006      printf("addCuts: stripped basis; rows %d + %d\n",
5007             numberRowsAtContinuous_,numberToAdd);
5008      lastws->print();
5009#     endif
5010      //for (i=0;i<numberToAdd;i++)
5011      //delete addCuts[i];
5012      delete [] addCuts;
5013      delete [] cutsToDrop ;
5014    }
5015/*
5016  Set the basis in the solver.
5017*/
5018    solver_->setWarmStart(lastws);
5019#if 0
5020    if ((numberNodes_%printFrequency_)==0) {
5021      printf("Objective %g, depth %d, unsatisfied %d\n",
5022             node->objectiveValue(),
5023             node->depth(),node->numberUnsatisfied());
5024    }
5025#endif
5026/*
5027  Clean up and we're out of here.
5028*/
5029    numberNodes_++;
5030    return 0;
5031  } 
5032/*
5033  This node has been fathomed by bound as we try to revive it out of the live
5034  set. Adjust the cut reference counts to reflect that we no longer need to
5035  explore the remaining branch arms, hence they will no longer reference any
5036  cuts. Cuts whose reference count falls to zero are deleted. 
5037*/
5038  else
5039  { int i;
5040    if (currentNumberCuts) {
5041#ifndef CBC_DETERMINISTIC_THREAD
5042      lockThread();
5043#endif
5044      int numberLeft = nodeInfo->numberBranchesLeft();
5045      for (i = 0 ; i < currentNumberCuts ; i++)
5046        { if (addedCuts_[i])
5047          { if (!addedCuts_[i]->decrement(numberLeft))
5048            { delete addedCuts_[i];
5049            addedCuts_[i] = NULL; } } }
5050#ifndef CBC_DETERMINISTIC_THREAD
5051      unlockThread();
5052#endif
5053    }
5054    return 1 ; }
5055}
5056
5057
5058/*
5059  Perform reduced cost fixing on integer variables.
5060
5061  The variables in question are already nonbasic at bound. We're just nailing
5062  down the current situation.
5063*/
5064
5065int CbcModel::reducedCostFix ()
5066
5067{
5068  if(!solverCharacteristics_->reducedCostsAccurate())
5069    return 0; //NLP
5070  double cutoff = getCutoff() ;
5071  double direction = solver_->getObjSense() ;
5072  double gap = cutoff - solver_->getObjValue()*direction ;
5073  double tolerance;
5074  solver_->getDblParam(OsiDualTolerance,tolerance) ;
5075  if (gap<=0.0)
5076    return 0;
5077  gap += 100.0*tolerance;
5078  double integerTolerance = getDblParam(CbcIntegerTolerance) ;
5079
5080  const double *lower = solver_->getColLower() ;
5081  const double *upper = solver_->getColUpper() ;
5082  const double *solution = solver_->getColSolution() ;
5083  const double *reducedCost = solver_->getReducedCost() ;
5084
5085  int numberFixed = 0 ;
5086
5087# ifdef COIN_HAS_CLP
5088  OsiClpSolverInterface * clpSolver
5089    = dynamic_cast<OsiClpSolverInterface *> (solver_);
5090  ClpSimplex * clpSimplex=NULL;
5091  if (clpSolver) 
5092    clpSimplex = clpSolver->getModelPtr();
5093# endif
5094  for (int i = 0 ; i < numberIntegers_ ; i++)
5095  { int iColumn = integerVariable_[i] ;
5096    double djValue = direction*reducedCost[iColumn] ;
5097    if (upper[iColumn]-lower[iColumn] > integerTolerance)
5098    { if (solution[iColumn] < lower[iColumn]+integerTolerance && djValue > gap)
5099      { solver_->setColUpper(iColumn,lower[iColumn]) ;
5100#ifdef COIN_HAS_CLP
5101      // may just have been fixed before
5102      if (clpSimplex)
5103        assert(clpSimplex->getColumnStatus(iColumn)==ClpSimplex::atLowerBound||
5104               clpSimplex->getColumnStatus(iColumn)==ClpSimplex::isFixed);
5105#endif
5106      numberFixed++ ; }
5107      else
5108      if (solution[iColumn] > upper[iColumn]-integerTolerance && -djValue > gap)
5109      { solver_->setColLower(iColumn,upper[iColumn]) ;
5110#ifdef COIN_HAS_CLP
5111      // may just have been fixed before
5112      if (clpSimplex)
5113        assert(clpSimplex->getColumnStatus(iColumn)==ClpSimplex::atUpperBound||
5114               clpSimplex->getColumnStatus(iColumn)==ClpSimplex::isFixed);
5115#endif
5116      numberFixed++ ; } } }
5117  numberDJFixed_ += numberFixed;
5118  return numberFixed; }
5119
5120// Collect coding to replace whichGenerator
5121void
5122CbcModel::resizeWhichGenerator(int numberNow, int numberAfter)
5123{
5124  if (numberAfter > maximumWhich_) {
5125    maximumWhich_ = CoinMax(maximumWhich_*2+100,numberAfter) ;
5126    int * temp = new int[2*maximumWhich_] ;
5127    memcpy(temp,whichGenerator_,numberNow*sizeof(int)) ;
5128    delete [] whichGenerator_ ;
5129    whichGenerator_ = temp ;
5130    memset(whichGenerator_+numberNow,0,(maximumWhich_-numberNow)*sizeof(int));
5131  }
5132}
5133
5134/** Solve the model using cuts
5135
5136  This version takes off redundant cuts from node.
5137  Returns true if feasible.
5138
5139  \todo
5140  Why do I need to resolve the problem? What has been done between the last
5141  relaxation and calling solveWithCuts?
5142
5143  If numberTries == 0 then user did not want any cuts.
5144*/
5145
5146bool 
5147CbcModel::solveWithCuts (OsiCuts &cuts, int numberTries, CbcNode *node)
5148/*
5149  Parameters:
5150    numberTries: (i) the maximum number of iterations for this round of cut
5151                     generation; if negative then we don't mind if drop is tiny.
5152   
5153    cuts:       (o) all cuts generated in this round of cut generation
5154
5155    node: (i)     So we can update dynamic pseudo costs
5156*/
5157                       
5158
5159{
5160# ifdef COIN_HAS_CLP
5161  OsiClpSolverInterface * clpSolver
5162    = dynamic_cast<OsiClpSolverInterface *> (solver_);
5163  int saveClpOptions=0;
5164  if (clpSolver) 
5165    saveClpOptions = clpSolver->specialOptions();
5166# endif
5167  //solver_->writeMps("saved");
5168#ifdef CBC_THREAD
5169  CbcModel ** threadModel = NULL;
5170  pthread_t * threadId = NULL;
5171  pthread_cond_t condition_main;
5172  pthread_mutex_t condition_mutex;
5173  pthread_mutex_t * mutex2 = NULL;
5174  pthread_cond_t * condition2 = NULL;
5175  threadStruct * threadInfo = NULL;
5176  void * saveMutex = NULL;
5177  if (numberThreads_&&(threadMode_&2)!=0&&!numberNodes_) {
5178    threadId = new pthread_t [numberThreads_];
5179    pthread_cond_init(&condition_main,NULL);
5180    pthread_mutex_init(&condition_mutex,NULL);
5181    threadModel = new CbcModel * [numberThreads_];
5182    threadInfo = new threadStruct [numberThreads_+1];
5183    mutex2 = new pthread_mutex_t [numberThreads_];
5184    condition2 = new pthread_cond_t [numberThreads_];
5185    saveMutex = mutex_;
5186    for (int i=0;i<numberThreads_;i++) {
5187      pthread_mutex_init(mutex2+i,NULL);
5188      pthread_cond_init(condition2+i,NULL);
5189      threadId[i]=0;
5190      threadModel[i]=new CbcModel;
5191      threadModel[i]->generator_ = new CbcCutGenerator * [1];
5192      delete threadModel[i]->solver_;
5193      threadModel[i]->solver_=NULL;
5194      threadModel[i]->numberThreads_=numberThreads_;
5195      mutex_ = (void *) (threadInfo+i);
5196      threadInfo[i].thisModel=(CbcModel *) threadModel[i];
5197      threadInfo[i].baseModel=this;
5198      threadInfo[i].threadIdOfBase=pthread_self();
5199      threadInfo[i].mutex2=mutex2+i;
5200      threadInfo[i].condition2=condition2+i;
5201      threadInfo[i].returnCode=-1;
5202      pthread_create(threadId+i,NULL,doCutsThread,threadInfo+i);
5203    }
5204    // Do a partial one for base model
5205    threadInfo[numberThreads_].baseModel=this;
5206    mutex_ = (void *) (threadInfo+numberThreads_);
5207    threadInfo[numberThreads_].condition2=&condition_main;
5208    threadInfo[numberThreads_].mutex2=&condition_mutex;
5209  }
5210#endif
5211  bool feasible = true ;
5212  int lastNumberCuts = 0 ;
5213  double lastObjective = -1.0e100 ;
5214  int violated = 0 ;
5215  int numberRowsAtStart = solver_->getNumRows() ;
5216  //printf("solver had %d rows\n",numberRowsAtStart);
5217  int numberColumns = solver_->getNumCols() ;
5218  CoinBigIndex numberElementsAtStart = solver_->getNumElements();
5219
5220  numberOldActiveCuts_ = numberRowsAtStart-numberRowsAtContinuous_ ;
5221  numberNewCuts_ = 0 ;
5222
5223  bool onOptimalPath = false ;
5224  const OsiRowCutDebugger *debugger = NULL;
5225  if ((specialOptions_&1)!=0) {
5226    /*
5227      See OsiRowCutDebugger for details. In a nutshell, make sure that current
5228      variable values do not conflict with a known optimal solution. (Obviously
5229      this can be fooled when there are multiple solutions.)
5230    */
5231    debugger = solver_->getRowCutDebugger() ;
5232    if (debugger) 
5233      onOptimalPath = (debugger->onOptimalPath(*solver_)) ;
5234  }
5235  OsiCuts slackCuts;
5236/*
5237  Resolve the problem. If we've lost feasibility, might as well bail out right
5238  after the debug stuff. The resolve will also refresh cached copies of the
5239  solver solution (cbcColLower_, ...) held by CbcModel.
5240*/
5241  double objectiveValue = solver_->getObjValue()*solver_->getObjSense();
5242  if (node)
5243    objectiveValue= node->objectiveValue();
5244  int returnCode = resolve(node ? node->nodeInfo() : NULL,1);
5245#ifdef COIN_DEVELOP
5246  //if (!solver_->getIterationCount()&&solver_->isProvenOptimal())
5247  //printf("zero iterations on first solve of branch\n");
5248#endif
5249  if (node&&node->nodeInfo()&&!node->nodeInfo()->numberBranchesLeft())
5250    node->nodeInfo()->allBranchesGone(); // can clean up
5251  feasible = returnCode  != 0 ;
5252  if (returnCode<0)
5253    numberTries=0;
5254  if (problemFeasibility_->feasible(this,0)<0) {
5255    feasible=false; // pretend infeasible
5256  }
5257 
5258#if NEW_UPDATE_OBJECT==0
5259  // Update branching information if wanted
5260  if(node &&branchingMethod_)
5261    branchingMethod_->updateInformation(solver_,node);
5262#elif NEW_UPDATE_OBJECT<2
5263  // Update branching information if wanted
5264  if(node &&branchingMethod_) {
5265    OsiBranchingObject * bobj = node->modifiableBranchingObject();
5266    CbcBranchingObject * cbcobj = dynamic_cast<CbcBranchingObject *> (bobj);
5267    if (cbcobj) {
5268      CbcObject * object = cbcobj->object();
5269      CbcObjectUpdateData update = object->createUpdateInformation(solver_,node,cbcobj);
5270      object->updateInformation(update);
5271    } else {
5272      branchingMethod_->updateInformation(solver_,node);
5273    }
5274  }
5275#else
5276  // Update branching information if wanted
5277  if(node &&branchingMethod_) {
5278    OsiBranchingObject * bobj = node->modifiableBranchingObject();
5279    CbcBranchingObject * cbcobj = dynamic_cast<CbcBranchingObject *> (bobj);
5280    if (cbcobj&&cbcobj->object()) {
5281      CbcObject * object = cbcobj->object();
5282      CbcObjectUpdateData update = object->createUpdateInformation(solver_,node,cbcobj);
5283      // have to compute object number as not saved
5284      CbcSimpleInteger * simpleObject =
5285          dynamic_cast <CbcSimpleInteger *>(object) ;
5286      int iObject;
5287      int iColumn = simpleObject->columnNumber();
5288      for (iObject = 0 ; iObject < numberObjects_ ; iObject++) {
5289        simpleObject =
5290          dynamic_cast <CbcSimpleInteger *>(object_[iObject]) ;
5291        if (simpleObject->columnNumber()==iColumn)
5292          break;
5293      }
5294      assert (iObject<numberObjects_);
5295      update.objectNumber_ = iObject;
5296      addUpdateInformation(update);
5297    } else {
5298      OsiIntegerBranchingObject * obj = dynamic_cast<OsiIntegerBranchingObject *> (bobj);
5299      if (obj) {
5300        const OsiObject * object = obj->originalObject();
5301        // have to compute object number as not saved
5302        int iObject;
5303        int iColumn = object->columnNumber();
5304        for (iObject = 0 ; iObject < numberObjects_ ; iObject++) {
5305          if (object_[iObject]->columnNumber()==iColumn)
5306            break;
5307        }
5308        assert (iObject<numberObjects_);
5309        int branch = obj->firstBranch();
5310        if (obj->branchIndex()==2)
5311          branch = 1-branch;
5312        assert (branch==0||branch==1);
5313        double originalValue=node->objectiveValue();
5314        double objectiveValue = solver_->getObjValue()*solver_->getObjSense();
5315        double changeInObjective = CoinMax(0.0,objectiveValue-originalValue);
5316        int iStatus = (feasible) ? 0 : 0;
5317        double value = obj->value();
5318        double movement;
5319        if (branch)
5320          movement = ceil(value)-value;
5321        else
5322          movement = value -floor(value);
5323#if 0
5324        // OUT as much too complicated - we are not at a natural hotstart place
5325        OsiBranchingInformation usefulInfo=usefulInformation();
5326        // hotInfo is meant for BEFORE a branch so we need to fool
5327        // was much simpler with alternate method
5328        double save[3];
5329        save[0]=usefulInfo.lower_[iColumn];
5330        save[1]=usefulInfo.solution_[iColumn];
5331        save[2]=usefulInfo.upper_[iColumn];
5332        usefulInfo.lower_[iColumn]=floor(value);
5333        usefulInfo.solution_[iColumn]=value;
5334        usefulInfo.upper_[iColumn]=ceil(value);
5335        OsiHotInfo hotInfo(solver_,&usefulInfo,&object,0);
5336        usefulInfo.lower_[iColumn]=save[0];
5337        usefulInfo.solution_[iColumn]=save[1];
5338        usefulInfo.upper_[iColumn]=save[2];
5339        if (branch) {
5340          hotInfo.setUpStatus(iStatus);
5341          hotInfo.setUpChange(changeInObjective);
5342          //object->setUpEstimate(movement);
5343        } else {
5344          hotInfo.setDownStatus(iStatus);
5345          hotInfo.setDownChange(changeInObjective);
5346          //object->setDownEstimate(movement);
5347        }
5348        branchingMethod_->chooseMethod()->updateInformation(&usefulInfo,branch,&hotInfo);
5349#else
5350        branchingMethod_->chooseMethod()->updateInformation(iObject,branch,changeInObjective,
5351                                                            movement,iStatus);
5352#endif
5353      }
5354    }
5355  }
5356#endif
5357
5358#ifdef CBC_DEBUG
5359  if (feasible)
5360  { printf("Obj value %g (%s) %d rows\n",solver_->getObjValue(),
5361           (solver_->isProvenOptimal())?"proven":"unproven",
5362           solver_->getNumRows()) ; }
5363 
5364  else
5365  { printf("Infeasible %d rows\n",solver_->getNumRows()) ; }
5366#endif
5367  if ((specialOptions_&1)!=0) {
5368/*
5369  If the RowCutDebugger said we were compatible with the optimal solution,
5370  and now we're suddenly infeasible, we might be confused. Then again, we
5371  may have fathomed by bound, heading for a rediscovery of an optimal solution.
5372*/
5373    if (onOptimalPath && !solver_->isDualObjectiveLimitReached()) {
5374      if (!feasible) {
5375        solver_->writeMps("infeas");
5376        CoinWarmStartBasis *slack =
5377          dynamic_cast<CoinWarmStartBasis *>(solver_->getEmptyWarmStart()) ;
5378        solver_->setWarmStart(slack);
5379        delete slack ;
5380        solver_->setHintParam(OsiDoReducePrint,false,OsiHintDo,0) ;
5381        solver_->initialSolve();
5382      }
5383      assert(feasible) ;
5384    }
5385  }
5386
5387  if (!feasible) {
5388    numberInfeasibleNodes_++;
5389# ifdef COIN_HAS_CLP
5390    if (clpSolver) 
5391    clpSolver->setSpecialOptions(saveClpOptions);
5392# endif
5393    return (false) ;
5394  }
5395  sumChangeObjective1_ += solver_->getObjValue()*solver_->getObjSense()
5396    - objectiveValue ;
5397  if ( getCurrentSeconds() > dblParam_[CbcMaximumSeconds] )
5398    numberTries=0; // exit
5399  //if ((numberNodes_%100)==0)
5400  //printf("XXa sum obj changed by %g\n",sumChangeObjective1_);
5401  objectiveValue = solver_->getObjValue()*solver_->getObjSense();
5402  // Return at once if numberTries zero
5403  if (!numberTries) {
5404    cuts=OsiCuts();
5405    numberNewCuts_=0;
5406# ifdef COIN_HAS_CLP
5407    if (clpSolver) 
5408    clpSolver->setSpecialOptions(saveClpOptions);
5409# endif
5410    return true;
5411  }
5412/*
5413  Do reduced cost fixing.
5414*/
5415  reducedCostFix() ;
5416/*
5417  Set up for at most numberTries rounds of cut generation. If numberTries is
5418  negative, we'll ignore the minimumDrop_ cutoff and keep generating cuts for
5419  the specified number of rounds.
5420*/
5421  double minimumDrop = minimumDrop_ ;
5422  if (numberTries<0)
5423  { numberTries = -numberTries ;
5424    minimumDrop = -1.0 ; }
5425/*
5426  Is it time to scan the cuts in order to remove redundant cuts? If so, set
5427  up to do it.
5428*/
5429# define SCANCUTS 100 
5430  int *countColumnCuts = NULL ;
5431  // Always accumulate row cut counts
5432  int * countRowCuts =new int[numberCutGenerators_+numberHeuristics_] ;
5433  memset(countRowCuts,0,
5434         (numberCutGenerators_+numberHeuristics_)*sizeof(int)) ;
5435  bool fullScan = false ;
5436  if ((numberNodes_%SCANCUTS) == 0)
5437  { fullScan = true ;
5438    countColumnCuts = new int[numberCutGenerators_+numberHeuristics_] ;
5439    memset(countColumnCuts,0,
5440           (numberCutGenerators_+numberHeuristics_)*sizeof(int)) ; }
5441
5442  double direction = solver_->getObjSense() ;
5443  double startObjective = solver_->getObjValue()*direction ;
5444
5445  currentPassNumber_ = 0 ;
5446  double primalTolerance = 1.0e-7 ;
5447  // We may need to keep going on
5448  bool keepGoing=false;
5449/*
5450  Begin cut generation loop. Cuts generated during each iteration are
5451  collected in theseCuts. The loop can be divided into four phases:
5452   1) Prep: Fix variables using reduced cost. In the first iteration only,
5453      consider scanning globalCuts_ and activating any applicable cuts.
5454   2) Cut Generation: Call each generator and heuristic registered in the
5455      generator_ and heuristic_ arrays. Newly generated global cuts are
5456      copied to globalCuts_ at this time.
5457   3) Cut Installation and Reoptimisation: Install column and row cuts in
5458      the solver. Copy row cuts to cuts (parameter). Reoptimise.
5459   4) Cut Purging: takeOffCuts() removes inactive cuts from the solver, and
5460      does the necessary bookkeeping in the model.
5461*/
5462  do
5463  { currentPassNumber_++ ;
5464    numberTries-- ;
5465    if (numberTries<0&&keepGoing) {
5466      // switch off all normal ones
5467      for (int i = 0;i<numberCutGenerators_;i++) {
5468        if (!generator_[i]->mustCallAgain())
5469          generator_[i]->setSwitchedOff(true);
5470      }
5471    }
5472    keepGoing=false;
5473    OsiCuts theseCuts ;
5474/*
5475  Scan previously generated global column and row cuts to see if any are
5476  useful.
5477*/
5478    int numberViolated=0;
5479    if (currentPassNumber_ == 1 && howOftenGlobalScan_ > 0 &&
5480        (numberNodes_%howOftenGlobalScan_) == 0)
5481    { int numberCuts = globalCuts_.sizeColCuts() ;
5482      int i;
5483      // possibly extend whichGenerator
5484      resizeWhichGenerator(numberViolated, numberViolated+numberCuts);
5485      for ( i = 0 ; i < numberCuts ; i++)
5486      { OsiColCut *thisCut = globalCuts_.colCutPtr(i) ;
5487        if (thisCut->violated(cbcColSolution_)>primalTolerance) {
5488          printf("Global cut added - violation %g\n",
5489                 thisCut->violated(cbcColSolution_)) ;
5490          whichGenerator_[numberViolated++]=-1;
5491#ifndef GLOBAL_CUTS_JUST_POINTERS
5492          theseCuts.insert(*thisCut) ;
5493#else
5494          theseCuts.insert(thisCut) ;
5495#endif
5496        }
5497      }
5498      numberCuts = globalCuts_.sizeRowCuts() ;
5499      // possibly extend whichGenerator
5500      resizeWhichGenerator(numberViolated, numberViolated+numberCuts);
5501      for ( i = 0;i<numberCuts;i++) {
5502        OsiRowCut * thisCut = globalCuts_.rowCutPtr(i) ;
5503        if (thisCut->violated(cbcColSolution_)>primalTolerance) {
5504          //printf("Global cut added - violation %g\n",
5505          // thisCut->violated(cbcColSolution_)) ;
5506          whichGenerator_[numberViolated++]=-1;
5507#ifndef GLOBAL_CUTS_JUST_POINTERS
5508          theseCuts.insert(*thisCut) ;
5509#else
5510          theseCuts.insert(thisCut) ;
5511#endif
5512        }
5513      }
5514      numberGlobalViolations_+=numberViolated;
5515    }
5516/*
5517  Generate new cuts (global and/or local) and/or apply heuristics.  If
5518  CglProbing is used, then it should be first as it can fix continuous
5519  variables.
5520
5521  At present, CglProbing is the only case where generateCuts will return
5522  true. generateCuts actually modifies variable bounds in the solver when
5523  CglProbing indicates that it can fix a variable. Reoptimisation is required
5524  to take full advantage.
5525
5526  The need to resolve here should only happen after a heuristic solution.
5527  (Note default OSI implementation of optimalBasisIsAvailable always returns
5528  false.)
5529*/
5530    if (solverCharacteristics_->warmStart()&&
5531        !solver_->optimalBasisIsAvailable()) {
5532      //printf("XXXXYY no opt basis\n");
5533      resolve(node ? node->nodeInfo() : NULL,3);
5534    }
5535    if (nextRowCut_) {
5536      // branch was a cut - add it
5537      theseCuts.insert(*nextRowCut_);
5538      if (handler_->logLevel()>1)
5539        nextRowCut_->print();
5540      const OsiRowCut * cut=nextRowCut_;
5541      double lb = cut->lb();
5542      double ub = cut->ub();
5543      int n=cut->row().getNumElements();
5544      const int * column = cut->row().getIndices();
5545      const double * element = cut->row().getElements();
5546      double sum=0.0;
5547      for (int i=0;i<n;i++) {
5548        int iColumn = column[i];
5549        double value = element[i];
5550        //if (cbcColSolution_[iColumn]>1.0e-7)
5551        //printf("value of %d is %g\n",iColumn,cbcColSolution_[iColumn]);
5552        sum += value * cbcColSolution_[iColumn];
5553      }
5554      delete nextRowCut_;
5555      nextRowCut_=NULL;
5556      if (handler_->logLevel()>1)
5557        printf("applying branch cut, sum is %g, bounds %g %g\n",sum,lb,ub);
5558      // possibly extend whichGenerator
5559      resizeWhichGenerator(numberViolated, numberViolated+1);
5560      // set whichgenerator (also serves as marker to say don't delete0
5561      whichGenerator_[numberViolated++]=-2;
5562    }
5563
5564    // reset probing info
5565    //if (probingInfo_)
5566    //probingInfo_->initializeFixing();
5567    int i;
5568    if ((threadMode_&2)==0||numberNodes_) {
5569      for (i = 0;i<numberCutGenerators_;i++) {
5570        int numberRowCutsBefore = theseCuts.sizeRowCuts() ;
5571        int numberColumnCutsBefore = theseCuts.sizeColCuts() ;
5572        int numberRowCutsAfter = numberRowCutsBefore;
5573        int numberColumnCutsAfter = numberColumnCutsBefore;
5574        bool generate = generator_[i]->normal();
5575        // skip if not optimal and should be (maybe a cut generator has fixed variables)
5576        if (generator_[i]->needsOptimalBasis()&&!solver_->basisIsAvailable())
5577          generate=false;
5578        if (generator_[i]->switchedOff())
5579          generate=false;;
5580        if (generate) {
5581          bool mustResolve = 
5582            generator_[i]->generateCuts(theseCuts,fullScan,solver_,node) ;
5583          numberRowCutsAfter = theseCuts.sizeRowCuts() ;
5584          if(numberRowCutsBefore < numberRowCutsAfter &&
5585             generator_[i]->mustCallAgain())
5586            keepGoing=true; // say must go round
5587          // Check last cut to see if infeasible
5588          if(numberRowCutsBefore < numberRowCutsAfter) {
5589            const OsiRowCut * thisCut = theseCuts.rowCutPtr(numberRowCutsAfter-1) ;
5590            if (thisCut->lb()>thisCut->ub()) {
5591              feasible = false; // sub-problem is infeasible
5592              break;
5593            }
5594          }
5595#ifdef CBC_DEBUG
5596          {
5597            int k ;
5598            for (k = numberRowCutsBefore;k<numberRowCutsAfter;k++) {
5599              OsiRowCut thisCut = theseCuts.rowCut(k) ;
5600              /* check size of elements.
5601                 We can allow smaller but this helps debug generators as it
5602                 is unsafe to have small elements */
5603              int n=thisCut.row().getNumElements();
5604              const int * column = thisCut.row().getIndices();
5605              const double * element = thisCut.row().getElements();
5606              //assert (n);
5607              for (int i=0;i<n;i++) {
5608                double value = element[i];
5609                assert(fabs(value)>1.0e-12&&fabs(value)<1.0e20);
5610              }
5611            }
5612          }
5613#endif
5614          if (mustResolve) {
5615            int returncode = resolve(node ? node->nodeInfo() : NULL,2);
5616            feasible = returnCode  != 0 ;
5617            if (returncode<0)
5618              numberTries=0;
5619            if ((specialOptions_&1)!=0) {
5620              debugger = solver_->getRowCutDebugger() ;
5621              if (debugger) 
5622                onOptimalPath = (debugger->onOptimalPath(*solver_)) ;
5623              else
5624                onOptimalPath=false;
5625              if (onOptimalPath && !solver_->isDualObjectiveLimitReached())
5626                assert(feasible) ;
5627            }
5628            if (!feasible)
5629              break ;
5630          }
5631        }
5632        numberRowCutsAfter = theseCuts.sizeRowCuts() ;
5633        numberColumnCutsAfter = theseCuts.sizeColCuts() ;
5634       
5635        if ((specialOptions_&1)!=0) {
5636          if (onOptimalPath) {
5637            int k ;
5638            for (k = numberRowCutsBefore;k<numberRowCutsAfter;k++) {
5639              OsiRowCut thisCut = theseCuts.rowCut(k) ;
5640              if(debugger->invalidCut(thisCut)) {
5641                solver_->writeMps("badCut");
5642#ifdef NDEBUG
5643                printf("Cut generator %d (%s) produced invalid cut (%dth in this go)\n",
5644                       i,generator_[i]->cutGeneratorName(),k-numberRowCutsBefore);
5645                const double *lower = getColLower() ;
5646                const double *upper = getColUpper() ;
5647                int numberColumns = solver_->getNumCols();
5648                for (int i=0;i<numberColumns;i++)
5649                  printf("%d bounds %g,%g\n",i,lower[i],upper[i]);
5650                abort();
5651#endif
5652              }
5653              assert(!debugger->invalidCut(thisCut)) ;
5654            }
5655          }
5656        }
5657/*
5658  The cut generator has done its thing, and maybe it generated some
5659  cuts.  Do a bit of bookkeeping: load
5660  whichGenerator[i] with the index of the generator responsible for a cut,
5661  and place cuts flagged as global in the global cut pool for the model.
5662
5663  lastNumberCuts is the sum of cuts added in previous iterations; it's the
5664  offset to the proper starting position in whichGenerator.
5665*/
5666        int numberBefore =
5667          numberRowCutsBefore+numberColumnCutsBefore+lastNumberCuts ;
5668        int numberAfter =
5669          numberRowCutsAfter+numberColumnCutsAfter+lastNumberCuts ;
5670        // possibly extend whichGenerator
5671        resizeWhichGenerator(numberBefore, numberAfter);
5672        int j ;
5673        if (fullScan) {
5674          // counts
5675          countColumnCuts[i] += numberColumnCutsAfter-numberColumnCutsBefore ;
5676        }
5677        countRowCuts[i] += numberRowCutsAfter-numberRowCutsBefore ;
5678       
5679        bool dodgyCuts=false;
5680        for (j = numberRowCutsBefore;j<numberRowCutsAfter;j++) {
5681          const OsiRowCut * thisCut = theseCuts.rowCutPtr(j) ;
5682          if (thisCut->lb()>1.0e10||thisCut->ub()<-1.0e10) {
5683            dodgyCuts=true;
5684            break;
5685          }
5686          whichGenerator_[numberBefore++] = i ;
5687          if (thisCut->lb()>thisCut->ub())
5688            violated=-2; // sub-problem is infeasible
5689          if (thisCut->globallyValid()) {
5690            // add to global list
5691            OsiRowCut newCut(*thisCut);
5692            newCut.setGloballyValid(true);
5693            newCut.mutableRow().setTestForDuplicateIndex(false);
5694            globalCuts_.insert(newCut) ;
5695          }
5696        }
5697        if (dodgyCuts) {
5698          for (int k=numberRowCutsAfter-1;k>=j;k--) {
5699            const OsiRowCut * thisCut = theseCuts.rowCutPtr(k) ;
5700            if (thisCut->lb()>thisCut->ub())
5701              violated=-2; // sub-problem is infeasible
5702            if (thisCut->lb()>1.0e10||thisCut->ub()<-1.0e10) 
5703              theseCuts.eraseRowCut(k);
5704          }
5705          numberRowCutsAfter = theseCuts.sizeRowCuts() ;
5706          for (;j<numberRowCutsAfter;j++) {
5707            const OsiRowCut * thisCut = theseCuts.rowCutPtr(j) ;
5708            whichGenerator_[numberBefore++] = i ;
5709            if (thisCut->globallyValid()) {
5710              // add to global list
5711              OsiRowCut newCut(*thisCut);
5712              newCut.setGloballyValid(true);
5713              newCut.mutableRow().setTestForDuplicateIndex(false);
5714              globalCuts_.insert(newCut) ;
5715            }
5716          }
5717        }
5718        for (j = numberColumnCutsBefore;j<numberColumnCutsAfter;j++) {
5719          whichGenerator_[numberBefore++] = i ;
5720          const OsiColCut * thisCut = theseCuts.colCutPtr(j) ;
5721          if (thisCut->globallyValid()) {
5722            // add to global list
5723            OsiColCut newCut(*thisCut);
5724            newCut.setGloballyValid(true);
5725            globalCuts_.insert(newCut) ;
5726          }
5727        }
5728      }
5729      // Add in any violated saved cuts
5730      if (!theseCuts.sizeRowCuts()&&!theseCuts.sizeColCuts()) {
5731        int numberOld = theseCuts.sizeRowCuts()+lastNumberCuts;
5732        int numberCuts = slackCuts.sizeRowCuts() ;
5733        int i;
5734        // possibly extend whichGenerator
5735        resizeWhichGenerator(numberOld, numberOld+numberCuts);
5736        for ( i = 0;i<numberCuts;i++) {
5737          const OsiRowCut * thisCut = slackCuts.rowCutPtr(i) ;
5738          if (thisCut->violated(cbcColSolution_)>100.0*primalTolerance) {
5739            if (messageHandler()->logLevel()>2)
5740              printf("Old cut added - violation %g\n",
5741                     thisCut->violated(cbcColSolution_)) ;
5742            whichGenerator_[numberOld++]=-1;
5743            theseCuts.insert(*thisCut) ;
5744          }
5745        }
5746      }
5747    } else {
5748      // do cuts independently
5749      OsiCuts * eachCuts = new OsiCuts [numberCutGenerators_];;
5750#ifdef CBC_THREAD
5751      if (!threadModel) {
5752#endif
5753        // generate cuts
5754        for (i = 0;i<numberCutGenerators_;i++) {
5755          bool generate = generator_[i]->normal();
5756          // skip if not optimal and should be (maybe a cut generator has fixed variables)
5757          if (generator_[i]->needsOptimalBasis()&&!solver_->basisIsAvailable())
5758            generate=false;
5759          if (generator_[i]->switchedOff())
5760            generate=false;;
5761          if (generate) 
5762            generator_[i]->generateCuts(eachCuts[i],fullScan,solver_,node) ;
5763        }
5764#ifdef CBC_THREAD
5765      } else {
5766        for (i=0;i<numberThreads_;i++) {
5767          // set solver here after cloning
5768          threadModel[i]->solver_=solver_->clone();
5769          threadModel[i]->numberNodes_ = (fullScan) ? 1 : 0;
5770        }
5771        // generate cuts
5772        for (i = 0;i<numberCutGenerators_;i++) {
5773          bool generate = generator_[i]->normal();
5774          // skip if not optimal and should be (maybe a cut generator has fixed variables)
5775          if (generator_[i]->needsOptimalBasis()&&!solver_->basisIsAvailable())
5776            generate=false;
5777          if (generator_[i]->switchedOff())
5778            generate=false;;
5779          if (generate) { 
5780            bool finished=false;
5781            int iThread=-1;
5782            // see if any available
5783            for (iThread=0;iThread<numberThreads_;iThread++) {
5784              if (threadInfo[iThread].returnCode) {
5785                finished=true;
5786                break;
5787              } else if (threadInfo[iThread].returnCode==0) {
5788                pthread_cond_signal(threadInfo[iThread].condition2); // unlock
5789              }
5790            }
5791            while (!finished) {
5792              pthread_mutex_lock(&condition_mutex);
5793              struct timespec absTime;
5794              clock_gettime(CLOCK_REALTIME,&absTime);
5795              absTime.tv_nsec += 1000000; // millisecond
5796              if (absTime.tv_nsec>=1000000000) {
5797                absTime.tv_nsec -= 1000000000;
5798                absTime.tv_sec++;
5799              }
5800              pthread_cond_timedwait(&condition_main,&condition_mutex,&absTime);
5801              pthread_mutex_unlock(&condition_mutex);
5802              for (iThread=0;iThread<numberThreads_;iThread++) {
5803                if (threadInfo[iThread].returnCode>0) {
5804                  finished=true;
5805                  break;
5806                } else if (threadInfo[iThread].returnCode==0) {
5807                  pthread_cond_signal(threadInfo[iThread].condition2); // unlock
5808                }
5809              }
5810            }
5811            assert (iThread<numberThreads_);
5812            assert (threadInfo[iThread].returnCode);
5813            threadModel[iThread]->generator_[0]=generator_[i];
5814            threadModel[iThread]->object_ = (OsiObject **) (eachCuts+i);
5815            // allow to start
5816            threadInfo[iThread].returnCode=0;
5817            pthread_cond_signal(threadInfo[iThread].condition2); // unlock
5818          }
5819        }
5820        // wait
5821        for (int iThread=0;iThread<numberThreads_;iThread++) {
5822          if (threadInfo[iThread].returnCode==0) {
5823            bool finished=false;
5824            pthread_cond_signal(threadInfo[iThread].condition2); // unlock
5825