source: branches/devel/Cbc/src/CbcCutGenerator.hpp @ 648

Last change on this file since 648 was 642, checked in by forrest, 12 years ago

update branches/devel for threads

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 12.5 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 true, 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, bool fullScan,OsiSolverInterface * solver,CbcNode * node); 
67  //@}
68
69   
70  /**@name Constructors and destructors */
71  //@{
72  /// Default constructor
73  CbcCutGenerator (); 
74
75  /// Normal constructor
76  CbcCutGenerator(CbcModel * model,CglCutGenerator * generator,
77                  int howOften=1, const char * name=NULL,
78                  bool normal=true, bool atSolution=false, 
79                  bool infeasible=false,int howOftenInsub=-100,
80                  int whatDepth=-1, int whatDepthInSub=-1,int switchOffIfLessThan=0);
81 
82  /// Copy constructor
83  CbcCutGenerator (const CbcCutGenerator &);
84
85  /// Assignment operator
86  CbcCutGenerator & operator=(const CbcCutGenerator& rhs);
87
88  /// Destructor
89  ~CbcCutGenerator ();
90  //@}
91
92  /**@name Gets and sets */
93  //@{
94  /** Set the client model.
95 
96    In addition to setting the client model, refreshModel also calls
97    the \c refreshSolver method of the CglCutGenerator object.
98  */
99  void refreshModel(CbcModel * model);
100
101  /// return name of generator
102  inline const char * cutGeneratorName() const
103  { return generatorName_;};
104
105  /** Set the cut generation interval
106
107    Set the number of nodes evaluated between calls to the Cgl object's
108    \p generateCuts routine.
109
110    If \p value is positive, cuts will always be generated at the specified
111    interval.
112    If \p value is negative, cuts will initially be generated at the specified
113    interval, but Cbc may adjust the value depending on the success of cuts
114    produced by this generator.
115
116    A value of -100 disables the generator, while a value of -99 means
117    just at root.
118  */
119  void setHowOften(int value) ;
120
121  /// Get the cut generation interval.
122  inline int howOften() const
123  { return whenCutGenerator_;};
124  /// Get the cut generation interval.in sub tree
125  inline int howOftenInSub() const
126  { return whenCutGeneratorInSub_;};
127
128  /** Set the cut generation depth
129
130    Set the depth criterion for calls to the Cgl object's
131    \p generateCuts routine.  Only active if > 0.
132
133    If whenCutGenerator is positive and this is positive then this overrides. 
134    If whenCutGenerator is -1 then this is used as criterion if any cuts
135    were generated at root node.
136    If whenCutGenerator is anything else this is ignored.
137  */
138  void setWhatDepth(int value) ;
139  /// Set the cut generation depth in sub tree
140  void setWhatDepthInSub(int value) ;
141  /// Get the cut generation depth criterion.
142  inline int whatDepth() const
143  { return depthCutGenerator_;};
144  /// Get the cut generation depth criterion.in sub tree
145  inline int whatDepthInSub() const
146  { return depthCutGeneratorInSub_;};
147
148  /// Get whether the cut generator should be called in the normal place
149  inline bool normal() const
150  { return normal_;};
151  /// Set whether the cut generator should be called in the normal place
152  inline void setNormal(bool value) 
153  { normal_=value;};
154  /// Get whether the cut generator should be called when a solution is found
155  inline bool atSolution() const
156  { return atSolution_;};
157  /// Set whether the cut generator should be called when a solution is found
158  inline void setAtSolution(bool value) 
159  { atSolution_=value;};
160  /** Get whether the cut generator should be called when the subproblem is
161      found to be infeasible.
162  */
163  inline bool whenInfeasible() const
164  { return whenInfeasible_;};
165  /** Set whether the cut generator should be called when the subproblem is
166      found to be infeasible.
167  */
168  inline void setWhenInfeasible(bool value) 
169  { whenInfeasible_=value;};
170  /// Get whether the cut generator is being timed
171  inline bool timing() const
172  { return timing_;};
173  /// Set whether the cut generator is being timed
174  inline void setTiming(bool value) 
175  { timing_=value; timeInCutGenerator_=0.0;};
176  /// Return time taken in cut generator
177  inline double timeInCutGenerator() const
178  { return timeInCutGenerator_;};
179  inline void incrementTimeInCutGenerator(double value)
180  { timeInCutGenerator_ += value;};
181  /// Get the \c CglCutGenerator corresponding to this \c CbcCutGenerator.
182  inline CglCutGenerator * generator() const
183  { return generator_;};
184  /// Number times cut generator entered
185  inline int numberTimesEntered() const
186  { return numberTimes_;};
187  inline void setNumberTimesEntered(int value)
188  { numberTimes_ = value;};
189  inline void incrementNumberTimesEntered(int value=1)
190  { numberTimes_ += value;};
191  /// Total number of cuts added
192  inline int numberCutsInTotal() const
193  { return numberCuts_;};
194  inline void setNumberCutsInTotal(int value)
195  { numberCuts_ = value;};
196  inline void incrementNumberCutsInTotal(int value=1)
197  { numberCuts_ += value;};
198  /// Total number of column cuts
199  inline int numberColumnCuts() const
200  { return numberColumnCuts_;};
201  inline void setNumberColumnCuts(int value)
202  { numberColumnCuts_ = value;};
203  inline void incrementNumberColumnCuts(int value=1)
204  { numberColumnCuts_ += value;};
205  /// Total number of cuts active after (at end of n cut passes at each node)
206  inline int numberCutsActive() const
207  { return numberCutsActive_;};
208  inline void setNumberCutsActive(int value)
209  { numberCutsActive_ = value;};
210  inline void incrementNumberCutsActive(int value=1)
211  { numberCutsActive_ += value;};
212  inline void setSwitchOffIfLessThan(int value) 
213  { switchOffIfLessThan_ = value;};
214  inline int switchOffIfLessThan() const
215  { return switchOffIfLessThan_;};
216  /// Say if optimal basis needed
217  inline bool needsOptimalBasis() const
218  { return generator_->needsOptimalBasis();};
219  /// Whether generator MUST be called again if any cuts (i.e. ignore break from loop)
220  inline bool mustCallAgain() const
221  { return mustCallAgain_;};
222  /// Set whether generator MUST be called again if any cuts (i.e. ignore break from loop)
223  inline void setMustCallAgain(bool yesNo)
224  { mustCallAgain_=yesNo;};
225  /// Whether generator switched off for moment
226  inline bool switchedOff() const
227  { return switchedOff_;};
228  /// Set whether generator switched off for moment
229  inline void setSwitchedOff(bool yesNo)
230  { switchedOff_=yesNo;};
231  /// Number of cuts generated at root
232  inline int numberCutsAtRoot() const
233  { return numberCutsAtRoot_;};
234  inline void setNumberCutsAtRoot(int value)
235  { numberCutsAtRoot_ = value;};
236  /// Number of cuts active at root
237  inline int numberActiveCutsAtRoot() const
238  { return numberActiveCutsAtRoot_;};
239  inline void setNumberActiveCutsAtRoot(int value)
240  { numberActiveCutsAtRoot_ = value;};
241  /// Set model
242  inline void setModel(CbcModel * model)
243  { model_ = model;};
244  //@}
245 
246private:
247  /// The client model
248  CbcModel *model_;
249
250  // The CglCutGenerator object
251  CglCutGenerator * generator_;
252
253  /** Number of nodes between calls to the CglCutGenerator::generateCuts
254     routine.
255  */
256  int whenCutGenerator_;
257  /** Number of nodes between calls to the CglCutGenerator::generateCuts
258     routine in sub tree.
259  */
260  int whenCutGeneratorInSub_;
261  /** If first pass at root produces fewer than this cuts then switch off
262   */
263  int switchOffIfLessThan_;
264
265  /** Depth at which to call the CglCutGenerator::generateCuts
266     routine (If >0 then overrides when and is called if depth%depthCutGenerator==0).
267  */
268  int depthCutGenerator_;
269
270  /** Depth at which to call the CglCutGenerator::generateCuts
271     routine (If >0 then overrides when and is called if depth%depthCutGenerator==0).
272     In sub tree.
273  */
274  int depthCutGeneratorInSub_;
275
276  /// Name of generator
277  char * generatorName_;
278
279  /// Whether to call the generator in the normal place
280  bool normal_;
281
282  /// Whether to call the generator when a new solution is found
283  bool atSolution_;
284
285  /// Whether to call generator when a subproblem is found to be infeasible
286  bool whenInfeasible_;
287  /// Whether generator MUST be called again if any cuts (i.e. ignore break from loop)
288  bool mustCallAgain_;
289  /// Temporary switch off marker
290  bool switchedOff_;
291  /// Whether call generator being timed
292  bool timing_;
293  /// Time in cut generator
294  double timeInCutGenerator_;
295 
296  /// Number times cut generator entered
297  int numberTimes_;
298  /// Total number of cuts added
299  int numberCuts_;
300  /// Total number of column cuts added
301  int numberColumnCuts_;
302  /// Total number of cuts active after (at end of n cut passes at each node)
303  int numberCutsActive_;
304  /// Number of cuts generated at root
305  int numberCutsAtRoot_;
306  /// Number of cuts active at root
307  int numberActiveCutsAtRoot_;
308};
309/** Abstract cut modifier base class
310
311    In exotic circumstances - cuts may need to be modified
312    a) strengthened - changed
313    b) weakened - changed
314    c) deleted - set to NULL
315    d) unchanged
316*/
317
318class CbcCutModifier {
319public:
320  /// Default Constructor
321  CbcCutModifier ();
322
323  // Copy constructor
324  CbcCutModifier ( const CbcCutModifier &);
325   
326  /// Destructor
327  virtual ~CbcCutModifier();
328
329  /// Assignment
330  CbcCutModifier & operator=(const CbcCutModifier& rhs);
331 /// Clone
332  virtual CbcCutModifier * clone() const = 0;
333
334  /** Returns
335      0 unchanged
336      1 strengthened
337      2 weakened
338      3 deleted
339  */
340  virtual int modify(const OsiSolverInterface * solver, OsiRowCut & cut) =0;
341  /// Create C++ lines to get to current state
342  virtual void generateCpp( FILE * fp) {};
343protected:
344 
345};
346
347/** Simple cut modifier base class
348
349    In exotic circumstances - cuts may need to be modified
350    a) strengthened - changed
351    b) weakened - changed
352    c) deleted - set to NULL
353    d) unchanged
354
355    initially get rid of cuts with variables >= k
356    could weaken
357*/
358
359class CbcCutSubsetModifier  : public CbcCutModifier {
360public:
361  /// Default Constructor
362  CbcCutSubsetModifier ();
363
364  /// Useful Constructor
365  CbcCutSubsetModifier (int firstOdd);
366
367  // Copy constructor
368  CbcCutSubsetModifier ( const CbcCutSubsetModifier &);
369   
370  /// Destructor
371  virtual ~CbcCutSubsetModifier();
372
373  /// Assignment
374  CbcCutSubsetModifier & operator=(const CbcCutSubsetModifier& rhs);
375 /// Clone
376  virtual CbcCutModifier * clone() const ;
377
378  /** Returns
379      0 unchanged
380      1 strengthened
381      2 weakened
382      3 deleted
383  */
384  virtual int modify(const OsiSolverInterface * solver, OsiRowCut & cut) ;
385  /// Create C++ lines to get to current state
386  virtual void generateCpp( FILE * fp) {};
387protected:
388  /// data
389  /// First odd variable
390  int firstOdd_;
391};
392
393#endif
Note: See TracBrowser for help on using the repository browser.