00001
00002
00003
00004 #ifndef CbcBranchBase_H
00005 #define CbcBranchBase_H
00006
00007 #include <string>
00008 #include <vector>
00009 #include "OsiBranchingObject.hpp"
00010 class OsiSolverInterface;
00011 class OsiSolverBranch;
00012
00013 class CbcModel;
00014 class CbcNode;
00015 class CbcNodeInfo;
00016 class CbcBranchingObject;
00017 class OsiChooseVariable;
00018 class CbcObjectUpdateData;
00019
00020
00021
00022 enum CbcRangeCompare {
00023 CbcRangeSame,
00024 CbcRangeDisjoint,
00025 CbcRangeSubset,
00026 CbcRangeSuperset,
00027 CbcRangeOverlap
00028 };
00029
00030
00031
00057
00058 typedef struct {
00059 CbcBranchingObject * possibleBranch;
00060 double upMovement;
00061 double downMovement;
00062 int numIntInfeasUp ;
00063 int numObjInfeasUp ;
00064 bool finishedUp;
00065 int numItersUp ;
00066 int numIntInfeasDown ;
00067 int numObjInfeasDown ;
00068 bool finishedDown;
00069 int numItersDown;
00070 int objectNumber;
00071 int fix;
00072 } CbcStrongInfo;
00073
00074 class CbcObject : public OsiObject {
00075
00076 public:
00077
00078
00079 CbcObject ();
00080
00081
00082 CbcObject (CbcModel * model);
00083
00084
00085 CbcObject ( const CbcObject &);
00086
00087
00088 CbcObject & operator=( const CbcObject& rhs);
00089
00091 virtual CbcObject * clone() const=0;
00092
00094 virtual ~CbcObject ();
00095
00110 #ifdef CBC_NEW_STYLE_BRANCH
00111 virtual double infeasibility(const OsiBranchingInformation * info,
00112 int &preferredWay) const=0;
00113 #else
00114 virtual double infeasibility(const OsiBranchingInformation * ,
00115 int &preferredWay) const
00116 {return infeasibility(preferredWay);}
00117 virtual double infeasibility(int &) const
00118 {throw CoinError("Need code","infeasibility","CbcBranchBase");}
00119 #endif
00120
00124 virtual void feasibleRegion() = 0;
00126 virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const;
00127
00132 virtual double feasibleRegion(OsiSolverInterface * solver) const ;
00133
00139 #ifdef CBC_NEW_STYLE_BRANCH
00140 virtual CbcBranchingObject * createCbcBranch(OsiSolverInterface * solver,const OsiBranchingInformation * info, int way) =0;
00141 #else
00142 virtual CbcBranchingObject * createCbcBranch(OsiSolverInterface * solver,const OsiBranchingInformation * info, int way)
00143 { return createBranch(solver,info,way);}
00144 virtual CbcBranchingObject * createBranch(OsiSolverInterface * ,
00145 const OsiBranchingInformation * , int )
00146 {throw CoinError("Need code","createBranch","CbcBranchBase");}
00147 #endif
00148
00153 virtual OsiBranchingObject * createOsiBranch(OsiSolverInterface * solver,const OsiBranchingInformation * info, int way) const;
00158 virtual OsiSolverBranch * solverBranch() const;
00159
00168 virtual CbcBranchingObject * preferredNewFeasible() const
00169 { return NULL;}
00170
00179 virtual CbcBranchingObject * notPreferredNewFeasible() const
00180 { return NULL;}
00181
00186 virtual void resetBounds(const OsiSolverInterface * ) {}
00187
00190 virtual void floorCeiling(double & floorValue, double & ceilingValue, double value,
00191 double tolerance) const;
00192
00196 virtual CbcObjectUpdateData createUpdateInformation(const OsiSolverInterface * solver,
00197 const CbcNode * node,
00198 const CbcBranchingObject * branchingObject);
00199
00201 virtual void updateInformation(const CbcObjectUpdateData & ) {}
00202
00204 inline int id() const
00205 { return id_;}
00206
00210 inline void setId(int value)
00211 { id_ = value;}
00212
00215 inline bool optionalObject() const
00216 { return (id_ >= 1000000000 && id_ < 1100000000);}
00217
00219 inline int position() const
00220 { return position_;}
00221
00223 inline void setPosition(int position)
00224 { position_ = position;}
00225
00227 inline void setModel(CbcModel * model)
00228 { model_ = model;}
00229
00231 inline CbcModel * model() const
00232 {return model_;}
00233
00235 inline int preferredWay() const
00236 { return preferredWay_;}
00238 inline void setPreferredWay(int value)
00239 { preferredWay_=value;}
00241 virtual void redoSequenceEtc(CbcModel * , int , const int * ) {}
00242
00243 protected:
00245
00247 CbcModel * model_;
00249 int id_;
00251 int position_;
00253 int preferredWay_;
00254
00255 };
00256
00275 class CbcBranchingObject : public OsiBranchingObject {
00276
00277 public:
00278
00280 CbcBranchingObject ();
00281
00283 CbcBranchingObject (CbcModel * model, int variable, int way , double value);
00284
00286 CbcBranchingObject ( const CbcBranchingObject &);
00287
00289 CbcBranchingObject & operator=( const CbcBranchingObject& rhs);
00290
00292 virtual CbcBranchingObject * clone() const=0;
00293
00295 virtual ~CbcBranchingObject ();
00296
00301 virtual int fillStrongInfo( CbcStrongInfo & ) {return 0;}
00303 inline void resetNumberBranchesLeft()
00304 { branchIndex_=0;}
00306 inline void setNumberBranches(int value)
00307 { branchIndex_=0;numberBranches_=value;}
00308
00315 virtual double branch()=0;
00322 virtual double branch(OsiSolverInterface * )
00323 { return branch();}
00326 virtual void fix(OsiSolverInterface * ,
00327 double * , double * ,
00328 int ) const {}
00329
00333 virtual void previousBranch() {
00334 assert(branchIndex_ > 0);
00335 branchIndex_--;
00336 way_ = -way_;
00337 }
00338
00339 using OsiBranchingObject::print ;
00342 virtual void print() const {}
00343
00355 inline int variable() const
00356 {return variable_;}
00357
00365 inline int way() const
00366 {return way_;}
00367
00372 inline void way(int way)
00373 {way_=way;}
00374
00376 inline void setModel(CbcModel * model)
00377 { model_ = model;}
00379 inline CbcModel * model() const
00380 {return model_;}
00381
00383 inline CbcObject * object() const
00384 {return originalCbcObject_;}
00386 inline void setOriginalObject(CbcObject * object)
00387 {originalCbcObject_=object;}
00388
00389
00390
00392 virtual int type() const = 0;
00393
00401 virtual int compareOriginalObject(const CbcBranchingObject* brObj) const
00402 {
00403 const CbcBranchingObject* br=dynamic_cast<const CbcBranchingObject*>(brObj);
00404 return variable() - br->variable();
00405 }
00406
00415 virtual CbcRangeCompare compareBranchingObject
00416 (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false) = 0;
00417
00418 protected:
00419
00421 CbcModel * model_;
00423 CbcObject * originalCbcObject_;
00424
00426 int variable_;
00427
00435 int way_;
00436
00437 };
00438
00439
00453 class CbcBranchDecision {
00454 public:
00456 CbcBranchDecision ();
00457
00458
00459 CbcBranchDecision ( const CbcBranchDecision &);
00460
00462 virtual ~CbcBranchDecision();
00463
00465 virtual CbcBranchDecision * clone() const = 0;
00466
00468 virtual void initialize(CbcModel * model) = 0;
00469
00479 virtual int
00480 betterBranch (CbcBranchingObject * thisOne,
00481 CbcBranchingObject * bestSoFar,
00482 double changeUp, int numberInfeasibilitiesUp,
00483 double changeDown, int numberInfeasibilitiesDown) = 0 ;
00484
00491 virtual int
00492 bestBranch (CbcBranchingObject ** objects, int numberObjects, int numberUnsatisfied,
00493 double * changeUp, int * numberInfeasibilitiesUp,
00494 double * changeDown, int * numberInfeasibilitiesDown,
00495 double objectiveValue) ;
00496
00499 virtual int whichMethod() {return 2;}
00500
00503 virtual void saveBranchingObject(OsiBranchingObject * ) {}
00506 virtual void updateInformation(OsiSolverInterface * ,
00507 const CbcNode * ) {}
00509 virtual void setBestCriterion(double ) {}
00510 virtual double getBestCriterion() const {return 0.0;}
00512 virtual void generateCpp( FILE * ) {}
00514 inline CbcModel * cbcModel() const
00515 { return model_;}
00516
00517
00518
00519 OsiChooseVariable * chooseMethod() const
00520 { return chooseMethod_;}
00522 void setChooseMethod(const OsiChooseVariable & method);
00523
00524 protected:
00525
00526
00527 CbcBranchingObject * object_;
00529 CbcModel * model_;
00530
00531
00532
00533 OsiChooseVariable * chooseMethod_;
00534 private:
00536 CbcBranchDecision & operator=(const CbcBranchDecision& rhs);
00537
00538 };
00548 class CbcConsequence {
00549
00550 public:
00551
00552
00553 CbcConsequence ();
00554
00555
00556 CbcConsequence ( const CbcConsequence & rhs);
00557
00558
00559 CbcConsequence & operator=( const CbcConsequence & rhs);
00560
00562 virtual CbcConsequence * clone() const=0;
00563
00565 virtual ~CbcConsequence ();
00566
00569 virtual void applyToSolver(OsiSolverInterface * solver, int state) const=0;
00570
00571 protected:
00572 };
00573
00574
00575 class CbcObjectUpdateData {
00576
00577 public:
00578
00580 CbcObjectUpdateData ();
00581
00583 CbcObjectUpdateData (CbcObject * object,
00584 int way,
00585 double change,
00586 int status,
00587 int intDecrease_,
00588 double branchingValue);
00589
00591 CbcObjectUpdateData ( const CbcObjectUpdateData &);
00592
00594 CbcObjectUpdateData & operator=( const CbcObjectUpdateData& rhs);
00595
00597 virtual ~CbcObjectUpdateData ();
00598
00599
00600 public:
00602
00604 CbcObject * object_;
00606 int way_;
00608 int objectNumber_;
00610 double change_;
00612 int status_;
00614 int intDecrease_;
00616 double branchingValue_;
00618 double originalObjective_;
00620 double cutoff_;
00621
00622 };
00623
00624
00625
00632 static inline CbcRangeCompare
00633 CbcCompareRanges(double* thisBd, const double* otherBd,
00634 const bool replaceIfOverlap)
00635 {
00636 const double lbDiff = thisBd[0] - otherBd[0];
00637 if (lbDiff < 0) {
00638 if (thisBd[1] >= otherBd[1]) {
00639 return CbcRangeSuperset;
00640 } else if (thisBd[1] < otherBd[0]) {
00641 return CbcRangeDisjoint;
00642 } else {
00643
00644 if (replaceIfOverlap) {
00645 thisBd[0] = otherBd[0];
00646 }
00647 return CbcRangeOverlap;
00648 }
00649 } else if (lbDiff > 0) {
00650 if (thisBd[1] <= otherBd[1]) {
00651 return CbcRangeSubset;
00652 } else if (thisBd[0] > otherBd[1]) {
00653 return CbcRangeDisjoint;
00654 } else {
00655
00656 if (replaceIfOverlap) {
00657 thisBd[1] = otherBd[1];
00658 }
00659 return CbcRangeOverlap;
00660 }
00661 } else {
00662 if (thisBd[1] == otherBd[1]) {
00663 return CbcRangeSame;
00664 }
00665 return thisBd[1] < otherBd[1] ? CbcRangeSubset : CbcRangeSuperset;
00666 }
00667
00668 return CbcRangeSame;
00669
00670 }
00671
00672
00673
00674 #endif