source: branches/sandbox/Cbc/src/CbcCutGenerator.hpp @ 1286

Last change on this file since 1286 was 1286, checked in by EdwinStraver, 10 years ago

Changed formatting using AStyle -A4 -p

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