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
00024
00061 class CbcNodeInfo {
00062
00063 public:
00064
00071 CbcNodeInfo ();
00072
00074 CbcNodeInfo ( const CbcNodeInfo &);
00075
00076 #if 0
00077
00082 CbcNodeInfo (CbcNodeInfo * parent);
00083 #endif
00084
00089 CbcNodeInfo (CbcNodeInfo * parent, CbcNode * owner);
00090
00096 virtual ~CbcNodeInfo();
00098
00099
00105 virtual void applyToModel (CbcModel *model, CoinWarmStartBasis *&basis,
00106 CbcCountRowCut **addCuts,
00107 int ¤tNumberCuts) const = 0 ;
00109 virtual int applyBounds(int iColumn, double & lower, double & upper,int force) = 0;
00110
00115 virtual CbcNodeInfo * buildRowBasis(CoinWarmStartBasis & basis) const = 0;
00117 virtual CbcNodeInfo * clone() const = 0;
00119 virtual void allBranchesGone() {}
00120 #if 1
00122 inline void increment(int amount=1)
00123 {numberPointingToThis_+=amount;}
00124
00126 inline int decrement(int amount=1)
00127 {numberPointingToThis_-=amount;return numberPointingToThis_;}
00128 #else
00130 void increment(int amount=1);
00132 int decrement(int amount=1);
00133 #endif
00134
00139 inline void initializeInfo(int number)
00140 {numberPointingToThis_=number;numberBranchesLeft_=number;}
00141
00143 inline int numberBranchesLeft() const
00144 {return numberBranchesLeft_;}
00145
00147 inline int numberPointingToThis() const
00148 {return numberPointingToThis_;}
00149
00151 inline void setNumberPointingToThis(int number)
00152 {numberPointingToThis_=number;}
00153
00155 inline int branchedOn()
00156 {numberPointingToThis_--;numberBranchesLeft_--;return numberBranchesLeft_;}
00157
00159 inline void throwAway()
00160 {numberPointingToThis_-=numberBranchesLeft_;numberBranchesLeft_=0;}
00161
00163 CbcNodeInfo * parent() const
00164 {return parent_;}
00166 inline void nullParent()
00167 { parent_=NULL;}
00168
00169 void addCuts(OsiCuts & cuts,int numberToBranch, int * whichGenerator);
00170 void addCuts(int numberCuts, CbcCountRowCut ** cuts,int numberToBranch);
00174 void deleteCuts(int numberToDelete,CbcCountRowCut ** cuts);
00175 void deleteCuts(int numberToDelete,int * which);
00176
00178 void deleteCut(int whichOne);
00179
00181 void decrementCuts(int change=1);
00182
00184 void incrementCuts(int change=1);
00185
00187 void decrementParentCuts(CbcModel * model, int change=1);
00188
00190 void incrementParentCuts(CbcModel * model, int change=1);
00191
00193 inline CbcCountRowCut ** cuts() const
00194 {return cuts_;}
00195
00197 inline int numberCuts() const
00198 {return numberCuts_;}
00199 inline void setNumberCuts(int value)
00200 {numberCuts_=value;}
00201
00203 inline void nullOwner()
00204 { owner_=NULL;}
00205 const inline CbcNode * owner() const
00206 { return owner_;}
00207 inline CbcNode * mutableOwner() const
00208 { return owner_;}
00210 inline int nodeNumber() const
00211 { return nodeNumber_;}
00212 inline void setNodeNumber(int node)
00213 { nodeNumber_=node;}
00219 void deactivate(int mode=3);
00221 inline bool allActivated() const
00222 { return (active_==7);}
00224 inline bool marked() const
00225 { return ((active_&8)!=0);}
00227 inline void mark()
00228 { active_ |= 8;}
00230 inline void unmark()
00231 { active_ &= ~8;}
00232
00234 inline const OsiBranchingObject * parentBranch() const
00235 { return parentBranch_;}
00236 protected:
00237
00245 int numberPointingToThis_;
00246
00248 CbcNodeInfo * parent_;
00249
00251 OsiBranchingObject * parentBranch_;
00252
00254 CbcNode * owner_;
00255
00257 int numberCuts_;
00258
00260 int nodeNumber_;
00261
00263 CbcCountRowCut ** cuts_;
00264
00267 int numberRows_;
00268
00275 int numberBranchesLeft_;
00281 int active_;
00282
00283 private:
00284
00286 CbcNodeInfo & operator=(const CbcNodeInfo& rhs);
00287
00289 void setParentBasedData();
00290 };
00291
00303 class CbcFullNodeInfo : public CbcNodeInfo {
00304
00305 public:
00306
00316 virtual void applyToModel (CbcModel *model, CoinWarmStartBasis *&basis,
00317 CbcCountRowCut **addCuts,
00318 int ¤tNumberCuts) const ;
00319
00321 virtual int applyBounds(int iColumn, double & lower, double & upper,int force) ;
00322
00327 virtual CbcNodeInfo * buildRowBasis(CoinWarmStartBasis & basis) const ;
00328
00329 CbcFullNodeInfo ();
00330
00333 CbcFullNodeInfo (CbcModel * model,
00334 int numberRowsAtContinuous);
00335
00336
00337 CbcFullNodeInfo ( const CbcFullNodeInfo &);
00338
00339
00340 ~CbcFullNodeInfo ();
00341
00343 virtual CbcNodeInfo * clone() const;
00344 protected:
00345
00351 CoinWarmStartBasis *basis_;
00352 int numberIntegers_;
00353
00354 double * lower_;
00355 double * upper_;
00356 private:
00358 CbcFullNodeInfo & operator=(const CbcFullNodeInfo& rhs);
00359 };
00360
00361
00362
00371 class CbcPartialNodeInfo : public CbcNodeInfo {
00372
00373 public:
00374
00380 virtual void applyToModel (CbcModel *model, CoinWarmStartBasis *&basis,
00381 CbcCountRowCut **addCuts,
00382 int ¤tNumberCuts) const ;
00383
00385 virtual int applyBounds(int iColumn, double & lower, double & upper,int force) ;
00390 virtual CbcNodeInfo * buildRowBasis(CoinWarmStartBasis & basis ) const ;
00391
00392 CbcPartialNodeInfo ();
00393
00394
00395 CbcPartialNodeInfo (CbcNodeInfo * parent, CbcNode * owner,
00396 int numberChangedBounds,const int * variables,
00397 const double * boundChanges,
00398 const CoinWarmStartDiff *basisDiff) ;
00399
00400
00401 CbcPartialNodeInfo ( const CbcPartialNodeInfo &);
00402
00403
00404 ~CbcPartialNodeInfo ();
00405
00407 virtual CbcNodeInfo * clone() const;
00409 inline const CoinWarmStartDiff *basisDiff() const
00410 { return basisDiff_ ;}
00412 inline const int * variables() const
00413 { return variables_;}
00414
00415 inline const double * newBounds() const
00416 { return newBounds_;}
00418 inline int numberChangedBounds() const
00419 { return numberChangedBounds_;}
00420 protected:
00421
00422
00424 CoinWarmStartDiff *basisDiff_ ;
00426 int * variables_;
00427
00428 double * newBounds_;
00430 int numberChangedBounds_;
00431 private:
00432
00434 CbcPartialNodeInfo & operator=(const CbcPartialNodeInfo& rhs);
00435 };
00436
00437
00438
00456 class CbcNode : public CoinTreeNode {
00457
00458 public:
00459
00461 CbcNode ();
00462
00464 CbcNode (CbcModel * model, CbcNode * lastNode);
00465
00467 CbcNode (const CbcNode &);
00468
00470 CbcNode & operator= (const CbcNode& rhs);
00471
00473 ~CbcNode ();
00474
00490 void
00491 createInfo(CbcModel * model,
00492 CbcNode * lastNode,
00493 const CoinWarmStartBasis *lastws,
00494 const double * lastLower, const double * lastUpper,
00495 int numberOldActiveCuts,int numberNewCuts);
00496
00517 int chooseBranch (CbcModel * model,
00518 CbcNode * lastNode,
00519 int numberPassesLeft);
00545 int chooseDynamicBranch (CbcModel * model,
00546 CbcNode * lastNode,
00547 OsiSolverBranch * & branches,
00548 int numberPassesLeft);
00575 int chooseOsiBranch (CbcModel * model,
00576 CbcNode * lastNode,
00577 OsiBranchingInformation * usefulInfo,
00578 int branchState);
00579 int analyze(CbcModel * model,double * results);
00581 void decrementCuts(int change=1);
00582
00584 void decrementParentCuts(CbcModel * model, int change=1);
00585
00587 void nullNodeInfo();
00596 void initializeInfo();
00597
00599 int branch(OsiSolverInterface * solver);
00600
00601
00602 inline CbcNodeInfo * nodeInfo() const
00603 {return nodeInfo_;}
00604
00605
00606 inline double objectiveValue() const
00607 { return objectiveValue_;}
00608 inline void setObjectiveValue(double value)
00609 { objectiveValue_=value;}
00611 inline int numberBranches() const
00612 { if (branch_)
00613 return (branch_->numberBranches()) ;
00614 else
00615 return (-1) ; }
00616
00617
00618
00619
00620
00621
00622
00623 int way() const;
00625 inline int depth() const
00626 {return depth_;}
00628 inline int numberUnsatisfied() const
00629 {return numberUnsatisfied_;}
00631 inline double sumInfeasibilities() const
00632 { return sumInfeasibilities_;}
00633
00634 inline double guessedObjectiveValue() const
00635 {return guessedObjectiveValue_;}
00636 inline void setGuessedObjectiveValue(double value)
00637 {guessedObjectiveValue_=value;}
00639 inline const OsiBranchingObject * branchingObject() const
00640 { return branch_;}
00642 inline OsiBranchingObject * modifiableBranchingObject() const
00643 { return branch_;}
00645 inline void setBranchingObject(OsiBranchingObject * branchingObject)
00646 { branch_ = branchingObject;}
00648 inline int nodeNumber() const
00649 { return nodeNumber_;}
00650 inline void setNodeNumber(int node)
00651 { nodeNumber_=node;}
00653 inline bool onTree() const
00654 { return (state_&1)!=0;}
00656 inline void setOnTree(bool yesNo)
00657 { if(yesNo) state_ |= 1; else state_ &= ~1; }
00659 inline bool active() const
00660 { return (state_&2)!=0;}
00662 inline void setActive(bool yesNo)
00663 { if(yesNo) state_ |= 2; else state_ &= ~2; }
00665 void print() const;
00666
00667 private:
00668
00670 CbcNodeInfo * nodeInfo_;
00672 double objectiveValue_;
00674 double guessedObjectiveValue_;
00676 double sumInfeasibilities_;
00678 OsiBranchingObject * branch_;
00680 int depth_;
00682 int numberUnsatisfied_;
00684 int nodeNumber_;
00689 int state_;
00690 };
00691
00692
00693 #endif