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

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

fixes

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