Cbc  2.9.9
CbcTreeLocal.hpp
Go to the documentation of this file.
1 /* \$Id: CbcTreeLocal.hpp 1573 2011-01-05 01:12:36Z lou \$ */
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
159  // best solution
160  double * bestSolution_;
161  // saved solution
162  double * savedSolution_;
163  // solution number at start of pass
165  /* Cut. If zero size then no solution yet. Otherwise is left hand branch */
167  // This cut fixes all 0-1 variables
169  // 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
179  // maximum number of diversifications
181  // current diversification
183  // Whether next will be strong diversification
185  // Current rhs
186  double rhs_;
187  // Save allowable gap
188  double savedGap_;
189  // Best solution
190  double bestCutoff_;
191  // time limit per subtree
193  // time when subtree started
195  // node limit for subtree
197  // node count when subtree started
199  // -1 not started, 0 == stop on first solution, 1 don't stop on first, 2 refinement step
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
325  // best solution
326  double * bestSolution_;
327  // saved solution
328  double * savedSolution_;
329  // solution number at start of pass
331  /* Cut. If zero size then no solution yet. Otherwise is left hand branch */
333  // This cut fixes all 0-1 variables
335  // 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
345  // maximum number of diversifications
347  // current diversification
349  // Whether next will be strong diversification
351  // Current rhs
352  double rhs_;
353  // Save allowable gap
354  double savedGap_;
355  // Best solution
356  double bestCutoff_;
357  // time limit per subtree
359  // time when subtree started
361  // node limit for subtree
363  // node count when subtree started
365  // -1 not started, 0 == stop on first solution, 1 don't stop on first, 2 refinement step
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
CbcNode * localNode_
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
CbcModel * model_
OsiRowCut fixedCut_
virtual void pop()
Remove the top node from the heap.
void setNodeLimit(int value)
OsiRowCut cut_
CbcNode * localNode_
double * savedSolution_
virtual CbcNode * top() const
Return the top node of the heap.
double * originalLower_
void deleteCut(OsiRowCut &cut)
Delete last cut branch.
virtual ~CbcTreeVariable()
virtual void push(CbcNode *x)
Add a node to the heap.
CbcModel * model_
virtual bool empty()
Test if empty *** note may be overridden.
int saveNumberSolutions_
int createCut(const double *solution, OsiRowCut &cut)
Create cut - return -1 if bad, 0 if okay and 1 if cut is everything.
double * originalUpper_
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.
double * bestSolution_
void deleteCut(OsiRowCut &cut)
Delete last cut branch.
double * bestSolution_
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.
Row Cut Class.
Definition: OsiRowCut.hpp:29
void setNodeLimit(int value)
double * originalUpper_
double * savedSolution_
double * originalLower_
bool refine() const
OsiRowCut fixedCut_
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:101
double bestCutoff_
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)