- Main Page
- Namespaces
- Classes
- Files
- Directories

- Search for |

- File List
- File Members

# 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