00001
00002
00003 #ifndef CbcBranchBase_H
00004 #define CbcBranchBase_H
00005
00006 #include <string>
00007 #include <vector>
00008 #include "OsiBranchingObject.hpp"
00009 class OsiSolverInterface;
00010 class OsiSolverBranch;
00011
00012 class CbcModel;
00013 class CbcNode;
00014 class CbcNodeInfo;
00015 class CbcBranchingObject;
00016 class OsiChooseVariable;
00017 class CbcObjectUpdateData;
00018
00019
00020
00021 enum CbcRangeCompare {
00022 CbcRangeSame,
00023 CbcRangeDisjoint,
00024 CbcRangeSubset,
00025 CbcRangeSuperset,
00026 CbcRangeOverlap
00027 };
00028
00029
00030
00056
00057 typedef struct {
00058 CbcBranchingObject * possibleBranch;
00059 double upMovement;
00060 double downMovement;
00061 int numIntInfeasUp ;
00062 int numObjInfeasUp ;
00063 bool finishedUp;
00064 int numItersUp ;
00065 int numIntInfeasDown ;
00066 int numObjInfeasDown ;
00067 bool finishedDown;
00068 int numItersDown;
00069 int objectNumber;
00070 int fix;
00071 } CbcStrongInfo;
00072
00073 class CbcObject : public OsiObject {
00074
00075 public:
00076
00077
00078 CbcObject ();
00079
00080
00081 CbcObject (CbcModel * model);
00082
00083
00084 CbcObject ( const CbcObject &);
00085
00086
00087 CbcObject & operator=( const CbcObject& rhs);
00088
00090 virtual CbcObject * clone() const=0;
00091
00093 virtual ~CbcObject ();
00094
00109 virtual double infeasibility(int &preferredWay) const = 0;
00111 virtual double infeasibility(const OsiBranchingInformation * info,
00112 int &preferredWay) const;
00113
00117 virtual void feasibleRegion() = 0;
00119 virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const;
00120
00126 virtual CbcBranchingObject * createBranch(int way) = 0;
00127
00144 virtual double infeasibility(const OsiSolverInterface * solver,int &preferredWay) const;
00145
00150 virtual double feasibleRegion(OsiSolverInterface * solver) const ;
00151
00157 virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver, int way) const;
00163 virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver,const OsiBranchingInformation * info, int way) const;
00168 virtual OsiSolverBranch * solverBranch() const;
00169
00178 virtual CbcBranchingObject * preferredNewFeasible() const
00179 { return NULL;}
00180
00189 virtual CbcBranchingObject * notPreferredNewFeasible() const
00190 { return NULL;}
00191
00196 virtual void resetBounds(const OsiSolverInterface * solver) {}
00197
00200 virtual void floorCeiling(double & floorValue, double & ceilingValue, double value,
00201 double tolerance) const;
00202
00206 virtual CbcObjectUpdateData createUpdateInformation(const OsiSolverInterface * solver,
00207 const CbcNode * node,
00208 const CbcBranchingObject * branchingObject);
00209
00211 virtual void updateInformation(const CbcObjectUpdateData & data) {}
00212
00214 inline int id() const
00215 { return id_;}
00216
00218 inline int position() const
00219 { return position_;}
00220
00222 inline void setPosition(int position)
00223 { position_ = position;}
00224
00226 inline void setModel(CbcModel * model)
00227 { model_ = model;}
00228
00230 inline CbcModel * model() const
00231 {return model_;}
00232
00234 inline int preferredWay() const
00235 { return preferredWay_;}
00237 inline void setPreferredWay(int value)
00238 { preferredWay_=value;}
00240 virtual void redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns) {}
00241
00242 protected:
00244
00246 CbcModel * model_;
00248 int id_;
00250 int position_;
00252 int preferredWay_;
00253
00254 };
00255
00274 class CbcBranchingObject : public OsiBranchingObject {
00275
00276 public:
00277
00279 CbcBranchingObject ();
00280
00282 CbcBranchingObject (CbcModel * model, int variable, int way , double value);
00283
00285 CbcBranchingObject ( const CbcBranchingObject &);
00286
00288 CbcBranchingObject & operator=( const CbcBranchingObject& rhs);
00289
00291 virtual CbcBranchingObject * clone() const=0;
00292
00294 virtual ~CbcBranchingObject ();
00295
00300 virtual int fillStrongInfo( CbcStrongInfo & info) {return 0;}
00302 inline void resetNumberBranchesLeft()
00303 { branchIndex_=0;}
00305 inline void setNumberBranches(int value)
00306 { branchIndex_=0;numberBranches_=value;}
00307
00314 virtual double branch()=0;
00321 virtual double branch(OsiSolverInterface * solver)
00322 { return branch();}
00325 virtual void fix(OsiSolverInterface * solver,
00326 double * lower, double * upper,
00327 int branchState) const {}
00328
00332 virtual void previousBranch() {
00333 assert(branchIndex_ > 0);
00334 branchIndex_--;
00335 way_ = -way_;
00336 }
00337
00338 using OsiBranchingObject::print ;
00341 virtual void print() const {}
00342
00354 inline int variable() const
00355 {return variable_;}
00356
00364 inline int way() const
00365 {return way_;}
00366
00371 inline void way(int way)
00372 {way_=way;}
00373
00375 inline void setModel(CbcModel * model)
00376 { model_ = model;}
00378 inline CbcModel * model() const
00379 {return model_;}
00380
00382 inline CbcObject * object() const
00383 {return originalCbcObject_;}
00385 inline void setOriginalObject(CbcObject * object)
00386 {originalCbcObject_=object;}
00387
00388
00389
00391 virtual int type() const = 0;
00392
00400 virtual int compareOriginalObject(const CbcBranchingObject* brObj) const
00401 {
00402 const CbcBranchingObject* br=dynamic_cast<const CbcBranchingObject*>(brObj);
00403 return variable() - br->variable();
00404 }
00405
00414 virtual CbcRangeCompare compareBranchingObject
00415 (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false) = 0;
00416
00417 protected:
00418
00420 CbcModel * model_;
00422 CbcObject * originalCbcObject_;
00423
00425 int variable_;
00426
00434 int way_;
00435
00436 };
00437
00438
00452 class CbcBranchDecision {
00453 public:
00455 CbcBranchDecision ();
00456
00457
00458 CbcBranchDecision ( const CbcBranchDecision &);
00459
00461 virtual ~CbcBranchDecision();
00462
00464 virtual CbcBranchDecision * clone() const = 0;
00465
00467 virtual void initialize(CbcModel * model) = 0;
00468
00478 virtual int
00479 betterBranch (CbcBranchingObject * thisOne,
00480 CbcBranchingObject * bestSoFar,
00481 double changeUp, int numberInfeasibilitiesUp,
00482 double changeDown, int numberInfeasibilitiesDown) = 0 ;
00483
00490 virtual int
00491 bestBranch (CbcBranchingObject ** objects, int numberObjects, int numberUnsatisfied,
00492 double * changeUp, int * numberInfeasibilitiesUp,
00493 double * changeDown, int * numberInfeasibilitiesDown,
00494 double objectiveValue) ;
00495
00498 virtual int whichMethod() {return 2;}
00499
00502 virtual void saveBranchingObject(OsiBranchingObject * object) {}
00505 virtual void updateInformation(OsiSolverInterface * solver,
00506 const CbcNode * node) {}
00508 virtual void setBestCriterion(double value) {}
00509 virtual double getBestCriterion() const {return 0.0;}
00511 virtual void generateCpp( FILE * fp) {}
00513 inline CbcModel * cbcModel() const
00514 { return model_;}
00515
00516
00517
00518 OsiChooseVariable * chooseMethod() const
00519 { return chooseMethod_;}
00521 void setChooseMethod(const OsiChooseVariable & method);
00522
00523 protected:
00524
00525
00526 CbcBranchingObject * object_;
00528 CbcModel * model_;
00529
00530
00531
00532 OsiChooseVariable * chooseMethod_;
00533 private:
00535 CbcBranchDecision & operator=(const CbcBranchDecision& rhs);
00536
00537 };
00547 class CbcConsequence {
00548
00549 public:
00550
00551
00552 CbcConsequence ();
00553
00554
00555 CbcConsequence ( const CbcConsequence & rhs);
00556
00557
00558 CbcConsequence & operator=( const CbcConsequence & rhs);
00559
00561 virtual CbcConsequence * clone() const=0;
00562
00564 virtual ~CbcConsequence ();
00565
00568 virtual void applyToSolver(OsiSolverInterface * solver, int state) const=0;
00569
00570 protected:
00571 };
00572
00573
00574 class CbcObjectUpdateData {
00575
00576 public:
00577
00579 CbcObjectUpdateData ();
00580
00582 CbcObjectUpdateData (CbcObject * object,
00583 int way,
00584 double change,
00585 int status,
00586 int intDecrease_,
00587 double branchingValue);
00588
00590 CbcObjectUpdateData ( const CbcObjectUpdateData &);
00591
00593 CbcObjectUpdateData & operator=( const CbcObjectUpdateData& rhs);
00594
00596 virtual ~CbcObjectUpdateData ();
00597
00598
00599 public:
00601
00603 CbcObject * object_;
00605 int way_;
00607 int objectNumber_;
00609 double change_;
00611 int status_;
00613 int intDecrease_;
00615 double branchingValue_;
00617 double originalObjective_;
00619 double cutoff_;
00620
00621 };
00622
00623
00624
00631 static inline CbcRangeCompare
00632 CbcCompareRanges(double* thisBd, const double* otherBd,
00633 const bool replaceIfOverlap)
00634 {
00635 const double lbDiff = thisBd[0] - otherBd[0];
00636 if (lbDiff < 0) {
00637 if (thisBd[1] >= otherBd[1]) {
00638 return CbcRangeSuperset;
00639 } else if (thisBd[1] < otherBd[0]) {
00640 return CbcRangeDisjoint;
00641 } else {
00642
00643 if (replaceIfOverlap) {
00644 thisBd[0] = otherBd[0];
00645 }
00646 return CbcRangeOverlap;
00647 }
00648 } else if (lbDiff > 0) {
00649 if (thisBd[1] <= otherBd[1]) {
00650 return CbcRangeSubset;
00651 } else if (thisBd[0] > otherBd[1]) {
00652 return CbcRangeDisjoint;
00653 } else {
00654
00655 if (replaceIfOverlap) {
00656 thisBd[1] = otherBd[1];
00657 }
00658 return CbcRangeOverlap;
00659 }
00660 } else {
00661 if (thisBd[1] == otherBd[1]) {
00662 return CbcRangeSame;
00663 }
00664 return thisBd[1] < otherBd[1] ? CbcRangeSubset : CbcRangeSuperset;
00665 }
00666
00667 return CbcRangeSame;
00668
00669 }
00670
00671
00672
00673 #endif