• Main Page
  • Related Pages
  • Namespaces
  • Classes
  • Files
  • File List
  • File Members

/build/buildd/coinor-cbc-2.5.0/Cbc/src/CbcTreeLocal.hpp

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

Generated on Sat Oct 23 2010 23:46:56 by  doxygen 1.7.1