source: stable/2.1/Cbc/src/CbcModel.cpp @ 941

Last change on this file since 941 was 941, checked in by forrest, 12 years ago

setBestSolution

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