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

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

chnages to try and make faster

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