Changeset 259

Timestamp:

Feb 18, 2006 3:46:11 PM (14 years ago)

Author:

forrest

Message:

changes to annoy people

Location:

trunk

Files:

• CbcCutGenerator.cpp (modified) (5 diffs)
• CbcModel.cpp (modified) (6 diffs)
• CbcNode.cpp (modified) (51 diffs)
• Test/Makefile.solve (modified) (1 diff)
• include/CbcCutGenerator.hpp (modified) (2 diffs)
• include/CbcModel.hpp (modified) (5 diffs)

trunk/CbcCutGenerator.cpp

@@ -33 +33 @@
     numberTimes_(0),
     numberCuts_(0),
+    numberColumnCuts_(0),
     numberCutsActive_(0)
 {
@@ -50 +51 @@
     numberTimes_(0),
     numberCuts_(0),
+    numberColumnCuts_(0),
     numberCutsActive_(0)
 {
@@ -86 +88 @@
   numberTimes_ = rhs.numberTimes_;
   numberCuts_ = rhs.numberCuts_;
+  numberColumnCuts_ = rhs.numberColumnCuts_;
   numberCutsActive_ = rhs.numberCutsActive_;
 }
@@ -112 +115 @@
     numberTimes_ = rhs.numberTimes_;
     numberCuts_ = rhs.numberCuts_;
+    numberColumnCuts_ = rhs.numberColumnCuts_;
     numberCutsActive_ = rhs.numberCutsActive_;
   }
@@ -203 +207 @@
       int numberColumns = solver->getNumCols();
       double primalTolerance = 1.0e-8;
+#if 0
+      int numberChanged=0,ifCut=0;
+      CoinPackedVector lbs;
+      CoinPackedVector ubs;
       for (j=0;j<numberColumns;j++) {
-        if (tightUpper[j]==tightLower[j]&&
-            upper[j]>lower[j]) {
-          // fix
-          solver->setColLower(j,tightLower[j]);
-          solver->setColUpper(j,tightUpper[j]);
-          if (tightLower[j]>solution[j]+primalTolerance||
-              tightUpper[j]<solution[j]-primalTolerance)
-            returnCode=true;
+        if (solver->isInteger(j)) {
+          if (tightUpper[j]<upper[j]) {
+            numberChanged++;
+            assert (tightUpper[j]==floor(tightUpper[j]+0.5));
+            ubs.insert(j,tightUpper[j]);
+            if (tightUpper[j]<solution[j]-primalTolerance)
+              ifCut=1;
+          }
+          if (tightLower[j]>lower[j]) {
+            numberChanged++;
+            assert (tightLower[j]==floor(tightLower[j]+0.5));
+            lbs.insert(j,tightLower[j]);
+            if (tightLower[j]>solution[j]+primalTolerance)
+              ifCut=1;
+          }
+        } else {
+          if (tightUpper[j]==tightLower[j]&&
+              upper[j]>lower[j]) {
+            // fix
+            //solver->setColLower(j,tightLower[j]);
+            //solver->setColUpper(j,tightUpper[j]);
+            double value = tightUpper[j];
+            numberChanged++;
+            if (value<upper[j])
+              ubs.insert(j,value);
+            if (value>lower[j])
+              lbs.insert(j,value);
+          }
         }
       }
-      //returnCode = !solver->basisIsAvailable();
+      if (numberChanged) {
+        OsiColCut cc;
+        cc.setUbs(ubs);
+        cc.setLbs(lbs);
+        if (ifCut) {
+          cc.setEffectiveness(100.0);
+        } else {
+          cc.setEffectiveness(1.0e-5);
+        }
+        cs.insert(cc);
+      }
+      // need to resolve if some bounds changed
+      returnCode = !solver->basisIsAvailable();
+      assert (!returnCode);
+#else
+      for (j=0;j<numberColumns;j++) {
+        if (solver->isInteger(j)) {
+          if (tightUpper[j]<upper[j]) {
+            double nearest = floor(tightUpper[j]+0.5);
+            assert (fabs(tightUpper[j]-nearest)<1.0e-7);
+            solver->setColUpper(j,nearest);
+            if (nearest<solution[j]-primalTolerance)
+              returnCode=true;
+          }
+          if (tightLower[j]>lower[j]) {
+            double nearest = floor(tightLower[j]+0.5);
+            assert (fabs(tightLower[j]-nearest)<1.0e-7);
+            solver->setColLower(j,nearest);
+            if (nearest>solution[j]+primalTolerance)
+              returnCode=true;
+          }
+        } else {
+          if (tightUpper[j]==tightLower[j]&&
+              upper[j]>lower[j]) {
+            // fix
+            solver->setColLower(j,tightLower[j]);
+            solver->setColUpper(j,tightUpper[j]);
+            if (tightLower[j]>solution[j]+primalTolerance||
+                tightUpper[j]<solution[j]-primalTolerance)
+              returnCode=true;
+          }
+        }
+      }
+      //if (!solver->basisIsAvailable()) 
+      //returnCode=true;
+#endif
     }
     if (timing_)

trunk/CbcModel.cpp

@@ -3406 +3406 @@
   numberNewCuts_(0),
   sizeMiniTree_(0),
