Ignore:
Timestamp:
Nov 9, 2009 6:33:07 PM (10 years ago)
Author:
EdwinStraver
Message:

Changed formatting using AStyle -A4 -p

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/sandbox/Cbc/src/CbcTreeLocal.hpp

    r1271 r1286  
    99    Matteo Fischetti and Andrea Lodi.
    1010
    11     The very simple version of the algorithm for problems with 
     11    The very simple version of the algorithm for problems with
    1212    0-1 variables and continuous is as follows:
    1313
     
    1919
    2020    If finished search and proven optimal then we can reverse cut so
    21     any solutions must be at least k+1 away from solution and we can 
     21    any solutions must be at least k+1 away from solution and we can
    2222    add a new cut limiting search to a k neighborhood of new solution
    2323    repeat.
    2424
    2525    If finished search and no new solution then the simplest version
    26     would reverse last cut and complete search.  The version implemented 
     26    would reverse last cut and complete search.  The version implemented
    2727    here can use time and node limits and can widen search (increase effective k)
    2828    .... and more
     
    4040public:
    4141
    42   // Default Constructor
    43   CbcTreeLocal ();
    44 
    45   /* Constructor with solution.
    46      If solution NULL no solution, otherwise must be integer
    47      range is initial upper bound (k) on difference from given solution.
    48      typeCuts -
    49               0 means just 0-1 cuts and will need to refine 0-1 solution
    50               1 uses weaker cuts on all integer variables
    51      maxDiversification is maximum number of range widenings to try
    52      timeLimit is seconds in subTree
    53      nodeLimit is nodes in subTree
    54      refine is whether to see if we can prove current solution is optimal
    55      when we fix all 0-1 (in case typeCuts==0 and there are general integer variables)
    56      if false then no refinement but reverse cuts weaker
    57   */
    58   CbcTreeLocal (CbcModel * model,const double * solution ,int range=10,
    59                    int typeCuts=0,int maxDiversification=0,
    60                    int timeLimit=1000000, int nodeLimit=1000000,bool refine=true);
    61   // Copy constructor
    62   CbcTreeLocal ( const CbcTreeLocal & rhs);
    63 
    64   // = operator
    65   CbcTreeLocal & operator=(const CbcTreeLocal & rhs);
    66    
    67   virtual ~CbcTreeLocal();
    68 
    69   /// Clone
    70   virtual CbcTree * clone() const;
    71   /// Create C++ lines to get to current state
    72   virtual void generateCpp( FILE * fp) ;
    73 
    74 /*! \name Heap access and maintenance methods */
     42    // Default Constructor
     43    CbcTreeLocal ();
     44
     45    /* Constructor with solution.
     46       If solution NULL no solution, otherwise must be integer
     47       range is initial upper bound (k) on difference from given solution.
     48       typeCuts -
     49                0 means just 0-1 cuts and will need to refine 0-1 solution
     50            1 uses weaker cuts on all integer variables
     51       maxDiversification is maximum number of range widenings to try
     52       timeLimit is seconds in subTree
     53       nodeLimit is nodes in subTree
     54       refine is whether to see if we can prove current solution is optimal
     55       when we fix all 0-1 (in case typeCuts==0 and there are general integer variables)
     56       if false then no refinement but reverse cuts weaker
     57    */
     58    CbcTreeLocal (CbcModel * model, const double * solution , int range = 10,
     59                  int typeCuts = 0, int maxDiversification = 0,
     60                  int timeLimit = 1000000, int nodeLimit = 1000000, bool refine = true);
     61    // Copy constructor
     62    CbcTreeLocal ( const CbcTreeLocal & rhs);
     63
     64    // = operator
     65    CbcTreeLocal & operator=(const CbcTreeLocal & rhs);
     66
     67    virtual ~CbcTreeLocal();
     68
     69    /// Clone
     70    virtual CbcTree * clone() const;
     71    /// Create C++ lines to get to current state
     72    virtual void generateCpp( FILE * fp) ;
     73
     74    /*! \name Heap access and maintenance methods */
    7575//@{
    7676
    77   /// Return the top node of the heap
    78   virtual CbcNode * top() const;
    79 
    80   /// Add a node to the heap
    81   virtual void push(CbcNode * x);
    82 
    83   /// Remove the top node from the heap
    84   virtual void pop() ;
     77    /// Return the top node of the heap
     78    virtual CbcNode * top() const;
     79
     80    /// Add a node to the heap
     81    virtual void push(CbcNode * x);
     82
     83    /// Remove the top node from the heap
     84    virtual void pop() ;
    8585
    8686//@}
    87 /*! \name Other stuff */
     87    /*! \name Other stuff */
    8888//@{
    8989
    90   /// Create cut - return -1 if bad, 0 if okay and 1 if cut is everything
    91   int createCut(const double * solution, OsiRowCut & cut);
    92 
    93   /// Test if empty *** note may be overridden
    94   virtual bool empty() ;
    95 
    96   /// We may have got an intelligent tree so give it one more chance
    97   virtual void endSearch() ;
    98   /// Other side of last cut branch (if bias==rhs_ will be weakest possible)
    99   void reverseCut(int state, double bias=0.0);
    100   /// Delete last cut branch
    101   void deleteCut(OsiRowCut & cut);
    102   /// Pass in solution (so can be used after heuristic)
    103   void passInSolution(const double * solution, double solutionValue);
    104   // range i.e. k
    105   inline int range() const
    106   { return range_;}
    107   // setrange i.e. k
    108   inline void setRange(int value)
    109   { range_ = value;}
    110   // Type of cuts - 0=just 0-1, 1=all
    111   inline int typeCuts() const
    112   { return typeCuts_;}
    113   // Type of cuts - 0=just 0-1, 1=all
    114   inline void setTypeCuts(int value)
    115   { typeCuts_ = value;}
    116   // maximum number of diversifications
    117   inline int maxDiversification() const
    118   { return maxDiversification_;}
    119   // maximum number of diversifications
    120   inline void setMaxDiversification(int value)
    121   { maxDiversification_ = value;}
    122   // time limit per subtree
    123   inline int timeLimit() const
    124   { return timeLimit_;}
    125   // time limit per subtree
    126   inline void setTimeLimit(int value)
    127   { timeLimit_ = value;}
    128   // node limit for subtree
    129   inline int nodeLimit() const
    130   { return nodeLimit_;}
    131   // node limit for subtree
    132   inline void setNodeLimit(int value)
    133   { nodeLimit_ = value;}
    134   // Whether to do refinement step
    135   inline bool refine() const
    136   { return refine_;}
    137   // Whether to do refinement step
    138   inline void setRefine(bool yesNo)
    139     { refine_ = yesNo;}
     90    /// Create cut - return -1 if bad, 0 if okay and 1 if cut is everything
     91    int createCut(const double * solution, OsiRowCut & cut);
     92
     93    /// Test if empty *** note may be overridden
     94    virtual bool empty() ;
     95
     96    /// We may have got an intelligent tree so give it one more chance
     97    virtual void endSearch() ;
     98    /// Other side of last cut branch (if bias==rhs_ will be weakest possible)
     99    void reverseCut(int state, double bias = 0.0);
     100    /// Delete last cut branch
     101    void deleteCut(OsiRowCut & cut);
     102    /// Pass in solution (so can be used after heuristic)
     103    void passInSolution(const double * solution, double solutionValue);
     104    // range i.e. k
     105    inline int range() const {
     106        return range_;
     107    }
     108    // setrange i.e. k
     109    inline void setRange(int value) {
     110        range_ = value;
     111    }
     112    // Type of cuts - 0=just 0-1, 1=all
     113    inline int typeCuts() const {
     114        return typeCuts_;
     115    }
     116    // Type of cuts - 0=just 0-1, 1=all
     117    inline void setTypeCuts(int value) {
     118        typeCuts_ = value;
     119    }
     120    // maximum number of diversifications
     121    inline int maxDiversification() const {
     122        return maxDiversification_;
     123    }
     124    // maximum number of diversifications
     125    inline void setMaxDiversification(int value) {
     126        maxDiversification_ = value;
     127    }
     128    // time limit per subtree
     129    inline int timeLimit() const {
     130        return timeLimit_;
     131    }
     132    // time limit per subtree
     133    inline void setTimeLimit(int value) {
     134        timeLimit_ = value;
     135    }
     136    // node limit for subtree
     137    inline int nodeLimit() const {
     138        return nodeLimit_;
     139    }
     140    // node limit for subtree
     141    inline void setNodeLimit(int value) {
     142        nodeLimit_ = value;
     143    }
     144    // Whether to do refinement step
     145    inline bool refine() const {
     146        return refine_;
     147    }
     148    // Whether to do refinement step
     149    inline void setRefine(bool yesNo) {
     150        refine_ = yesNo;
     151    }
    140152
    141153//@}
    142154private:
    143   // Node for local cuts
    144   CbcNode * localNode_;
    145   // best solution
    146   double * bestSolution_;
    147   // saved solution
    148   double * savedSolution_;
    149   // solution number at start of pass
    150   int saveNumberSolutions_;
    151   /* Cut.  If zero size then no solution yet.  Otherwise is left hand branch */
    152   OsiRowCut cut_;
    153   // This cut fixes all 0-1 variables
    154   OsiRowCut fixedCut_;
    155   // Model
    156   CbcModel * model_;
    157   // Original lower bounds
    158   double * originalLower_;
    159   // Original upper bounds
    160   double * originalUpper_;
    161   // range i.e. k
    162   int range_;
    163   // Type of cuts - 0=just 0-1, 1=all
    164   int typeCuts_;
    165   // maximum number of diversifications
    166   int maxDiversification_;
    167   // current diversification
    168   int diversification_;
    169   // Whether next will be strong diversification
    170   bool nextStrong_;
    171   // Current rhs
    172   double rhs_;
    173   // Save allowable gap
    174   double savedGap_;
    175   // Best solution
    176   double bestCutoff_;
    177   // time limit per subtree
    178   int timeLimit_;
    179   // time when subtree started
    180   int startTime_;
    181   // node limit for subtree
    182   int nodeLimit_;
    183   // node count when subtree started
    184   int startNode_;
    185   // -1 not started, 0 == stop on first solution, 1 don't stop on first, 2 refinement step
    186   int searchType_;
    187   // Whether to do refinement step
    188   bool refine_;
     155    // Node for local cuts
     156    CbcNode * localNode_;
     157    // best solution
     158    double * bestSolution_;
     159    // saved solution
     160    double * savedSolution_;
     161    // solution number at start of pass
     162    int saveNumberSolutions_;
     163    /* Cut.  If zero size then no solution yet.  Otherwise is left hand branch */
     164    OsiRowCut cut_;
     165    // This cut fixes all 0-1 variables
     166    OsiRowCut fixedCut_;
     167    // Model
     168    CbcModel * model_;
     169    // Original lower bounds
     170    double * originalLower_;
     171    // Original upper bounds
     172    double * originalUpper_;
     173    // range i.e. k
     174    int range_;
     175    // Type of cuts - 0=just 0-1, 1=all
     176    int typeCuts_;
     177    // maximum number of diversifications
     178    int maxDiversification_;
     179    // current diversification
     180    int diversification_;
     181    // Whether next will be strong diversification
     182    bool nextStrong_;
     183    // Current rhs
     184    double rhs_;
     185    // Save allowable gap
     186    double savedGap_;
     187    // Best solution
     188    double bestCutoff_;
     189    // time limit per subtree
     190    int timeLimit_;
     191    // time when subtree started
     192    int startTime_;
     193    // node limit for subtree
     194    int nodeLimit_;
     195    // node count when subtree started
     196    int startNode_;
     197    // -1 not started, 0 == stop on first solution, 1 don't stop on first, 2 refinement step
     198    int searchType_;
     199    // Whether to do refinement step
     200    bool refine_;
    189201
    190202};
     
    194206public:
    195207
    196   // Default Constructor
    197   CbcTreeVariable ();
    198 
    199   /* Constructor with solution.
    200      If solution NULL no solution, otherwise must be integer
    201      range is initial upper bound (k) on difference from given solution.
    202      typeCuts -
    203               0 means just 0-1 cuts and will need to refine 0-1 solution
    204               1 uses weaker cuts on all integer variables
    205      maxDiversification is maximum number of range widenings to try
    206      timeLimit is seconds in subTree
    207      nodeLimit is nodes in subTree
    208      refine is whether to see if we can prove current solution is optimal
    209      when we fix all 0-1 (in case typeCuts==0 and there are general integer variables)
    210      if false then no refinement but reverse cuts weaker
    211   */
    212   CbcTreeVariable (CbcModel * model,const double * solution ,int range=10,
    213                    int typeCuts=0,int maxDiversification=0,
    214                    int timeLimit=1000000, int nodeLimit=1000000,bool refine=true);
    215   // Copy constructor
    216   CbcTreeVariable ( const CbcTreeVariable & rhs);
    217 
    218   // = operator
    219   CbcTreeVariable & operator=(const CbcTreeVariable & rhs);
    220    
    221   virtual ~CbcTreeVariable();
    222 
    223   /// Clone
    224   virtual CbcTree * clone() const;
    225   /// Create C++ lines to get to current state
    226   virtual void generateCpp( FILE * fp) ;
    227 
    228 /*! \name Heap access and maintenance methods */
     208    // Default Constructor
     209    CbcTreeVariable ();
     210
     211    /* Constructor with solution.
     212       If solution NULL no solution, otherwise must be integer
     213       range is initial upper bound (k) on difference from given solution.
     214       typeCuts -
     215                0 means just 0-1 cuts and will need to refine 0-1 solution
     216            1 uses weaker cuts on all integer variables
     217       maxDiversification is maximum number of range widenings to try
     218       timeLimit is seconds in subTree
     219       nodeLimit is nodes in subTree
     220       refine is whether to see if we can prove current solution is optimal
     221       when we fix all 0-1 (in case typeCuts==0 and there are general integer variables)
     222       if false then no refinement but reverse cuts weaker
     223    */
     224    CbcTreeVariable (CbcModel * model, const double * solution , int range = 10,
     225                     int typeCuts = 0, int maxDiversification = 0,
     226                     int timeLimit = 1000000, int nodeLimit = 1000000, bool refine = true);
     227    // Copy constructor
     228    CbcTreeVariable ( const CbcTreeVariable & rhs);
     229
     230    // = operator
     231    CbcTreeVariable & operator=(const CbcTreeVariable & rhs);
     232
     233    virtual ~CbcTreeVariable();
     234
     235    /// Clone
     236    virtual CbcTree * clone() const;
     237    /// Create C++ lines to get to current state
     238    virtual void generateCpp( FILE * fp) ;
     239
     240    /*! \name Heap access and maintenance methods */
    229241//@{
    230242
    231   /// Return the top node of the heap
    232   virtual CbcNode * top() const;
    233 
    234   /// Add a node to the heap
    235   virtual void push(CbcNode * x);
    236 
    237   /// Remove the top node from the heap
    238   virtual void pop() ;
     243    /// Return the top node of the heap
     244    virtual CbcNode * top() const;
     245
     246    /// Add a node to the heap
     247    virtual void push(CbcNode * x);
     248
     249    /// Remove the top node from the heap
     250    virtual void pop() ;
    239251
    240252//@}
    241 /*! \name Other stuff */
     253    /*! \name Other stuff */
    242254//@{
    243255
    244   /// Create cut - return -1 if bad, 0 if okay and 1 if cut is everything
    245   int createCut(const double * solution, OsiRowCut & cut);
    246 
    247   /// Test if empty *** note may be overridden
    248   virtual bool empty() ;
    249 
    250   /// We may have got an intelligent tree so give it one more chance
    251   virtual void endSearch() ;
    252   /// Other side of last cut branch (if bias==rhs_ will be weakest possible)
    253   void reverseCut(int state, double bias=0.0);
    254   /// Delete last cut branch
    255   void deleteCut(OsiRowCut & cut);
    256   /// Pass in solution (so can be used after heuristic)
    257   void passInSolution(const double * solution, double solutionValue);
    258   // range i.e. k
    259   inline int range() const
    260   { return range_;}
    261   // setrange i.e. k
    262   inline void setRange(int value)
    263   { range_ = value;}
    264   // Type of cuts - 0=just 0-1, 1=all
    265   inline int typeCuts() const
    266   { return typeCuts_;}
    267   // Type of cuts - 0=just 0-1, 1=all
    268   inline void setTypeCuts(int value)
    269   { typeCuts_ = value;}
    270   // maximum number of diversifications
    271   inline int maxDiversification() const
    272   { return maxDiversification_;}
    273   // maximum number of diversifications
    274   inline void setMaxDiversification(int value)
    275   { maxDiversification_ = value;}
    276   // time limit per subtree
    277   inline int timeLimit() const
    278   { return timeLimit_;}
    279   // time limit per subtree
    280   inline void setTimeLimit(int value)
    281   { timeLimit_ = value;}
    282   // node limit for subtree
    283   inline int nodeLimit() const
    284   { return nodeLimit_;}
    285   // node limit for subtree
    286   inline void setNodeLimit(int value)
    287   { nodeLimit_ = value;}
    288   // Whether to do refinement step
    289   inline bool refine() const
    290   { return refine_;}
    291   // Whether to do refinement step
    292   inline void setRefine(bool yesNo)
    293     { refine_ = yesNo;}
     256    /// Create cut - return -1 if bad, 0 if okay and 1 if cut is everything
     257    int createCut(const double * solution, OsiRowCut & cut);
     258
     259    /// Test if empty *** note may be overridden
     260    virtual bool empty() ;
     261
     262    /// We may have got an intelligent tree so give it one more chance
     263    virtual void endSearch() ;
     264    /// Other side of last cut branch (if bias==rhs_ will be weakest possible)
     265    void reverseCut(int state, double bias = 0.0);
     266    /// Delete last cut branch
     267    void deleteCut(OsiRowCut & cut);
     268    /// Pass in solution (so can be used after heuristic)
     269    void passInSolution(const double * solution, double solutionValue);
     270    // range i.e. k
     271    inline int range() const {
     272        return range_;
     273    }
     274    // setrange i.e. k
     275    inline void setRange(int value) {
     276        range_ = value;
     277    }
     278    // Type of cuts - 0=just 0-1, 1=all
     279    inline int typeCuts() const {
     280        return typeCuts_;
     281    }
     282    // Type of cuts - 0=just 0-1, 1=all
     283    inline void setTypeCuts(int value) {
     284        typeCuts_ = value;
     285    }
     286    // maximum number of diversifications
     287    inline int maxDiversification() const {
     288        return maxDiversification_;
     289    }
     290    // maximum number of diversifications
     291    inline void setMaxDiversification(int value) {
     292        maxDiversification_ = value;
     293    }
     294    // time limit per subtree
     295    inline int timeLimit() const {
     296        return timeLimit_;
     297    }
     298    // time limit per subtree
     299    inline void setTimeLimit(int value) {
     300        timeLimit_ = value;
     301    }
     302    // node limit for subtree
     303    inline int nodeLimit() const {
     304        return nodeLimit_;
     305    }
     306    // node limit for subtree
     307    inline void setNodeLimit(int value) {
     308        nodeLimit_ = value;
     309    }
     310    // Whether to do refinement step
     311    inline bool refine() const {
     312        return refine_;
     313    }
     314    // Whether to do refinement step
     315    inline void setRefine(bool yesNo) {
     316        refine_ = yesNo;
     317    }
    294318
    295319//@}
    296320private:
    297   // Node for local cuts
    298   CbcNode * localNode_;
    299   // best solution
    300   double * bestSolution_;
    301   // saved solution
    302   double * savedSolution_;
    303   // solution number at start of pass
    304   int saveNumberSolutions_;
    305   /* Cut.  If zero size then no solution yet.  Otherwise is left hand branch */
    306   OsiRowCut cut_;
    307   // This cut fixes all 0-1 variables
    308   OsiRowCut fixedCut_;
    309   // Model
    310   CbcModel * model_;
    311   // Original lower bounds
    312   double * originalLower_;
    313   // Original upper bounds
    314   double * originalUpper_;
    315   // range i.e. k
    316   int range_;
    317   // Type of cuts - 0=just 0-1, 1=all
    318   int typeCuts_;
    319   // maximum number of diversifications
    320   int maxDiversification_;
    321   // current diversification
    322   int diversification_;
    323   // Whether next will be strong diversification
    324   bool nextStrong_;
    325   // Current rhs
    326   double rhs_;
    327   // Save allowable gap
    328   double savedGap_;
    329   // Best solution
    330   double bestCutoff_;
    331   // time limit per subtree
    332   int timeLimit_;
    333   // time when subtree started
    334   int startTime_;
    335   // node limit for subtree
    336   int nodeLimit_;
    337   // node count when subtree started
    338   int startNode_;
    339   // -1 not started, 0 == stop on first solution, 1 don't stop on first, 2 refinement step
    340   int searchType_;
    341   // Whether to do refinement step
    342   bool refine_;
     321    // Node for local cuts
     322    CbcNode * localNode_;
     323    // best solution
     324    double * bestSolution_;
     325    // saved solution
     326    double * savedSolution_;
     327    // solution number at start of pass
     328    int saveNumberSolutions_;
     329    /* Cut.  If zero size then no solution yet.  Otherwise is left hand branch */
     330    OsiRowCut cut_;
     331    // This cut fixes all 0-1 variables
     332    OsiRowCut fixedCut_;
     333    // Model
     334    CbcModel * model_;
     335    // Original lower bounds
     336    double * originalLower_;
     337    // Original upper bounds
     338    double * originalUpper_;
     339    // range i.e. k
     340    int range_;
     341    // Type of cuts - 0=just 0-1, 1=all
     342    int typeCuts_;
     343    // maximum number of diversifications
     344    int maxDiversification_;
     345    // current diversification
     346    int diversification_;
     347    // Whether next will be strong diversification
     348    bool nextStrong_;
     349    // Current rhs
     350    double rhs_;
     351    // Save allowable gap
     352    double savedGap_;
     353    // Best solution
     354    double bestCutoff_;
     355    // time limit per subtree
     356    int timeLimit_;
     357    // time when subtree started
     358    int startTime_;
     359    // node limit for subtree
     360    int nodeLimit_;
     361    // node count when subtree started
     362    int startNode_;
     363    // -1 not started, 0 == stop on first solution, 1 don't stop on first, 2 refinement step
     364    int searchType_;
     365    // Whether to do refinement step
     366    bool refine_;
    343367
    344368};
Note: See TracChangeset for help on using the changeset viewer.