Changeset 477

Timestamp:

Nov 3, 2006 3:48:00 PM (15 years ago)

Author:

forrest

Message:

for nonlinear and start moving to OsiTree?
afor n

Location:

branches/devel/Cbc/src

Files:

• CbcBranchActual.cpp (modified) (2 diffs)
• CbcModel.cpp (modified) (21 diffs)
• CbcModel.hpp (modified) (2 diffs)
• CbcNode.cpp (modified) (2 diffs)
• CbcNode.hpp (modified) (2 diffs)
• CbcStrategy.cpp (modified) (1 diff)
• CbcTree.hpp (modified) (1 diff)
• CoinSolve.cpp (modified) (1 diff)

branches/devel/Cbc/src/CbcBranchActual.cpp

@@ -985 +985 @@
   int iColumn = originalCbcObject_->columnNumber();
   assert (variable_==iColumn);
+  double olb,oub ;
+  olb = model_->solver()->getColLower()[iColumn] ;
+  oub = model_->solver()->getColUpper()[iColumn] ;
   if (way_<0) {
 #ifdef CBC_DEBUG
@@ -1008 +1011 @@
     way_=-1;      // Swap direction
   }
+  double nlb = model_->solver()->getColLower()[iColumn];
+  if (nlb<olb) {
+#ifndef NDEBUG
+    printf("bad lb change for column %d from %g to %g\n",iColumn,olb,nlb);
+#endif
+    model_->solver()->setColLower(iColumn,olb);
+  }
+  double nub = model_->solver()->getColUpper()[iColumn];
+  if (nub>oub) {
+#ifndef NDEBUG
+    printf("bad ub change for column %d from %g to %g\n",iColumn,oub,nub);
+#endif
+    model_->solver()->setColUpper(iColumn,oub);
+  }
+#ifndef NDEBUG
+  if (nlb<olb+1.0e-8&&nub>oub-1.0e-8)
+    printf("bad null change for column %d - bounds %g,%g\n",iColumn,olb,oub);
+#endif
   return 0.0;
 }

branches/devel/Cbc/src/CbcModel.cpp

@@ -281 +281 @@
 
 
-
+static double trueIncrement=0.0;
 void 
 CbcModel::analyzeObjective ()
@@ -311 +311 @@
 */
   double maximumCost = 0.0 ;
+  trueIncrement=0.0;
   bool possibleMultiple = true ;
   int iColumn ;
@@ -335 +336 @@
       while (10.0*multiplier*maximumCost < 1.0e8)
         multiplier *= 10.0 ;
