# CbcTreeLocal.hpp

Go to the documentation of this file.

    00001 /* $Id: CbcTreeLocal.hpp 1573 2011-01-05 01:12:36Z lou $ */
    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