CbcTreeLocal.hpp
Go to the documentation of this file.
1 /* $Id: CbcTreeLocal.hpp 1286 2009-11-09 23:33:07Z EdwinStraver $ */
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"
35 class CbcModel;
36 
37 
38 class CbcTreeLocal : public CbcTree {
39 
40 public:
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 
70  virtual CbcTree * clone() const;
72  virtual void generateCpp( FILE * fp) ;
73 
76 
78  virtual CbcNode * top() const;
79 
81  virtual void push(CbcNode * x);
82 
84  virtual void pop() ;
85 
87 
89 
91  int createCut(const double * solution, OsiRowCut & cut);
92 
94  virtual bool empty() ;
95 
97  virtual void endSearch() ;
99  void reverseCut(int state, double bias = 0.0);
101  void deleteCut(OsiRowCut & cut);
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 
154 private:
155  // Node for local cuts
157  // best solution
158  double * bestSolution_;
159  // saved solution
160  double * savedSolution_;
161  // solution number at start of pass
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
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
177  // maximum number of diversifications
179  // current diversification
181  // Whether next will be strong diversification
183  // Current rhs
184  double rhs_;
185  // Save allowable gap
186  double savedGap_;
187  // Best solution
188  double bestCutoff_;
189  // time limit per subtree
191  // time when subtree started
193  // node limit for subtree
195  // node count when subtree started
197  // -1 not started, 0 == stop on first solution, 1 don't stop on first, 2 refinement step
199  // Whether to do refinement step
200  bool refine_;
201 
202 };
203 
204 class CbcTreeVariable : public CbcTree {
205 
206 public:
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
232 
233  virtual ~CbcTreeVariable();
234 
236  virtual CbcTree * clone() const;
238  virtual void generateCpp( FILE * fp) ;
239 
242 
244  virtual CbcNode * top() const;
245 
247  virtual void push(CbcNode * x);
248 
250  virtual void pop() ;
251 
253 
255 
257  int createCut(const double * solution, OsiRowCut & cut);
258 
260  virtual bool empty() ;
261 
263  virtual void endSearch() ;
265  void reverseCut(int state, double bias = 0.0);
267  void deleteCut(OsiRowCut & cut);
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 
320 private:
321  // Node for local cuts
323  // best solution
324  double * bestSolution_;
325  // saved solution
326  double * savedSolution_;
327  // solution number at start of pass
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
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
343  // maximum number of diversifications
345  // current diversification
347  // Whether next will be strong diversification
349  // Current rhs
350  double rhs_;
351  // Save allowable gap
352  double savedGap_;
353  // Best solution
354  double bestCutoff_;
355  // time limit per subtree
357  // time when subtree started
359  // node limit for subtree
361  // node count when subtree started
363  // -1 not started, 0 == stop on first solution, 1 don't stop on first, 2 refinement step
365  // Whether to do refinement step
366  bool refine_;
367 
368 };
369 #endif
370