1 | /* $Id: CbcCutGenerator.hpp 1839 2013-01-16 18:41:25Z forrest $ */ |
---|
2 | // Copyright (C) 2003, 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 CbcCutGenerator_H |
---|
7 | #define CbcCutGenerator_H |
---|
8 | |
---|
9 | #include "OsiSolverInterface.hpp" |
---|
10 | #include "OsiCuts.hpp" |
---|
11 | #include "CglCutGenerator.hpp" |
---|
12 | #include "CbcCutModifier.hpp" |
---|
13 | |
---|
14 | class CbcModel; |
---|
15 | class OsiRowCut; |
---|
16 | class OsiRowCutDebugger; |
---|
17 | |
---|
18 | //############################################################################# |
---|
19 | |
---|
20 | /** Interface between Cbc and Cut Generation Library. |
---|
21 | |
---|
22 | \c CbcCutGenerator is intended to provide an intelligent interface between |
---|
23 | Cbc and the cutting plane algorithms in the CGL. A \c CbcCutGenerator is |
---|
24 | bound to a \c CglCutGenerator and to an \c CbcModel. It contains parameters |
---|
25 | which control when and how the \c generateCuts method of the |
---|
26 | \c CglCutGenerator will be called. |
---|
27 | |
---|
28 | The builtin decision criteria available to use when deciding whether to |
---|
29 | generate cuts are limited: every <i>X</i> nodes, when a solution is found, |
---|
30 | and when a subproblem is found to be infeasible. The idea is that the class |
---|
31 | will grow more intelligent with time. |
---|
32 | |
---|
33 | \todo Add a pointer to function member which will allow a client to install |
---|
34 | their own decision algorithm to decide whether or not to call the CGL |
---|
35 | \p generateCuts method. Create a default decision method that looks |
---|
36 | at the builtin criteria. |
---|
37 | |
---|
38 | \todo It strikes me as not good that generateCuts contains code specific to |
---|
39 | individual CGL algorithms. Another set of pointer to function members, |
---|
40 | so that the client can specify the cut generation method as well as |
---|
41 | pre- and post-generation methods? Taken a bit further, should this |
---|
42 | class contain a bunch of pointer to function members, one for each |
---|
43 | of the places where the cut generator might be referenced? |
---|
44 | Initialization, root node, search tree node, discovery of solution, |
---|
45 | and termination all come to mind. Initialization and termination would |
---|
46 | also be useful for instrumenting cbc. |
---|
47 | */ |
---|
48 | |
---|
49 | class CbcCutGenerator { |
---|
50 | |
---|
51 | public: |
---|
52 | |
---|
53 | /** \name Generate Cuts */ |
---|
54 | //@{ |
---|
55 | /** Generate cuts for the client model. |
---|
56 | |
---|
57 | Evaluate the state of the client model and decide whether to generate cuts. |
---|
58 | The generated cuts are inserted into and returned in the collection of cuts |
---|
59 | \p cs. |
---|
60 | |
---|
61 | If \p fullScan is !=0, the generator is obliged to call the CGL |
---|
62 | \c generateCuts routine. Otherwise, it is free to make a local decision. |
---|
63 | Negative fullScan says things like at integer solution |
---|
64 | The current implementation uses \c whenCutGenerator_ to decide. |
---|
65 | |
---|
66 | The routine returns true if reoptimisation is needed (because the state of |
---|
67 | the solver interface has been modified). |
---|
68 | |
---|
69 | If node then can find out depth |
---|
70 | */ |
---|
71 | bool generateCuts( OsiCuts &cs, int fullScan, OsiSolverInterface * solver, |
---|
72 | CbcNode * node); |
---|
73 | //@} |
---|
74 | |
---|
75 | |
---|
76 | /**@name Constructors and destructors */ |
---|
77 | //@{ |
---|
78 | /// Default constructor |
---|
79 | CbcCutGenerator (); |
---|
80 | |
---|
81 | /// Normal constructor |
---|
82 | CbcCutGenerator(CbcModel * model, CglCutGenerator * generator, |
---|
83 | int howOften = 1, const char * name = NULL, |
---|
84 | bool normal = true, bool atSolution = false, |
---|
85 | bool infeasible = false, int howOftenInsub = -100, |
---|
86 | int whatDepth = -1, int whatDepthInSub = -1, int switchOffIfLessThan = 0); |
---|
87 | |
---|
88 | /// Copy constructor |
---|
89 | CbcCutGenerator (const CbcCutGenerator &); |
---|
90 | |
---|
91 | /// Assignment operator |
---|
92 | CbcCutGenerator & operator=(const CbcCutGenerator& rhs); |
---|
93 | |
---|
94 | /// Destructor |
---|
95 | ~CbcCutGenerator (); |
---|
96 | //@} |
---|
97 | |
---|
98 | /**@name Gets and sets */ |
---|
99 | //@{ |
---|
100 | /** Set the client model. |
---|
101 | |
---|
102 | In addition to setting the client model, refreshModel also calls |
---|
103 | the \c refreshSolver method of the CglCutGenerator object. |
---|
104 | */ |
---|
105 | void refreshModel(CbcModel * model); |
---|
106 | |
---|
107 | /// return name of generator |
---|
108 | inline const char * cutGeneratorName() const { |
---|
109 | return generatorName_; |
---|
110 | } |
---|
111 | |
---|
112 | /// Create C++ lines to show how to tune |
---|
113 | void generateTuning( FILE * fp); |
---|
114 | /** Set the cut generation interval |
---|
115 | |
---|
116 | Set the number of nodes evaluated between calls to the Cgl object's |
---|
117 | \p generateCuts routine. |
---|
118 | |
---|
119 | If \p value is positive, cuts will always be generated at the specified |
---|
120 | interval. |
---|
121 | If \p value is negative, cuts will initially be generated at the specified |
---|
122 | interval, but Cbc may adjust the value depending on the success of cuts |
---|
123 | produced by this generator. |
---|
124 | |
---|
125 | A value of -100 disables the generator, while a value of -99 means |
---|
126 | just at root. |
---|
127 | */ |
---|
128 | void setHowOften(int value) ; |
---|
129 | |
---|
130 | /// Get the cut generation interval. |
---|
131 | inline int howOften() const { |
---|
132 | return whenCutGenerator_; |
---|
133 | } |
---|
134 | /// Get the cut generation interval.in sub tree |
---|
135 | inline int howOftenInSub() const { |
---|
136 | return whenCutGeneratorInSub_; |
---|
137 | } |
---|
138 | /// Get level of cut inaccuracy (0 means exact e.g. cliques) |
---|
139 | inline int inaccuracy() const { |
---|
140 | return inaccuracy_; |
---|
141 | } |
---|
142 | /// Set level of cut inaccuracy (0 means exact e.g. cliques) |
---|
143 | inline void setInaccuracy(int level) { |
---|
144 | inaccuracy_ = level; |
---|
145 | } |
---|
146 | |
---|
147 | /** Set the cut generation depth |
---|
148 | |
---|
149 | Set the depth criterion for calls to the Cgl object's |
---|
150 | \p generateCuts routine. Only active if > 0. |
---|
151 | |
---|
152 | If whenCutGenerator is positive and this is positive then this overrides. |
---|
153 | If whenCutGenerator is -1 then this is used as criterion if any cuts |
---|
154 | were generated at root node. |
---|
155 | If whenCutGenerator is anything else this is ignored. |
---|
156 | */ |
---|
157 | void setWhatDepth(int value) ; |
---|
158 | /// Set the cut generation depth in sub tree |
---|
159 | void setWhatDepthInSub(int value) ; |
---|
160 | /// Get the cut generation depth criterion. |
---|
161 | inline int whatDepth() const { |
---|
162 | return depthCutGenerator_; |
---|
163 | } |
---|
164 | /// Get the cut generation depth criterion.in sub tree |
---|
165 | inline int whatDepthInSub() const { |
---|
166 | return depthCutGeneratorInSub_; |
---|
167 | } |
---|
168 | |
---|
169 | /// Get switches (for debug) |
---|
170 | inline int switches() const { |
---|
171 | return switches_; |
---|
172 | } |
---|
173 | /// Get whether the cut generator should be called in the normal place |
---|
174 | inline bool normal() const { |
---|
175 | return (switches_&1) != 0; |
---|
176 | } |
---|
177 | /// Set whether the cut generator should be called in the normal place |
---|
178 | inline void setNormal(bool value) { |
---|
179 | switches_ &= ~1; |
---|
180 | switches_ |= value ? 1 : 0; |
---|
181 | } |
---|
182 | /// Get whether the cut generator should be called when a solution is found |
---|
183 | inline bool atSolution() const { |
---|
184 | return (switches_&2) != 0; |
---|
185 | } |
---|
186 | /// Set whether the cut generator should be called when a solution is found |
---|
187 | inline void setAtSolution(bool value) { |
---|
188 | switches_ &= ~2; |
---|
189 | switches_ |= value ? 2 : 0; |
---|
190 | } |
---|
191 | /** Get whether the cut generator should be called when the subproblem is |
---|
192 | found to be infeasible. |
---|
193 | */ |
---|
194 | inline bool whenInfeasible() const { |
---|
195 | return (switches_&4) != 0; |
---|
196 | } |
---|
197 | /** Set whether the cut generator should be called when the subproblem is |
---|
198 | found to be infeasible. |
---|
199 | */ |
---|
200 | inline void setWhenInfeasible(bool value) { |
---|
201 | switches_ &= ~4; |
---|
202 | switches_ |= value ? 4 : 0; |
---|
203 | } |
---|
204 | /// Get whether the cut generator is being timed |
---|
205 | inline bool timing() const { |
---|
206 | return (switches_&64) != 0; |
---|
207 | } |
---|
208 | /// Set whether the cut generator is being timed |
---|
209 | inline void setTiming(bool value) { |
---|
210 | switches_ &= ~64; |
---|
211 | switches_ |= value ? 64 : 0; |
---|
212 | timeInCutGenerator_ = 0.0; |
---|
213 | } |
---|
214 | /// Return time taken in cut generator |
---|
215 | inline double timeInCutGenerator() const { |
---|
216 | return timeInCutGenerator_; |
---|
217 | } |
---|
218 | inline void incrementTimeInCutGenerator(double value) { |
---|
219 | timeInCutGenerator_ += value; |
---|
220 | } |
---|
221 | /// Get the \c CglCutGenerator corresponding to this \c CbcCutGenerator. |
---|
222 | inline CglCutGenerator * generator() const { |
---|
223 | return generator_; |
---|
224 | } |
---|
225 | /// Number times cut generator entered |
---|
226 | inline int numberTimesEntered() const { |
---|
227 | return numberTimes_; |
---|
228 | } |
---|
229 | inline void setNumberTimesEntered(int value) { |
---|
230 | numberTimes_ = value; |
---|
231 | } |
---|
232 | inline void incrementNumberTimesEntered(int value = 1) { |
---|
233 | numberTimes_ += value; |
---|
234 | } |
---|
235 | /// Total number of cuts added |
---|
236 | inline int numberCutsInTotal() const { |
---|
237 | return numberCuts_; |
---|
238 | } |
---|
239 | inline void setNumberCutsInTotal(int value) { |
---|
240 | numberCuts_ = value; |
---|
241 | } |
---|
242 | inline void incrementNumberCutsInTotal(int value = 1) { |
---|
243 | numberCuts_ += value; |
---|
244 | } |
---|
245 | /// Total number of elements added |
---|
246 | inline int numberElementsInTotal() const { |
---|
247 | return numberElements_; |
---|
248 | } |
---|
249 | inline void setNumberElementsInTotal(int value) { |
---|
250 | numberElements_ = value; |
---|
251 | } |
---|
252 | inline void incrementNumberElementsInTotal(int value = 1) { |
---|
253 | numberElements_ += value; |
---|
254 | } |
---|
255 | /// Total number of column cuts |
---|
256 | inline int numberColumnCuts() const { |
---|
257 | return numberColumnCuts_; |
---|
258 | } |
---|
259 | inline void setNumberColumnCuts(int value) { |
---|
260 | numberColumnCuts_ = value; |
---|
261 | } |
---|
262 | inline void incrementNumberColumnCuts(int value = 1) { |
---|
263 | numberColumnCuts_ += value; |
---|
264 | } |
---|
265 | /// Total number of cuts active after (at end of n cut passes at each node) |
---|
266 | inline int numberCutsActive() const { |
---|
267 | return numberCutsActive_; |
---|
268 | } |
---|
269 | inline void setNumberCutsActive(int value) { |
---|
270 | numberCutsActive_ = value; |
---|
271 | } |
---|
272 | inline void incrementNumberCutsActive(int value = 1) { |
---|
273 | numberCutsActive_ += value; |
---|
274 | } |
---|
275 | inline void setSwitchOffIfLessThan(int value) { |
---|
276 | switchOffIfLessThan_ = value; |
---|
277 | } |
---|
278 | inline int switchOffIfLessThan() const { |
---|
279 | return switchOffIfLessThan_; |
---|
280 | } |
---|
281 | /// Say if optimal basis needed |
---|
282 | inline bool needsOptimalBasis() const { |
---|
283 | return (switches_&128) != 0; |
---|
284 | } |
---|
285 | /// Set if optimal basis needed |
---|
286 | inline void setNeedsOptimalBasis(bool yesNo) { |
---|
287 | switches_ &= ~128; |
---|
288 | switches_ |= yesNo ? 128 : 0; |
---|
289 | } |
---|
290 | /// Whether generator MUST be called again if any cuts (i.e. ignore break from loop) |
---|
291 | inline bool mustCallAgain() const { |
---|
292 | return (switches_&8) != 0; |
---|
293 | } |
---|
294 | /// Set whether generator MUST be called again if any cuts (i.e. ignore break from loop) |
---|
295 | inline void setMustCallAgain(bool yesNo) { |
---|
296 | switches_ &= ~8; |
---|
297 | switches_ |= yesNo ? 8 : 0; |
---|
298 | } |
---|
299 | /// Whether generator switched off for moment |
---|
300 | inline bool switchedOff() const { |
---|
301 | return (switches_&16) != 0; |
---|
302 | } |
---|
303 | /// Set whether generator switched off for moment |
---|
304 | inline void setSwitchedOff(bool yesNo) { |
---|
305 | switches_ &= ~16; |
---|
306 | switches_ |= yesNo ? 16 : 0; |
---|
307 | } |
---|
308 | /// Whether last round of cuts did little |
---|
309 | inline bool ineffectualCuts() const { |
---|
310 | return (switches_&512) != 0; |
---|
311 | } |
---|
312 | /// Set whether last round of cuts did little |
---|
313 | inline void setIneffectualCuts(bool yesNo) { |
---|
314 | switches_ &= ~512; |
---|
315 | switches_ |= yesNo ? 512 : 0; |
---|
316 | } |
---|
317 | /// Whether to use if any cuts generated |
---|
318 | inline bool whetherToUse() const { |
---|
319 | return (switches_&1024) != 0; |
---|
320 | } |
---|
321 | /// Set whether to use if any cuts generated |
---|
322 | inline void setWhetherToUse(bool yesNo) { |
---|
323 | switches_ &= ~1024; |
---|
324 | switches_ |= yesNo ? 1024 : 0; |
---|
325 | } |
---|
326 | /// Whether in must call again mode (or after others) |
---|
327 | inline bool whetherInMustCallAgainMode() const { |
---|
328 | return (switches_&2048) != 0; |
---|
329 | } |
---|
330 | /// Set whether in must call again mode (or after others) |
---|
331 | inline void setWhetherInMustCallAgainMode(bool yesNo) { |
---|
332 | switches_ &= ~2048; |
---|
333 | switches_ |= yesNo ? 2048 : 0; |
---|
334 | } |
---|
335 | /// Whether to call at end |
---|
336 | inline bool whetherCallAtEnd() const { |
---|
337 | return (switches_&4096) != 0; |
---|
338 | } |
---|
339 | /// Set whether to call at end |
---|
340 | inline void setWhetherCallAtEnd(bool yesNo) { |
---|
341 | switches_ &= ~4096; |
---|
342 | switches_ |= yesNo ? 4096 : 0; |
---|
343 | } |
---|
344 | /// Number of cuts generated at root |
---|
345 | inline int numberCutsAtRoot() const { |
---|
346 | return numberCutsAtRoot_; |
---|
347 | } |
---|
348 | inline void setNumberCutsAtRoot(int value) { |
---|
349 | numberCutsAtRoot_ = value; |
---|
350 | } |
---|
351 | /// Number of cuts active at root |
---|
352 | inline int numberActiveCutsAtRoot() const { |
---|
353 | return numberActiveCutsAtRoot_; |
---|
354 | } |
---|
355 | inline void setNumberActiveCutsAtRoot(int value) { |
---|
356 | numberActiveCutsAtRoot_ = value; |
---|
357 | } |
---|
358 | /// Number of short cuts at root |
---|
359 | inline int numberShortCutsAtRoot() const { |
---|
360 | return numberShortCutsAtRoot_; |
---|
361 | } |
---|
362 | inline void setNumberShortCutsAtRoot(int value) { |
---|
363 | numberShortCutsAtRoot_ = value; |
---|
364 | } |
---|
365 | /// Set model |
---|
366 | inline void setModel(CbcModel * model) { |
---|
367 | model_ = model; |
---|
368 | } |
---|
369 | /// Whether global cuts at root |
---|
370 | inline bool globalCutsAtRoot() const { |
---|
371 | return (switches_&32) != 0; |
---|
372 | } |
---|
373 | /// Set whether global cuts at root |
---|
374 | inline void setGlobalCutsAtRoot(bool yesNo) { |
---|
375 | switches_ &= ~32; |
---|
376 | switches_ |= yesNo ? 32 : 0; |
---|
377 | } |
---|
378 | /// Whether global cuts |
---|
379 | inline bool globalCuts() const { |
---|
380 | return (switches_&256) != 0; |
---|
381 | } |
---|
382 | /// Set whether global cuts |
---|
383 | inline void setGlobalCuts(bool yesNo) { |
---|
384 | switches_ &= ~256; |
---|
385 | switches_ |= yesNo ? 256 : 0; |
---|
386 | } |
---|
387 | /// Add in statistics from other |
---|
388 | void addStatistics(const CbcCutGenerator * other); |
---|
389 | /// Scale back statistics by factor |
---|
390 | void scaleBackStatistics(int factor); |
---|
391 | //@} |
---|
392 | |
---|
393 | private: |
---|
394 | /**@name Private gets and sets */ |
---|
395 | //@{ |
---|
396 | //@} |
---|
397 | /// Saved cuts |
---|
398 | OsiCuts savedCuts_; |
---|
399 | /// Time in cut generator |
---|
400 | double timeInCutGenerator_; |
---|
401 | /// The client model |
---|
402 | CbcModel *model_; |
---|
403 | |
---|
404 | // The CglCutGenerator object |
---|
405 | CglCutGenerator * generator_; |
---|
406 | |
---|
407 | /// Name of generator |
---|
408 | char * generatorName_; |
---|
409 | |
---|
410 | /** Number of nodes between calls to the CglCutGenerator::generateCuts |
---|
411 | routine. |
---|
412 | */ |
---|
413 | int whenCutGenerator_; |
---|
414 | /** Number of nodes between calls to the CglCutGenerator::generateCuts |
---|
415 | routine in sub tree. |
---|
416 | */ |
---|
417 | int whenCutGeneratorInSub_; |
---|
418 | /** If first pass at root produces fewer than this cuts then switch off |
---|
419 | */ |
---|
420 | int switchOffIfLessThan_; |
---|
421 | |
---|
422 | /** Depth at which to call the CglCutGenerator::generateCuts |
---|
423 | routine (If >0 then overrides when and is called if depth%depthCutGenerator==0). |
---|
424 | */ |
---|
425 | int depthCutGenerator_; |
---|
426 | |
---|
427 | /** Depth at which to call the CglCutGenerator::generateCuts |
---|
428 | routine (If >0 then overrides when and is called if depth%depthCutGenerator==0). |
---|
429 | In sub tree. |
---|
430 | */ |
---|
431 | int depthCutGeneratorInSub_; |
---|
432 | |
---|
433 | /// Level of cut inaccuracy (0 means exact e.g. cliques) |
---|
434 | int inaccuracy_; |
---|
435 | /// Number times cut generator entered |
---|
436 | int numberTimes_; |
---|
437 | /// Total number of cuts added |
---|
438 | int numberCuts_; |
---|
439 | /// Total number of elements added |
---|
440 | int numberElements_; |
---|
441 | /// Total number of column cuts added |
---|
442 | int numberColumnCuts_; |
---|
443 | /// Total number of cuts active after (at end of n cut passes at each node) |
---|
444 | int numberCutsActive_; |
---|
445 | /// Number of cuts generated at root |
---|
446 | int numberCutsAtRoot_; |
---|
447 | /// Number of cuts active at root |
---|
448 | int numberActiveCutsAtRoot_; |
---|
449 | /// Number of short cuts at root |
---|
450 | int numberShortCutsAtRoot_; |
---|
451 | /// Switches - see gets and sets |
---|
452 | int switches_; |
---|
453 | }; |
---|
454 | |
---|
455 | // How often to do if mostly switched off (A) |
---|
456 | # define SCANCUTS 1000 |
---|
457 | // How often to do if mostly switched off (probing B) |
---|
458 | # define SCANCUTS_PROBING 1000 |
---|
459 | |
---|
460 | #endif |
---|
461 | |
---|