source: trunk/include/CbcBranchBase.hpp @ 216

Last change on this file since 216 was 216, checked in by forrest, 16 years ago

add branching stuff

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