Osi
trunk
|
00001 // Copyright (C) 2006, International Business Machines 00002 // Corporation and others. All Rights Reserved. 00003 // This code is licensed under the terms of the Eclipse Public License (EPL). 00004 00005 #ifndef OsiBranchingObject_H 00006 #define OsiBranchingObject_H 00007 00008 #include <cassert> 00009 #include <string> 00010 #include <vector> 00011 00012 #include "CoinError.hpp" 00013 #include "CoinTypes.hpp" 00014 00015 class OsiSolverInterface; 00016 class OsiSolverBranch; 00017 00018 class OsiBranchingObject; 00019 class OsiBranchingInformation; 00020 00021 //############################################################################# 00022 //This contains the abstract base class for an object and for branching. 00023 //It also contains a simple integer class 00024 //############################################################################# 00025 00056 class OsiObject { 00057 00058 public: 00059 00061 OsiObject (); 00062 00064 OsiObject ( const OsiObject &); 00065 00067 OsiObject & operator=( const OsiObject& rhs); 00068 00070 virtual OsiObject * clone() const=0; 00071 00073 virtual ~OsiObject (); 00074 00096 double infeasibility(const OsiSolverInterface * solver,int &whichWay) const ; 00097 // Faster version when more information available 00098 virtual double infeasibility(const OsiBranchingInformation * info, int &whichWay) const =0; 00099 // This does NOT set mutable stuff 00100 virtual double checkInfeasibility(const OsiBranchingInformation * info) const; 00101 00106 virtual double feasibleRegion(OsiSolverInterface * solver) const ; 00112 virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const =0; 00113 00119 virtual OsiBranchingObject * createBranch(OsiSolverInterface * /*solver*/, 00120 const OsiBranchingInformation * /*info*/, 00121 int /*way*/) const {throw CoinError("Need code","createBranch","OsiBranchingObject"); return NULL; } 00122 00125 virtual bool canDoHeuristics() const 00126 {return true;} 00129 virtual bool canMoveToNearest() const 00130 {return false;} 00134 virtual int columnNumber() const; 00136 inline int priority() const 00137 { return priority_;} 00139 inline void setPriority(int priority) 00140 { priority_ = priority;} 00143 virtual bool boundBranch() const 00144 {return true;} 00146 virtual bool canHandleShadowPrices() const 00147 { return false;} 00149 inline int numberWays() const 00150 { return numberWays_;} 00152 inline void setNumberWays(int numberWays) 00153 { numberWays_ = static_cast<short int>(numberWays) ; } 00158 inline void setWhichWay(int way) 00159 { whichWay_ = static_cast<short int>(way) ; } 00164 inline int whichWay() const 00165 { return whichWay_;} 00167 virtual int preferredWay() const 00168 { return -1;} 00170 inline double infeasibility() const 00171 { return infeasibility_;} 00173 virtual double upEstimate() const; 00175 virtual double downEstimate() const; 00180 virtual void resetBounds(const OsiSolverInterface * ) {} 00183 virtual void resetSequenceEtc(int , const int * ) {} 00185 virtual void updateBefore(const OsiObject * ) {} 00187 virtual void updateAfter(const OsiObject * , const OsiObject * ) {} 00188 00189 protected: 00191 00193 mutable double infeasibility_; 00195 mutable short whichWay_; 00197 short numberWays_; 00199 int priority_; 00200 00201 }; 00204 00205 00206 class OsiObject2 : public OsiObject { 00207 00208 public: 00209 00211 OsiObject2 (); 00212 00214 OsiObject2 ( const OsiObject2 &); 00215 00217 OsiObject2 & operator=( const OsiObject2& rhs); 00218 00220 virtual ~OsiObject2 (); 00221 00223 inline void setPreferredWay(int value) 00224 {preferredWay_=value;} 00225 00227 virtual int preferredWay() const 00228 { return preferredWay_;} 00229 protected: 00231 int preferredWay_; 00233 mutable double otherInfeasibility_; 00234 00235 }; 00236 00254 class OsiBranchingObject { 00255 00256 public: 00257 00259 OsiBranchingObject (); 00260 00262 OsiBranchingObject (OsiSolverInterface * solver, double value); 00263 00265 OsiBranchingObject ( const OsiBranchingObject &); 00266 00268 OsiBranchingObject & operator=( const OsiBranchingObject& rhs); 00269 00271 virtual OsiBranchingObject * clone() const=0; 00272 00274 virtual ~OsiBranchingObject (); 00275 00277 inline int numberBranches() const 00278 {return numberBranches_;} 00279 00281 inline int numberBranchesLeft() const 00282 {return numberBranches_-branchIndex_;} 00283 00285 inline void incrementNumberBranchesLeft() 00286 { numberBranches_ ++;} 00287 00291 inline void setNumberBranchesLeft(int /*value*/) 00292 {/*assert (value==1&&!branchIndex_);*/ numberBranches_=1;} 00293 00295 inline void decrementNumberBranchesLeft() 00296 {branchIndex_++;} 00297 00303 virtual double branch(OsiSolverInterface * solver)=0; 00309 virtual double branch() {return branch(NULL);} 00312 virtual bool boundBranch() const 00313 {return true;} 00317 inline int branchIndex() const 00318 {return branchIndex_;} 00319 00322 inline void setBranchingIndex(int branchIndex) 00323 { branchIndex_ = static_cast<short int>(branchIndex) ; } 00324 00326 inline double value() const 00327 {return value_;} 00328 00330 inline const OsiObject * originalObject() const 00331 {return originalObject_;} 00333 inline void setOriginalObject(const OsiObject * object) 00334 {originalObject_=object;} 00338 virtual void checkIsCutoff(double ) {} 00340 int columnNumber() const; 00343 virtual void print(const OsiSolverInterface * =NULL) const {} 00344 00345 protected: 00346 00348 double value_; 00349 00351 const OsiObject * originalObject_; 00352 00355 int numberBranches_; 00356 00360 short branchIndex_; 00361 00362 }; 00363 /* This contains information 00364 This could also contain pseudo shadow prices 00365 or information for dealing with computing and trusting pseudo-costs 00366 */ 00367 class OsiBranchingInformation { 00368 00369 public: 00370 00372 OsiBranchingInformation (); 00373 00378 OsiBranchingInformation (const OsiSolverInterface * solver, bool normalSolver,bool copySolution=false); 00379 00381 OsiBranchingInformation ( const OsiBranchingInformation &); 00382 00384 OsiBranchingInformation & operator=( const OsiBranchingInformation& rhs); 00385 00387 virtual OsiBranchingInformation * clone() const; 00388 00390 virtual ~OsiBranchingInformation (); 00391 00392 // Note public 00393 public: 00395 00402 int stateOfSearch_; 00404 double objectiveValue_; 00406 double cutoff_; 00408 double direction_; 00410 double integerTolerance_; 00412 double primalTolerance_; 00414 double timeRemaining_; 00416 double defaultDual_; 00418 mutable const OsiSolverInterface * solver_; 00420 int numberColumns_; 00422 mutable const double * lower_; 00424 mutable const double * solution_; 00426 mutable const double * upper_; 00428 const double * hotstartSolution_; 00430 const double * pi_; 00432 const double * rowActivity_; 00434 const double * objective_; 00436 const double * rowLower_; 00438 const double * rowUpper_; 00440 const double * elementByColumn_; 00442 const CoinBigIndex * columnStart_; 00444 const int * columnLength_; 00446 const int * row_; 00452 double * usefulRegion_; 00454 int * indexRegion_; 00456 int numberSolutions_; 00458 int numberBranchingSolutions_; 00460 int depth_; 00462 bool owningSolution_; 00463 }; 00464 00466 00467 class OsiTwoWayBranchingObject : public OsiBranchingObject { 00468 00469 public: 00470 00472 OsiTwoWayBranchingObject (); 00473 00480 OsiTwoWayBranchingObject (OsiSolverInterface *solver,const OsiObject * originalObject, 00481 int way , double value) ; 00482 00484 OsiTwoWayBranchingObject ( const OsiTwoWayBranchingObject &); 00485 00487 OsiTwoWayBranchingObject & operator= (const OsiTwoWayBranchingObject& rhs); 00488 00490 virtual ~OsiTwoWayBranchingObject (); 00491 00492 using OsiBranchingObject::branch ; 00498 virtual double branch(OsiSolverInterface * solver)=0; 00499 00500 inline int firstBranch() const { return firstBranch_; } 00502 inline int way() const 00503 { return !branchIndex_ ? firstBranch_ : -firstBranch_;} 00504 protected: 00506 int firstBranch_; 00507 }; 00509 00510 00511 class OsiSimpleInteger : public OsiObject2 { 00512 00513 public: 00514 00516 OsiSimpleInteger (); 00517 00519 OsiSimpleInteger (const OsiSolverInterface * solver, int iColumn); 00520 00522 OsiSimpleInteger (int iColumn, double lower, double upper); 00523 00525 OsiSimpleInteger ( const OsiSimpleInteger &); 00526 00528 virtual OsiObject * clone() const; 00529 00531 OsiSimpleInteger & operator=( const OsiSimpleInteger& rhs); 00532 00534 virtual ~OsiSimpleInteger (); 00535 00536 using OsiObject::infeasibility ; 00538 virtual double infeasibility(const OsiBranchingInformation * info, int & whichWay) const; 00539 00540 using OsiObject::feasibleRegion ; 00546 virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const; 00547 00552 virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) const; 00553 00554 00556 inline void setColumnNumber(int value) 00557 {columnNumber_=value;} 00558 00563 virtual int columnNumber() const; 00564 00566 inline double originalLowerBound() const 00567 { return originalLower_;} 00568 inline void setOriginalLowerBound(double value) 00569 { originalLower_=value;} 00570 inline double originalUpperBound() const 00571 { return originalUpper_;} 00572 inline void setOriginalUpperBound(double value) 00573 { originalUpper_=value;} 00578 virtual void resetBounds(const OsiSolverInterface * solver) ; 00581 virtual void resetSequenceEtc(int numberColumns, const int * originalColumns); 00582 00584 virtual double upEstimate() const; 00586 virtual double downEstimate() const; 00588 virtual bool canHandleShadowPrices() const 00589 { return false;} 00590 protected: 00593 double originalLower_; 00595 double originalUpper_; 00597 int columnNumber_; 00598 00599 }; 00607 class OsiIntegerBranchingObject : public OsiTwoWayBranchingObject { 00608 00609 public: 00610 00612 OsiIntegerBranchingObject (); 00613 00621 OsiIntegerBranchingObject (OsiSolverInterface *solver,const OsiSimpleInteger * originalObject, 00622 int way , double value) ; 00630 OsiIntegerBranchingObject (OsiSolverInterface *solver,const OsiSimpleInteger * originalObject, 00631 int way , double value, double downUpperBound, double upLowerBound) ; 00632 00634 OsiIntegerBranchingObject ( const OsiIntegerBranchingObject &); 00635 00637 OsiIntegerBranchingObject & operator= (const OsiIntegerBranchingObject& rhs); 00638 00640 virtual OsiBranchingObject * clone() const; 00641 00643 virtual ~OsiIntegerBranchingObject (); 00644 00645 using OsiBranchingObject::branch ; 00651 virtual double branch(OsiSolverInterface * solver); 00652 00653 using OsiBranchingObject::print ; 00656 virtual void print(const OsiSolverInterface * solver=NULL); 00657 00658 protected: 00659 // Probably could get away with just value which is already stored 00661 double down_[2]; 00663 double up_[2]; 00664 }; 00665 00666 00674 class OsiSOS : public OsiObject2 { 00675 00676 public: 00677 00678 // Default Constructor 00679 OsiSOS (); 00680 00685 OsiSOS (const OsiSolverInterface * solver, int numberMembers, 00686 const int * which, const double * weights, int type=1); 00687 00688 // Copy constructor 00689 OsiSOS ( const OsiSOS &); 00690 00692 virtual OsiObject * clone() const; 00693 00694 // Assignment operator 00695 OsiSOS & operator=( const OsiSOS& rhs); 00696 00697 // Destructor 00698 virtual ~OsiSOS (); 00699 00700 using OsiObject::infeasibility ; 00702 virtual double infeasibility(const OsiBranchingInformation * info,int & whichWay) const; 00703 00704 using OsiObject::feasibleRegion ; 00710 virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const; 00711 00716 virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) const; 00718 virtual double upEstimate() const; 00720 virtual double downEstimate() const; 00721 00723 virtual void resetSequenceEtc(int numberColumns, const int * originalColumns); 00724 00726 inline int numberMembers() const 00727 {return numberMembers_;} 00728 00730 inline const int * members() const 00731 {return members_;} 00732 00734 inline int sosType() const 00735 {return sosType_;} 00736 00738 inline int setType() const 00739 {return sosType_;} 00740 00742 inline const double * weights() const 00743 { return weights_;} 00744 00747 virtual bool canDoHeuristics() const 00748 {return (sosType_==1&&integerValued_);} 00750 inline void setIntegerValued(bool yesNo) 00751 { integerValued_=yesNo;} 00753 virtual bool canHandleShadowPrices() const 00754 { return true;} 00756 inline void setNumberMembers(int value) 00757 {numberMembers_=value;} 00758 00760 inline int * mutableMembers() const 00761 {return members_;} 00762 00764 inline void setSosType(int value) 00765 {sosType_=value;} 00766 00768 inline double * mutableWeights() const 00769 { return weights_;} 00770 protected: 00772 00774 int * members_; 00776 double * weights_; 00777 00779 int numberMembers_; 00781 int sosType_; 00783 bool integerValued_; 00784 }; 00785 00789 class OsiSOSBranchingObject : public OsiTwoWayBranchingObject { 00790 00791 public: 00792 00793 // Default Constructor 00794 OsiSOSBranchingObject (); 00795 00796 // Useful constructor 00797 OsiSOSBranchingObject (OsiSolverInterface * solver, const OsiSOS * originalObject, 00798 int way, 00799 double separator); 00800 00801 // Copy constructor 00802 OsiSOSBranchingObject ( const OsiSOSBranchingObject &); 00803 00804 // Assignment operator 00805 OsiSOSBranchingObject & operator=( const OsiSOSBranchingObject& rhs); 00806 00808 virtual OsiBranchingObject * clone() const; 00809 00810 // Destructor 00811 virtual ~OsiSOSBranchingObject (); 00812 00813 using OsiBranchingObject::branch ; 00815 virtual double branch(OsiSolverInterface * solver); 00816 00817 using OsiBranchingObject::print ; 00820 virtual void print(const OsiSolverInterface * solver=NULL); 00821 private: 00823 }; 00827 class OsiLotsize : public OsiObject2 { 00828 00829 public: 00830 00831 // Default Constructor 00832 OsiLotsize (); 00833 00834 /* Useful constructor - passed model index. 00835 Also passed valid values - if range then pairs 00836 */ 00837 OsiLotsize (const OsiSolverInterface * solver, int iColumn, 00838 int numberPoints, const double * points, bool range=false); 00839 00840 // Copy constructor 00841 OsiLotsize ( const OsiLotsize &); 00842 00844 virtual OsiObject * clone() const; 00845 00846 // Assignment operator 00847 OsiLotsize & operator=( const OsiLotsize& rhs); 00848 00849 // Destructor 00850 virtual ~OsiLotsize (); 00851 00852 using OsiObject::infeasibility ; 00854 virtual double infeasibility(const OsiBranchingInformation * info, int & whichWay) const; 00855 00856 using OsiObject::feasibleRegion ; 00864 virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const; 00865 00870 virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) const; 00871 00872 00874 inline void setColumnNumber(int value) 00875 {columnNumber_=value;} 00876 00881 virtual int columnNumber() const; 00887 virtual void resetBounds(const OsiSolverInterface * solver); 00888 00892 bool findRange(double value, double integerTolerance) const; 00893 00896 virtual void floorCeiling(double & floorLotsize, double & ceilingLotsize, double value, 00897 double tolerance) const; 00898 00900 inline double originalLowerBound() const 00901 { return bound_[0];} 00902 inline double originalUpperBound() const 00903 { return bound_[rangeType_*numberRanges_-1];} 00905 inline int rangeType() const 00906 { return rangeType_;} 00908 inline int numberRanges() const 00909 { return numberRanges_;} 00911 inline double * bound() const 00912 { return bound_;} 00915 virtual void resetSequenceEtc(int numberColumns, const int * originalColumns); 00916 00918 virtual double upEstimate() const; 00920 virtual double downEstimate() const; 00922 virtual bool canHandleShadowPrices() const 00923 { return true;} 00926 virtual bool canDoHeuristics() const 00927 {return false;} 00928 00929 private: 00931 00933 int columnNumber_; 00935 int rangeType_; 00937 int numberRanges_; 00938 // largest gap 00939 double largestGap_; 00941 double * bound_; 00943 mutable int range_; 00944 }; 00945 00946 00957 class OsiLotsizeBranchingObject : public OsiTwoWayBranchingObject { 00958 00959 public: 00960 00962 OsiLotsizeBranchingObject (); 00963 00971 OsiLotsizeBranchingObject (OsiSolverInterface *solver,const OsiLotsize * originalObject, 00972 int way , double value) ; 00973 00975 OsiLotsizeBranchingObject ( const OsiLotsizeBranchingObject &); 00976 00978 OsiLotsizeBranchingObject & operator= (const OsiLotsizeBranchingObject& rhs); 00979 00981 virtual OsiBranchingObject * clone() const; 00982 00984 virtual ~OsiLotsizeBranchingObject (); 00985 00986 using OsiBranchingObject::branch ; 00992 virtual double branch(OsiSolverInterface * solver); 00993 00994 using OsiBranchingObject::print ; 00997 virtual void print(const OsiSolverInterface * solver=NULL); 00998 00999 protected: 01001 double down_[2]; 01003 double up_[2]; 01004 }; 01005 #endif