-
-      for (iColumn = 0 ; iColumn < numberColumns ; iColumn++)
-      { if (upper[iColumn] > lower[iColumn]+1.0e-8)
-        { if (isInteger(iColumn)&&objective[iColumn])
-          { double value = fabs(objective[iColumn])*multiplier ;
+    int bigIntegers = 0; // Count of large costs which are integer
+    for (iColumn = 0 ; iColumn < numberColumns ; iColumn++) {
+      if (upper[iColumn] > lower[iColumn]+1.0e-8) {
+        if (isInteger(iColumn)&&objective[iColumn]) {
+          double value = fabs(objective[iColumn])*multiplier ;
+          if (value <2.1e9) {
             int nearest = (int) floor(value+0.5) ;
             if (fabs(value-floor(value+0.5)) > 1.0e-8)
-            { increment = 0 ;
+              { increment = 0 ;
               break ; }
             else if (!increment)
-            { increment = nearest ; }
+              { increment = nearest ; }
             else
-            { increment = gcd(increment,nearest) ; } } } }
+              { increment = gcd(increment,nearest) ; }
+          } else {
+            // large value - may still be multiple of 1.0
+            value = fabs(objective[iColumn]);
+            if (fabs(value-floor(value+0.5)) > 1.0e-8) {
+              increment=0;
+              break;
+            } else {
+              bigIntegers++;
+            }
+          }
+        }
+      }
+    }
+
 /*
   If the increment beats the current value for objective change, install it.
@@ -354 +370 @@
       { double value = increment ;
         double cutoff = getDblParam(CbcModel::CbcCutoffIncrement) ;
+        if (bigIntegers) {
+          // allow for 1.0
+          increment = gcd(increment,(int) multiplier);
+          value = increment;
+        }
         value /= multiplier ;
+        trueIncrement=CoinMax(cutoff,value);;
         if (value*0.999 > cutoff)
         { messageHandler()->message(CBC_INTEGERINCREMENT,
@@ -748 +770 @@
       solver_->findIntegersAndSOS(false);
       numberObjects_=solver_->numberObjects();
-      object_ = new OsiObject * [numberObjects_];
-      for (int iObject = 0 ; iObject < numberObjects_ ; iObject++) {
-        object_[iObject]=solver_->object(iObject)->clone();
-      }
+      object_ = solver_->objects();
+      ownObjects_ = false;
     }
     branchingMethod_->chooseMethod()->setSolver(solver_);
@@ -2196 +2216 @@
     if (originalObject) {
       int iColumn;
+      assert (ownObjects_);
       for (iColumn=0;iColumn<numberObjects_;iColumn++) 
         delete object_[iColumn];
@@ -2353 +2374 @@
   numberObjects_(0),
   object_(NULL),
+  ownObjects_(true),
   originalColumns_(NULL),
   howOftenGlobalScan_(1),
@@ -2481 +2503 @@
   numberObjects_(0),
   object_(NULL),
+  ownObjects_(true),
   originalColumns_(NULL),
   howOftenGlobalScan_(1),
@@ -2767 +2790 @@
   else
   { eventHandler_ = NULL ; }
-  numberObjects_=rhs.numberObjects_;
-  if (numberObjects_) {
-    object_ = new OsiObject * [numberObjects_];
-    int i;
-    for (i=0;i<numberObjects_;i++) 
-      object_[i]=(rhs.object_[i])->clone();
+  ownObjects_ = rhs.ownObjects_;
+  if (ownObjects_) {
+    numberObjects_=rhs.numberObjects_;
+    if (numberObjects_) {
+      object_ = new OsiObject * [numberObjects_];
+      int i;
+      for (i=0;i<numberObjects_;i++) 
+        object_[i]=(rhs.object_[i])->clone();
+    } else {
+      object_=NULL;
+    }
   } else {
+    // assume will be redone
+    numberObjects_=0;
     object_=NULL;
   }
@@ -3047 +3077 @@
     else
     { eventHandler_ = NULL ; }
-    for (i=0;i<numberObjects_;i++)
-      delete object_[i];
-    delete [] object_;
-    numberObjects_=rhs.numberObjects_;
-    if (numberObjects_) {
-      object_ = new OsiObject * [numberObjects_];
-      int i;
-      for (i=0;i<numberObjects_;i++) 
-        object_[i]=(rhs.object_[i])->clone();
+    if (ownObjects_) {
+      for (i=0;i<numberObjects_;i++)
+        delete object_[i];
+      delete [] object_;
+      numberObjects_=rhs.numberObjects_;
+      if (numberObjects_) {
+        object_ = new OsiObject * [numberObjects_];
+        int i;
+        for (i=0;i<numberObjects_;i++) 
+          object_[i]=(rhs.object_[i])->clone();
+      } else {
+        object_=NULL;
+    }
     } else {
+      // assume will be redone
+      numberObjects_=0;
       object_=NULL;
     }
@@ -3185 +3221 @@
   integerVariable_=NULL;
   int i;
-  for (i=0;i<numberObjects_;i++)
-    delete object_[i];
-  delete [] object_;
+  if (ownObjects_) {
+    for (i=0;i<numberObjects_;i++)
+      delete object_[i];
+    delete [] object_;
+  }
+  ownObjects_=true;
   object_=NULL;
   numberIntegers_=0;
@@ -3859 +3898 @@
     objectiveValue= node->objectiveValue();
   int returnCode = resolve(node ? node->nodeInfo() : NULL,1);
+#ifdef COIN_DEVELOP
+  //if (!solver_->getIterationCount()&&solver_->isProvenOptimal())
+  //printf("zero iterations on first solve of branch\n");
+#endif
   if (node&&!node->nodeInfo()->numberBranchesLeft())
     node->nodeInfo()->allBranchesGone(); // can clean up
@@ -5213 +5256 @@
     }
   } 
-  if (!feasible&& continuousObjective_ <-1.0e30) {
+  if (false&&!feasible&& continuousObjective_ <-1.0e30) {
     // at root node - double double check
     bool saveTakeHint;
@@ -5227 +5270 @@
     }
   }
+  if (feasible&&!solverCharacteristics_->solutionAddsCuts()) {
+    //double increment = getDblParam(CbcModel::CbcCutoffIncrement) ;
+    double cutoff ;
+    solver_->getDblParam(OsiDualObjectiveLimit,cutoff) ;
+    double distance = fabs(cutoff-solver_->getObjValue());
+    if (distance<10.0*trueIncrement) {
+      double offset;
+      solver_->getDblParam(OsiObjOffset,offset);
+      double objFixedValue = -offset;
+      double objValue=0.0;
+      double direction = solver_->getObjSense();
+      const double * solution = solver_->getColSolution();
+      const double * objective = solver_->getObjCoefficients();
+      const double * columnLower = solver_->getColLower();
+      const double * columnUpper = solver_->getColUpper();
+      int numberColumns = solver_->getNumCols();
+      int increment = 0 ;
+      double multiplier = 1.0/trueIncrement;
+      int bigIntegers = 0; // Count of large costs which are integer
+      for (int iColumn=0;iColumn<numberColumns;iColumn++) {
+        double value = solution[iColumn];
+        // make sure clean
+        value = CoinMin(value,columnUpper[iColumn]);
+        value = CoinMax(value,columnLower[iColumn]);
+        double cost = direction * objective[iColumn];
+        if (cost) {
+          if (columnLower[iColumn]<columnUpper[iColumn]) {
+            objValue += value*cost;
+            value = fabs(cost)*multiplier ;
+            if (value <2.1e9) {
+              int nearest = (int) floor(value+0.5) ;
+              assert (fabs(value-floor(value+0.5)) < 1.0e-8);
+              if (!increment) 
+                increment = nearest ; 
+              else
+                increment = gcd(increment,nearest) ;
+            } else {
+              // large value - may still be multiple of 1.0
+              value = fabs(objective[iColumn]);
+              assert(fabs(value-floor(value+0.5)) < 1.0e-8);
+              bigIntegers++;
+            }
+          } else {
+            // fixed
+            objFixedValue += value*cost;
+          }
+        }
+      }
+      if (increment) {
+        double value = increment ;
+        value /= multiplier ;
+        if (value>trueIncrement) {
+          double x = objValue/value;
+          x = ceil(x-1.0e-5);
+          x *= value;
+          //printf("fixed %g, variable %g -> %g, sum %g - cutoff %g\n",
+          // objFixedValue,objValue,x,x+objFixedValue,cutoff);
+          x += objFixedValue;
+          if (x>cutoff + 1.0e-5*fabs(cutoff)+1.0e-5) {
+            //printf("Node cutoff\n");
+            feasible=false;
+          }
+        } else {
+          value = trueIncrement;
+          double x = objValue/value;
+          x = ceil(x-1.0e-5);
+          x *= value;
+          x += objFixedValue;
+          if (x>cutoff + 1.0e-5*fabs(cutoff)+1.0e-5) {
+            //printf("Node cutoff\n");
+            feasible=false;
+          }
+        }
+      }
+    }
+  }
+
   setPointers(solver_);
   int returnStatus = feasible ? 1 : 0;
@@ -5504 +5624 @@
     delete [] element;
     newModel->addObjects(numberCliques,object);
+    assert (ownObjects_);
     for (;i<numberCliques;i++) 
       delete object[i];
@@ -5510 +5631 @@
     return newModel;
   } else {
+    assert (ownObjects_);
     if (numberCliques>0) {
       addObjects(numberCliques,object);
@@ -5651 +5773 @@
 CbcModel::deleteObjects(bool getIntegers)
 {
-  int i;
-  for (i=0;i<numberObjects_;i++)
-    delete object_[i];
-  delete [] object_;
+  if (ownObjects_) {
+    int i;
+    for (i=0;i<numberObjects_;i++)
+      delete object_[i];
+    delete [] object_;
+  }
   object_ = NULL;
   numberObjects_=0;
-  if (getIntegers)
+  if (getIntegers&&ownObjects_)
     findIntegers(true);
 }
@@ -5943 +6067 @@
   }
   delete [] mark;
+  assert (ownObjects_);
   delete [] object_;
   object_ = temp;
@@ -6056 +6181 @@
   }
   delete [] mark;
+  assert (ownObjects_);
   delete [] object_;
   object_ = temp;
@@ -7097 +7223 @@
                                    bool weak)
 {
+  printf("DEPRECATED\n");
   status_ = 0;
   // solve LP
@@ -7222 +7349 @@
               double value = fabs(objective[iColumn])*multiplier;
               int nearest = (int) floor(value+0.5);
-              if (fabs(value-floor(value+0.5))>1.0e-8) {
+              if (fabs(value-floor(value+0.5))>1.0e-8||value>2.1e9) {
                 increment=0;
                 break; // no good

branches/devel/Cbc/src/CbcModel.hpp

@@ -1357 +1357 @@
   inline bool normalSolver() const
   { return (specialOptions_&16)==0;};
+  /// Now we may not own objects - just point to solver's objects
+  inline bool ownObjects() const
+  { return ownObjects_;};
   //@}
   //---------------------------------------------------------------------------
@@ -1828 +1831 @@
   */
   OsiObject ** object_;
-
+  /// Now we may not own objects - just point to solver's objects
+  bool ownObjects_;
   
   /// Original columns as created by integerPresolve

branches/devel/Cbc/src/CbcNode.cpp

@@ -624 +624 @@
   for (i=0;i<numberChangedBounds_;i++) {
     int variable = variables_[i];
+    int k = variable&0x7fffffff;
     if ((variable&0x80000000)==0) {
       // lower bound changing
-      solver->setColLower(variable,newBounds_[i]);
+#ifndef NDEBUG
+      double oldValue = solver->getColLower()[k];
+      assert (newBounds_[i]>oldValue-1.0e-8);
+      if (newBounds_[i]<oldValue+1.0e-8)
+        printf("bad null lower change for column %d - bound %g\n",k,oldValue);
+#endif
+      solver->setColLower(k,newBounds_[i]);
     } else {
       // upper bound changing
-      solver->setColUpper(variable&0x7fffffff,newBounds_[i]);
+#ifndef NDEBUG
+      double oldValue = solver->getColUpper()[k];
+      assert (newBounds_[i]<oldValue+1.0e-8);
+      if (newBounds_[i]>oldValue-1.0e-8)
+        printf("bad null upper change for column %d - bound %g\n",k,oldValue);
+#endif
+      solver->setColUpper(k,newBounds_[i]);
     }
   }
@@ -3167 +3180 @@
                   dynamic_cast <CbcBranchingObject *>(branch_) ;
                 assert (branchObj);
-                branchObj->way(preferredWay);
+                //branchObj->way(preferredWay);
+                branchObj->way(betterWay);
               }
               if (couldChooseFirst)