+  searchStrategy_(-1),
+  numberStrongIterations_(0),
   resolveAfterTakeOffCuts_(true)
 {
@@ -3521 +3523 @@
   numberNewCuts_(0),
   sizeMiniTree_(0),
+  searchStrategy_(-1),
+  numberStrongIterations_(0),
   resolveAfterTakeOffCuts_(true)
 {
@@ -3710 +3714 @@
   numberNewCuts_(rhs.numberNewCuts_),
   sizeMiniTree_(rhs.sizeMiniTree_),
+  searchStrategy_(rhs.searchStrategy_),
+  numberStrongIterations_(rhs.numberStrongIterations_),
   resolveAfterTakeOffCuts_(rhs.resolveAfterTakeOffCuts_)
 {
@@ -4011 +4017 @@
     resolveAfterTakeOffCuts_=rhs.resolveAfterTakeOffCuts_;
     sizeMiniTree_ = rhs.sizeMiniTree_;
+    searchStrategy_ = rhs.searchStrategy_;
+    numberStrongIterations_ = rhs.numberStrongIterations_;
     lastHeuristic_ = NULL;
     numberCutGenerators_ = rhs.numberCutGenerators_;
@@ -4243 +4251 @@
   numberOldActiveCuts_=0;
   numberNewCuts_=0;
+  searchStrategy_=-1;
+  numberStrongIterations_=0;
   // Parameters which need to be reset
   dblParam_[CbcCutoffIncrement] = 1e-5;
@@ -6226 +6236 @@
     return this;
   }
+}
+// Fill in useful estimates
+void 
+CbcModel::pseudoShadow(double * down, double * up)
+{
+  // Column copy of matrix
+  const double * element = solver_->getMatrixByCol()->getElements();
+  const int * row = solver_->getMatrixByCol()->getIndices();
+  const CoinBigIndex * columnStart = solver_->getMatrixByCol()->getVectorStarts();
+  const int * columnLength = solver_->getMatrixByCol()->getVectorLengths();
+  const double *objective = solver_->getObjCoefficients() ;
+  int numberColumns = solver_->getNumCols() ;
+  double direction = solver_->getObjSense();
+  int iColumn;
+  const double * dual = cbcRowPrice_;
+  down = new double[numberColumns];
+  up = new double[numberColumns];
+  double upSum=1.0e-20;
+  double downSum = 1.0e-20;
+  int numberIntegers=0;
+  for (iColumn=0;iColumn<numberColumns;iColumn++) {
+    CoinBigIndex start = columnStart[iColumn];
+    CoinBigIndex end = start + columnLength[iColumn];
+    double upValue = 0.0;
+    double downValue = 0.0;
+    double value = direction*objective[iColumn];
+    if (value) {
+      if (value>0.0)
+        upValue += value;
+      else
+        downValue -= value;
+    }
+    for (CoinBigIndex j=start;j<end;j++) {
+      int iRow = row[j];
+      value = -dual[iRow];
+      if (value) {
+        value *= element[j];
+        if (value>0.0)
+          upValue += value;
+        else
+          downValue -= value;
+      }
+    }
+    // use dj if bigger
+    double dj = cbcReducedCost_[iColumn];
+    upValue = CoinMax(upValue,dj);
+    downValue = CoinMax(downValue,-dj);
+    up[iColumn]=upValue;
+    down[iColumn]=downValue;
+    if (solver_->isInteger(iColumn)) {
+      if (!numberNodes_)
+        printf("%d - dj %g up %g down %g cost %g\n",
+               iColumn,dj,upValue,downValue,objective[iColumn]);
+      upSum += upValue;
+      downSum += downValue;
+      numberIntegers++;
+    }
+  }
+  if (numberIntegers) {
+    double smallDown = 0.01*(downSum/((double) numberIntegers));
+    double smallUp = 0.01*(upSum/((double) numberIntegers));
+    for (int i=0;i<numberObjects_;i++) {
+      CbcSimpleIntegerDynamicPseudoCost * obj1 =
+        dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(object_[i]) ;
+      if (obj1) {
+        iColumn = obj1->columnNumber();
+        double upPseudoCost = obj1->upDynamicPseudoCost();
+        double saveUp = upPseudoCost;
+        upPseudoCost = CoinMax(upPseudoCost,smallUp);
+        upPseudoCost = CoinMax(upPseudoCost,up[iColumn]);
+        upPseudoCost = CoinMax(upPseudoCost,0.1*down[iColumn]);
+        obj1->setUpDynamicPseudoCost(upPseudoCost);
+        if (upPseudoCost>saveUp&&!numberNodes_)
+          printf("For %d up went from %g to %g\n",
+                 iColumn,saveUp,upPseudoCost);
+        double downPseudoCost = obj1->downDynamicPseudoCost();
+        double saveDown = downPseudoCost;
+        downPseudoCost = CoinMax(downPseudoCost,smallDown);
+        downPseudoCost = CoinMax(downPseudoCost,down[iColumn]);
+        downPseudoCost = CoinMax(downPseudoCost,0.1*down[iColumn]);
+        obj1->setDownDynamicPseudoCost(downPseudoCost);
+        if (downPseudoCost>saveDown&&!numberNodes_)
+          printf("For %d down went from %g to %g\n",
+                 iColumn,saveDown,downPseudoCost);
+      }
+    }
+  }
+  delete [] down;
+  delete [] up;
 }
 

trunk/CbcNode.cpp

@@ -18 +18 @@
 #include "CbcModel.hpp"
 #include "CbcNode.hpp"
+#include "CbcStatistics.hpp"
 #include "CbcBranchActual.hpp"
 #include "CbcBranchDynamic.hpp"
@@ -883 +884 @@
   if (model->hotstartSolution())
     numberStrong=0;
+  int numberStrongDone=0;
+  int numberUnfinished=0;
+  int numberStrongInfeasible=0;
+  int numberStrongIterations=0;
   int saveNumberStrong=numberStrong;
   int numberObjects = model->numberObjects();
@@ -917 +922 @@
     estimatedDegradation=0.0; 
     //int numberIntegerInfeasibilities=0; // without odd ones
+    numberStrongDone=0;
+    numberUnfinished=0;
+    numberStrongInfeasible=0;
+    numberStrongIterations=0;
     
     // We may go round this loop twice (only if we think we have solution)
@@ -926 +935 @@
       //                      numberIntegerInfeasibilities,
       //                      numberObjectInfeasibilities);
-      // If forcePriority > 0 then we want best solution
       const double * hotstartSolution = model->hotstartSolution();
       const int * hotstartPriorities = model->hotstartPriorities();
@@ -1079 +1087 @@
           } 
         }
