Cbc 2.10.11
Loading...
Searching...
No Matches
CbcTreeLocal.hpp
Go to the documentation of this file.
1/* $Id$ */
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
39class CbcTreeLocal : public CbcTree {
40
41public:
42 // Default Constructor
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
63
64 // = operator
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 {
107 return range_;
108 }
109 // setrange i.e. k
110 inline void setRange(int value)
111 {
112 range_ = value;
113 }
114 // Type of cuts - 0=just 0-1, 1=all
115 inline int typeCuts() const
116 {
117 return typeCuts_;
118 }
119 // Type of cuts - 0=just 0-1, 1=all
120 inline void setTypeCuts(int value)
121 {
122 typeCuts_ = value;
123 }
124 // maximum number of diversifications
125 inline int maxDiversification() const
126 {
127 return maxDiversification_;
128 }
129 // maximum number of diversifications
130 inline void setMaxDiversification(int value)
131 {
132 maxDiversification_ = value;
133 }
134 // time limit per subtree
135 inline int timeLimit() const
136 {
137 return timeLimit_;
138 }
139 // time limit per subtree
140 inline void setTimeLimit(int value)
141 {
142 timeLimit_ = value;
143 }
144 // node limit for subtree
145 inline int nodeLimit() const
146 {
147 return nodeLimit_;
148 }
149 // node limit for subtree
150 inline void setNodeLimit(int value)
151 {
152 nodeLimit_ = value;
153 }
154 // Whether to do refinement step
155 inline bool refine() const
156 {
157 return refine_;
158 }
159 // Whether to do refinement step
160 inline void setRefine(bool yesNo)
161 {
162 refine_ = yesNo;
163 }
164
166private:
167 // Node for local cuts
169 // best solution
171 // saved solution
173 // solution number at start of pass
175 /* Cut. If zero size then no solution yet. Otherwise is left hand branch */
176 OsiRowCut cut_;
177 // This cut fixes all 0-1 variables
178 OsiRowCut fixedCut_;
179 // Model
181 // Original lower bounds
183 // Original upper bounds
185 // range i.e. k
187 // Type of cuts - 0=just 0-1, 1=all
189 // maximum number of diversifications
191 // current diversification
193 // Whether next will be strong diversification
195 // Current rhs
196 double rhs_;
197 // Save allowable gap
198 double savedGap_;
199 // Best solution
201 // time limit per subtree
203 // time when subtree started
205 // node limit for subtree
207 // node count when subtree started
209 // -1 not started, 0 == stop on first solution, 1 don't stop on first, 2 refinement step
211 // Whether to do refinement step
213};
214
215class CbcTreeVariable : public CbcTree {
216
217public:
218 // Default Constructor
220
221 /* Constructor with solution.
222 If solution NULL no solution, otherwise must be integer
223 range is initial upper bound (k) on difference from given solution.
224 typeCuts -
225 0 means just 0-1 cuts and will need to refine 0-1 solution
226 1 uses weaker cuts on all integer variables
227 maxDiversification is maximum number of range widenings to try
228 timeLimit is seconds in subTree
229 nodeLimit is nodes in subTree
230 refine is whether to see if we can prove current solution is optimal
231 when we fix all 0-1 (in case typeCuts==0 and there are general integer variables)
232 if false then no refinement but reverse cuts weaker
233 */
234 CbcTreeVariable(CbcModel *model, const double *solution, int range = 10,
235 int typeCuts = 0, int maxDiversification = 0,
236 int timeLimit = 1000000, int nodeLimit = 1000000, bool refine = true);
237 // Copy constructor
239
240 // = operator
242
244
246 virtual CbcTree *clone() const;
248 virtual void generateCpp(FILE *fp);
249
252
254 virtual CbcNode *top() const;
255
257 virtual void push(CbcNode *x);
258
260 virtual void pop();
261
263
265
267 int createCut(const double *solution, OsiRowCut &cut);
268
270 virtual bool empty();
271
273 virtual void endSearch();
275 void reverseCut(int state, double bias = 0.0);
277 void deleteCut(OsiRowCut &cut);
279 void passInSolution(const double *solution, double solutionValue);
280 // range i.e. k
281 inline int range() const
282 {
283 return range_;
284 }
285 // setrange i.e. k
286 inline void setRange(int value)
287 {
288 range_ = value;
289 }
290 // Type of cuts - 0=just 0-1, 1=all
291 inline int typeCuts() const
292 {
293 return typeCuts_;
294 }
295 // Type of cuts - 0=just 0-1, 1=all
296 inline void setTypeCuts(int value)
297 {
298 typeCuts_ = value;
299 }
300 // maximum number of diversifications
301 inline int maxDiversification() const
302 {
303 return maxDiversification_;
304 }
305 // maximum number of diversifications
306 inline void setMaxDiversification(int value)
307 {
308 maxDiversification_ = value;
309 }
310 // time limit per subtree
311 inline int timeLimit() const
312 {
313 return timeLimit_;
314 }
315 // time limit per subtree
316 inline void setTimeLimit(int value)
317 {
318 timeLimit_ = value;
319 }
320 // node limit for subtree
321 inline int nodeLimit() const
322 {
323 return nodeLimit_;
324 }
325 // node limit for subtree
326 inline void setNodeLimit(int value)
327 {
328 nodeLimit_ = value;
329 }
330 // Whether to do refinement step
331 inline bool refine() const
332 {
333 return refine_;
334 }
335 // Whether to do refinement step
336 inline void setRefine(bool yesNo)
337 {
338 refine_ = yesNo;
339 }
340
342private:
343 // Node for local cuts
345 // best solution
347 // saved solution
349 // solution number at start of pass
351 /* Cut. If zero size then no solution yet. Otherwise is left hand branch */
352 OsiRowCut cut_;
353 // This cut fixes all 0-1 variables
354 OsiRowCut fixedCut_;
355 // Model
357 // Original lower bounds
359 // Original upper bounds
361 // range i.e. k
363 // Type of cuts - 0=just 0-1, 1=all
365 // maximum number of diversifications
367 // current diversification
369 // Whether next will be strong diversification
371 // Current rhs
372 double rhs_;
373 // Save allowable gap
374 double savedGap_;
375 // Best solution
377 // time limit per subtree
379 // time when subtree started
381 // node limit for subtree
383 // node count when subtree started
385 // -1 not started, 0 == stop on first solution, 1 don't stop on first, 2 refinement step
387 // Whether to do refinement step
389};
390#endif
391
392/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
393*/
Simple Branch and bound class.
Definition CbcModel.hpp:100
Information required while the node is live.
Definition CbcNode.hpp:49
CbcTreeLocal(const CbcTreeLocal &rhs)
virtual CbcNode * top() const
Return the top node of the heap.
void setTypeCuts(int value)
void setRefine(bool yesNo)
bool refine() const
int typeCuts() const
int range() const
CbcTreeLocal & operator=(const CbcTreeLocal &rhs)
virtual void generateCpp(FILE *fp)
Create C++ lines to get to current state.
OsiRowCut fixedCut_
void setTimeLimit(int value)
CbcTreeLocal(CbcModel *model, const double *solution, int range=10, int typeCuts=0, int maxDiversification=0, int timeLimit=1000000, int nodeLimit=1000000, bool refine=true)
int maxDiversification() const
virtual void push(CbcNode *x)
Add a node to the heap.
virtual void endSearch()
We may have got an intelligent tree so give it one more chance.
void reverseCut(int state, double bias=0.0)
Other side of last cut branch (if bias==rhs_ will be weakest possible)
virtual ~CbcTreeLocal()
double * originalUpper_
void passInSolution(const double *solution, double solutionValue)
Pass in solution (so can be used after heuristic)
double * originalLower_
void setRange(int value)
virtual bool empty()
Test if empty *** note may be overridden.
int nodeLimit() const
void setMaxDiversification(int value)
void deleteCut(OsiRowCut &cut)
Delete last cut branch.
int timeLimit() const
CbcModel * model_
CbcNode * localNode_
double * bestSolution_
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)
double * savedSolution_
virtual CbcTree * clone() const
Clone.
virtual void pop()
Remove the top node from the heap.
int maxDiversification() const
virtual bool empty()
Test if empty *** note may be overridden.
CbcTreeVariable(const CbcTreeVariable &rhs)
virtual void push(CbcNode *x)
Add a node to the heap.
void setTypeCuts(int value)
void passInSolution(const double *solution, double solutionValue)
Pass in solution (so can be used after heuristic)
virtual void generateCpp(FILE *fp)
Create C++ lines to get to current state.
virtual CbcNode * top() const
Return the top node of the heap.
int typeCuts() const
virtual void pop()
Remove the top node from the heap.
int timeLimit() const
int nodeLimit() const
void setTimeLimit(int value)
double * savedSolution_
virtual CbcTree * clone() const
Clone.
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)
void setRange(int value)
double * originalLower_
void reverseCut(int state, double bias=0.0)
Other side of last cut branch (if bias==rhs_ will be weakest possible)
virtual void endSearch()
We may have got an intelligent tree so give it one more chance.
double * originalUpper_
void setRefine(bool yesNo)
CbcTreeVariable & operator=(const CbcTreeVariable &rhs)
virtual ~CbcTreeVariable()
CbcTreeVariable(CbcModel *model, const double *solution, int range=10, int typeCuts=0, int maxDiversification=0, int timeLimit=1000000, int nodeLimit=1000000, bool refine=true)
void setMaxDiversification(int value)
int range() const
bool refine() const
void deleteCut(OsiRowCut &cut)
Delete last cut branch.
Using MS heap implementation.
Definition CbcTree.hpp:52