00001
00002
00003
00004 #ifndef CbcNode_H
00005 #define CbcNode_H
00006
00007 #include <string>
00008 #include <vector>
00009
00010 #include "CoinWarmStartBasis.hpp"
00011 #include "CoinSearchTree.hpp"
00012 #include "CbcBranchBase.hpp"
00013
00014 class OsiSolverInterface;
00015 class OsiSolverBranch;
00016
00017 class OsiCuts;
00018 class OsiRowCut;
00019 class OsiRowCutDebugger;
00020 class CoinWarmStartBasis;
00021 class CbcCountRowCut;
00022 class CbcModel;
00023 class CbcNode;
00024 class CbcSubProblem;
00025 class CbcGeneralBranchingObject;
00026
00027
00064 class CbcNodeInfo {
00065
00066 public:
00067
00074 CbcNodeInfo ();
00075
00077 CbcNodeInfo ( const CbcNodeInfo &);
00078
00079 #if 0
00080
00085 CbcNodeInfo (CbcNodeInfo * parent);
00086 #endif
00087
00092 CbcNodeInfo (CbcNodeInfo * parent, CbcNode * owner);
00093
00099 virtual ~CbcNodeInfo();
00101
00102
00108 virtual void applyToModel (CbcModel *model, CoinWarmStartBasis *&basis,
00109 CbcCountRowCut **addCuts,
00110 int ¤tNumberCuts) const = 0 ;
00112 virtual int applyBounds(int iColumn, double & lower, double & upper,int force) = 0;
00113
00118 virtual CbcNodeInfo * buildRowBasis(CoinWarmStartBasis & basis) const = 0;
00120 virtual CbcNodeInfo * clone() const = 0;
00122 virtual void allBranchesGone() {}
00123 #if 1
00124
00125 inline void increment(int amount=1)
00126 {numberPointingToThis_+=amount;}
00127
00129 inline int decrement(int amount=1)
00130 {numberPointingToThis_-=amount;return numberPointingToThis_;}
00131 #else
00132
00133 void increment(int amount=1);
00135 int decrement(int amount=1);
00136 #endif
00137
00142 inline void initializeInfo(int number)
00143 {numberPointingToThis_=number;numberBranchesLeft_=number;}
00144
00146 inline int numberBranchesLeft() const
00147 {return numberBranchesLeft_;}
00148
00150 inline void setNumberBranchesLeft(int value)
00151 {numberBranchesLeft_ = value;}
00152
00154 inline int numberPointingToThis() const
00155 {return numberPointingToThis_;}
00156
00158 inline void setNumberPointingToThis(int number)
00159 {numberPointingToThis_=number;}
00160
00162 inline void incrementNumberPointingToThis()
00163 {numberPointingToThis_ ++;}
00164
00166 inline int branchedOn()
00167 {numberPointingToThis_--;numberBranchesLeft_--;return numberBranchesLeft_;}
00168
00170 inline void throwAway()
00171 {numberPointingToThis_-=numberBranchesLeft_;numberBranchesLeft_=0;}
00172
00174 CbcNodeInfo * parent() const
00175 {return parent_;}
00177 inline void nullParent()
00178 { parent_=NULL;}
00179
00180 void addCuts(OsiCuts & cuts,int numberToBranch,
00181 int numberPointingToThis);
00182 void addCuts(int numberCuts, CbcCountRowCut ** cuts,int numberToBranch);
00186 void deleteCuts(int numberToDelete,CbcCountRowCut ** cuts);
00187 void deleteCuts(int numberToDelete,int * which);
00188
00190 void deleteCut(int whichOne);
00191
00193 void decrementCuts(int change=1);
00194
00196 void incrementCuts(int change=1);
00197
00199 void decrementParentCuts(CbcModel * model, int change=1);
00200
00202 void incrementParentCuts(CbcModel * model, int change=1);
00203
00205 inline CbcCountRowCut ** cuts() const
00206 {return cuts_;}
00207
00209 inline int numberCuts() const
00210 {return numberCuts_;}
00211 inline void setNumberCuts(int value)
00212 {numberCuts_=value;}
00213
00215 inline void nullOwner()
00216 { owner_=NULL;}
00217 const inline CbcNode * owner() const
00218 { return owner_;}
00219 inline CbcNode * mutableOwner() const
00220 { return owner_;}
00222 inline int nodeNumber() const
00223 { return nodeNumber_;}
00224 inline void setNodeNumber(int node)
00225 { nodeNumber_=node;}
00231 void deactivate(int mode=3);
00233 inline bool allActivated() const
00234 { return (active_==7);}
00236 inline bool marked() const
00237 { return ((active_&8)!=0);}
00239 inline void mark()
00240 { active_ |= 8;}
00242 inline void unmark()
00243 { active_ &= ~8;}
00244
00246 inline const OsiBranchingObject * parentBranch() const
00247 { return parentBranch_;}
00249 void unsetParentBasedData();
00250 protected:
00251
00259 int numberPointingToThis_;
00260
00262 CbcNodeInfo * parent_;
00263
00265 OsiBranchingObject * parentBranch_;
00266
00268 CbcNode * owner_;
00269
00271 int numberCuts_;
00272
00274 int nodeNumber_;
00275
00277 CbcCountRowCut ** cuts_;
00278
00281 int numberRows_;
00282
00289 int numberBranchesLeft_;
00295 int active_;
00296
00297 private:
00298
00300 CbcNodeInfo & operator=(const CbcNodeInfo& rhs);
00301
00303 void setParentBasedData();
00304 };
00305
00317 class CbcFullNodeInfo : public CbcNodeInfo {
00318
00319 public:
00320
00330 virtual void applyToModel (CbcModel *model, CoinWarmStartBasis *&basis,
00331 CbcCountRowCut **addCuts,
00332 int ¤tNumberCuts) const ;
00333
00335 virtual int applyBounds(int iColumn, double & lower, double & upper,int force) ;
00336
00341 virtual CbcNodeInfo * buildRowBasis(CoinWarmStartBasis & basis) const ;
00342
00343 CbcFullNodeInfo ();
00344
00347 CbcFullNodeInfo (CbcModel * model,
00348 int numberRowsAtContinuous);
00349
00350
00351 CbcFullNodeInfo ( const CbcFullNodeInfo &);
00352
00353
00354 ~CbcFullNodeInfo ();
00355
00357 virtual CbcNodeInfo * clone() const;
00359 inline const double * lower() const
00360 { return lower_;}
00362 inline const double * upper() const
00363 { return upper_;}
00364 protected:
00365
00371 CoinWarmStartBasis *basis_;
00372 int numberIntegers_;
00373
00374 double * lower_;
00375 double * upper_;
00376 private:
00378 CbcFullNodeInfo & operator=(const CbcFullNodeInfo& rhs);
00379 };
00380
00381
00382
00391 class CbcPartialNodeInfo : public CbcNodeInfo {
00392
00393 public:
00394
00400 virtual void applyToModel (CbcModel *model, CoinWarmStartBasis *&basis,
00401 CbcCountRowCut **addCuts,
00402 int ¤tNumberCuts) const ;
00403
00405 virtual int applyBounds(int iColumn, double & lower, double & upper,int force) ;
00410 virtual CbcNodeInfo * buildRowBasis(CoinWarmStartBasis & basis ) const ;
00411
00412 CbcPartialNodeInfo ();
00413
00414
00415 CbcPartialNodeInfo (CbcNodeInfo * parent, CbcNode * owner,
00416 int numberChangedBounds,const int * variables,
00417 const double * boundChanges,
00418 const CoinWarmStartDiff *basisDiff) ;
00419
00420
00421 CbcPartialNodeInfo ( const CbcPartialNodeInfo &);
00422
00423
00424 ~CbcPartialNodeInfo ();
00425
00427 virtual CbcNodeInfo * clone() const;
00429 inline const CoinWarmStartDiff *basisDiff() const
00430 { return basisDiff_ ;}
00432 inline const int * variables() const
00433 { return variables_;}
00434
00435 inline const double * newBounds() const
00436 { return newBounds_;}
00438 inline int numberChangedBounds() const
00439 { return numberChangedBounds_;}
00440 protected:
00441
00442
00444 CoinWarmStartDiff *basisDiff_ ;
00446 int * variables_;
00447
00448 double * newBounds_;
00450 int numberChangedBounds_;
00451 private:
00452
00454 CbcPartialNodeInfo & operator=(const CbcPartialNodeInfo& rhs);
00455 };
00456
00457
00475 class CbcNode : public CoinTreeNode {
00476
00477 public:
00478
00480 CbcNode ();
00481
00483 CbcNode (CbcModel * model, CbcNode * lastNode);
00484
00486 CbcNode (const CbcNode &);
00487
00489 CbcNode & operator= (const CbcNode& rhs);
00490
00492 ~CbcNode ();
00493
00509 void
00510 createInfo(CbcModel * model,
00511 CbcNode * lastNode,
00512 const CoinWarmStartBasis *lastws,
00513 const double * lastLower, const double * lastUpper,
00514 int numberOldActiveCuts,int numberNewCuts);
00515
00536 int chooseBranch (CbcModel * model,
00537 CbcNode * lastNode,
00538 int numberPassesLeft);
00564 int chooseDynamicBranch (CbcModel * model,
00565 CbcNode * lastNode,
00566 OsiSolverBranch * & branches,
00567 int numberPassesLeft);
00594 int chooseOsiBranch (CbcModel * model,
00595 CbcNode * lastNode,
00596 OsiBranchingInformation * usefulInfo,
00597 int branchState);
00613 int chooseClpBranch (CbcModel * model,
00614 CbcNode * lastNode);
00615 int analyze(CbcModel * model,double * results);
00617 void decrementCuts(int change=1);
00618
00620 void decrementParentCuts(CbcModel * model, int change=1);
00621
00623 void nullNodeInfo();
00632 void initializeInfo();
00633
00635 int branch(OsiSolverInterface * solver);
00636
00640 double checkIsCutoff(double cutoff);
00641
00642 inline CbcNodeInfo * nodeInfo() const
00643 {return nodeInfo_;}
00644
00645
00646 inline double objectiveValue() const
00647 { return objectiveValue_;}
00648 inline void setObjectiveValue(double value)
00649 { objectiveValue_=value;}
00651 inline int numberBranches() const
00652 { if (branch_)
00653 return (branch_->numberBranches()) ;
00654 else
00655 return (-1) ; }
00656
00657
00658
00659
00660
00661
00662
00663 int way() const;
00665 inline int depth() const
00666 {return depth_;}
00668 inline void setDepth(int value)
00669 {depth_ = value;}
00671 inline int numberUnsatisfied() const
00672 { return numberUnsatisfied_;}
00674 inline void setNumberUnsatisfied(int value)
00675 { numberUnsatisfied_ = value;}
00677 inline double sumInfeasibilities() const
00678 { return sumInfeasibilities_;}
00680 inline void setSumInfeasibilities(double value)
00681 { sumInfeasibilities_ = value;}
00682
00683 inline double guessedObjectiveValue() const
00684 {return guessedObjectiveValue_;}
00685 inline void setGuessedObjectiveValue(double value)
00686 {guessedObjectiveValue_=value;}
00688 inline const OsiBranchingObject * branchingObject() const
00689 { return branch_;}
00691 inline OsiBranchingObject * modifiableBranchingObject() const
00692 { return branch_;}
00694 inline void setBranchingObject(OsiBranchingObject * branchingObject)
00695 { branch_ = branchingObject;}
00697 inline int nodeNumber() const
00698 { return nodeNumber_;}
00699 inline void setNodeNumber(int node)
00700 { nodeNumber_=node;}
00702 inline bool onTree() const
00703 { return (state_&1)!=0;}
00705 inline void setOnTree(bool yesNo)
00706 { if(yesNo) state_ |= 1; else state_ &= ~1; }
00708 inline bool active() const
00709 { return (state_&2)!=0;}
00711 inline void setActive(bool yesNo)
00712 { if(yesNo) state_ |= 2; else state_ &= ~2; }
00714 void print() const;
00716 inline void checkInfo() const
00717 { assert (nodeInfo_->numberBranchesLeft()==
00718 branch_->numberBranchesLeft());}
00719
00720 private:
00721
00723 CbcNodeInfo * nodeInfo_;
00725 double objectiveValue_;
00727 double guessedObjectiveValue_;
00729 double sumInfeasibilities_;
00731 OsiBranchingObject * branch_;
00733 int depth_;
00735 int numberUnsatisfied_;
00737 int nodeNumber_;
00742 int state_;
00743 };
00744
00745
00746 #endif