-        if (roundAgain) {
+        if (roundAgain&&saveNumberStrong) {
           // restore basis
           solver->setWarmStart(ws);
@@ -1348 +1356 @@
           if (feasible) {
             solver->solveFromHotStart() ;
+            numberStrongDone++;
+            numberStrongIterations += solver->getIterationCount();
             /*
               We now have an estimate of objective degradation that we can use for strong
@@ -1373 +1383 @@
           iStatus = outputStuff[2*i];
           choice[i].numItersDown = outputStuff[2*numberStrong+2*i];
+          numberStrongDone++;
+          numberStrongIterations += choice[i].numItersDown;
           newObjectiveValue = objectiveValue+newUpper[i];
           solver->setColSolution(outputSolution[2*i]);
@@ -1381 +1393 @@
           if (newObjectiveValue>=model->getCutoff()) {
             objectiveChange = 1.0e100; // say infeasible
+            numberStrongInfeasible++;
           } else {
             // See if integer solution
@@ -1391 +1404 @@
               model->setLastHeuristic(NULL);
               model->incrementUsed(solver->getColSolution());
-              if (newObjectiveValue >= model->getCutoff())      //  *new* cutoff
+              if (newObjectiveValue >= model->getCutoff()) {    //  *new* cutoff
                 objectiveChange = 1.0e100 ;
+                numberStrongInfeasible++;
+              }
             }
           }
         } else if (iStatus==1) {
           objectiveChange = 1.0e100 ;
+          numberStrongInfeasible++;
         } else {
           // Can't say much as we did not finish
           choice[i].finishedDown = false ;
+          numberUnfinished++;
         }
         choice[i].downMovement = objectiveChange ;
@@ -1440 +1457 @@
           if (feasible) {
             solver->solveFromHotStart() ;
+            numberStrongDone++;
+            numberStrongIterations += solver->getIterationCount();
             /*
               We now have an estimate of objective degradation that we can use for strong
@@ -1465 +1484 @@
           iStatus = outputStuff[2*i+1];
           choice[i].numItersUp = outputStuff[2*numberStrong+2*i+1];
+          numberStrongDone++;
+          numberStrongIterations += choice[i].numItersUp;
           newObjectiveValue = objectiveValue+newLower[i];
           solver->setColSolution(outputSolution[2*i+1]);
@@ -1473 +1494 @@
           if (newObjectiveValue>=model->getCutoff()) {
             objectiveChange = 1.0e100; // say infeasible
+            numberStrongInfeasible++;
           } else {
             // See if integer solution
@@ -1483 +1505 @@
               model->setLastHeuristic(NULL);
               model->incrementUsed(solver->getColSolution());
-              if (newObjectiveValue >= model->getCutoff())      //  *new* cutoff
+              if (newObjectiveValue >= model->getCutoff()) {    //  *new* cutoff
                 objectiveChange = 1.0e100 ;
+                numberStrongInfeasible++;
+              }
             }
           }
         } else if (iStatus==1) {
           objectiveChange = 1.0e100 ;
+          numberStrongInfeasible++;
         } else {
           // Can't say much as we did not finish
           choice[i].finishedUp = false ;
+          numberUnfinished++;
         }
         choice[i].upMovement = objectiveChange ;
@@ -1654 +1680 @@
       }
       delete ws;
+      int numberNodes = model->getNodeCount();
+      // update number of strong iterations
+      model->setNumberStrongIterations(model->numberStrongIterations()+numberStrongIterations);
       
       /*
@@ -1665 +1694 @@
       if (anyAction>=0) {
         
-        int numberNodes = model->getNodeCount();
         // get average cost per iteration and assume stopped ones
         // would stop after 50% more iterations at average cost??? !!! ???
@@ -1807 +1835 @@
   //assert(objectiveValue_ == solver->getObjSense()*solver->getObjValue());
   double cutoff =model->getCutoff();
+  double distanceToCutoff=cutoff-objectiveValue_;
   const double * lower = solver->getColLower();
   const double * upper = solver->getColUpper();
@@ -1831 +1860 @@
   if (model->hotstartSolution()) 
     return -3;
+#define RANGING
+#ifdef RANGING
   // Pass number
   int kPass=0;
+  int numberRows = solver->getNumRows();
+#endif
   int numberColumns = model->getNumCols();
-  int numberRows = solver->getNumRows();
   double * saveUpper = new double[numberColumns];
   double * saveLower = new double[numberColumns];
@@ -1851 +1883 @@
     decision = new CbcBranchDynamicDecision();
   int numberMini=0;
-  int xStrong=0;
-  int xIters=0;
   int xPen=0;
   int xMark=0;
@@ -1888 +1918 @@
     osiclp->setSpecialOptions(saveClpOptions|1024);
   }
+  int saveSearchStrategy2 = model->searchStrategy();
+  if (saveSearchStrategy2<999) {
+    // Get average up and down costs
+    double averageUp=0.0;
+    double averageDown=0.0;
+    {
+      int numberUp=0;
+      int numberDown=0;
+      int i;
+      for ( i=0;i<numberObjects;i++) {
+        CbcObject * object = model->modifiableObject(i);
+        CbcSimpleIntegerDynamicPseudoCost * dynamicObject =
+          dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(object) ;
+        assert(dynamicObject);
+        if (dynamicObject->numberTimesUp()) {
+          numberUp++;
+          averageUp += dynamicObject->upDynamicPseudoCost();
+        }
+        if (dynamicObject->numberTimesDown()) {
+          numberDown++;
+          averageDown += dynamicObject->downDynamicPseudoCost();
+        }
+      }
+      if (numberUp) 
+        averageUp /= (double) numberUp;
+      else
+        averageUp=1.0;
+      if (numberDown) 
+        averageDown /= (double) numberDown;
+      else
+        averageDown=1.0;
+      for ( i=0;i<numberObjects;i++) {
+        CbcObject * object = model->modifiableObject(i);
+        CbcSimpleIntegerDynamicPseudoCost * dynamicObject =
+          dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(object) ;
+        assert(dynamicObject);
+        if (!dynamicObject->numberTimesUp()) 
+          dynamicObject->setUpDynamicPseudoCost(averageUp);
+      if (!dynamicObject->numberTimesDown()) 
+        dynamicObject->setDownDynamicPseudoCost(averageDown);
+      }
+    }
+  } else if (saveSearchStrategy2<1999) {
+    // pseudo shadow prices
+    model->pseudoShadow(NULL,NULL);
+  } else if (saveSearchStrategy2<2999) {
+    // leave old ones
+  } else if (saveSearchStrategy2<3999) {
+    // pseudo shadow prices at root
+    if (!numberNodes)
+      model->pseudoShadow(NULL,NULL);
+  } else {
+    abort();
+  }
+  if (saveSearchStrategy2>=0)
+    saveSearchStrategy2 = saveSearchStrategy2 % 1000;
+  if (saveSearchStrategy2==999)
+    saveSearchStrategy2=-1;
+  int px[4]={-1,-1,-1,-1};
+  int saveSearchStrategy = saveSearchStrategy2<99 ? saveSearchStrategy2 : saveSearchStrategy2-100;
+  bool newWay = saveSearchStrategy2>98;
+  int numberNotTrusted=0;
+  int numberStrongDone;
+  int numberUnfinished;
+  int numberStrongInfeasible;
+  int numberStrongIterations;
   while(!finished) {
     finished=true;
@@ -1896 +1992 @@
     int numberIntegerInfeasibilities=0; // without odd ones
     int numberToDo=0;
-    double averageDown=0.0;
-    int numberDown=0;
-    double averageUp=0.0;
-    int numberUp=0;
     int iBestNot=-1;
     int iBestGot=-1;
     double best=0.0;
-    int numberNotTrusted=0;
+    numberNotTrusted=0;
+    numberStrongDone=0;
+    numberUnfinished=0;
+    numberStrongInfeasible=0;
+    numberStrongIterations=0;
     int * which = objectMark+numberObjects+1;
     int neededPenalties;
@@ -1931 +2027 @@
       numberToDo=0;
       neededPenalties=0;
-      averageDown=0.0;
-      numberDown=0;
-      averageUp=0.0;
-      numberUp=0;
       iBestNot=-1;
       double bestNot=0.0;
@@ -1948 +2040 @@
         double infeasibility = object->infeasibility(preferredWay);
         int priorityLevel = object->priority();
+#define ZERO_ONE 0
+#define ZERO_FAKE 1.0e20;
+#if ZERO_ONE==1
+        // branch on 0-1 first (temp)
+        if (fabs(saveSolution[dynamicObject->columnNumber()])<1.0)
+          priorityLevel--;
+#endif
+#if ZERO_ONE==2
+        if (fabs(saveSolution[dynamicObject->columnNumber()])<1.0)
+          infeasibility *= ZERO_FAKE;
+#endif
         if (infeasibility) {
+          int iColumn = dynamicObject->columnNumber();
+          double gap = saveUpper[iColumn]-saveLower[iColumn];
+          // Give precedence to ones with gap of 1.0 
+          assert(gap>0.0);
+          infeasibility /= CoinMin(gap,100.0);
           if (!depth_&&false) {
             // try closest to 0.5
-            int iColumn = dynamicObject->columnNumber();
             double part =saveSolution[iColumn]-floor(saveSolution[iColumn]);
             infeasibility = fabs(0.5-part);
@@ -1957 +2064 @@
           bool gotDown=false;
           int numberThisDown = dynamicObject->numberTimesDown();
-          if (numberThisDown) {
-            averageDown += dynamicObject->downDynamicPseudoCost();
-            numberDown++;
-            if (numberThisDown>=numberBeforeTrust)
-              gotDown=true;
-          }
+          if (numberThisDown>=numberBeforeTrust)
+            gotDown=true;
           bool gotUp=false;
           int numberThisUp = dynamicObject->numberTimesUp();
-          if (numberThisUp) {
-            averageUp += dynamicObject->upDynamicPseudoCost();
-            numberUp++;
-            if (numberThisUp>=numberBeforeTrust)
-              gotUp=true;
-          }
+          if (numberThisUp>=numberBeforeTrust)
+            gotUp=true;
           if ((numberNodes%PRINT_STUFF)==0&&PRINT_STUFF>0)
             printf("%d down %d %g up %d %g - infeas %g\n",
@@ -2004 +2103 @@
             int iColumn = dynamicObject->columnNumber();
             double part =saveSolution[iColumn]-floor(saveSolution[iColumn]);
-            sort[numberToDo]=-infeasibility;
+            sort[numberToDo]=-10.0*infeasibility;
+            if (!(numberThisUp+numberThisDown))
+              sort[numberToDo] *= 100.0; // make even more likely
             if (1.0-fabs(part-0.5)>bestNot) {
               iBestNot=numberToDo;
@@ -2085 +2186 @@
     //bool skipAll = (numberBeforeTrust>20&&numberNodes>20000&&numberNotTrusted==0);
     bool skipAll = numberNotTrusted==0;
+    bool doneHotStart=false;
+#ifndef CBC_WEAK_STRONG
     if ((numberNodes%20)==0||(model->specialOptions()&8)!=0)
       skipAll=false;
+#endif
+    int searchStrategy = saveSearchStrategy>=0 ? (saveSearchStrategy%10) : -1;
+    if (!newWay) {
+    // 10 up always use %10, 20 up as 10 and allow penalties
+    // But adjust depending on ratio of iterations
+    if (searchStrategy>0&&saveSearchStrategy<10) {
+      if (numberBeforeTrust>=5&&numberBeforeTrust<=10) {
+        if (searchStrategy!=2) {
+          int numberIterations = model->getIterationCount();
+          int numberStrongIterations = model->numberStrongIterations();
+          if (numberStrongIterations>numberIterations+10000) {
+            searchStrategy=2;
+            //skipAll=true;
+          } else if (numberStrongIterations*4+1000<numberIterations||depth_<5) {
+            searchStrategy=3;
+            skipAll=false;
+          }
+        } else {
+          skipAll=true;
+        }
+      }
+    }
+    } else {
+    // But adjust depending on ratio of iterations
+    if (saveSearchStrategy<0) {
+      // unset
+      if ((numberNodes%20)==0||(model->specialOptions()&8)!=0) {
+        // Do numberStrong
+        searchStrategy=3;
+      } else if (depth_<5) {
+        // Do numberStrong
+        searchStrategy=2;
+      } else {
+        int numberIterations = model->getIterationCount();
+        int numberStrongIterations = model->numberStrongIterations();
+        int numberRows = solver->getNumRows();
+        if (numberStrongIterations>numberIterations+CoinMin(10000,10*numberRows)) {
+          // off
+          searchStrategy=0;
+        } else if (numberStrongIterations*4+1000<numberIterations) {
+          // Do numberStrong if not trusted
+          searchStrategy=2;
+        } else {
+          searchStrategy=1;
+        }
+      }
+    }
+    if (searchStrategy<3&&(!numberNotTrusted||!searchStrategy))
+      skipAll=true;
+    else
+      skipAll=false;
+    }
     // worth trying if too many times
     // Save basis
@@ -2092 +2247 @@
     // save limit
     int saveLimit=0;
+    solver->getIntParam(OsiMaxNumIterationHotStart,saveLimit);
     if (!skipAll) {
       ws = solver->getWarmStart();
-      solver->getIntParam(OsiMaxNumIterationHotStart,saveLimit);
-      if (!saveStateOfSearch&&saveLimit<100)
-        solver->setIntParam(OsiMaxNumIterationHotStart,100); 
+      int limit=100;
+#if 0
+      int averageBranchIterations = model->getIterationCount()/(model->getNodeCount()+1);
+      if (numberNodes)
+        limit = CoinMin(CoinMax(limit,2*averageBranchIterations),500);
+      else
+        limit = 500;
+#endif
+      if ((!saveStateOfSearch||searchStrategy>3)&&saveLimit<limit&&saveLimit==100)
+        solver->setIntParam(OsiMaxNumIterationHotStart,limit); 
     }
     // Say which one will be best
@@ -2126 +2289 @@
         solver->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,&easy) ;
       int iDo;
-#define RANGING
 #ifdef RANGING
-      if (skipAll&&numberBeforeTrust)
+      if ((skipAll&&numberBeforeTrust&&saveSearchStrategy<20)||saveSearchStrategy<10)
         numberPenalties=0;
       {
@@ -2134 +2296 @@
         double needed = neededPenalties;
         needed *= numberRows;
-        if (needed>1.0e6) {
+        if (needed>1.0e6&&numberNodes&&saveSearchStrategy<20) {
           numberPenalties=0;
           neededPenalties=0;
@@ -2154 +2316 @@
           solver->markHotStart();
         }
+        doneHotStart=true;
         xMark++;
         kPass++;
@@ -2159 +2322 @@
         const double * downCost=osiclp->upRange();
         const double * upCost=osiclp->downRange();
-        //printf("numberTodo %d needed %d numberpenalties %d\n",numberToDo,needed,numberPenalties);
+        //printf("numberTodo %d needed %d numberpenalties %d\n",numberToDo,neededPenalties,numberPenalties);
         double invTrust = 1.0/((double) numberBeforeTrust);
         for (int i=0;i<neededPenalties;i++) {
@@ -2189 +2352 @@
           }
           sort[j] = - CoinMin(downEstimate[iObject],upEstimate[iObject]);
-          if ((numberNodes%PRINT_STUFF)==0&&PRINT_STUFF>0)
+#ifdef CBC_WEAK_STRONG
+          sort[j] -= 1.0e10; // make more likely to be chosen
+#endif
+          //if ((numberNodes%PRINT_STUFF)==0&&PRINT_STUFF>0)
+          if (!numberNodes)
             printf("%d pen down ps %g -> %g up ps %g -> %g\n",
                    iObject,downCost[i],downPenalty,upCost[i],upPenalty);
@@ -2197 +2364 @@
           // Mark hot start
           solver->markHotStart();
+          doneHotStart=true;
           xMark++;
           //if (solver->isProvenPrimalInfeasible())
@@ -2206 +2374 @@
       }
 #else
-      // Mark hot start
-      solver->markHotStart();
-          xMark++;
+      if (!skipAll) {
+        // Mark hot start
+        doneHotStart=true;
+        solver->markHotStart();
+        xMark++;
+      }
       // make sure best will be first
       if (iBestGot>=0)
@@ -2232 +2403 @@
       //printf("todo %d, strong %d\n",numberToDo,numberStrong);
       int numberTest=numberNotTrusted>0 ? numberStrong : (numberStrong+1)/2;
-      int numberTest2 = CoinMax(2*numberStrong,10)+1000000;
+      int numberTest2 = 2*numberStrong;
+      if (!newWay) {
+      if (searchStrategy==3) {
+        // Previously decided we need strong
+        doQuickly=false;
+        numberTest = numberStrong;
+        //numberTest2 = 1000000;
+      }
+      if (searchStrategy<0||searchStrategy==1)
+        //numberTest2 = 1000000;
 #if 0
       if (numberBeforeTrust>20&&(numberNodes>20000||(numberNodes>200&&numberNotTrusted==0))) {
@@ -2242 +2422 @@
 #else
       // Try nearly always off
-      if ((numberNodes%20)!=0) {
-        numberTest=0;
+      if (searchStrategy<2) {
+        if ((numberNodes%20)!=0) {
+          if ((model->specialOptions()&8)==0) {
+            numberTest=0;
+            doQuickly=true;
+          }
+        } else {
+          doQuickly=false;
+          numberTest=2*numberStrong;
+        }
+      } else if (searchStrategy!=3) {
         doQuickly=true;
-      } else {
-        doQuickly=true;
-        numberTest=2*numberStrong;
+        numberTest=numberStrong;
       }
 #endif
       if (depth_<10&&numberStrong) {
-        doQuickly=false;
-        if (depth_<7)
-          numberStrong *=3;
-        if (!depth_) 
-          numberStrong=CoinMin(6*numberStrong,numberToDo);
-        numberTest=numberStrong;
+        if (searchStrategy!=2) {
+          doQuickly=false;
+          if (depth_<7)
+            numberStrong *=3;
+          if (!depth_) 
+            numberStrong=CoinMin(6*numberStrong,numberToDo);
+          numberTest=numberStrong;
+        }
         model->setStateOfSearch(2); // use min min
       }
@@ -2264 +2453 @@
       // if too many and big then just do 10 its
       if (!skipAll&&saveStateOfSearch) {
-        //if (numberNotTrusted>3*numberStrong&&numberRows>250&&numberColumns>1000)
+        //if (numberNotTrusted>3*numberStrong&&numberRows>250&&numberColumns>1000&&saveLimit==100)
           // off solver->setIntParam(OsiMaxNumIterationHotStart,10); 
       }
-      double distanceToCutoff=model->getCutoff()-objectiveValue_;
       // make negative for test
       distanceToCutoff = - distanceToCutoff;
@@ -2287 +2475 @@
         numberTest = CoinMax(numberTest,5);
       }
+      } else {
+      int numberTest=numberNotTrusted>0 ? numberStrong : (numberStrong+1)/2;
+      int numberTest2 = 2*numberStrong;
+      if (searchStrategy>=3) {
+        // Previously decided we need strong
+        doQuickly=false;
+        if (depth_<7)
+          numberStrong *=3;
+        if (!depth_) 
+          numberStrong=CoinMin(6*numberStrong,numberToDo);
+        numberTest = numberStrong;
+        numberTest2 *= 2;
+      } else if (searchStrategy==2||(searchStrategy==1&&depth_<6)) {
+        numberStrong *=2;
+        if (!depth_) 
+          numberStrong=CoinMin(2*numberStrong,numberToDo);
+        numberTest = numberStrong;
+      } else if (searchStrategy==1&&numberNotTrusted) {
+        numberTest = numberStrong;
+      } else {
+        numberTest=0;
+        skipAll=true;
+      }
+      distanceToCutoff=model->getCutoff()-objectiveValue_;
+      // make negative for test
+      distanceToCutoff = - distanceToCutoff;
+      if (numberObjects>-100) {
+        // larger 
+        distanceToCutoff *= 100.0;
+      }
+      distanceToCutoff = -COIN_DBL_MAX;
+      if (skipAll) {
+        numberTest=0;
+        doQuickly=true;
+      }
+      }
+      px[0]=numberTest;
+      px[1]=numberTest2;
+      px[2]= doQuickly ? 1 : -1;
+      px[3]=numberStrong;
+      //printf("skipAll %c doQuickly %c numberTest %d numberTest2 %d numberNot %d\n",
+      //     skipAll ? 'Y' : 'N',doQuickly ? 'Y' : 'N',numberTest,numberTest2,numberNotTrusted);
       // See if we want mini tree
       bool wantMiniTree=false;
@@ -2313 +2543 @@
         // see if can skip strong branching
         int canSkip = choice.possibleBranch->fillStrongInfo(choice);
-        if (!doQuickly||numberTest>0)
+        if (!newWay) {
+        if (!doQuickly||(numberTest>0&&searchStrategy!=2))
           canSkip=0;
+        } else {
+        if (skipAll)
+          canSkip=1;
+        else if (numberTest>0&&searchStrategy>=3)
+          canSkip=0;
+        }
         if (!numberBeforeTrust) {
           canSkip=1;
@@ -2320 +2557 @@
         if (sort[iDo]<distanceToCutoff)
           canSkip=0;
-        if (numberTest2<=0&&sort[iDo]>distanceToCutoff)
+        if (((numberTest2<=0&&numberTest<=0)||skipAll)&&sort[iDo]>distanceToCutoff) {
           canSkip=1; // always skip
+          if (iDo>20)
+            break; // give up anyway
+        }
         if (model->messageHandler()->logLevel()>3&&numberBeforeTrust) 
           dynamicObject->print(1,choice.possibleBranch->value());
         // was if (!canSkip)
+        if (newWay)
+        numberTest2--;
         if (!canSkip) {
           numberTest--;
+          if (!newWay)
           numberTest2--;
           // just do a few
-          if (canSkip)
-            solver->setIntParam(OsiMaxNumIterationHotStart,10); 
+          //if (canSkip)
+          //solver->setIntParam(OsiMaxNumIterationHotStart,10); 
           double objectiveChange ;
           double newObjectiveValue=1.0e100;
@@ -2346 +2589 @@
           choice.possibleBranch->branch() ;
           solver->solveFromHotStart() ;
-          xStrong++;
-          xIters += solver->getIterationCount();
+          numberStrongDone++;
+          numberStrongIterations += solver->getIterationCount();
           /*
             We now have an estimate of objective degradation that we can use for strong
@@ -2370 +2613 @@
             if (newObjectiveValue>=cutoff) {
               objectiveChange = 1.0e100; // say infeasible
+              numberStrongInfeasible++;
             } else {
               // See if integer solution
@@ -2381 +2625 @@
                 model->incrementUsed(solver->getColSolution());
                 cutoff =model->getCutoff();
-                if (newObjectiveValue >= cutoff)        //  *new* cutoff
+                if (newObjectiveValue >= cutoff) {      //  *new* cutoff
                   objectiveChange = 1.0e100 ;
+                  numberStrongInfeasible++;
+                }
               }
             }
           } else if (iStatus==1) {
             objectiveChange = 1.0e100 ;
+            numberStrongInfeasible++;
           } else {
             // Can't say much as we did not finish
             choice.finishedDown = false ;
+            numberUnfinished++;
           }
           choice.downMovement = objectiveChange ;
@@ -2409 +2657 @@
           choice.possibleBranch->branch();
           solver->solveFromHotStart() ;
-          xStrong++;
-          xIters += solver->getIterationCount();
+          numberStrongDone++;
+          numberStrongIterations += solver->getIterationCount();
           /*
             We now have an estimate of objective degradation that we can use for strong
@@ -2433 +2681 @@
             if (newObjectiveValue>=cutoff) {
               objectiveChange = 1.0e100; // say infeasible
+              numberStrongInfeasible++;
             } else {
               // See if integer solution
@@ -2444 +2693 @@
                 model->incrementUsed(solver->getColSolution());
                 cutoff =model->getCutoff();
-                if (newObjectiveValue >= cutoff)        //  *new* cutoff
+                if (newObjectiveValue >= cutoff) {      //  *new* cutoff
                   objectiveChange = 1.0e100 ;
+                  numberStrongInfeasible++;
+                }
               }
             }
           } else if (iStatus==1) {
             objectiveChange = 1.0e100 ;
+            numberStrongInfeasible++;
           } else {
             // Can't say much as we did not finish
             choice.finishedUp = false ;
+            numberUnfinished++;
           }
           choice.upMovement = objectiveChange ;
@@ -2488 +2741 @@
             choice.upMovement = CoinMax(0.0,choice.upMovement);
             choice.downMovement = CoinMax(0.0,choice.downMovement);
+#if ZERO_ONE==2
+            // branch on 0-1 first (temp)
+            if (fabs(choice.possibleBranch->value())<1.0) {
+              choice.upMovement *= ZERO_FAKE;
+              choice.downMovement *= ZERO_FAKE;
+            }
+#endif
             // feasible - see which best
             if (!canSkip) {
+              if (iColumn==-46) {
+                printf("sort %g downest %g upest %g ",sort[iDo],downEstimate[iObject],
+                     upEstimate[iObject]);
+                printf("downMove %g upMove %g value %g current pseudo %g %g\n",
+                       choice.downMovement,choice.upMovement,choice.possibleBranch->value(),
+                       dynamicObject->downDynamicPseudoCost(),dynamicObject->upDynamicPseudoCost());
+              }
               if (model->messageHandler()->logLevel()>3) 
                 printf("sort %g downest %g upest %g ",sort[iDo],downEstimate[iObject],
@@ -2505 +2772 @@
               decision->setBestCriterion(-1.0);
             double bestCriterion = -1.0;
+            double gap = saveUpper[iColumn]-saveLower[iColumn];
+            // Give precedence to ones with gap of 1.0 
+            assert(gap>0.0);
+            double factor = changeFactor/CoinMin(gap,100.0);
             int betterWay = decision->betterBranch(choice.possibleBranch,
                                                    branch_,
-                                                   choice.upMovement*changeFactor,
+                                                   choice.upMovement*factor,
                                                    choice.numIntInfeasUp ,
-                                                   choice.downMovement*changeFactor,
+                                                   choice.downMovement*factor,
                                                    choice.numIntInfeasDown );
             if (wantMiniTree) {
@@ -2578 +2849 @@
               saveLower[iColumn]=value;
               solver->setColLower(iColumn,value);
+              assert(doneHotStart);
+              solver->unmarkHotStart();
+              solver->markHotStart();
 #endif
             }
@@ -2602 +2876 @@
               saveUpper[iColumn]=value;
               solver->setColUpper(iColumn,value);
+              assert(doneHotStart);
+              solver->unmarkHotStart();
+              solver->markHotStart();
 #endif
             }
@@ -2648 +2925 @@
                  iDo,whichChoice,numberToDo);
       }
-      if (!skipAll) {
+      if (doneHotStart) {
         // Delete the snapshot
         solver->unmarkHotStart();
         // back to normal
         solver->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,NULL) ;
-        solver->setIntParam(OsiMaxNumIterationHotStart,saveLimit);
         // restore basis
         solver->setWarmStart(ws);
       }
+      solver->setIntParam(OsiMaxNumIterationHotStart,saveLimit);
       // Unless infeasible we will carry on
       // But we could fix anyway
@@ -2726 +3003 @@
   }
   if (model->messageHandler()->logLevel()>2) 
-    printf("%d strong, %d iters, %d pen, %d mark, %d fixed, action %d\n",
-         xStrong,xIters,xPen,xMark,numberToFix,anyAction);
+    printf("%d strong, %d iters, %d pen, %d mark, %d fixed, action %d nnott %d nt %d, %d dq %s ns %d\n",
+         numberStrongDone,numberStrongIterations,xPen,xMark,
+           numberToFix,anyAction,numberNotTrusted,px[0],px[1],px[2]>0 ? "y" : "n",px[3]);
+  // update number of strong iterations
+  model->setNumberStrongIterations(model->numberStrongIterations()+numberStrongIterations);
+  if (!newWay) {
+  if (((model->searchStrategy()+1)%1000)==0) {
+    if (solver->messageHandler()->logLevel()>1)
+      printf("%d strong, %d iters, %d inf, %d not finished, %d not trusted\n",
+             numberStrongDone,numberStrongIterations,numberStrongInfeasible,numberUnfinished,
+             numberNotTrusted);
+    // decide what to do
+    int strategy=1;
+    if (numberUnfinished*4>numberStrongDone&&numberStrongInfeasible*10<numberStrongDone) {
+      strategy=2;
+      if (model->logLevel()>1)
+        printf("going to strategy 2\n");
+    }
+    if (numberNodes)
+      strategy=1;  // should only happen after hot start
+    model->setSearchStrategy(strategy);
+  }
+  }
   //if (numberToFix&&depth_<5)
   //printf("%d fixed by strong at depth %d\n",numberToFix,depth_);

trunk/Test/Makefile.solve

@@ -55 +55 @@
 ifneq (,$(filter COIN_HAS_OSICLP, $(Define)))
 #  add in USE
-CXXFLAGS += $(addprefix -D,COIN_USE_CLP)
+#CXXFLAGS += $(addprefix -D,COIN_USE_CLP)
 else
   $(error COIN_HAS_CLP is not defined in Makefiles/Makefile.location. Probably the line 'CoinLibsDefined += COIN_libClp' is commented out.)

trunk/include/CbcCutGenerator.hpp

@@ -183 +183 @@
   inline int numberTimesEntered() const
   { return numberTimes_;};
-  void setNumberTimesEntered(int value)
+  inline void setNumberTimesEntered(int value)
   { numberTimes_ = value;};
-  void incrementNumberTimesEntered(int value=1)
+  inline void incrementNumberTimesEntered(int value=1)
   { numberTimes_ += value;};
   /// Total number of cuts added
   inline int numberCutsInTotal() const
   { return numberCuts_;};
-  void setNumberCutsInTotal(int value)
+  inline void setNumberCutsInTotal(int value)
   { numberCuts_ = value;};
-  void incrementNumberCutsInTotal(int value=1)
+  inline void incrementNumberCutsInTotal(int value=1)
   { numberCuts_ += value;};
+  /// Total number of column cuts
+  inline int numberColumnCuts() const
+  { return numberColumnCuts_;};
+  inline void setNumberColumnCuts(int value)
+  { numberColumnCuts_ = value;};
+  inline void incrementNumberColumnCuts(int value=1)
+  { numberColumnCuts_ += value;};
   /// Total number of cuts active after (at end of n cut passes at each node)
   inline int numberCutsActive() const
   { return numberCutsActive_;};
-  void setNumberCutsActive(int value)
+  inline void setNumberCutsActive(int value)
   { numberCutsActive_ = value;};
-  void incrementNumberCutsActive(int value=1)
+  inline void incrementNumberCutsActive(int value=1)
   { numberCutsActive_ += value;};
   inline void setSwitchOffIfLessThan(int value) 
@@ -260 +267 @@
   /// Total number of cuts added
   int numberCuts_;
+  /// Total number of column cuts added
+  int numberColumnCuts_;
   /// Total number of cuts active after (at end of n cut passes at each node)
   int numberCutsActive_;

trunk/include/CbcModel.hpp

@@ -366 +366 @@
   void findIntegers(bool startAgain);
 
-  /** If numberBeforeTrust >0 then we are going to use CbcBranchDynamic.
-      Scan and convert CbcSimpleInteger objects
-  */
-  void convertToDynamic();
-  
   //@}
 
@@ -1115 +1110 @@
   inline void setStateOfSearch(int state)
   { stateOfSearch_=state;};
+  /// Strategy worked out - mainly at root node for use by CbcNode
+  inline int searchStrategy() const
+  { return searchStrategy_;};
   /// Set strategy worked out - mainly at root node for use by CbcNode
   inline void setSearchStrategy(int value)
-  { /*searchStrategy_ = value; for compatibility*/};
+  { searchStrategy_ = value; };
 
   /// Get the number of cut generators
@@ -1396 +1394 @@
   void addCuts1(CbcNode * node, CoinWarmStartBasis *&lastws);
 
+  /** If numberBeforeTrust >0 then we are going to use CbcBranchDynamic.
+      Scan and convert CbcSimpleInteger objects
+  */
+  void convertToDynamic();
+  /// Use cliques for pseudocost information - return nonzero if infeasible
+  int cliquePseudoCosts(int doStatistics);
+  /// Fill in useful estimates
+  void pseudoShadow(double * down, double * up);
+
   /// Get the hotstart solution 
   inline const double * hotstartSolution() const
@@ -1417 +1424 @@
   inline CbcNode * currentNode() const
   { return currentNode_;};
+  /// Set the number of iterations done in strong branching.
+  inline void setNumberStrongIterations(int number)
+  { numberStrongIterations_ = number;};
+  /// Get the number of iterations done in strong branching.
+  inline int numberStrongIterations() const
+  { return numberStrongIterations_;};
   //@}
 
@@ -1740 +1753 @@
   /// Size of mini - tree
   int sizeMiniTree_;
+  /// Strategy worked out - mainly at root node
+  int searchStrategy_;
+  /// Number of iterations in strong branching
+  int numberStrongIterations_;
   /// Whether to force a resolve after takeOffCuts
   bool resolveAfterTakeOffCuts_;