Cbc  2.8.12
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
CbcTreeLocal.hpp
Go to the documentation of this file.
1 /* $Id: CbcTreeLocal.hpp 1573 2011-01-05 01:12:36Z lou $ */
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"
37 class CbcModel;
38 
39 
40 class CbcTreeLocal : public CbcTree {
41 
42 public:
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 
72  virtual CbcTree * clone() const;
74  virtual void generateCpp( FILE * fp) ;
75 
78 
80  virtual CbcNode * top() const;
81 
83  virtual void push(CbcNode * x);
84 
86  virtual void pop() ;
87 
89 
91 
93  int createCut(const double * solution, OsiRowCut & cut);
94 
96  virtual bool empty() ;
97 
99  virtual void endSearch() ;
101  void reverseCut(int state, double bias = 0.0);
103  void deleteCut(OsiRowCut & cut);
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 
156 private:
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 
206 class CbcTreeVariable : public CbcTree {
207 
208 public:
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
234 
235  virtual ~CbcTreeVariable();
236 
238  virtual CbcTree * clone() const;
240  virtual void generateCpp( FILE * fp) ;
241 
244 
246  virtual CbcNode * top() const;
247 
249  virtual void push(CbcNode * x);
250 
252  virtual void pop() ;
253 
255 
257 
259  int createCut(const double * solution, OsiRowCut & cut);
260 
262  virtual bool empty() ;
263 
265  virtual void endSearch() ;
267  void reverseCut(int state, double bias = 0.0);
269  void deleteCut(OsiRowCut & cut);
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 
322 private:
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 
void setTypeCuts(int value)
CbcTreeLocal & operator=(const CbcTreeLocal &rhs)
int maxDiversification() const
int nodeLimit() const
bool refine() const
virtual void generateCpp(FILE *fp)
Create C++ lines to get to current state.
int typeCuts() const
int range() const
virtual CbcNode * top() const
Return the top node of the heap.
int range() const
virtual ~CbcTreeLocal()
void setRange(int value)
virtual void pop()
Remove the top node from the heap.
void passInSolution(const double *solution, double solutionValue)
Pass in solution (so can be used after heuristic)
virtual void push(CbcNode *x)
Add a node to the heap.
int maxDiversification() const
void setTimeLimit(int value)
void setMaxDiversification(int value)
int timeLimit() const
void setRefine(bool yesNo)
int typeCuts() const
virtual void pop()
Remove the top node from the heap.
void setNodeLimit(int value)
virtual CbcNode * top() const
Return the top node of the heap.
void deleteCut(OsiRowCut &cut)
Delete last cut branch.
virtual ~CbcTreeVariable()
virtual void push(CbcNode *x)
Add a node to the heap.
virtual bool empty()
Test if empty *** note may be overridden.
int createCut(const double *solution, OsiRowCut &cut)
Create cut - return -1 if bad, 0 if okay and 1 if cut is everything.
Using MS heap implementation.
Definition: CbcTree.hpp:53
virtual CbcTree * clone() const
Clone.
virtual void endSearch()
We may have got an intelligent tree so give it one more chance.
void deleteCut(OsiRowCut &cut)
Delete last cut branch.
int timeLimit() const
CbcTreeVariable & operator=(const CbcTreeVariable &rhs)
void setMaxDiversification(int value)
virtual bool empty()
Test if empty *** note may be overridden.
Information required while the node is live.
Definition: CbcNode.hpp:49
void setTimeLimit(int value)
int createCut(const double *solution, OsiRowCut &cut)
Create cut - return -1 if bad, 0 if okay and 1 if cut is everything.
void setNodeLimit(int value)
bool refine() const
int nodeLimit() const
void setRange(int value)
void setRefine(bool yesNo)
virtual void generateCpp(FILE *fp)
Create C++ lines to get to current state.
void passInSolution(const double *solution, double solutionValue)
Pass in solution (so can be used after heuristic)
void reverseCut(int state, double bias=0.0)
Other side of last cut branch (if bias==rhs_ will be weakest possible)
Simple Branch and bound class.
Definition: CbcModel.hpp:100
void setTypeCuts(int value)
virtual void endSearch()
We may have got an intelligent tree so give it one more chance.
virtual CbcTree * clone() const
Clone.
void reverseCut(int state, double bias=0.0)
Other side of last cut branch (if bias==rhs_ will be weakest possible)