Cbc trunk
CbcTreeLocal.hpp
Go to the documentation of this file.
00001 /* $Id$ */
00002 // Copyright (C) 2004, International Business Machines
00003 // Corporation and others.  All Rights Reserved.
00004 // This code is licensed under the terms of the Eclipse Public License (EPL).
00005 
00006 #ifndef CbcTreeLocal_H
00007 #define CbcTreeLocal_H
00008 
00009 //#############################################################################
00010 /*  This implements (approximately) local branching as in the 2002 paper by
00011     Matteo Fischetti and Andrea Lodi.
00012 
00013     The very simple version of the algorithm for problems with
00014     0-1 variables and continuous is as follows:
00015 
00016     Obtain a feasible solution (one can be passed in).
00017 
00018     Add a cut which limits search to a k neighborhood of this solution.
00019     (At most k 0-1 variables may change value)
00020     Do branch and bound on this problem.
00021 
00022     If finished search and proven optimal then we can reverse cut so
00023     any solutions must be at least k+1 away from solution and we can
00024     add a new cut limiting search to a k neighborhood of new solution
00025     repeat.
00026 
00027     If finished search and no new solution then the simplest version
00028     would reverse last cut and complete search.  The version implemented
00029     here can use time and node limits and can widen search (increase effective k)
00030     .... and more
00031 
00032 */
00033 
00034 #include "CbcTree.hpp"
00035 #include "CbcNode.hpp"
00036 #include "OsiRowCut.hpp"
00037 class CbcModel;
00038 
00039 
00040 class CbcTreeLocal : public CbcTree {
00041 
00042 public:
00043 
00044     // Default Constructor
00045     CbcTreeLocal ();
00046 
00047     /* Constructor with solution.
00048        If solution NULL no solution, otherwise must be integer
00049        range is initial upper bound (k) on difference from given solution.
00050        typeCuts -
00051                 0 means just 0-1 cuts and will need to refine 0-1 solution
00052             1 uses weaker cuts on all integer variables
00053        maxDiversification is maximum number of range widenings to try
00054        timeLimit is seconds in subTree
00055        nodeLimit is nodes in subTree
00056        refine is whether to see if we can prove current solution is optimal
00057        when we fix all 0-1 (in case typeCuts==0 and there are general integer variables)
00058        if false then no refinement but reverse cuts weaker
00059     */
00060     CbcTreeLocal (CbcModel * model, const double * solution , int range = 10,
00061                   int typeCuts = 0, int maxDiversification = 0,
00062                   int timeLimit = 1000000, int nodeLimit = 1000000, bool refine = true);
00063     // Copy constructor
00064     CbcTreeLocal ( const CbcTreeLocal & rhs);
00065 
00066     // = operator
00067     CbcTreeLocal & operator=(const CbcTreeLocal & rhs);
00068 
00069     virtual ~CbcTreeLocal();
00070 
00072     virtual CbcTree * clone() const;
00074     virtual void generateCpp( FILE * fp) ;
00075 
00078 
00080     virtual CbcNode * top() const;
00081 
00083     virtual void push(CbcNode * x);
00084 
00086     virtual void pop() ;
00087 
00089 
00091 
00093     int createCut(const double * solution, OsiRowCut & cut);
00094 
00096     virtual bool empty() ;
00097 
00099     virtual void endSearch() ;
00101     void reverseCut(int state, double bias = 0.0);
00103     void deleteCut(OsiRowCut & cut);
00105     void passInSolution(const double * solution, double solutionValue);
00106     // range i.e. k
00107     inline int range() const {
00108         return range_;
00109     }
00110     // setrange i.e. k
00111     inline void setRange(int value) {
00112         range_ = value;
00113     }
00114     // Type of cuts - 0=just 0-1, 1=all
00115     inline int typeCuts() const {
00116         return typeCuts_;
00117     }
00118     // Type of cuts - 0=just 0-1, 1=all
00119     inline void setTypeCuts(int value) {
00120         typeCuts_ = value;
00121     }
00122     // maximum number of diversifications
00123     inline int maxDiversification() const {
00124         return maxDiversification_;
00125     }
00126     // maximum number of diversifications
00127     inline void setMaxDiversification(int value) {
00128         maxDiversification_ = value;
00129     }
00130     // time limit per subtree
00131     inline int timeLimit() const {
00132         return timeLimit_;
00133     }
00134     // time limit per subtree
00135     inline void setTimeLimit(int value) {
00136         timeLimit_ = value;
00137     }
00138     // node limit for subtree
00139     inline int nodeLimit() const {
00140         return nodeLimit_;
00141     }
00142     // node limit for subtree
00143     inline void setNodeLimit(int value) {
00144         nodeLimit_ = value;
00145     }
00146     // Whether to do refinement step
00147     inline bool refine() const {
00148         return refine_;
00149     }
00150     // Whether to do refinement step
00151     inline void setRefine(bool yesNo) {
00152         refine_ = yesNo;
00153     }
00154 
00156 private:
00157     // Node for local cuts
00158     CbcNode * localNode_;
00159     // best solution
00160     double * bestSolution_;
00161     // saved solution
00162     double * savedSolution_;
00163     // solution number at start of pass
00164     int saveNumberSolutions_;
00165     /* Cut.  If zero size then no solution yet.  Otherwise is left hand branch */
00166     OsiRowCut cut_;
00167     // This cut fixes all 0-1 variables
00168     OsiRowCut fixedCut_;
00169     // Model
00170     CbcModel * model_;
00171     // Original lower bounds
00172     double * originalLower_;
00173     // Original upper bounds
00174     double * originalUpper_;
00175     // range i.e. k
00176     int range_;
00177     // Type of cuts - 0=just 0-1, 1=all
00178     int typeCuts_;
00179     // maximum number of diversifications
00180     int maxDiversification_;
00181     // current diversification
00182     int diversification_;
00183     // Whether next will be strong diversification
00184     bool nextStrong_;
00185     // Current rhs
00186     double rhs_;
00187     // Save allowable gap
00188     double savedGap_;
00189     // Best solution
00190     double bestCutoff_;
00191     // time limit per subtree
00192     int timeLimit_;
00193     // time when subtree started
00194     int startTime_;
00195     // node limit for subtree
00196     int nodeLimit_;
00197     // node count when subtree started
00198     int startNode_;
00199     // -1 not started, 0 == stop on first solution, 1 don't stop on first, 2 refinement step
00200     int searchType_;
00201     // Whether to do refinement step
00202     bool refine_;
00203 
00204 };
00205 
00206 class CbcTreeVariable : public CbcTree {
00207 
00208 public:
00209 
00210     // Default Constructor
00211     CbcTreeVariable ();
00212 
00213     /* Constructor with solution.
00214        If solution NULL no solution, otherwise must be integer
00215        range is initial upper bound (k) on difference from given solution.
00216        typeCuts -
00217                 0 means just 0-1 cuts and will need to refine 0-1 solution
00218             1 uses weaker cuts on all integer variables
00219        maxDiversification is maximum number of range widenings to try
00220        timeLimit is seconds in subTree
00221        nodeLimit is nodes in subTree
00222        refine is whether to see if we can prove current solution is optimal
00223        when we fix all 0-1 (in case typeCuts==0 and there are general integer variables)
00224        if false then no refinement but reverse cuts weaker
00225     */
00226     CbcTreeVariable (CbcModel * model, const double * solution , int range = 10,
00227                      int typeCuts = 0, int maxDiversification = 0,
00228                      int timeLimit = 1000000, int nodeLimit = 1000000, bool refine = true);
00229     // Copy constructor
00230     CbcTreeVariable ( const CbcTreeVariable & rhs);
00231 
00232     // = operator
00233     CbcTreeVariable & operator=(const CbcTreeVariable & rhs);
00234 
00235     virtual ~CbcTreeVariable();
00236 
00238     virtual CbcTree * clone() const;
00240     virtual void generateCpp( FILE * fp) ;
00241 
00244 
00246     virtual CbcNode * top() const;
00247 
00249     virtual void push(CbcNode * x);
00250 
00252     virtual void pop() ;
00253 
00255 
00257 
00259     int createCut(const double * solution, OsiRowCut & cut);
00260 
00262     virtual bool empty() ;
00263 
00265     virtual void endSearch() ;
00267     void reverseCut(int state, double bias = 0.0);
00269     void deleteCut(OsiRowCut & cut);
00271     void passInSolution(const double * solution, double solutionValue);
00272     // range i.e. k
00273     inline int range() const {
00274         return range_;
00275     }
00276     // setrange i.e. k
00277     inline void setRange(int value) {
00278         range_ = value;
00279     }
00280     // Type of cuts - 0=just 0-1, 1=all
00281     inline int typeCuts() const {
00282         return typeCuts_;
00283     }
00284     // Type of cuts - 0=just 0-1, 1=all
00285     inline void setTypeCuts(int value) {
00286         typeCuts_ = value;
00287     }
00288     // maximum number of diversifications
00289     inline int maxDiversification() const {
00290         return maxDiversification_;
00291     }
00292     // maximum number of diversifications
00293     inline void setMaxDiversification(int value) {
00294         maxDiversification_ = value;
00295     }
00296     // time limit per subtree
00297     inline int timeLimit() const {
00298         return timeLimit_;
00299     }
00300     // time limit per subtree
00301     inline void setTimeLimit(int value) {
00302         timeLimit_ = value;
00303     }
00304     // node limit for subtree
00305     inline int nodeLimit() const {
00306         return nodeLimit_;
00307     }
00308     // node limit for subtree
00309     inline void setNodeLimit(int value) {
00310         nodeLimit_ = value;
00311     }
00312     // Whether to do refinement step
00313     inline bool refine() const {
00314         return refine_;
00315     }
00316     // Whether to do refinement step
00317     inline void setRefine(bool yesNo) {
00318         refine_ = yesNo;
00319     }
00320 
00322 private:
00323     // Node for local cuts
00324     CbcNode * localNode_;
00325     // best solution
00326     double * bestSolution_;
00327     // saved solution
00328     double * savedSolution_;
00329     // solution number at start of pass
00330     int saveNumberSolutions_;
00331     /* Cut.  If zero size then no solution yet.  Otherwise is left hand branch */
00332     OsiRowCut cut_;
00333     // This cut fixes all 0-1 variables
00334     OsiRowCut fixedCut_;
00335     // Model
00336     CbcModel * model_;
00337     // Original lower bounds
00338     double * originalLower_;
00339     // Original upper bounds
00340     double * originalUpper_;
00341     // range i.e. k
00342     int range_;
00343     // Type of cuts - 0=just 0-1, 1=all
00344     int typeCuts_;
00345     // maximum number of diversifications
00346     int maxDiversification_;
00347     // current diversification
00348     int diversification_;
00349     // Whether next will be strong diversification
00350     bool nextStrong_;
00351     // Current rhs
00352     double rhs_;
00353     // Save allowable gap
00354     double savedGap_;
00355     // Best solution
00356     double bestCutoff_;
00357     // time limit per subtree
00358     int timeLimit_;
00359     // time when subtree started
00360     int startTime_;
00361     // node limit for subtree
00362     int nodeLimit_;
00363     // node count when subtree started
00364     int startNode_;
00365     // -1 not started, 0 == stop on first solution, 1 don't stop on first, 2 refinement step
00366     int searchType_;
00367     // Whether to do refinement step
00368     bool refine_;
00369 
00370 };
00371 #endif
00372 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines