source: branches/devel/Cbc/src/CbcBranchBase.hpp @ 445

Last change on this file since 445 was 445, checked in by forrest, 13 years ago

for OsiSOS and add more stats to cut generators

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 15.7 KB
Line 
1// Copyright (C) 2002, International Business Machines
2// Corporation and others.  All Rights Reserved.
3#ifndef CbcBranchBase_H
4#define CbcBranchBase_H
5
6#include <string>
7#include <vector>
8#include "OsiBranchingObject.hpp"
9class OsiSolverInterface;
10class OsiSolverBranch;
11
12class CbcModel;
13class CbcNode;
14class CbcNodeInfo;
15class CbcBranchingObject;
16class OsiChooseVariable;
17
18//#############################################################################
19
20/** Abstract base class for `objects'.
21    It now just has stuff that OsiObject does not have
22
23  The branching model used in Cbc is based on the idea of an <i>object</i>.
24  In the abstract, an object is something that has a feasible region, can be
25  evaluated for infeasibility, can be branched on (<i>i.e.</i>, there's some
26  constructive action to be taken to move toward feasibility), and allows
27  comparison of the effect of branching.
28
29  This class (CbcObject) is the base class for an object. To round out the
30  branching model, the class CbcBranchingObject describes how to perform a
31  branch, and the class CbcBranchDecision describes how to compare two
32  CbcBranchingObjects.
33
34  To create a new type of object you need to provide three methods:
35  #infeasibility(), #feasibleRegion(), and #createBranch(), described below.
36
37  This base class is primarily virtual to allow for any form of structure.
38  Any form of discontinuity is allowed.
39
40  \todo The notion that all branches are binary (two arms) is wired into the
41        implementation of CbcObject, CbcBranchingObject, and
42        CbcBranchDecision. Changing this will require a moderate amount of
43        recoding.
44 */
45// This can be used if object wants to skip strong branching
46  typedef struct {
47    CbcBranchingObject * possibleBranch; // what a branch would do
48    double upMovement; // cost going up (and initial away from feasible)
49    double downMovement; // cost going down
50    int numIntInfeasUp ; // without odd ones
51    int numObjInfeasUp ; // just odd ones
52    bool finishedUp; // true if solver finished
53    int numItersUp ; // number of iterations in solver
54    int numIntInfeasDown ; // without odd ones
55    int numObjInfeasDown ; // just odd ones
56    bool finishedDown; // true if solver finished
57    int numItersDown; // number of iterations in solver
58    int objectNumber; // Which object it is
59    int fix; // 0 if no fix, 1 if we can fix up, -1 if we can fix down
60  } CbcStrongInfo;
61
62class CbcObject : public OsiObject {
63
64public:
65
66  // Default Constructor
67  CbcObject ();
68
69  // Useful constructor
70  CbcObject (CbcModel * model);
71 
72  // Copy constructor
73  CbcObject ( const CbcObject &);
74   
75  // Assignment operator
76  CbcObject & operator=( const CbcObject& rhs);
77
78  /// Clone
79  virtual CbcObject * clone() const=0;
80
81  /// Destructor
82  virtual ~CbcObject ();
83
84  /** Infeasibility of the object
85
86      This is some measure of the infeasibility of the object. It should be
87      scaled to be in the range [0.0, 0.5], with 0.0 indicating the object
88      is satisfied.
89
90      The preferred branching direction is returned in preferredWay,
91
92      This is used to prepare for strong branching but should also think of
93      case when no strong branching
94     
95      The object may also compute an estimate of cost of going "up" or "down".
96      This will probably be based on pseudo-cost ideas
97  */
98  virtual double infeasibility(int &preferredWay) const = 0;
99  /// Dummy one for compatibility
100  virtual double infeasibility(const OsiBranchingInformation * info,
101                               int &preferredWay) const;
102
103  /** For the variable(s) referenced by the object,
104      look at the current solution and set bounds to match the solution.
105  */
106  virtual void feasibleRegion() = 0;
107  /// Dummy one for compatibility
108  virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const;
109
110  /** Create a branching object and indicate which way to branch first.
111
112      The branching object has to know how to create branches (fix
113      variables, etc.)
114  */
115  virtual CbcBranchingObject * createBranch(int way) = 0;
116 
117  /** Infeasibility of the object
118     
119    This is some measure of the infeasibility of the object. 0.0
120    indicates that the object is satisfied.
121 
122    The preferred branching direction is returned in way,
123 
124    This is used to prepare for strong branching but should also think of
125    case when no strong branching
126 
127    The object may also compute an estimate of cost of going "up" or "down".
128    This will probably be based on pseudo-cost ideas
129
130    This should also set mutable infeasibility_ and whichWay_
131    This is for instant re-use for speed
132  */
133  virtual double infeasibility(const OsiSolverInterface * solver,int &preferredWay) const;
134 
135  /** For the variable(s) referenced by the object,
136      look at the current solution and set bounds to match the solution.
137      Returns measure of how much it had to move solution to make feasible
138  */
139  virtual double feasibleRegion(OsiSolverInterface * solver) const ;
140 
141  /** Create a branching object and indicate which way to branch first.
142     
143      The branching object has to know how to create branches (fix
144      variables, etc.)
145  */
146  virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver, int way) const;
147  /** Create a branching object and indicate which way to branch first.
148     
149      The branching object has to know how to create branches (fix
150      variables, etc.)
151  */
152  virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver,const OsiBranchingInformation * info, int way) const;
153  /** Create an OsiSolverBranch object
154
155      This returns NULL if branch not represented by bound changes
156  */
157  virtual OsiSolverBranch * solverBranch() const;
158 
159  /** \brief Given a valid solution (with reduced costs, etc.),
160      return a branching object which would give a new feasible
161      point in a good direction.
162
163      If the method cannot generate a feasible point (because there aren't
164      any, or because it isn't bright enough to find one), it should
165      return null.
166  */
167  virtual CbcBranchingObject * preferredNewFeasible() const 
168  { return NULL;};
169 
170  /** \brief Given a valid solution (with reduced costs, etc.),
171      return a branching object which would give a new feasible
172      point in a bad direction.
173
174      If the method cannot generate a feasible point (because there aren't
175      any, or because it isn't bright enough to find one), it should
176      return null.
177  */
178  virtual CbcBranchingObject * notPreferredNewFeasible() const 
179  { return NULL;};
180
181  /** Reset variable bounds to their original values.
182 
183    Bounds may be tightened, so it may be good to be able to reset them to
184    their original values.
185   */
186  virtual void resetBounds(const OsiSolverInterface * solver) {};
187 
188  /** Returns floor and ceiling i.e. closest valid points
189  */
190  virtual void floorCeiling(double & floorValue, double & ceilingValue, double value,
191                            double tolerance) const;
192
193  /// Identifier (normally column number in matrix)
194  inline int id() const
195  { return id_;};
196 
197   /// update model
198  inline void setModel(CbcModel * model)
199  { model_ = model;};
200 
201  /// Return model
202  inline CbcModel * model() const
203  {return  model_;};
204
205  /// If -1 down always chosen first, +1 up always, 0 normal
206  inline int preferredWay() const
207  { return preferredWay_;};
208  /// Set -1 down always chosen first, +1 up always, 0 normal
209  inline void setPreferredWay(int value)
210  { preferredWay_=value;};
211  /// Redoes data when sequence numbers change
212  virtual void redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns) {};
213 
214protected:
215  /// data
216
217  /// Model
218  CbcModel * model_;
219  /// Identifier (normally column number in matrix)
220  int id_;
221  /// If -1 down always chosen first, +1 up always, 0 normal
222  int preferredWay_;
223
224};
225
226/** \brief Abstract branching object base class
227    Now just difference with OsiBranchingObject
228
229  In the abstract, an CbcBranchingObject contains instructions for how to
230  branch. We want an abstract class so that we can describe how to branch on
231  simple objects (<i>e.g.</i>, integers) and more exotic objects
232  (<i>e.g.</i>, cliques or hyperplanes).
233
234  The #branch() method is the crucial routine: it is expected to be able to
235  step through a set of branch arms, executing the actions required to create
236  each subproblem in turn. The base class is primarily virtual to allow for
237  a wide range of problem modifications.
238
239  See CbcObject for an overview of the three classes (CbcObject,
240  CbcBranchingObject, and CbcBranchDecision) which make up cbc's branching
241  model.
242*/
243
244class CbcBranchingObject : public OsiBranchingObject {
245
246public:
247
248  /// Default Constructor
249  CbcBranchingObject ();
250
251  /// Constructor
252  CbcBranchingObject (CbcModel * model, int variable, int way , double value);
253 
254  /// Copy constructor
255  CbcBranchingObject ( const CbcBranchingObject &);
256   
257  /// Assignment operator
258  CbcBranchingObject & operator=( const CbcBranchingObject& rhs);
259
260  /// Clone
261  virtual CbcBranchingObject * clone() const=0;
262
263  /// Destructor
264  virtual ~CbcBranchingObject ();
265
266  /** Some branchingObjects may claim to be able to skip
267      strong branching.  If so they ahve to fill in CbcStrongInfo.
268      The object mention in incoming CbcStrongInfo must match.
269      Returns nonzero if skip is wanted */
270  virtual int fillStrongInfo( CbcStrongInfo & info) {return 0;};
271  /// Reset number of branches left to original
272  inline void resetNumberBranchesLeft()
273  { branchIndex_=0;};
274
275  /** \brief Execute the actions required to branch, as specified by the
276             current state of the branching object, and advance the object's
277             state.  Mainly for diagnostics, whether it is true branch or
278             strong branching is also passed.
279             Returns change in guessed objective on next branch
280  */
281  virtual double branch()=0;
282
283  /** \brief Print something about branch - only if log level high
284  */
285  virtual void print() const {};
286
287  /** \brief Index identifying the associated CbcObject within its class.
288 
289    The name is misleading, and typically the index will <i>not</i> refer
290    directly to a variable.
291    Rather, it identifies an CbcObject within the class of similar
292    CbcObjects
293   
294    <i>E.g.</i>, for an CbcSimpleInteger, variable() is the index of the
295    integer variable in the set of integer variables (<i>not</i> the index of
296    the variable in the set of all variables).
297  */
298  inline int variable() const
299  {return variable_;};
300
301  /** Get the state of the branching object
302 
303    Returns a code indicating the active arm of the branching object.
304    The precise meaning is defined in the derived class.
305
306    \sa #way_
307  */
308  inline int way() const
309  {return way_;};
310
311  /** Set the state of the branching object.
312
313    See #way()
314  */
315  inline void way(int way)
316  {way_=way;};
317
318  /// Return model
319  inline CbcModel * model() const
320  {return  model_;};
321
322  /// Return pointer back to object which created
323  inline CbcObject * object() const
324  {return  originalCbcObject_;};
325  /// Set pointer back to object which created
326  inline void setOriginalObject(CbcObject * object)
327  {originalCbcObject_=object;};
328
329protected:
330
331  /// The model that owns this branching object
332  CbcModel * model_;
333  /// Pointer back to object which created
334  CbcObject * originalCbcObject_;
335
336  /// Branching variable (0 is first integer)
337  int variable_;
338  // was - Way to branch - -1 down (first), 1 up, -2 down (second), 2 up (second)
339  /** The state of the branching object.
340
341    Specifies the active arm of the branching object. Coded as -1 to take
342    the `down' arm, +1 for the `up' arm. `Down' and `up' are defined based on
343    the natural meaning (floor and ceiling, respectively) for a simple integer.
344    The precise meaning is defined in the derived class.
345  */
346  int way_;
347
348};
349
350
351/** Abstract branching decision base class
352
353  In the abstract, an CbcBranchDecision object is expected to be able to
354  compare two possible branching choices.
355
356  The #betterBranch() method is the crucial routine. It is expected to be able
357  to compare two \link CbcBranchingObject CbcBranchingObjects \endlink.
358
359  See CbcObject for an overview of the three classes (CbcObject,
360  CbcBranchingObject, and CbcBranchDecision) which make up cbc's branching
361  model.
362*/
363
364class CbcBranchDecision {
365public:
366  /// Default Constructor
367  CbcBranchDecision ();
368
369  // Copy constructor
370  CbcBranchDecision ( const CbcBranchDecision &);
371   
372  /// Destructor
373  virtual ~CbcBranchDecision();
374
375 /// Clone
376  virtual CbcBranchDecision * clone() const = 0;
377
378  /// Initialize <i>e.g.</i> before starting to choose a branch at a node
379  virtual void initialize(CbcModel * model) = 0;
380
381  /** \brief Compare two branching objects. Return nonzero if branching
382             using \p thisOne is better than branching using \p bestSoFar.
383   
384    If \p bestSoFar is NULL, the routine should return a nonzero value.
385    This routine is used only after strong branching.
386    Either this or bestBranch is used depending which user wants.
387
388 */
389
390  virtual int
391  betterBranch (CbcBranchingObject * thisOne,
392                CbcBranchingObject * bestSoFar,
393                double changeUp, int numberInfeasibilitiesUp,
394                double changeDown, int numberInfeasibilitiesDown) = 0 ;
395
396  /** \brief Compare N branching objects. Return index of best
397      and sets way of branching in chosen object.
398   
399    Either this or betterBranch is used depending which user wants.
400  */
401
402  virtual int
403  bestBranch (CbcBranchingObject ** objects, int numberObjects, int numberUnsatisfied,
404              double * changeUp, int * numberInfeasibilitiesUp,
405              double * changeDown, int * numberInfeasibilitiesDown,
406              double objectiveValue) ;
407
408  /** Says whether this method can handle both methods -
409      1 better, 2 best, 3 both */
410  virtual int whichMethod() {return 2;};
411
412  /** Saves a clone of current branching object.  Can be used to update
413      information on object causing branch - after branch */
414  virtual void saveBranchingObject(OsiBranchingObject * object) {};
415  /** Pass in information on branch just done.
416      assumes object can get information from solver */
417  virtual void updateInformation(OsiSolverInterface * solver, 
418                                 const CbcNode * node) {};
419  /** Sets or gets best criterion so far */
420  virtual void setBestCriterion(double value) {};
421  virtual double getBestCriterion() const {return 0.0;};
422  /// Create C++ lines to get to current state
423  virtual void generateCpp( FILE * fp) {};
424  /// Model
425  inline CbcModel * cbcModel() const
426  { return model_;}
427  /* If chooseMethod_ id non-null then the rest is fairly pointless
428     as choosemethod_ will be doing all work
429  */
430  OsiChooseVariable * chooseMethod() const
431  { return chooseMethod_;};
432  /// Set (clone) chooseMethod
433  void setChooseMethod(const OsiChooseVariable & method);
434
435protected:
436 
437  // Clone of branching object
438  CbcBranchingObject * object_;
439  /// Pointer to model
440  CbcModel * model_;
441  /* If chooseMethod_ id non-null then the rest is fairly pointless
442     as choosemethod_ will be doing all work
443  */
444  OsiChooseVariable * chooseMethod_;
445private:
446  /// Assignment is illegal
447  CbcBranchDecision & operator=(const CbcBranchDecision& rhs);
448 
449};
450/** Abstract base class for consequent bounds.
451    When a variable is branched on it normally interacts with other variables by
452    means of equations.  There are cases where we want to step outside LP and do something
453    more directly e.g. fix bounds.  This class is for that.
454
455    At present it need not be virtual as only instance is CbcFixVariable, but ...
456
457 */
458
459class CbcConsequence {
460
461public:
462
463  // Default Constructor
464  CbcConsequence ();
465
466  // Copy constructor
467  CbcConsequence ( const CbcConsequence & rhs);
468   
469  // Assignment operator
470  CbcConsequence & operator=( const CbcConsequence & rhs);
471
472  /// Clone
473  virtual CbcConsequence * clone() const=0;
474
475  /// Destructor
476  virtual ~CbcConsequence ();
477
478  /** Apply to an LP solver.  Action depends on state
479   */
480  virtual void applyToSolver(OsiSolverInterface * solver, int state) const=0;
481 
482protected:
483};
484
485#endif
Note: See TracBrowser for help on using the repository browser.