Osi trunk
OsiBranchingObject.hpp
Go to the documentation of this file.
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   ~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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines