source: trunk/Cbc/src/CbcCutGenerator.hpp @ 1839

Last change on this file since 1839 was 1839, checked in by forrest, 7 years ago

multiple root solvers, stronger strong branching and cutoff as constraint

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 15.0 KB
Line 
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
14class CbcModel;
15class OsiRowCut;
16class 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
49class CbcCutGenerator  {
50
51public:
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
393private:
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
Note: See TracBrowser for help on using the repository browser.