00001
00002
00003 #ifndef CbcNode_H
00004 #define CbcNode_H
00005
00006 #include <string>
00007 #include <vector>
00008
00009 #include "CoinWarmStartBasis.hpp"
00010 #include "CoinSearchTree.hpp"
00011 #include "CbcBranchBase.hpp"
00012
00013 class OsiSolverInterface;
00014 class OsiSolverBranch;
00015
00016 class OsiCuts;
00017 class OsiRowCut;
00018 class OsiRowCutDebugger;
00019 class CoinWarmStartBasis;
00020 class CbcCountRowCut;
00021 class CbcModel;
00022 class CbcNode;
00023 class CbcSubProblem;
00024 class CbcGeneralBranchingObject;
00025
00026
00063 class CbcNodeInfo {
00064
00065 public:
00066
00073 CbcNodeInfo ();
00074
00076 CbcNodeInfo ( const CbcNodeInfo &);
00077
00078 #if 0
00079
00084 CbcNodeInfo (CbcNodeInfo * parent);
00085 #endif
00086
00091 CbcNodeInfo (CbcNodeInfo * parent, CbcNode * owner);
00092
00098 virtual ~CbcNodeInfo();
00100
00101
00107 virtual void applyToModel (CbcModel *model, CoinWarmStartBasis *&basis,
00108 CbcCountRowCut **addCuts,
00109 int ¤tNumberCuts) const = 0 ;
00111 virtual int applyBounds(int iColumn, double & lower, double & upper,int force) = 0;
00112
00117 virtual CbcNodeInfo * buildRowBasis(CoinWarmStartBasis & basis) const = 0;
00119 virtual CbcNodeInfo * clone() const = 0;
00121 virtual void allBranchesGone() {}
00122 #if 1
00124 inline void increment(int amount=1)
00125 {numberPointingToThis_+=amount;}
00126
00128 inline int decrement(int amount=1)
00129 {numberPointingToThis_-=amount;return numberPointingToThis_;}
00130 #else
00132 void increment(int amount=1);
00134 int decrement(int amount=1);
00135 #endif
00136
00141 inline void initializeInfo(int number)
00142 {numberPointingToThis_=number;numberBranchesLeft_=number;}
00143
00145 inline int numberBranchesLeft() const
00146 {return numberBranchesLeft_;}
00147
00149 inline void setNumberBranchesLeft(int value)
00150 {numberBranchesLeft_ = value;}
00151
00153 inline int numberPointingToThis() const
00154 {return numberPointingToThis_;}
00155
00157 inline void setNumberPointingToThis(int number)
00158 {numberPointingToThis_=number;}
00159
00161 inline void incrementNumberPointingToThis()
00162 {numberPointingToThis_ ++;}
00163
00165 inline int branchedOn()
00166 {numberPointingToThis_--;numberBranchesLeft_--;return numberBranchesLeft_;}
00167
00169 inline void throwAway()
00170 {numberPointingToThis_-=numberBranchesLeft_;numberBranchesLeft_=0;}
00171
00173 CbcNodeInfo * parent() const
00174 {return parent_;}
00176 inline void nullParent()
00177 { parent_=NULL;}
00178
00179 void addCuts(OsiCuts & cuts,int numberToBranch, int * whichGenerator
00180 ,int numberPointingToThis);
00181 void addCuts(int numberCuts, CbcCountRowCut ** cuts,int numberToBranch);
00185 void deleteCuts(int numberToDelete,CbcCountRowCut ** cuts);
00186 void deleteCuts(int numberToDelete,int * which);
00187
00189 void deleteCut(int whichOne);
00190
00192 void decrementCuts(int change=1);
00193
00195 void incrementCuts(int change=1);
00196
00198 void decrementParentCuts(CbcModel * model, int change=1);
00199
00201 void incrementParentCuts(CbcModel * model, int change=1);
00202
00204 inline CbcCountRowCut ** cuts() const
00205 {return cuts_;}
00206
00208 inline int numberCuts() const
00209 {return numberCuts_;}
00210 inline void setNumberCuts(int value)
00211 {numberCuts_=value;}
00212
00214 inline void nullOwner()
00215 { owner_=NULL;}
00216 const inline CbcNode * owner() const
00217 { return owner_;}
00218 inline CbcNode * mutableOwner() const
00219 { return owner_;}
00221 inline int nodeNumber() const
00222 { return nodeNumber_;}
00223 inline void setNodeNumber(int node)
00224 { nodeNumber_=node;}
00230 void deactivate(int mode=3);
00232 inline bool allActivated() const
00233 { return (active_==7);}
00235 inline bool marked() const
00236 { return ((active_&8)!=0);}
00238 inline void mark()
00239 { active_ |= 8;}
00241 inline void unmark()
00242 { active_ &= ~8;}
00243
00245 inline const OsiBranchingObject * parentBranch() const
00246 { return parentBranch_;}
00248 void unsetParentBasedData();
00249 protected:
00250
00258 int numberPointingToThis_;
00259
00261 CbcNodeInfo * parent_;
00262
00264 OsiBranchingObject * parentBranch_;
00265
00267 CbcNode * owner_;
00268
00270 int numberCuts_;
00271
00273 int nodeNumber_;
00274
00276 CbcCountRowCut ** cuts_;
00277
00280 int numberRows_;
00281
00288 int numberBranchesLeft_;
00294 int active_;
00295
00296 private:
00297
00299 CbcNodeInfo & operator=(const CbcNodeInfo& rhs);
00300
00302 void setParentBasedData();
00303 };
00304
00316 class CbcFullNodeInfo : public CbcNodeInfo {
00317
00318 public:
00319
00329 virtual void applyToModel (CbcModel *model, CoinWarmStartBasis *&basis,
00330 CbcCountRowCut **addCuts,
00331 int ¤tNumberCuts) const ;
00332
00334 virtual int applyBounds(int iColumn, double & lower, double & upper,int force) ;
00335
00340 virtual CbcNodeInfo * buildRowBasis(CoinWarmStartBasis & basis) const ;
00341
00342 CbcFullNodeInfo ();
00343
00346 CbcFullNodeInfo (CbcModel * model,
00347 int numberRowsAtContinuous);
00348
00349
00350 CbcFullNodeInfo ( const CbcFullNodeInfo &);
00351
00352
00353 ~CbcFullNodeInfo ();
00354
00356 virtual CbcNodeInfo * clone() const;
00358 inline const double * lower() const
00359 { return lower_;}
00361 inline const double * upper() const
00362 { return upper_;}
00363 protected:
00364
00370 CoinWarmStartBasis *basis_;
00371 int numberIntegers_;
00372
00373 double * lower_;
00374 double * upper_;
00375 private:
00377 CbcFullNodeInfo & operator=(const CbcFullNodeInfo& rhs);
00378 };
00379
00380
00381
00390 class CbcPartialNodeInfo : public CbcNodeInfo {
00391
00392 public:
00393
00399 virtual void applyToModel (CbcModel *model, CoinWarmStartBasis *&basis,
00400 CbcCountRowCut **addCuts,
00401 int ¤tNumberCuts) const ;
00402
00404 virtual int applyBounds(int iColumn, double & lower, double & upper,int force) ;
00409 virtual CbcNodeInfo * buildRowBasis(CoinWarmStartBasis & basis ) const ;
00410
00411 CbcPartialNodeInfo ();
00412
00413
00414 CbcPartialNodeInfo (CbcNodeInfo * parent, CbcNode * owner,
00415 int numberChangedBounds,const int * variables,
00416 const double * boundChanges,
00417 const CoinWarmStartDiff *basisDiff) ;
00418
00419
00420 CbcPartialNodeInfo ( const CbcPartialNodeInfo &);
00421
00422
00423 ~CbcPartialNodeInfo ();
00424
00426 virtual CbcNodeInfo * clone() const;
00428 inline const CoinWarmStartDiff *basisDiff() const
00429 { return basisDiff_ ;}
00431 inline const int * variables() const
00432 { return variables_;}
00433
00434 inline const double * newBounds() const
00435 { return newBounds_;}
00437 inline int numberChangedBounds() const
00438 { return numberChangedBounds_;}
00439 protected:
00440
00441
00443 CoinWarmStartDiff *basisDiff_ ;
00445 int * variables_;
00446
00447 double * newBounds_;
00449 int numberChangedBounds_;
00450 private:
00451
00453 CbcPartialNodeInfo & operator=(const CbcPartialNodeInfo& rhs);
00454 };
00455
00456
00474 class CbcNode : public CoinTreeNode {
00475
00476 public:
00477
00479 CbcNode ();
00480
00482 CbcNode (CbcModel * model, CbcNode * lastNode);
00483
00485 CbcNode (const CbcNode &);
00486
00488 CbcNode & operator= (const CbcNode& rhs);
00489
00491 ~CbcNode ();
00492
00508 void
00509 createInfo(CbcModel * model,
00510 CbcNode * lastNode,
00511 const CoinWarmStartBasis *lastws,
00512 const double * lastLower, const double * lastUpper,
00513 int numberOldActiveCuts,int numberNewCuts);
00514
00535 int chooseBranch (CbcModel * model,
00536 CbcNode * lastNode,
00537 int numberPassesLeft);
00563 int chooseDynamicBranch (CbcModel * model,
00564 CbcNode * lastNode,
00565 OsiSolverBranch * & branches,
00566 int numberPassesLeft);
00593 int chooseOsiBranch (CbcModel * model,
00594 CbcNode * lastNode,
00595 OsiBranchingInformation * usefulInfo,
00596 int branchState);
00612 int chooseClpBranch (CbcModel * model,
00613 CbcNode * lastNode);
00614 int analyze(CbcModel * model,double * results);
00616 void decrementCuts(int change=1);
00617
00619 void decrementParentCuts(CbcModel * model, int change=1);
00620
00622 void nullNodeInfo();
00631 void initializeInfo();
00632
00634 int branch(OsiSolverInterface * solver);
00635
00639 double checkIsCutoff(double cutoff);
00640
00641 inline CbcNodeInfo * nodeInfo() const
00642 {return nodeInfo_;}
00643
00644
00645 inline double objectiveValue() const
00646 { return objectiveValue_;}
00647 inline void setObjectiveValue(double value)
00648 { objectiveValue_=value;}
00650 inline int numberBranches() const
00651 { if (branch_)
00652 return (branch_->numberBranches()) ;
00653 else
00654 return (-1) ; }
00655
00656
00657
00658
00659
00660
00661
00662 int way() const;
00664 inline int depth() const
00665 {return depth_;}
00667 inline void setDepth(int value)
00668 {depth_ = value;}
00670 inline int numberUnsatisfied() const
00671 { return numberUnsatisfied_;}
00673 inline void setNumberUnsatisfied(int value)
00674 { numberUnsatisfied_ = value;}
00676 inline double sumInfeasibilities() const
00677 { return sumInfeasibilities_;}
00679 inline void setSumInfeasibilities(double value)
00680 { sumInfeasibilities_ = value;}
00681
00682 inline double guessedObjectiveValue() const
00683 {return guessedObjectiveValue_;}
00684 inline void setGuessedObjectiveValue(double value)
00685 {guessedObjectiveValue_=value;}
00687 inline const OsiBranchingObject * branchingObject() const
00688 { return branch_;}
00690 inline OsiBranchingObject * modifiableBranchingObject() const
00691 { return branch_;}
00693 inline void setBranchingObject(OsiBranchingObject * branchingObject)
00694 { branch_ = branchingObject;}
00696 inline int nodeNumber() const
00697 { return nodeNumber_;}
00698 inline void setNodeNumber(int node)
00699 { nodeNumber_=node;}
00701 inline bool onTree() const
00702 { return (state_&1)!=0;}
00704 inline void setOnTree(bool yesNo)
00705 { if(yesNo) state_ |= 1; else state_ &= ~1; }
00707 inline bool active() const
00708 { return (state_&2)!=0;}
00710 inline void setActive(bool yesNo)
00711 { if(yesNo) state_ |= 2; else state_ &= ~2; }
00713 void print() const;
00715 inline void checkInfo() const
00716 { assert (nodeInfo_->numberBranchesLeft()==
00717 branch_->numberBranchesLeft());}
00718
00719 private:
00720
00722 CbcNodeInfo * nodeInfo_;
00724 double objectiveValue_;
00726 double guessedObjectiveValue_;
00728 double sumInfeasibilities_;
00730 OsiBranchingObject * branch_;
00732 int depth_;
00734 int numberUnsatisfied_;
00736 int nodeNumber_;
00741 int state_;
00742 };
00743
00744
00745 #endif