source: stable/2.8/Cbc/src/CbcTreeLocal.hpp @ 1870

Last change on this file since 1870 was 1573, checked in by lou, 9 years ago

Change to EPL license notice.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 11.0 KB
Line 
1/* $Id: CbcTreeLocal.hpp 1573 2011-01-05 01:12:36Z forrest $ */
2// Copyright (C) 2004, International Business Machines
3// Corporation and others.  All Rights Reserved.
4// This code is licensed under the terms of the Eclipse Public License (EPL).
5
6#ifndef CbcTreeLocal_H
7#define CbcTreeLocal_H
8
9//#############################################################################
10/*  This implements (approximately) local branching as in the 2002 paper by
11    Matteo Fischetti and Andrea Lodi.
12
13    The very simple version of the algorithm for problems with
14    0-1 variables and continuous is as follows:
15
16    Obtain a feasible solution (one can be passed in).
17
18    Add a cut which limits search to a k neighborhood of this solution.
19    (At most k 0-1 variables may change value)
20    Do branch and bound on this problem.
21
22    If finished search and proven optimal then we can reverse cut so
23    any solutions must be at least k+1 away from solution and we can
24    add a new cut limiting search to a k neighborhood of new solution
25    repeat.
26
27    If finished search and no new solution then the simplest version
28    would reverse last cut and complete search.  The version implemented
29    here can use time and node limits and can widen search (increase effective k)
30    .... and more
31
32*/
33
34#include "CbcTree.hpp"
35#include "CbcNode.hpp"
36#include "OsiRowCut.hpp"
37class CbcModel;
38
39
40class CbcTreeLocal : public CbcTree {
41
42public:
43
44    // Default Constructor
45    CbcTreeLocal ();
46
47    /* Constructor with solution.
48       If solution NULL no solution, otherwise must be integer
49       range is initial upper bound (k) on difference from given solution.
50       typeCuts -
51                0 means just 0-1 cuts and will need to refine 0-1 solution
52            1 uses weaker cuts on all integer variables
53       maxDiversification is maximum number of range widenings to try
54       timeLimit is seconds in subTree
55       nodeLimit is nodes in subTree
56       refine is whether to see if we can prove current solution is optimal
57       when we fix all 0-1 (in case typeCuts==0 and there are general integer variables)
58       if false then no refinement but reverse cuts weaker
59    */
60    CbcTreeLocal (CbcModel * model, const double * solution , int range = 10,
61                  int typeCuts = 0, int maxDiversification = 0,
62                  int timeLimit = 1000000, int nodeLimit = 1000000, bool refine = true);
63    // Copy constructor
64    CbcTreeLocal ( const CbcTreeLocal & rhs);
65
66    // = operator
67    CbcTreeLocal & operator=(const CbcTreeLocal & rhs);
68
69    virtual ~CbcTreeLocal();
70
71    /// Clone
72    virtual CbcTree * clone() const;
73    /// Create C++ lines to get to current state
74    virtual void generateCpp( FILE * fp) ;
75
76    /*! \name Heap access and maintenance methods */
77//@{
78
79    /// Return the top node of the heap
80    virtual CbcNode * top() const;
81
82    /// Add a node to the heap
83    virtual void push(CbcNode * x);
84
85    /// Remove the top node from the heap
86    virtual void pop() ;
87
88//@}
89    /*! \name Other stuff */
90//@{
91
92    /// Create cut - return -1 if bad, 0 if okay and 1 if cut is everything
93    int createCut(const double * solution, OsiRowCut & cut);
94
95    /// Test if empty *** note may be overridden
96    virtual bool empty() ;
97
98    /// We may have got an intelligent tree so give it one more chance
99    virtual void endSearch() ;
100    /// Other side of last cut branch (if bias==rhs_ will be weakest possible)
101    void reverseCut(int state, double bias = 0.0);
102    /// Delete last cut branch
103    void deleteCut(OsiRowCut & cut);
104    /// Pass in solution (so can be used after heuristic)
105    void passInSolution(const double * solution, double solutionValue);
106    // range i.e. k
107    inline int range() const {
108        return range_;
109    }
110    // setrange i.e. k
111    inline void setRange(int value) {
112        range_ = value;
113    }
114    // Type of cuts - 0=just 0-1, 1=all
115    inline int typeCuts() const {
116        return typeCuts_;
117    }
118    // Type of cuts - 0=just 0-1, 1=all
119    inline void setTypeCuts(int value) {
120        typeCuts_ = value;
121    }
122    // maximum number of diversifications
123    inline int maxDiversification() const {
124        return maxDiversification_;
125    }
126    // maximum number of diversifications
127    inline void setMaxDiversification(int value) {
128        maxDiversification_ = value;
129    }
130    // time limit per subtree
131    inline int timeLimit() const {
132        return timeLimit_;
133    }
134    // time limit per subtree
135    inline void setTimeLimit(int value) {
136        timeLimit_ = value;
137    }
138    // node limit for subtree
139    inline int nodeLimit() const {
140        return nodeLimit_;
141    }
142    // node limit for subtree
143    inline void setNodeLimit(int value) {
144        nodeLimit_ = value;
145    }
146    // Whether to do refinement step
147    inline bool refine() const {
148        return refine_;
149    }
150    // Whether to do refinement step
151    inline void setRefine(bool yesNo) {
152        refine_ = yesNo;
153    }
154
155//@}
156private:
157    // Node for local cuts
158    CbcNode * localNode_;
159    // best solution
160    double * bestSolution_;
161    // saved solution
162    double * savedSolution_;
163    // solution number at start of pass
164    int saveNumberSolutions_;
165    /* Cut.  If zero size then no solution yet.  Otherwise is left hand branch */
166    OsiRowCut cut_;
167    // This cut fixes all 0-1 variables
168    OsiRowCut fixedCut_;
169    // Model
170    CbcModel * model_;
171    // Original lower bounds
172    double * originalLower_;
173    // Original upper bounds
174    double * originalUpper_;
175    // range i.e. k
176    int range_;
177    // Type of cuts - 0=just 0-1, 1=all
178    int typeCuts_;
179    // maximum number of diversifications
180    int maxDiversification_;
181    // current diversification
182    int diversification_;
183    // Whether next will be strong diversification
184    bool nextStrong_;
185    // Current rhs
186    double rhs_;
187    // Save allowable gap
188    double savedGap_;
189    // Best solution
190    double bestCutoff_;
191    // time limit per subtree
192    int timeLimit_;
193    // time when subtree started
194    int startTime_;
195    // node limit for subtree
196    int nodeLimit_;
197    // node count when subtree started
198    int startNode_;
199    // -1 not started, 0 == stop on first solution, 1 don't stop on first, 2 refinement step
200    int searchType_;
201    // Whether to do refinement step
202    bool refine_;
203
204};
205
206class CbcTreeVariable : public CbcTree {
207
208public:
209
210    // Default Constructor
211    CbcTreeVariable ();
212
213    /* Constructor with solution.
214       If solution NULL no solution, otherwise must be integer
215       range is initial upper bound (k) on difference from given solution.
216       typeCuts -
217                0 means just 0-1 cuts and will need to refine 0-1 solution
218            1 uses weaker cuts on all integer variables
219       maxDiversification is maximum number of range widenings to try
220       timeLimit is seconds in subTree
221       nodeLimit is nodes in subTree
222       refine is whether to see if we can prove current solution is optimal
223       when we fix all 0-1 (in case typeCuts==0 and there are general integer variables)
224       if false then no refinement but reverse cuts weaker
225    */
226    CbcTreeVariable (CbcModel * model, const double * solution , int range = 10,
227                     int typeCuts = 0, int maxDiversification = 0,
228                     int timeLimit = 1000000, int nodeLimit = 1000000, bool refine = true);
229    // Copy constructor
230    CbcTreeVariable ( const CbcTreeVariable & rhs);
231
232    // = operator
233    CbcTreeVariable & operator=(const CbcTreeVariable & rhs);
234
235    virtual ~CbcTreeVariable();
236
237    /// Clone
238    virtual CbcTree * clone() const;
239    /// Create C++ lines to get to current state
240    virtual void generateCpp( FILE * fp) ;
241
242    /*! \name Heap access and maintenance methods */
243//@{
244
245    /// Return the top node of the heap
246    virtual CbcNode * top() const;
247
248    /// Add a node to the heap
249    virtual void push(CbcNode * x);
250
251    /// Remove the top node from the heap
252    virtual void pop() ;
253
254//@}
255    /*! \name Other stuff */
256//@{
257
258    /// Create cut - return -1 if bad, 0 if okay and 1 if cut is everything
259    int createCut(const double * solution, OsiRowCut & cut);
260
261    /// Test if empty *** note may be overridden
262    virtual bool empty() ;
263
264    /// We may have got an intelligent tree so give it one more chance
265    virtual void endSearch() ;
266    /// Other side of last cut branch (if bias==rhs_ will be weakest possible)
267    void reverseCut(int state, double bias = 0.0);
268    /// Delete last cut branch
269    void deleteCut(OsiRowCut & cut);
270    /// Pass in solution (so can be used after heuristic)
271    void passInSolution(const double * solution, double solutionValue);
272    // range i.e. k
273    inline int range() const {
274        return range_;
275    }
276    // setrange i.e. k
277    inline void setRange(int value) {
278        range_ = value;
279    }
280    // Type of cuts - 0=just 0-1, 1=all
281    inline int typeCuts() const {
282        return typeCuts_;
283    }
284    // Type of cuts - 0=just 0-1, 1=all
285    inline void setTypeCuts(int value) {
286        typeCuts_ = value;
287    }
288    // maximum number of diversifications
289    inline int maxDiversification() const {
290        return maxDiversification_;
291    }
292    // maximum number of diversifications
293    inline void setMaxDiversification(int value) {
294        maxDiversification_ = value;
295    }
296    // time limit per subtree
297    inline int timeLimit() const {
298        return timeLimit_;
299    }
300    // time limit per subtree
301    inline void setTimeLimit(int value) {
302        timeLimit_ = value;
303    }
304    // node limit for subtree
305    inline int nodeLimit() const {
306        return nodeLimit_;
307    }
308    // node limit for subtree
309    inline void setNodeLimit(int value) {
310        nodeLimit_ = value;
311    }
312    // Whether to do refinement step
313    inline bool refine() const {
314        return refine_;
315    }
316    // Whether to do refinement step
317    inline void setRefine(bool yesNo) {
318        refine_ = yesNo;
319    }
320
321//@}
322private:
323    // Node for local cuts
324    CbcNode * localNode_;
325    // best solution
326    double * bestSolution_;
327    // saved solution
328    double * savedSolution_;
329    // solution number at start of pass
330    int saveNumberSolutions_;
331    /* Cut.  If zero size then no solution yet.  Otherwise is left hand branch */
332    OsiRowCut cut_;
333    // This cut fixes all 0-1 variables
334    OsiRowCut fixedCut_;
335    // Model
336    CbcModel * model_;
337    // Original lower bounds
338    double * originalLower_;
339    // Original upper bounds
340    double * originalUpper_;
341    // range i.e. k
342    int range_;
343    // Type of cuts - 0=just 0-1, 1=all
344    int typeCuts_;
345    // maximum number of diversifications
346    int maxDiversification_;
347    // current diversification
348    int diversification_;
349    // Whether next will be strong diversification
350    bool nextStrong_;
351    // Current rhs
352    double rhs_;
353    // Save allowable gap
354    double savedGap_;
355    // Best solution
356    double bestCutoff_;
357    // time limit per subtree
358    int timeLimit_;
359    // time when subtree started
360    int startTime_;
361    // node limit for subtree
362    int nodeLimit_;
363    // node count when subtree started
364    int startNode_;
365    // -1 not started, 0 == stop on first solution, 1 don't stop on first, 2 refinement step
366    int searchType_;
367    // Whether to do refinement step
368    bool refine_;
369
370};
371#endif
372
Note: See TracBrowser for help on using the repository browser.