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 void setModel(CbcModel * model)
00219 { model_ = model;}
00220
00222 inline CbcModel * model() const
00223 {return model_;}
00224
00226 inline int preferredWay() const
00227 { return preferredWay_;}
00229 inline void setPreferredWay(int value)
00230 { preferredWay_=value;}
00232 virtual void redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns) {}
00233
00234 protected:
00236
00238 CbcModel * model_;
00240 int id_;
00242 int preferredWay_;
00243
00244 };
00245
00264 class CbcBranchingObject : public OsiBranchingObject {
00265
00266 public:
00267
00269 CbcBranchingObject ();
00270
00272 CbcBranchingObject (CbcModel * model, int variable, int way , double value);
00273
00275 CbcBranchingObject ( const CbcBranchingObject &);
00276
00278 CbcBranchingObject & operator=( const CbcBranchingObject& rhs);
00279
00281 virtual CbcBranchingObject * clone() const=0;
00282
00284 virtual ~CbcBranchingObject ();
00285
00290 virtual int fillStrongInfo( CbcStrongInfo & info) {return 0;}
00292 inline void resetNumberBranchesLeft()
00293 { branchIndex_=0;}
00294
00301 virtual double branch()=0;
00308 virtual double branch(OsiSolverInterface * solver)
00309 { return branch();}
00310
00314 virtual void previousBranch() {
00315 assert(branchIndex_ > 0);
00316 branchIndex_--;
00317 way_ = -way_;
00318 }
00319
00320 using OsiBranchingObject::print ;
00323 virtual void print() const {}
00324
00336 inline int variable() const
00337 {return variable_;}
00338
00346 inline int way() const
00347 {return way_;}
00348
00353 inline void way(int way)
00354 {way_=way;}
00355
00357 inline void setModel(CbcModel * model)
00358 { model_ = model;}
00360 inline CbcModel * model() const
00361 {return model_;}
00362
00364 inline CbcObject * object() const
00365 {return originalCbcObject_;}
00367 inline void setOriginalObject(CbcObject * object)
00368 {originalCbcObject_=object;}
00369
00370
00371
00373 virtual int type() const = 0;
00374
00382 virtual int compareOriginalObject(const CbcBranchingObject* brObj) const
00383 {
00384 const CbcBranchingObject* br=dynamic_cast<const CbcBranchingObject*>(brObj);
00385 return variable() - br->variable();
00386 }
00387
00396 virtual CbcRangeCompare compareBranchingObject
00397 (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false) = 0;
00398
00399 protected:
00400
00402 CbcModel * model_;
00404 CbcObject * originalCbcObject_;
00405
00407 int variable_;
00408
00416 int way_;
00417
00418 };
00419
00420
00434 class CbcBranchDecision {
00435 public:
00437 CbcBranchDecision ();
00438
00439
00440 CbcBranchDecision ( const CbcBranchDecision &);
00441
00443 virtual ~CbcBranchDecision();
00444
00446 virtual CbcBranchDecision * clone() const = 0;
00447
00449 virtual void initialize(CbcModel * model) = 0;
00450
00460 virtual int
00461 betterBranch (CbcBranchingObject * thisOne,
00462 CbcBranchingObject * bestSoFar,
00463 double changeUp, int numberInfeasibilitiesUp,
00464 double changeDown, int numberInfeasibilitiesDown) = 0 ;
00465
00472 virtual int
00473 bestBranch (CbcBranchingObject ** objects, int numberObjects, int numberUnsatisfied,
00474 double * changeUp, int * numberInfeasibilitiesUp,
00475 double * changeDown, int * numberInfeasibilitiesDown,
00476 double objectiveValue) ;
00477
00480 virtual int whichMethod() {return 2;}
00481
00484 virtual void saveBranchingObject(OsiBranchingObject * object) {}
00487 virtual void updateInformation(OsiSolverInterface * solver,
00488 const CbcNode * node) {}
00490 virtual void setBestCriterion(double value) {}
00491 virtual double getBestCriterion() const {return 0.0;}
00493 virtual void generateCpp( FILE * fp) {}
00495 inline CbcModel * cbcModel() const
00496 { return model_;}
00497
00498
00499
00500 OsiChooseVariable * chooseMethod() const
00501 { return chooseMethod_;}
00503 void setChooseMethod(const OsiChooseVariable & method);
00504
00505 protected:
00506
00507
00508 CbcBranchingObject * object_;
00510 CbcModel * model_;
00511
00512
00513
00514 OsiChooseVariable * chooseMethod_;
00515 private:
00517 CbcBranchDecision & operator=(const CbcBranchDecision& rhs);
00518
00519 };
00529 class CbcConsequence {
00530
00531 public:
00532
00533
00534 CbcConsequence ();
00535
00536
00537 CbcConsequence ( const CbcConsequence & rhs);
00538
00539
00540 CbcConsequence & operator=( const CbcConsequence & rhs);
00541
00543 virtual CbcConsequence * clone() const=0;
00544
00546 virtual ~CbcConsequence ();
00547
00550 virtual void applyToSolver(OsiSolverInterface * solver, int state) const=0;
00551
00552 protected:
00553 };
00554
00555
00556 class CbcObjectUpdateData {
00557
00558 public:
00559
00561 CbcObjectUpdateData ();
00562
00564 CbcObjectUpdateData (CbcObject * object,
00565 int way,
00566 double change,
00567 int status,
00568 int intDecrease_,
00569 double branchingValue);
00570
00572 CbcObjectUpdateData ( const CbcObjectUpdateData &);
00573
00575 CbcObjectUpdateData & operator=( const CbcObjectUpdateData& rhs);
00576
00578 virtual ~CbcObjectUpdateData ();
00579
00580
00581 public:
00583
00585 CbcObject * object_;
00587 int way_;
00589 int objectNumber_;
00591 double change_;
00593 int status_;
00595 int intDecrease_;
00597 double branchingValue_;
00599 double originalObjective_;
00601 double cutoff_;
00602
00603 };
00604
00605
00606
00613 static inline CbcRangeCompare
00614 CbcCompareRanges(double* thisBd, const double* otherBd,
00615 const bool replaceIfOverlap)
00616 {
00617 const double lbDiff = thisBd[0] - otherBd[0];
00618 if (lbDiff < 0) {
00619 if (thisBd[1] >= otherBd[1]) {
00620 return CbcRangeSuperset;
00621 } else if (thisBd[1] < otherBd[0]) {
00622 return CbcRangeDisjoint;
00623 } else {
00624
00625 if (replaceIfOverlap) {
00626 thisBd[0] = otherBd[0];
00627 }
00628 return CbcRangeOverlap;
00629 }
00630 } else if (lbDiff > 0) {
00631 if (thisBd[1] <= otherBd[1]) {
00632 return CbcRangeSubset;
00633 } else if (thisBd[0] > otherBd[1]) {
00634 return CbcRangeDisjoint;
00635 } else {
00636
00637 if (replaceIfOverlap) {
00638 thisBd[1] = otherBd[1];
00639 }
00640 return CbcRangeOverlap;
00641 }
00642 } else {
00643 if (thisBd[1] == otherBd[1]) {
00644 return CbcRangeSame;
00645 }
00646 return thisBd[1] < otherBd[1] ? CbcRangeSubset : CbcRangeSuperset;
00647 }
00648
00649 return CbcRangeSame;
00650
00651 }
00652
00653
00654
00655 #endif