source: stable/2.6/Cbc/src/CbcTreeLocal.hpp @ 2122

Last change on this file since 2122 was 1286, checked in by EdwinStraver, 10 years ago

Changed formatting using AStyle -A4 -p

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 10.9 KB
Line 
1/* $Id: CbcTreeLocal.hpp 1286 2009-11-09 23:33:07Z forrest $ */
2// Copyright (C) 2004, International Business Machines
3// Corporation and others.  All Rights Reserved.
4#ifndef CbcTreeLocal_H
5#define CbcTreeLocal_H
6
7//#############################################################################
8/*  This implements (approximately) local branching as in the 2002 paper by
9    Matteo Fischetti and Andrea Lodi.
10
11    The very simple version of the algorithm for problems with
12    0-1 variables and continuous is as follows:
13
14    Obtain a feasible solution (one can be passed in).
15
16    Add a cut which limits search to a k neighborhood of this solution.
17    (At most k 0-1 variables may change value)
18    Do branch and bound on this problem.
19
20    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
22    add a new cut limiting search to a k neighborhood of new solution
23    repeat.
24
25    If finished search and no new solution then the simplest version
26    would reverse last cut and complete search.  The version implemented
27    here can use time and node limits and can widen search (increase effective k)
28    .... and more
29
30*/
31
32#include "CbcTree.hpp"
33#include "CbcNode.hpp"
34#include "OsiRowCut.hpp"
35class CbcModel;
36
37
38class CbcTreeLocal : public CbcTree {
39
40public:
41
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 */
75//@{
76
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() ;
85
86//@}
87    /*! \name Other stuff */
88//@{
89
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    }
152
153//@}
154private:
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_;
201
202};
203
204class CbcTreeVariable : public CbcTree {
205
206public:
207
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 */
241//@{
242
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() ;
251
252//@}
253    /*! \name Other stuff */
254//@{
255
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    }
318
319//@}
320private:
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_;
367
368};
369#endif
370
Note: See TracBrowser for help on using the repository browser.