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

- File List
- File Members

# /home/coin/SVN-release/Alps-1.2.1/Osi/src/Osi/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 #include "CoinError.hpp"
    00011
    00012 class OsiSolverInterface;
    00013 class OsiSolverBranch;
    00014
    00015 class OsiBranchingObject;
    00016 class OsiBranchingInformation;
    00017
    00018 //#############################################################################
    00019 //This contains the abstract base class for an object and for branching.
    00020 //It also contains a simple integer class
    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   // Faster version when more information available
    00095   virtual double infeasibility(const OsiBranchingInformation * info, int &whichWay) const =0;
    00096   // This does NOT set mutable stuff
    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 * /*solver*/,
    00117                                             const OsiBranchingInformation * /*info*/,
    00118                                             int /*way*/) 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 /*value*/)
    00289   {/*assert (value==1&&!branchIndex_);*/ 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 /* This contains information
    00361    This could also contain pseudo shadow prices
    00362    or information for dealing with computing and trusting pseudo-costs
    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   // Note public
    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   // Probably could get away with just value which is already stored
    00658   double down_[2];
    00660   double up_[2];
    00661 };
    00662
    00663
    00671 class OsiSOS : public OsiObject2 {
    00672
    00673 public:
    00674
    00675   // Default Constructor
    00676   OsiSOS ();
    00677
    00682   OsiSOS (const OsiSolverInterface * solver, int numberMembers,
    00683            const int * which, const double * weights, int type=1);
    00684
    00685   // Copy constructor
    00686   OsiSOS ( const OsiSOS &);
    00687
    00689   virtual OsiObject * clone() const;
    00690
    00691   // Assignment operator
    00692   OsiSOS & operator=( const OsiSOS& rhs);
    00693
    00694   // Destructor
    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   // Default Constructor
    00791   OsiSOSBranchingObject ();
    00792
    00793   // Useful constructor
    00794   OsiSOSBranchingObject (OsiSolverInterface * solver,  const OsiSOS * originalObject,
    00795                             int way,
    00796                          double separator);
    00797
    00798   // Copy constructor
    00799   OsiSOSBranchingObject ( const OsiSOSBranchingObject &);
    00800
    00801   // Assignment operator
    00802   OsiSOSBranchingObject & operator=( const OsiSOSBranchingObject& rhs);
    00803
    00805   virtual OsiBranchingObject * clone() const;
    00806
    00807   // Destructor
    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   // Default Constructor
    00829   OsiLotsize ();
    00830
    00831   /* Useful constructor - passed model index.
    00832      Also passed valid values - if range then pairs
    00833   */
    00834   OsiLotsize (const OsiSolverInterface * solver, int iColumn,
    00835               int numberPoints, const double * points, bool range=false);
    00836
    00837   // Copy constructor
    00838   OsiLotsize ( const OsiLotsize &);
    00839
    00841   virtual OsiObject * clone() const;
    00842
    00843   // Assignment operator
    00844   OsiLotsize & operator=( const OsiLotsize& rhs);
    00845
    00846   // Destructor
    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   // largest gap
    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