00001
00002
00003 #ifndef OsiBranchingObject_H
00004 #define OsiBranchingObject_H
00005
00006 #include <cassert>
00007 #include <string>
00008 #include <vector>
00009
00010 #include "CoinError.hpp"
00011
00012 class OsiSolverInterface;
00013 class OsiSolverBranch;
00014
00015 class OsiBranchingObject;
00016 class OsiBranchingInformation;
00017
00018
00019
00020
00021
00022
00053 class OsiObject {
00054
00055 public:
00056
00058 OsiObject ();
00059
00061 OsiObject ( const OsiObject &);
00062
00064 OsiObject & operator=( const OsiObject& rhs);
00065
00067 virtual OsiObject * clone() const=0;
00068
00070 virtual ~OsiObject ();
00071
00093 double infeasibility(const OsiSolverInterface * solver,int &whichWay) const ;
00094
00095 virtual double infeasibility(const OsiBranchingInformation * info, int &whichWay) const =0;
00096
00097 virtual double checkInfeasibility(const OsiBranchingInformation * info) const;
00098
00103 virtual double feasibleRegion(OsiSolverInterface * solver) const ;
00109 virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const =0;
00110
00116 virtual OsiBranchingObject * createBranch(OsiSolverInterface * ,
00117 const OsiBranchingInformation * ,
00118 int ) const {throw CoinError("Need code","createBranch","OsiBranchingObject"); return NULL; }
00119
00122 virtual bool canDoHeuristics() const
00123 {return true;}
00126 virtual bool canMoveToNearest() const
00127 {return false;}
00131 virtual int columnNumber() const;
00133 inline int priority() const
00134 { return priority_;}
00136 inline void setPriority(int priority)
00137 { priority_ = priority;}
00140 virtual bool boundBranch() const
00141 {return true;}
00143 virtual bool canHandleShadowPrices() const
00144 { return false;}
00146 inline int numberWays() const
00147 { return numberWays_;}
00149 inline void setNumberWays(int numberWays)
00150 { numberWays_ = static_cast<short int>(numberWays) ; }
00155 inline void setWhichWay(int way)
00156 { whichWay_ = static_cast<short int>(way) ; }
00161 inline int whichWay() const
00162 { return whichWay_;}
00164 virtual int preferredWay() const
00165 { return -1;}
00167 inline double infeasibility() const
00168 { return infeasibility_;}
00170 virtual double upEstimate() const;
00172 virtual double downEstimate() const;
00177 virtual void resetBounds(const OsiSolverInterface * ) {}
00180 virtual void resetSequenceEtc(int , const int * ) {}
00182 virtual void updateBefore(const OsiObject * ) {}
00184 virtual void updateAfter(const OsiObject * , const OsiObject * ) {}
00185
00186 protected:
00188
00190 mutable double infeasibility_;
00192 mutable short whichWay_;
00194 short numberWays_;
00196 int priority_;
00197
00198 };
00201
00202
00203 class OsiObject2 : public OsiObject {
00204
00205 public:
00206
00208 OsiObject2 ();
00209
00211 OsiObject2 ( const OsiObject2 &);
00212
00214 OsiObject2 & operator=( const OsiObject2& rhs);
00215
00217 virtual ~OsiObject2 ();
00218
00220 inline void setPreferredWay(int value)
00221 {preferredWay_=value;}
00222
00224 virtual int preferredWay() const
00225 { return preferredWay_;}
00226 protected:
00228 int preferredWay_;
00230 mutable double otherInfeasibility_;
00231
00232 };
00233
00251 class OsiBranchingObject {
00252
00253 public:
00254
00256 OsiBranchingObject ();
00257
00259 OsiBranchingObject (OsiSolverInterface * solver, double value);
00260
00262 OsiBranchingObject ( const OsiBranchingObject &);
00263
00265 OsiBranchingObject & operator=( const OsiBranchingObject& rhs);
00266
00268 virtual OsiBranchingObject * clone() const=0;
00269
00271 virtual ~OsiBranchingObject ();
00272
00274 inline int numberBranches() const
00275 {return numberBranches_;}
00276
00278 inline int numberBranchesLeft() const
00279 {return numberBranches_-branchIndex_;}
00280
00282 inline void incrementNumberBranchesLeft()
00283 { numberBranches_ ++;}
00284
00288 inline void setNumberBranchesLeft(int )
00289 { numberBranches_=1;}
00290
00292 inline void decrementNumberBranchesLeft()
00293 {branchIndex_++;}
00294
00300 virtual double branch(OsiSolverInterface * solver)=0;
00306 virtual double branch() {return branch(NULL);}
00309 virtual bool boundBranch() const
00310 {return true;}
00314 inline int branchIndex() const
00315 {return branchIndex_;}
00316
00319 inline void setBranchingIndex(int branchIndex)
00320 { branchIndex_ = static_cast<short int>(branchIndex) ; }
00321
00323 inline double value() const
00324 {return value_;}
00325
00327 inline const OsiObject * originalObject() const
00328 {return originalObject_;}
00330 inline void setOriginalObject(const OsiObject * object)
00331 {originalObject_=object;}
00335 virtual void checkIsCutoff(double ) {}
00337 int columnNumber() const;
00340 virtual void print(const OsiSolverInterface * =NULL) const {}
00341
00342 protected:
00343
00345 double value_;
00346
00348 const OsiObject * originalObject_;
00349
00352 int numberBranches_;
00353
00357 short branchIndex_;
00358
00359 };
00360
00361
00362
00363
00364 class OsiBranchingInformation {
00365
00366 public:
00367
00369 OsiBranchingInformation ();
00370
00375 OsiBranchingInformation (const OsiSolverInterface * solver, bool normalSolver,bool copySolution=false);
00376
00378 OsiBranchingInformation ( const OsiBranchingInformation &);
00379
00381 OsiBranchingInformation & operator=( const OsiBranchingInformation& rhs);
00382
00384 virtual OsiBranchingInformation * clone() const;
00385
00387 virtual ~OsiBranchingInformation ();
00388
00389
00390 public:
00392
00399 int stateOfSearch_;
00401 double objectiveValue_;
00403 double cutoff_;
00405 double direction_;
00407 double integerTolerance_;
00409 double primalTolerance_;
00411 double timeRemaining_;
00413 double defaultDual_;
00415 mutable const OsiSolverInterface * solver_;
00417 int numberColumns_;
00419 mutable const double * lower_;
00421 mutable const double * solution_;
00423 mutable const double * upper_;
00425 const double * hotstartSolution_;
00427 const double * pi_;
00429 const double * rowActivity_;
00431 const double * objective_;
00433 const double * rowLower_;
00435 const double * rowUpper_;
00437 const double * elementByColumn_;
00439 const CoinBigIndex * columnStart_;
00441 const int * columnLength_;
00443 const int * row_;
00449 double * usefulRegion_;
00451 int * indexRegion_;
00453 int numberSolutions_;
00455 int numberBranchingSolutions_;
00457 int depth_;
00459 bool owningSolution_;
00460 };
00461
00463
00464 class OsiTwoWayBranchingObject : public OsiBranchingObject {
00465
00466 public:
00467
00469 OsiTwoWayBranchingObject ();
00470
00477 OsiTwoWayBranchingObject (OsiSolverInterface *solver,const OsiObject * originalObject,
00478 int way , double value) ;
00479
00481 OsiTwoWayBranchingObject ( const OsiTwoWayBranchingObject &);
00482
00484 OsiTwoWayBranchingObject & operator= (const OsiTwoWayBranchingObject& rhs);
00485
00487 virtual ~OsiTwoWayBranchingObject ();
00488
00489 using OsiBranchingObject::branch ;
00495 virtual double branch(OsiSolverInterface * solver)=0;
00496
00497 inline int firstBranch() const { return firstBranch_; }
00499 inline int way() const
00500 { return !branchIndex_ ? firstBranch_ : -firstBranch_;}
00501 protected:
00503 int firstBranch_;
00504 };
00506
00507
00508 class OsiSimpleInteger : public OsiObject2 {
00509
00510 public:
00511
00513 OsiSimpleInteger ();
00514
00516 OsiSimpleInteger (const OsiSolverInterface * solver, int iColumn);
00517
00519 OsiSimpleInteger (int iColumn, double lower, double upper);
00520
00522 OsiSimpleInteger ( const OsiSimpleInteger &);
00523
00525 virtual OsiObject * clone() const;
00526
00528 OsiSimpleInteger & operator=( const OsiSimpleInteger& rhs);
00529
00531 virtual ~OsiSimpleInteger ();
00532
00533 using OsiObject::infeasibility ;
00535 virtual double infeasibility(const OsiBranchingInformation * info, int & whichWay) const;
00536
00537 using OsiObject::feasibleRegion ;
00543 virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const;
00544
00549 virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) const;
00550
00551
00553 inline void setColumnNumber(int value)
00554 {columnNumber_=value;}
00555
00560 virtual int columnNumber() const;
00561
00563 inline double originalLowerBound() const
00564 { return originalLower_;}
00565 inline void setOriginalLowerBound(double value)
00566 { originalLower_=value;}
00567 inline double originalUpperBound() const
00568 { return originalUpper_;}
00569 inline void setOriginalUpperBound(double value)
00570 { originalUpper_=value;}
00575 virtual void resetBounds(const OsiSolverInterface * solver) ;
00578 virtual void resetSequenceEtc(int numberColumns, const int * originalColumns);
00579
00581 virtual double upEstimate() const;
00583 virtual double downEstimate() const;
00585 virtual bool canHandleShadowPrices() const
00586 { return false;}
00587 protected:
00590 double originalLower_;
00592 double originalUpper_;
00594 int columnNumber_;
00595
00596 };
00604 class OsiIntegerBranchingObject : public OsiTwoWayBranchingObject {
00605
00606 public:
00607
00609 OsiIntegerBranchingObject ();
00610
00618 OsiIntegerBranchingObject (OsiSolverInterface *solver,const OsiSimpleInteger * originalObject,
00619 int way , double value) ;
00627 OsiIntegerBranchingObject (OsiSolverInterface *solver,const OsiSimpleInteger * originalObject,
00628 int way , double value, double downUpperBound, double upLowerBound) ;
00629
00631 OsiIntegerBranchingObject ( const OsiIntegerBranchingObject &);
00632
00634 OsiIntegerBranchingObject & operator= (const OsiIntegerBranchingObject& rhs);
00635
00637 virtual OsiBranchingObject * clone() const;
00638
00640 virtual ~OsiIntegerBranchingObject ();
00641
00642 using OsiBranchingObject::branch ;
00648 virtual double branch(OsiSolverInterface * solver);
00649
00650 using OsiBranchingObject::print ;
00653 virtual void print(const OsiSolverInterface * solver=NULL);
00654
00655 protected:
00656
00658 double down_[2];
00660 double up_[2];
00661 };
00662
00663
00671 class OsiSOS : public OsiObject2 {
00672
00673 public:
00674
00675
00676 OsiSOS ();
00677
00682 OsiSOS (const OsiSolverInterface * solver, int numberMembers,
00683 const int * which, const double * weights, int type=1);
00684
00685
00686 OsiSOS ( const OsiSOS &);
00687
00689 virtual OsiObject * clone() const;
00690
00691
00692 OsiSOS & operator=( const OsiSOS& rhs);
00693
00694
00695 virtual ~OsiSOS ();
00696
00697 using OsiObject::infeasibility ;
00699 virtual double infeasibility(const OsiBranchingInformation * info,int & whichWay) const;
00700
00701 using OsiObject::feasibleRegion ;
00707 virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const;
00708
00713 virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) const;
00715 virtual double upEstimate() const;
00717 virtual double downEstimate() const;
00718
00720 virtual void resetSequenceEtc(int numberColumns, const int * originalColumns);
00721
00723 inline int numberMembers() const
00724 {return numberMembers_;}
00725
00727 inline const int * members() const
00728 {return members_;}
00729
00731 inline int sosType() const
00732 {return sosType_;}
00733
00735 inline int setType() const
00736 {return sosType_;}
00737
00739 inline const double * weights() const
00740 { return weights_;}
00741
00744 virtual bool canDoHeuristics() const
00745 {return (sosType_==1&&integerValued_);}
00747 inline void setIntegerValued(bool yesNo)
00748 { integerValued_=yesNo;}
00750 virtual bool canHandleShadowPrices() const
00751 { return true;}
00753 inline void setNumberMembers(int value)
00754 {numberMembers_=value;}
00755
00757 inline int * mutableMembers() const
00758 {return members_;}
00759
00761 inline void setSosType(int value)
00762 {sosType_=value;}
00763
00765 inline double * mutableWeights() const
00766 { return weights_;}
00767 protected:
00769
00771 int * members_;
00773 double * weights_;
00774
00776 int numberMembers_;
00778 int sosType_;
00780 bool integerValued_;
00781 };
00782
00786 class OsiSOSBranchingObject : public OsiTwoWayBranchingObject {
00787
00788 public:
00789
00790
00791 OsiSOSBranchingObject ();
00792
00793
00794 OsiSOSBranchingObject (OsiSolverInterface * solver, const OsiSOS * originalObject,
00795 int way,
00796 double separator);
00797
00798
00799 OsiSOSBranchingObject ( const OsiSOSBranchingObject &);
00800
00801
00802 OsiSOSBranchingObject & operator=( const OsiSOSBranchingObject& rhs);
00803
00805 virtual OsiBranchingObject * clone() const;
00806
00807
00808 virtual ~OsiSOSBranchingObject ();
00809
00810 using OsiBranchingObject::branch ;
00812 virtual double branch(OsiSolverInterface * solver);
00813
00814 using OsiBranchingObject::print ;
00817 virtual void print(const OsiSolverInterface * solver=NULL);
00818 private:
00820 };
00824 class OsiLotsize : public OsiObject2 {
00825
00826 public:
00827
00828
00829 OsiLotsize ();
00830
00831
00832
00833
00834 OsiLotsize (const OsiSolverInterface * solver, int iColumn,
00835 int numberPoints, const double * points, bool range=false);
00836
00837
00838 OsiLotsize ( const OsiLotsize &);
00839
00841 virtual OsiObject * clone() const;
00842
00843
00844 OsiLotsize & operator=( const OsiLotsize& rhs);
00845
00846
00847 ~OsiLotsize ();
00848
00849 using OsiObject::infeasibility ;
00851 virtual double infeasibility(const OsiBranchingInformation * info, int & whichWay) const;
00852
00853 using OsiObject::feasibleRegion ;
00861 virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const;
00862
00867 virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) const;
00868
00869
00871 inline void setColumnNumber(int value)
00872 {columnNumber_=value;}
00873
00878 virtual int columnNumber() const;
00884 virtual void resetBounds(const OsiSolverInterface * solver);
00885
00889 bool findRange(double value, double integerTolerance) const;
00890
00893 virtual void floorCeiling(double & floorLotsize, double & ceilingLotsize, double value,
00894 double tolerance) const;
00895
00897 inline double originalLowerBound() const
00898 { return bound_[0];}
00899 inline double originalUpperBound() const
00900 { return bound_[rangeType_*numberRanges_-1];}
00902 inline int rangeType() const
00903 { return rangeType_;}
00905 inline int numberRanges() const
00906 { return numberRanges_;}
00908 inline double * bound() const
00909 { return bound_;}
00912 virtual void resetSequenceEtc(int numberColumns, const int * originalColumns);
00913
00915 virtual double upEstimate() const;
00917 virtual double downEstimate() const;
00919 virtual bool canHandleShadowPrices() const
00920 { return true;}
00923 virtual bool canDoHeuristics() const
00924 {return false;}
00925
00926 private:
00928
00930 int columnNumber_;
00932 int rangeType_;
00934 int numberRanges_;
00935
00936 double largestGap_;
00938 double * bound_;
00940 mutable int range_;
00941 };
00942
00943
00954 class OsiLotsizeBranchingObject : public OsiTwoWayBranchingObject {
00955
00956 public:
00957
00959 OsiLotsizeBranchingObject ();
00960
00968 OsiLotsizeBranchingObject (OsiSolverInterface *solver,const OsiLotsize * originalObject,
00969 int way , double value) ;
00970
00972 OsiLotsizeBranchingObject ( const OsiLotsizeBranchingObject &);
00973
00975 OsiLotsizeBranchingObject & operator= (const OsiLotsizeBranchingObject& rhs);
00976
00978 virtual OsiBranchingObject * clone() const;
00979
00981 virtual ~OsiLotsizeBranchingObject ();
00982
00983 using OsiBranchingObject::branch ;
00989 virtual double branch(OsiSolverInterface * solver);
00990
00991 using OsiBranchingObject::print ;
00994 virtual void print(const OsiSolverInterface * solver=NULL);
00995
00996 protected:
00998 double down_[2];
01000 double up_[2];
01001 };
01002 #endif