branches/devel/Cbc/src/CbcNode.hpp

@@ -8 +8 @@
 
 #include "CoinWarmStartBasis.hpp"
+#include "CoinSearchTree.hpp"
 #include "CbcBranchBase.hpp"
 
@@ -388 +389 @@
 */
 
-class CbcNode  {
+class CbcNode : public CoinTreeNode {
  
 public:

branches/devel/Cbc/src/CbcStrategy.cpp

@@ -285 +285 @@
     model.solver()->messageHandler()->setLogLevel(0);
   } else {
-    model.messageHandler()->setLogLevel(2);
-    model.solver()->messageHandler()->setLogLevel(1);
-    model.setPrintFrequency(50);
+    model.messageHandler()->setLogLevel(CoinMax(2,model.messageHandler()->logLevel()));
+    model.solver()->messageHandler()->setLogLevel(CoinMax(1,model.solver()->messageHandler()->logLevel()));
+    model.setPrintFrequency(CoinMin(50,model.printFrequency()));
   }
 }

branches/devel/Cbc/src/CbcTree.hpp

@@ -96 +96 @@
 
 };
+
+/// New style
+#include "CoinSearchTree.hpp"
+/*! \class tree
+    \brief Implementation of live set as a heap.
+
+    This class is used to hold the set of live nodes in the search tree.
+*/
+
+class CbcNewTree : public CbcTree, public CoinSearchTreeManager {
+
+public:
+
+  // Default Constructor 
+  CbcNewTree ();
+
+  // Copy constructor 
+  CbcNewTree ( const CbcNewTree & rhs);
+  // = operator
+  CbcNewTree & operator=(const CbcNewTree & rhs);
+   
+  virtual ~CbcNewTree();
+
+  /// Clone
+  virtual CbcNewTree * clone() const;
+  /// Create C++ lines to get to current state
+  virtual void generateCpp( FILE * fp) {};
+
+/*! \name Heap access and maintenance methods */
+//@{
+
+  /// Set comparison function and resort heap
+  void setComparison(CbcCompareBase  &compare);
+
+  /// Return the top node of the heap 
+  virtual CbcNode * top() const;
+
+  /// Add a node to the heap
+  virtual void push(CbcNode * x);
+
+  /// Remove the top node from the heap
+  virtual void pop() ;
+  /// Gets best node and takes off heap
+  virtual CbcNode * bestNode(double cutoff);
+
+//@}
+/*! \name vector methods */
+//@{
+
+  /// Test if empty *** note may be overridden
+  virtual bool empty() ;
+
+  /// Return size
+  inline int size() const
+  { return nodes_.size();}
+
+  /// [] operator
+  inline CbcNode * operator [] (int i) const
+  { return nodes_[i];}
+
+  /// Return a node pointer
+  inline CbcNode * nodePointer (int i) const
+  { return nodes_[i];}
+
+//@}
+
+/*! \name Search tree maintenance */
+//@{
+
+/*! \brief Prune the tree using an objective function cutoff
+
+  This routine removes all nodes with objective worst than the
+  specified cutoff value.
+  It also sets bestPossibleObjective to best
+  of all on tree before deleting.
+*/
+
+  void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
+
+  /// Get best on list using alternate method
+  CbcNode * bestAlternate();
+
+  /// We may have got an intelligent tree so give it one more chance
+  virtual void endSearch() {}
+//@}
+protected:
+
+
+};
 #endif
 

branches/devel/Cbc/src/CoinSolve.cpp

@@ -475 +475 @@
 {
 #ifdef COIN_DEVELOP
+  if (!babModel->ownObjects())
+    return;
   //const double *objective = solver->getObjCoefficients() ;
   const double *columnLower = solver->getColLower() ;