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

Last change on this file since 1121 was 1121, checked in by forrest, 11 years ago

compiler warnings, deterministic parallel and stability

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