source: stable/2.4/Cbc/src/CbcCutGenerator.hpp @ 1271

Last change on this file since 1271 was 1271, checked in by forrest, 10 years ago

Creating new stable branch 2.4 from trunk (rev 1270)

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 14.5 KB
Line 
1/* $Id: CbcCutGenerator.hpp 1271 2009-11-05 15:57:25Z forrest $ */
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  /// Create C++ lines to show how to tune
109  void generateTuning( FILE * fp);
110  /** Set the cut generation interval
111
112    Set the number of nodes evaluated between calls to the Cgl object's
113    \p generateCuts routine.
114
115    If \p value is positive, cuts will always be generated at the specified
116    interval.
117    If \p value is negative, cuts will initially be generated at the specified
118    interval, but Cbc may adjust the value depending on the success of cuts
119    produced by this generator.
120
121    A value of -100 disables the generator, while a value of -99 means
122    just at root.
123  */
124  void setHowOften(int value) ;
125
126  /// Get the cut generation interval.
127  inline int howOften() const
128  { return whenCutGenerator_;}
129  /// Get the cut generation interval.in sub tree
130  inline int howOftenInSub() const
131  { return whenCutGeneratorInSub_;}
132  /// Get level of cut inaccuracy (0 means exact e.g. cliques)
133  inline int inaccuracy() const
134  { return inaccuracy_;}
135  /// Set level of cut inaccuracy (0 means exact e.g. cliques)
136  inline void setInaccuracy(int level)
137  { inaccuracy_=level;}
138
139  /** Set the cut generation depth
140
141    Set the depth criterion for calls to the Cgl object's
142    \p generateCuts routine.  Only active if > 0.
143
144    If whenCutGenerator is positive and this is positive then this overrides. 
145    If whenCutGenerator is -1 then this is used as criterion if any cuts
146    were generated at root node.
147    If whenCutGenerator is anything else this is ignored.
148  */
149  void setWhatDepth(int value) ;
150  /// Set the cut generation depth in sub tree
151  void setWhatDepthInSub(int value) ;
152  /// Get the cut generation depth criterion.
153  inline int whatDepth() const
154  { return depthCutGenerator_;}
155  /// Get the cut generation depth criterion.in sub tree
156  inline int whatDepthInSub() const
157  { return depthCutGeneratorInSub_;}
158
159  /// Get whether the cut generator should be called in the normal place
160  inline bool normal() const
161  { return (switches_&1)!=0;}
162  /// Set whether the cut generator should be called in the normal place
163  inline void setNormal(bool value) 
164  { switches_&=~1;switches_ |= value ? 1 : 0;}
165  /// Get whether the cut generator should be called when a solution is found
166  inline bool atSolution() const
167  { return (switches_&2)!=0;}
168  /// Set whether the cut generator should be called when a solution is found
169  inline void setAtSolution(bool value) 
170  { switches_&=~2;switches_ |= value ? 2 : 0;}
171  /** Get whether the cut generator should be called when the subproblem is
172      found to be infeasible.
173  */
174  inline bool whenInfeasible() const
175  { return (switches_&4)!=0;}
176  /** Set whether the cut generator should be called when the subproblem is
177      found to be infeasible.
178  */
179  inline void setWhenInfeasible(bool value) 
180  { switches_&=~4;switches_ |= value ? 4 : 0;}
181  /// Get whether the cut generator is being timed
182  inline bool timing() const
183  { return (switches_&64)!=0;}
184  /// Set whether the cut generator is being timed
185  inline void setTiming(bool value) 
186  { switches_&=~64;switches_ |= value ? 64 : 0; timeInCutGenerator_=0.0;}
187  /// Return time taken in cut generator
188  inline double timeInCutGenerator() const
189  { return timeInCutGenerator_;}
190  inline void incrementTimeInCutGenerator(double value)
191  { timeInCutGenerator_ += value;}
192  /// Get the \c CglCutGenerator corresponding to this \c CbcCutGenerator.
193  inline CglCutGenerator * generator() const
194  { return generator_;}
195  /// Number times cut generator entered
196  inline int numberTimesEntered() const
197  { return numberTimes_;}
198  inline void setNumberTimesEntered(int value)
199  { numberTimes_ = value;}
200  inline void incrementNumberTimesEntered(int value=1)
201  { numberTimes_ += value;}
202  /// Total number of cuts added
203  inline int numberCutsInTotal() const
204  { return numberCuts_;}
205  inline void setNumberCutsInTotal(int value)
206  { numberCuts_ = value;}
207  inline void incrementNumberCutsInTotal(int value=1)
208  { numberCuts_ += value;}
209  /// Total number of elements added
210  inline int numberElementsInTotal() const
211  { return numberElements_;}
212  inline void setNumberElementsInTotal(int value)
213  { numberElements_ = value;}
214  inline void incrementNumberElementsInTotal(int value=1)
215  { numberElements_ += value;}
216  /// Total number of column cuts
217  inline int numberColumnCuts() const
218  { return numberColumnCuts_;}
219  inline void setNumberColumnCuts(int value)
220  { numberColumnCuts_ = value;}
221  inline void incrementNumberColumnCuts(int value=1)
222  { numberColumnCuts_ += value;}
223  /// Total number of cuts active after (at end of n cut passes at each node)
224  inline int numberCutsActive() const
225  { return numberCutsActive_;}
226  inline void setNumberCutsActive(int value)
227  { numberCutsActive_ = value;}
228  inline void incrementNumberCutsActive(int value=1)
229  { numberCutsActive_ += value;}
230  inline void setSwitchOffIfLessThan(int value) 
231  { switchOffIfLessThan_ = value;}
232  inline int switchOffIfLessThan() const
233  { return switchOffIfLessThan_;}
234  /// Say if optimal basis needed
235  inline bool needsOptimalBasis() const
236  { return (switches_&128)!=0;}
237  /// Set if optimal basis needed
238  inline void setNeedsOptimalBasis(bool yesNo)
239  { switches_&=~128;switches_ |= yesNo ? 128 : 0;}
240  /// Whether generator MUST be called again if any cuts (i.e. ignore break from loop)
241  inline bool mustCallAgain() const
242  { return (switches_&8)!=0;}
243  /// Set whether generator MUST be called again if any cuts (i.e. ignore break from loop)
244  inline void setMustCallAgain(bool yesNo)
245  { switches_&=~8;switches_ |= yesNo ? 8 : 0;}
246  /// Whether generator switched off for moment
247  inline bool switchedOff() const
248  { return (switches_&16)!=0;}
249  /// Set whether generator switched off for moment
250  inline void setSwitchedOff(bool yesNo)
251  { switches_&=~16;switches_ |= yesNo ? 16 : 0;}
252  /// Whether last round of cuts did little
253  inline bool ineffectualCuts() const
254  { return (switches_&512)!=0;}
255  /// Set whether last round of cuts did little
256  inline void setIneffectualCuts(bool yesNo)
257  { switches_&=~512;switches_ |= yesNo ? 512 : 0;}
258  /// Whether to use if any cuts generated
259  inline bool whetherToUse() const
260  { return (switches_&1024)!=0;}
261  /// Set whether to use if any cuts generated
262  inline void setWhetherToUse(bool yesNo)
263  { switches_&=~1024;switches_ |= yesNo ? 1024 : 0;}
264  /// Number of cuts generated at root
265  inline int numberCutsAtRoot() const
266  { return numberCutsAtRoot_;}
267  inline void setNumberCutsAtRoot(int value)
268  { numberCutsAtRoot_ = value;}
269  /// Number of cuts active at root
270  inline int numberActiveCutsAtRoot() const
271  { return numberActiveCutsAtRoot_;}
272  inline void setNumberActiveCutsAtRoot(int value)
273  { numberActiveCutsAtRoot_ = value;}
274  /// Number of short cuts at root
275  inline int numberShortCutsAtRoot() const
276  { return numberShortCutsAtRoot_;}
277  /// Set model
278  inline void setModel(CbcModel * model)
279  { model_ = model;}
280  //@}
281 
282private:
283  /**@name Private gets and sets */
284  //@{
285  /// Whether global cuts at root
286  inline bool globalCutsAtRoot() const
287  { return (switches_&32)!=0;}
288  /// Set whether global cuts at root
289  inline void setGlobalCutsAtRoot(bool yesNo)
290  { switches_&=~32;switches_ |= yesNo ? 32 : 0;}
291  /// Whether global cuts
292  inline bool globalCuts() const
293  { return (switches_&256)!=0;}
294  /// Set whether global cuts
295  inline void setGlobalCuts(bool yesNo)
296  { switches_&=~256;switches_ |= yesNo ? 256 : 0;}
297  //@}
298  /// Saved cuts
299  OsiCuts savedCuts_;
300  /// Time in cut generator
301  double timeInCutGenerator_;
302  /// The client model
303  CbcModel *model_; 
304
305  // The CglCutGenerator object
306  CglCutGenerator * generator_;
307
308  /// Name of generator
309  char * generatorName_;
310
311  /** Number of nodes between calls to the CglCutGenerator::generateCuts
312     routine.
313  */
314  int whenCutGenerator_;
315  /** Number of nodes between calls to the CglCutGenerator::generateCuts
316     routine in sub tree.
317  */
318  int whenCutGeneratorInSub_;
319  /** If first pass at root produces fewer than this cuts then switch off
320   */
321  int switchOffIfLessThan_;
322
323  /** Depth at which to call the CglCutGenerator::generateCuts
324     routine (If >0 then overrides when and is called if depth%depthCutGenerator==0).
325  */
326  int depthCutGenerator_;
327
328  /** Depth at which to call the CglCutGenerator::generateCuts
329     routine (If >0 then overrides when and is called if depth%depthCutGenerator==0).
330     In sub tree.
331  */
332  int depthCutGeneratorInSub_;
333
334  /// Level of cut inaccuracy (0 means exact e.g. cliques)
335  int inaccuracy_;
336  /// Number times cut generator entered
337  int numberTimes_;
338  /// Total number of cuts added
339  int numberCuts_;
340  /// Total number of elements added
341  int numberElements_;
342  /// Total number of column cuts added
343  int numberColumnCuts_;
344  /// Total number of cuts active after (at end of n cut passes at each node)
345  int numberCutsActive_;
346  /// Number of cuts generated at root
347  int numberCutsAtRoot_;
348  /// Number of cuts active at root
349  int numberActiveCutsAtRoot_;
350  /// Number of short cuts at root
351  int numberShortCutsAtRoot_;
352  /// Switches - see gets and sets
353  int switches_;
354};
355/** Abstract cut modifier base class
356
357    In exotic circumstances - cuts may need to be modified
358    a) strengthened - changed
359    b) weakened - changed
360    c) deleted - set to NULL
361    d) unchanged
362*/
363
364class CbcCutModifier {
365public:
366  /// Default Constructor
367  CbcCutModifier ();
368
369  // Copy constructor
370  CbcCutModifier ( const CbcCutModifier &);
371   
372  /// Destructor
373  virtual ~CbcCutModifier();
374
375  /// Assignment
376  CbcCutModifier & operator=(const CbcCutModifier& rhs);
377 /// Clone
378  virtual CbcCutModifier * clone() const = 0;
379
380  /** Returns
381      0 unchanged
382      1 strengthened
383      2 weakened
384      3 deleted
385  */
386  virtual int modify(const OsiSolverInterface * solver, OsiRowCut & cut) =0;
387  /// Create C++ lines to get to current state
388  virtual void generateCpp( FILE * ) {}
389protected:
390 
391};
392
393/** Simple cut modifier base class
394
395    In exotic circumstances - cuts may need to be modified
396    a) strengthened - changed
397    b) weakened - changed
398    c) deleted - set to NULL
399    d) unchanged
400
401    initially get rid of cuts with variables >= k
402    could weaken
403*/
404
405class CbcCutSubsetModifier  : public CbcCutModifier {
406public:
407  /// Default Constructor
408  CbcCutSubsetModifier ();
409
410  /// Useful Constructor
411  CbcCutSubsetModifier (int firstOdd);
412
413  // Copy constructor
414  CbcCutSubsetModifier ( const CbcCutSubsetModifier &);
415   
416  /// Destructor
417  virtual ~CbcCutSubsetModifier();
418
419  /// Assignment
420  CbcCutSubsetModifier & operator=(const CbcCutSubsetModifier& rhs);
421 /// Clone
422  virtual CbcCutModifier * clone() const ;
423
424  /** Returns
425      0 unchanged
426      1 strengthened
427      2 weakened
428      3 deleted
429  */
430  virtual int modify(const OsiSolverInterface * solver, OsiRowCut & cut) ;
431  /// Create C++ lines to get to current state
432  virtual void generateCpp( FILE * ) {}
433protected:
434  /// data
435  /// First odd variable
436  int firstOdd_;
437};
438// How often to do if mostly switched off (A)
439# define SCANCUTS 1000 
440// How often to do if mostly switched off (probing B)
441# define SCANCUTS_PROBING 1000 
442
443#endif
Note: See TracBrowser for help on using the repository browser.