- Main Page
- Modules
- Namespaces
- Classes
- Files
- Related Pages

- File List
- File Members

# /home/coin/SVN-release/Blis-0.91.0/Osi/src/OsiBranchingObject.hpp

Go to the documentation of this file.

    00001 // Copyright (C) 2006, International Business Machines
    00002 // Corporation and others.  All Rights Reserved.
    00003 #ifndef OsiBranchingObject_H
    00004 #define OsiBranchingObject_H
    00005
    00006 #include <cassert>
    00007 #include <string>
    00008 #include <vector>
    00009
    00010 class OsiSolverInterface;
    00011 class OsiSolverBranch;
    00012
    00013 class OsiBranchingObject;
    00014 class OsiBranchingInformation;
    00015
    00016 //#############################################################################
    00017 //This contains the abstract base class for an object and for branching.
    00018 //It also contains a simple integer class
    00019 //#############################################################################
    00020
    00051 class OsiObject {
    00052
    00053 public:
    00054
    00056   OsiObject ();
    00057
    00059   OsiObject ( const OsiObject &);
    00060
    00062   OsiObject & operator=( const OsiObject& rhs);
    00063
    00065   virtual OsiObject * clone() const=0;
    00066
    00068   virtual ~OsiObject ();
    00069
    00091   virtual double infeasibility(const OsiSolverInterface * solver,int &whichWay) const ;
    00092   // Faster version when more information available
    00093   virtual double infeasibility(const OsiBranchingInformation * info, int &whichWay) const =0;
    00094   // This does NOT set mutable stuff
    00095   virtual double checkInfeasibility(const OsiBranchingInformation * info) const;
    00096
    00101   virtual double feasibleRegion(OsiSolverInterface * solver) const ;
    00107   virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const =0;
    00108
    00114   virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) const = 0;
    00115
    00118   virtual bool canDoHeuristics() const
    00119   {return true;}
    00122   virtual bool canMoveToNearest() const
    00123   {return false;}
    00127   virtual int columnNumber() const;
    00129   inline int priority() const
    00130   { return priority_;}
    00132   inline void setPriority(int priority)
    00133   { priority_ = priority;}
    00136   virtual bool boundBranch() const
    00137   {return true;}
    00139   virtual bool canHandleShadowPrices() const
    00140   { return false;}
    00142   inline int numberWays() const
    00143   { return numberWays_;}
    00145   inline void setNumberWays(int numberWays)
    00146   { numberWays_ = static_cast<short int>(numberWays) ; }
    00151   inline void setWhichWay(int way)
    00152   { whichWay_ = static_cast<short int>(way) ; }
    00157   inline int whichWay() const
    00158   { return whichWay_;}
    00160   virtual int preferredWay() const
    00161   { return -1;}
    00163   inline double infeasibility() const
    00164   { return infeasibility_;}
    00166   virtual double upEstimate() const;
    00168   virtual double downEstimate() const;
    00173   virtual void resetBounds(const OsiSolverInterface * solver) {}
    00176   virtual void resetSequenceEtc(int numberColumns, const int * originalColumns) {}
    00178   virtual void updateBefore(const OsiObject * rhs) {}
    00180   virtual void updateAfter(const OsiObject * rhs, const OsiObject * baseObject) {}
    00181
    00182 protected:
    00184
    00186   mutable double infeasibility_;
    00188   mutable short whichWay_;
    00190   short  numberWays_;
    00192   int priority_;
    00193
    00194 };
    00197
    00198
    00199 class OsiObject2 : public OsiObject {
    00200
    00201 public:
    00202
    00204   OsiObject2 ();
    00205
    00207   OsiObject2 ( const OsiObject2 &);
    00208
    00210   OsiObject2 & operator=( const OsiObject2& rhs);
    00211
    00213   virtual ~OsiObject2 ();
    00214
    00216   inline void setPreferredWay(int value)
    00217   {preferredWay_=value;}
    00218
    00220   virtual int preferredWay() const
    00221   { return preferredWay_;}
    00222 protected:
    00224   int preferredWay_;
    00226   mutable double otherInfeasibility_;
    00227
    00228 };
    00229
    00247 class OsiBranchingObject {
    00248
    00249 public:
    00250
    00252   OsiBranchingObject ();
    00253
    00255   OsiBranchingObject (OsiSolverInterface * solver, double value);
    00256
    00258   OsiBranchingObject ( const OsiBranchingObject &);
    00259
    00261   OsiBranchingObject & operator=( const OsiBranchingObject& rhs);
    00262
    00264   virtual OsiBranchingObject * clone() const=0;
    00265
    00267   virtual ~OsiBranchingObject ();
    00268
    00270   inline int numberBranches() const
    00271   {return numberBranches_;}
    00272
    00274   inline int numberBranchesLeft() const
    00275   {return numberBranches_-branchIndex_;}
    00276
    00278   inline void incrementNumberBranchesLeft()
    00279   { numberBranches_ ++;}
    00280
    00284   inline void setNumberBranchesLeft(int value)
    00285   {assert (value==1&&!branchIndex_); numberBranches_=1;}
    00286
    00288   inline void decrementNumberBranchesLeft()
    00289   {branchIndex_++;}
    00290
    00296   virtual double branch(OsiSolverInterface * solver)=0;
    00302   virtual double branch() {return branch(NULL);}
    00305   virtual bool boundBranch() const
    00306   {return true;}
    00310   inline int branchIndex() const
    00311   {return branchIndex_;}
    00312
    00315   inline void setBranchingIndex(int branchIndex)
    00316   { branchIndex_ = static_cast<short int>(branchIndex) ; }
    00317
    00319   inline double value() const
    00320   {return value_;}
    00321
    00323   inline const OsiObject * originalObject() const
    00324   {return  originalObject_;}
    00326   inline void setOriginalObject(const OsiObject * object)
    00327   {originalObject_=object;}
    00331   virtual void checkIsCutoff(double cutoff) {}
    00333   int columnNumber() const;
    00336   virtual void print(const OsiSolverInterface * solver=NULL) const {}
    00337
    00338 protected:
    00339
    00341   double value_;
    00342
    00344   const OsiObject * originalObject_;
    00345
    00348   int numberBranches_;
    00349
    00353   short branchIndex_;
    00354
    00355 };
    00356 /* This contains information
    00357    This could also contain pseudo shadow prices
    00358    or information for dealing with computing and trusting pseudo-costs
    00359 */
    00360 class OsiBranchingInformation {
    00361
    00362 public:
    00363
    00365   OsiBranchingInformation ();
    00366
    00371   OsiBranchingInformation (const OsiSolverInterface * solver, bool normalSolver,bool copySolution=false);
    00372
    00374   OsiBranchingInformation ( const OsiBranchingInformation &);
    00375
    00377   OsiBranchingInformation & operator=( const OsiBranchingInformation& rhs);
    00378
    00380   virtual OsiBranchingInformation * clone() const;
    00381
    00383   virtual ~OsiBranchingInformation ();
    00384
    00385   // Note public
    00386 public:
    00388
    00395   int stateOfSearch_;
    00397   double objectiveValue_;
    00399   double cutoff_;
    00401   double direction_;
    00403   double integerTolerance_;
    00405   double primalTolerance_;
    00407   double timeRemaining_;
    00409   double defaultDual_;
    00411   mutable const OsiSolverInterface * solver_;
    00413   int numberColumns_;
    00415   mutable const double * lower_;
    00417   mutable const double * solution_;
    00419   mutable const double * upper_;
    00421   const double * hotstartSolution_;
    00423   const double * pi_;
    00425   const double * rowActivity_;
    00427   const double * objective_;
    00429   const double * rowLower_;
    00431   const double * rowUpper_;
    00433   const double * elementByColumn_;
    00435   const CoinBigIndex * columnStart_;
    00437   const int * columnLength_;
    00439   const int * row_;
    00445   double * usefulRegion_;
    00447   int * indexRegion_;
    00449   int numberSolutions_;
    00451   int numberBranchingSolutions_;
    00453   int depth_;
    00455   bool owningSolution_;
    00456 };
    00457
    00459
    00460 class OsiTwoWayBranchingObject : public OsiBranchingObject {
    00461
    00462 public:
    00463
    00465   OsiTwoWayBranchingObject ();
    00466
    00473   OsiTwoWayBranchingObject (OsiSolverInterface *solver,const OsiObject * originalObject,
    00474                              int way , double value) ;
    00475
    00477   OsiTwoWayBranchingObject ( const OsiTwoWayBranchingObject &);
    00478
    00480   OsiTwoWayBranchingObject & operator= (const OsiTwoWayBranchingObject& rhs);
    00481
    00483   virtual ~OsiTwoWayBranchingObject ();
    00484
    00485   using OsiBranchingObject::branch ;
    00491   virtual double branch(OsiSolverInterface * solver)=0;
    00492
    00493   inline int firstBranch() const { return firstBranch_; }
    00495   inline int way() const
    00496   { return !branchIndex_ ? firstBranch_ : -firstBranch_;}
    00497 protected:
    00499   int firstBranch_;
    00500 };
    00502
    00503
    00504 class OsiSimpleInteger : public OsiObject2 {
    00505
    00506 public:
    00507
    00509   OsiSimpleInteger ();
    00510
    00512   OsiSimpleInteger (const OsiSolverInterface * solver, int iColumn);
    00513
    00515   OsiSimpleInteger (int iColumn, double lower, double upper);
    00516
    00518   OsiSimpleInteger ( const OsiSimpleInteger &);
    00519
    00521   virtual OsiObject * clone() const;
    00522
    00524   OsiSimpleInteger & operator=( const OsiSimpleInteger& rhs);
    00525
    00527   virtual ~OsiSimpleInteger ();
    00528
    00529   using OsiObject::infeasibility ;
    00531   virtual double infeasibility(const OsiBranchingInformation * info, int & whichWay) const;
    00532
    00533   using OsiObject::feasibleRegion ;
    00539   virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const;
    00540
    00545   virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) const;
    00546
    00547
    00549   inline void setColumnNumber(int value)
    00550   {columnNumber_=value;}
    00551
    00556   virtual int columnNumber() const;
    00557
    00559   inline double originalLowerBound() const
    00560   { return originalLower_;}
    00561   inline void setOriginalLowerBound(double value)
    00562   { originalLower_=value;}
    00563   inline double originalUpperBound() const
    00564   { return originalUpper_;}
    00565   inline void setOriginalUpperBound(double value)
    00566   { originalUpper_=value;}
    00571   virtual void resetBounds(const OsiSolverInterface * solver) ;
    00574   virtual void resetSequenceEtc(int numberColumns, const int * originalColumns);
    00575
    00577   virtual double upEstimate() const;
    00579   virtual double downEstimate() const;
    00581   virtual bool canHandleShadowPrices() const
    00582   { return false;}
    00583 protected:
    00586   double originalLower_;
    00588   double originalUpper_;
    00590   int columnNumber_;
    00591
    00592 };
    00600 class OsiIntegerBranchingObject : public OsiTwoWayBranchingObject {
    00601
    00602 public:
    00603
    00605   OsiIntegerBranchingObject ();
    00606
    00614   OsiIntegerBranchingObject (OsiSolverInterface *solver,const OsiSimpleInteger * originalObject,
    00615                              int way , double value) ;
    00623   OsiIntegerBranchingObject (OsiSolverInterface *solver,const OsiSimpleInteger * originalObject,
    00624                              int way , double value, double downUpperBound, double upLowerBound) ;
    00625
    00627   OsiIntegerBranchingObject ( const OsiIntegerBranchingObject &);
    00628
    00630   OsiIntegerBranchingObject & operator= (const OsiIntegerBranchingObject& rhs);
    00631
    00633   virtual OsiBranchingObject * clone() const;
    00634
    00636   virtual ~OsiIntegerBranchingObject ();
    00637
    00638   using OsiBranchingObject::branch ;
    00644   virtual double branch(OsiSolverInterface * solver);
    00645
    00646   using OsiBranchingObject::print ;
    00649   virtual void print(const OsiSolverInterface * solver=NULL);
    00650
    00651 protected:
    00652   // Probably could get away with just value which is already stored
    00654   double down_[2];
    00656   double up_[2];
    00657 };
    00658
    00659
    00667 class OsiSOS : public OsiObject2 {
    00668
    00669 public:
    00670
    00671   // Default Constructor
    00672   OsiSOS ();
    00673
    00678   OsiSOS (const OsiSolverInterface * solver, int numberMembers,
    00679            const int * which, const double * weights, int type=1);
    00680
    00681   // Copy constructor
    00682   OsiSOS ( const OsiSOS &);
    00683
    00685   virtual OsiObject * clone() const;
    00686
    00687   // Assignment operator
    00688   OsiSOS & operator=( const OsiSOS& rhs);
    00689
    00690   // Destructor
    00691   virtual ~OsiSOS ();
    00692
    00693   using OsiObject::infeasibility ;
    00695   virtual double infeasibility(const OsiBranchingInformation * info,int & whichWay) const;
    00696
    00697   using OsiObject::feasibleRegion ;
    00703   virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const;
    00704
    00709   virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) const;
    00711   virtual double upEstimate() const;
    00713   virtual double downEstimate() const;
    00714
    00716   virtual void resetSequenceEtc(int numberColumns, const int * originalColumns);
    00717
    00719   inline int numberMembers() const
    00720   {return numberMembers_;}
    00721
    00723   inline const int * members() const
    00724   {return members_;}
    00725
    00727   inline int sosType() const
    00728   {return sosType_;}
    00729
    00731   inline int setType() const
    00732   {return sosType_;}
    00733
    00735   inline const double * weights() const
    00736   { return weights_;}
    00737
    00740   virtual bool canDoHeuristics() const
    00741   {return (sosType_==1&&integerValued_);}
    00743   inline void setIntegerValued(bool yesNo)
    00744   { integerValued_=yesNo;}
    00746   virtual bool canHandleShadowPrices() const
    00747   { return true;}
    00749   inline void setNumberMembers(int value)
    00750   {numberMembers_=value;}
    00751
    00753   inline int * mutableMembers() const
    00754   {return members_;}
    00755
    00757   inline void setSosType(int value)
    00758   {sosType_=value;}
    00759
    00761   inline  double * mutableWeights() const
    00762   { return weights_;}
    00763 protected:
    00765
    00767   int * members_;
    00769   double * weights_;
    00770
    00772   int numberMembers_;
    00774   int sosType_;
    00776   bool integerValued_;
    00777 };
    00778
    00782 class OsiSOSBranchingObject : public OsiTwoWayBranchingObject {
    00783
    00784 public:
    00785
    00786   // Default Constructor
    00787   OsiSOSBranchingObject ();
    00788
    00789   // Useful constructor
    00790   OsiSOSBranchingObject (OsiSolverInterface * solver,  const OsiSOS * originalObject,
    00791                             int way,
    00792                          double separator);
    00793
    00794   // Copy constructor
    00795   OsiSOSBranchingObject ( const OsiSOSBranchingObject &);
    00796
    00797   // Assignment operator
    00798   OsiSOSBranchingObject & operator=( const OsiSOSBranchingObject& rhs);
    00799
    00801   virtual OsiBranchingObject * clone() const;
    00802
    00803   // Destructor
    00804   virtual ~OsiSOSBranchingObject ();
    00805
    00806   using OsiBranchingObject::branch ;
    00808   virtual double branch(OsiSolverInterface * solver);
    00809
    00810   using OsiBranchingObject::print ;
    00813   virtual void print(const OsiSolverInterface * solver=NULL);
    00814 private:
    00816 };
    00820 class OsiLotsize : public OsiObject2 {
    00821
    00822 public:
    00823
    00824   // Default Constructor
    00825   OsiLotsize ();
    00826
    00827   /* Useful constructor - passed model index.
    00828      Also passed valid values - if range then pairs
    00829   */
    00830   OsiLotsize (const OsiSolverInterface * solver, int iColumn,
    00831               int numberPoints, const double * points, bool range=false);
    00832
    00833   // Copy constructor
    00834   OsiLotsize ( const OsiLotsize &);
    00835
    00837   virtual OsiObject * clone() const;
    00838
    00839   // Assignment operator
    00840   OsiLotsize & operator=( const OsiLotsize& rhs);
    00841
    00842   // Destructor
    00843   ~OsiLotsize ();
    00844
    00845   using OsiObject::infeasibility ;
    00847   virtual double infeasibility(const OsiBranchingInformation * info, int & whichWay) const;
    00848
    00849   using OsiObject::feasibleRegion ;
    00857   virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const;
    00858
    00863   virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) const;
    00864
    00865
    00867   inline void setColumnNumber(int value)
    00868   {columnNumber_=value;}
    00869
    00874   virtual int columnNumber() const;
    00880   virtual void resetBounds(const OsiSolverInterface * solver);
    00881
    00885   bool findRange(double value, double integerTolerance) const;
    00886
    00889   virtual void floorCeiling(double & floorLotsize, double & ceilingLotsize, double value,
    00890                             double tolerance) const;
    00891
    00893   inline double originalLowerBound() const
    00894   { return bound_[0];}
    00895   inline double originalUpperBound() const
    00896   { return bound_[rangeType_*numberRanges_-1];}
    00898   inline int rangeType() const
    00899   { return rangeType_;}
    00901   inline int numberRanges() const
    00902   { return numberRanges_;}
    00904   inline double * bound() const
    00905   { return bound_;}
    00908   virtual void resetSequenceEtc(int numberColumns, const int * originalColumns);
    00909
    00911   virtual double upEstimate() const;
    00913   virtual double downEstimate() const;
    00915   virtual bool canHandleShadowPrices() const
    00916   { return true;}
    00919   virtual bool canDoHeuristics() const
    00920   {return false;}
    00921
    00922 private:
    00924
    00926   int columnNumber_;
    00928   int rangeType_;
    00930   int numberRanges_;
    00931   // largest gap
    00932   double largestGap_;
    00934   double * bound_;
    00936   mutable int range_;
    00937 };
    00938
    00939
    00950 class OsiLotsizeBranchingObject : public OsiTwoWayBranchingObject {
    00951
    00952 public:
    00953
    00955   OsiLotsizeBranchingObject ();
    00956
    00964   OsiLotsizeBranchingObject (OsiSolverInterface *solver,const OsiLotsize * originalObject,
    00965                              int way , double value) ;
    00966
    00968   OsiLotsizeBranchingObject ( const OsiLotsizeBranchingObject &);
    00969
    00971   OsiLotsizeBranchingObject & operator= (const OsiLotsizeBranchingObject& rhs);
    00972
    00974   virtual OsiBranchingObject * clone() const;
    00975
    00977   virtual ~OsiLotsizeBranchingObject ();
    00978
    00979   using OsiBranchingObject::branch ;
    00985   virtual double branch(OsiSolverInterface * solver);
    00986
    00987   using OsiBranchingObject::print ;
    00990   virtual void print(const OsiSolverInterface * solver=NULL);
    00991
    00992 protected:
    00994   double down_[2];
    00996   double up_[2];
    00997 };
    00998 #endif