source: trunk/include/CbcBranchBase.hpp @ 129

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

make createBranch non const

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 12.2 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   /// update model
161  inline void setModel(CbcModel * model)
162  { model_ = model;};
163 
164  /// Return model
165  inline CbcModel * model() const
166  {return  model_;};
167
168  /// Return "up" estimate (default 1.0e-5)
169  virtual double upEstimate() const;
170  /// Return "down" estimate (default 1.0e-5)
171  virtual double downEstimate() const;
172 
173protected:
174  /// data
175
176  /// Model
177  CbcModel * model_;
178  /// Identifier (normally column number in matrix)
179  int id_;
180  /// Priority
181  int priority_;
182
183};
184
185/** \brief Abstract branching object base class
186
187  In the abstract, an CbcBranchingObject contains instructions for how to
188  branch. We want an abstract class so that we can describe how to branch on
189  simple objects (<i>e.g.</i>, integers) and more exotic objects
190  (<i>e.g.</i>, cliques or hyperplanes).
191
192  The #branch() method is the crucial routine: it is expected to be able to
193  step through a set of branch arms, executing the actions required to create
194  each subproblem in turn. The base class is primarily virtual to allow for
195  a wide range of problem modifications.
196
197  See CbcObject for an overview of the three classes (CbcObject,
198  CbcBranchingObject, and CbcBranchDecision) which make up cbc's branching
199  model.
200*/
201
202class CbcBranchingObject {
203
204public:
205
206  /// Default Constructor
207  CbcBranchingObject ();
208
209  /// Constructor
210  CbcBranchingObject (CbcModel * model, int variable, int way , double value);
211 
212  /// Copy constructor
213  CbcBranchingObject ( const CbcBranchingObject &);
214   
215  /// Assignment operator
216  CbcBranchingObject & operator=( const CbcBranchingObject& rhs);
217
218  /// Clone
219  virtual CbcBranchingObject * clone() const=0;
220
221  /// Destructor
222  virtual ~CbcBranchingObject ();
223
224  /** Some branchingObjects may claim to be able to skip
225      strong branching.  If so they ahve to fill in CbcStrongInfo.
226      The object mention in incoming CbcStrongInfo must match.
227      Returns nonzero if skip is wanted */
228  virtual int fillStrongInfo( CbcStrongInfo & info) {return 0;};
229  /** The number of branch arms created for this branching object
230
231    \todo The hardwired `2' has to be changed before cbc can do branches with
232          more than two arms.
233  */
234  virtual int numberBranches() const
235  {return 2;};
236
237  /// The number of branch arms left to be evaluated
238  virtual int numberBranchesLeft() const
239  {return numberBranchesLeft_;};
240
241  /** \brief Execute the actions required to branch, as specified by the
242             current state of the branching object, and advance the object's
243             state.  Mainly for diagnostics, whether it is true branch or
244             strong branching is also passed.
245             Returns change in guessed objective on next branch
246  */
247  virtual double branch(bool normalBranch=false)=0;
248
249  /** \brief Print something about branch - only if log level high
250  */
251  virtual void print(bool normalBranch) {};
252
253  /** \brief Return true if branch should fix variables
254  */
255  virtual bool boundBranch() const 
256  {return true;};
257
258  /** \brief Index identifying the associated CbcObject within its class.
259 
260    The name is misleading, and typically the index will <i>not</i> refer
261    directly to a variable.
262    Rather, it identifies an CbcObject within the class of similar
263    CbcObjects
264   
265    <i>E.g.</i>, for an CbcSimpleInteger, variable() is the index of the
266    integer variable in the set of integer variables (<i>not</i> the index of
267    the variable in the set of all variables).
268  */
269  inline int variable() const
270  {return variable_;};
271
272  /** Get the state of the branching object
273 
274    Returns a code indicating the active arm of the branching object.
275    The precise meaning is defined in the derived class.
276
277    \sa #way_
278  */
279  inline int way() const
280  {return way_;};
281
282  /** Set the state of the branching object.
283
284    See #way()
285  */
286  inline void way(int way)
287  {way_=way;};
288
289  /// Current value
290  inline double value() const
291  {return value_;};
292 
293  /// Return model
294  inline CbcModel * model() const
295  {return  model_;};
296
297protected:
298
299  /// The model that owns this branching object
300  CbcModel * model_;
301
302  /// Branching variable (0 is first integer)
303  int variable_;
304  // was - Way to branch - -1 down (first), 1 up, -2 down (second), 2 up (second)
305  /** The state of the branching object.
306
307    Specifies the active arm of the branching object. Coded as -1 to take
308    the `down' arm, +1 for the `up' arm. `Down' and `up' are defined based on
309    the natural meaning (floor and ceiling, respectively) for a simple integer.
310    The precise meaning is defined in the derived class.
311  */
312  int way_;
313
314  /// Current value
315  double value_;
316
317  /** Number of arms remaining to be evaluated
318
319    \todo Compare with CbcNodeInfo::numberBranchesLeft_, and check for
320          redundancy.
321  */
322  int numberBranchesLeft_;
323
324};
325
326
327/** Abstract branching decision base class
328
329  In the abstract, an CbcBranchDecision object is expected to be able to
330  compare two possible branching choices.
331
332  The #betterBranch() method is the crucial routine. It is expected to be able
333  to compare two \link CbcBranchingObject CbcBranchingObjects \endlink.
334
335  See CbcObject for an overview of the three classes (CbcObject,
336  CbcBranchingObject, and CbcBranchDecision) which make up cbc's branching
337  model.
338*/
339
340class CbcBranchDecision {
341public:
342  /// Default Constructor
343  CbcBranchDecision ();
344
345  /// Destructor
346  virtual ~CbcBranchDecision();
347
348 /// Clone
349  virtual CbcBranchDecision * clone() const = 0;
350
351  /// Initialize <i>e.g.</i> before starting to choose a branch at a node
352  virtual void initialize(CbcModel * model) = 0;
353
354  /** \brief Compare two branching objects. Return nonzero if branching
355             using \p thisOne is better than branching using \p bestSoFar.
356   
357    If \p bestSoFar is NULL, the routine should return a nonzero value.
358    This routine is used only after strong branching.
359    Either this or bestBranch is used depending which user wants.
360 */
361
362  virtual int
363  betterBranch (CbcBranchingObject * thisOne,
364                CbcBranchingObject * bestSoFar,
365                double changeUp, int numberInfeasibilitiesUp,
366                double changeDown, int numberInfeasibilitiesDown) = 0 ;
367
368  /** \brief Compare N branching objects. Return index of best
369      and sets way of branching in chosen object.
370   
371    Either this or betterBranch is used depending which user wants.
372  */
373
374  virtual int
375  bestBranch (CbcBranchingObject ** objects, int numberObjects, int numberUnsatisfied,
376              double * changeUp, int * numberInfeasibilitiesUp,
377              double * changeDown, int * numberInfeasibilitiesDown,
378              double objectiveValue) ;
379
380  /** Says whether this method can handle both methods -
381      1 better, 2 best, 3 both */
382  virtual int whichMethod() {return 2;};
383
384  /** Saves a clone of current branching object.  Can be used to update
385      information on object causing branch - after branch */
386  virtual void saveBranchingObject(CbcBranchingObject * object) {};
387  /** Pass in information on branch just done.
388      assumes object can get information from solver */
389  virtual void updateInformation(OsiSolverInterface * solver) {};
390
391protected:
392 
393  // Clone of branching object
394  CbcBranchingObject * object_;
395private:
396  /// Assignment is illegal
397  CbcBranchDecision & operator=(const CbcBranchDecision& rhs);
398 
399};
400
401#endif
Note: See TracBrowser for help on using the repository browser.