source: trunk/include/CbcBranchBase.hpp @ 122

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

major changes

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 10.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
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
43class CbcObject {
44
45public:
46
47  // Default Constructor
48  CbcObject ();
49
50  // Useful constructor
51  CbcObject (CbcModel * model);
52 
53  // Copy constructor
54  CbcObject ( const CbcObject &);
55   
56  // Assignment operator
57  CbcObject & operator=( const CbcObject& rhs);
58
59  /// Clone
60  virtual CbcObject * clone() const=0;
61
62  /// Destructor
63  virtual ~CbcObject ();
64
65  /** Infeasibility of the object
66
67      This is some measure of the infeasibility of the object. It should be
68      scaled to be in the range [0.0, 0.5], with 0.0 indicating the object
69      is satisfied.
70
71      The preferred branching direction is returned in preferredWay,
72
73      This is used to prepare for strong branching but should also think of
74      case when no strong branching
75     
76      The object may also compute an estimate of cost of going "up" or "down".
77      This will probably be based on pseudo-cost ideas
78  */
79  virtual double infeasibility(int &preferredWay) const = 0;
80
81  /** For the variable(s) referenced by the object,
82      look at the current solution and set bounds to match the solution.
83  */
84  virtual void feasibleRegion() = 0;
85
86  /** Create a branching object and indicate which way to branch first.
87
88      The branching object has to know how to create branches (fix
89      variables, etc.)
90  */
91  virtual CbcBranchingObject * createBranch(int way) const = 0;
92 
93  /** \brief Given a valid solution (with reduced costs, etc.),
94      return a branching object which would give a new feasible
95      point in a good direction.
96
97      If the method cannot generate a feasible point (because there aren't
98      any, or because it isn't bright enough to find one), it should
99      return null.
100  */
101  virtual CbcBranchingObject * preferredNewFeasible() const 
102  { return NULL;};
103 
104  /** \brief Given a valid solution (with reduced costs, etc.),
105      return a branching object which would give a new feasible
106      point in a bad direction.
107
108      If the method cannot generate a feasible point (because there aren't
109      any, or because it isn't bright enough to find one), it should
110      return null.
111  */
112  virtual CbcBranchingObject * notPreferredNewFeasible() const 
113  { return NULL;};
114
115  /** Reset variable bounds to their original values.
116 
117    Bounds may be tightened, so it may be good to be able to reset them to
118    their original values.
119   */
120  virtual void resetBounds() {};
121 
122  /** \brief Return true if branch created by object should fix variables
123  */
124  virtual bool boundBranch() const 
125  {return true;};
126  /** Returns floor and ceiling i.e. closest valid points
127  */
128  virtual void floorCeiling(double & floorValue, double & ceilingValue, double value,
129                            double tolerance) const;
130
131  /// Identifier (normally column number in matrix)
132  inline int id() const
133  { return id_;};
134  /// Return Priority
135  inline int priority() const
136  { return priority_;};
137  /// Set priority
138  inline void setPriority(int priority)
139  { priority_ = priority;};
140 
141  /// Column number if single column object -1 otherwise
142  virtual int columnNumber() const;
143 
144   /// update model
145  inline void setModel(CbcModel * model)
146  { model_ = model;};
147 
148  /// Return model
149  inline CbcModel * model() const
150  {return  model_;};
151
152  /// Return "up" estimate (default 1.0e-5)
153  virtual double upEstimate() const;
154  /// Return "down" estimate (default 1.0e-5)
155  virtual double downEstimate() const;
156 
157protected:
158  /// data
159
160  /// Model
161  CbcModel * model_;
162  /// Identifier (normally column number in matrix)
163  int id_;
164  /// Priority
165  int priority_;
166
167};
168
169/** \brief Abstract branching object base class
170
171  In the abstract, an CbcBranchingObject contains instructions for how to
172  branch. We want an abstract class so that we can describe how to branch on
173  simple objects (<i>e.g.</i>, integers) and more exotic objects
174  (<i>e.g.</i>, cliques or hyperplanes).
175
176  The #branch() method is the crucial routine: it is expected to be able to
177  step through a set of branch arms, executing the actions required to create
178  each subproblem in turn. The base class is primarily virtual to allow for
179  a wide range of problem modifications.
180
181  See CbcObject for an overview of the three classes (CbcObject,
182  CbcBranchingObject, and CbcBranchDecision) which make up cbc's branching
183  model.
184*/
185
186class CbcBranchingObject {
187
188public:
189
190  /// Default Constructor
191  CbcBranchingObject ();
192
193  /// Constructor
194  CbcBranchingObject (CbcModel * model, int variable, int way , double value);
195 
196  /// Copy constructor
197  CbcBranchingObject ( const CbcBranchingObject &);
198   
199  /// Assignment operator
200  CbcBranchingObject & operator=( const CbcBranchingObject& rhs);
201
202  /// Clone
203  virtual CbcBranchingObject * clone() const=0;
204
205  /// Destructor
206  virtual ~CbcBranchingObject ();
207 
208  /** The number of branch arms created for this branching object
209
210    \todo The hardwired `2' has to be changed before cbc can do branches with
211          more than two arms.
212  */
213  virtual int numberBranches() const
214  {return 2;};
215
216  /// The number of branch arms left to be evaluated
217  virtual int numberBranchesLeft() const
218  {return numberBranchesLeft_;};
219
220  /** \brief Execute the actions required to branch, as specified by the
221             current state of the branching object, and advance the object's
222             state.  Mainly for diagnostics, whether it is true branch or
223             strong branching is also passed.
224             Returns change in guessed objective on next branch
225  */
226  virtual double branch(bool normalBranch=false)=0;
227
228  /** \brief Print something about branch - only if log level high
229  */
230  virtual void print(bool normalBranch) {};
231
232  /** \brief Return true if branch should fix variables
233  */
234  virtual bool boundBranch() const 
235  {return true;};
236
237  /** \brief Index identifying the associated CbcObject within its class.
238 
239    The name is misleading, and typically the index will <i>not</i> refer
240    directly to a variable.
241    Rather, it identifies an CbcObject within the class of similar
242    CbcObjects
243   
244    <i>E.g.</i>, for an CbcSimpleInteger, variable() is the index of the
245    integer variable in the set of integer variables (<i>not</i> the index of
246    the variable in the set of all variables).
247  */
248  inline int variable() const
249  {return variable_;};
250
251  /** Get the state of the branching object
252 
253    Returns a code indicating the active arm of the branching object.
254    The precise meaning is defined in the derived class.
255
256    \sa #way_
257  */
258  inline int way() const
259  {return way_;};
260
261  /** Set the state of the branching object.
262
263    See #way()
264  */
265  inline void way(int way)
266  {way_=way;};
267
268  /// Current value
269  inline double value() const
270  {return value_;};
271 
272  /// Return model
273  inline CbcModel * model() const
274  {return  model_;};
275
276protected:
277
278  /// The model that owns this branching object
279  CbcModel * model_;
280
281  /// Branching variable (0 is first integer)
282  int variable_;
283  // was - Way to branch - -1 down (first), 1 up, -2 down (second), 2 up (second)
284  /** The state of the branching object.
285
286    Specifies the active arm of the branching object. Coded as -1 to take
287    the `down' arm, +1 for the `up' arm. `Down' and `up' are defined based on
288    the natural meaning (floor and ceiling, respectively) for a simple integer.
289    The precise meaning is defined in the derived class.
290  */
291  int way_;
292
293  /// Current value
294  double value_;
295
296  /** Number of arms remaining to be evaluated
297
298    \todo Compare with CbcNodeInfo::numberBranchesLeft_, and check for
299          redundancy.
300  */
301  int numberBranchesLeft_;
302
303};
304
305
306/** Abstract branching decision base class
307
308  In the abstract, an CbcBranchDecision object is expected to be able to
309  compare two possible branching choices.
310
311  The #betterBranch() method is the crucial routine. It is expected to be able
312  to compare two \link CbcBranchingObject CbcBranchingObjects \endlink.
313
314  See CbcObject for an overview of the three classes (CbcObject,
315  CbcBranchingObject, and CbcBranchDecision) which make up cbc's branching
316  model.
317*/
318
319class CbcBranchDecision {
320public:
321  /// Default Constructor
322  CbcBranchDecision ();
323
324  /// Destructor
325  virtual ~CbcBranchDecision();
326
327 /// Clone
328  virtual CbcBranchDecision * clone() const = 0;
329
330  /// Initialize <i>e.g.</i> before starting to choose a branch at a node
331  virtual void initialize(CbcModel * model) = 0;
332
333  /** \brief Compare two branching objects. Return nonzero if branching
334             using \p thisOne is better than branching using \p bestSoFar.
335   
336    If \p bestSoFar is NULL, the routine should return a nonzero value.
337    This routine is used only after strong branching.
338
339    It is now reccommended that bestBranch is used - see below.
340    This has been left for compatibility.
341 */
342
343  virtual int
344  betterBranch (CbcBranchingObject * thisOne,
345                CbcBranchingObject * bestSoFar,
346                double changeUp, int numberInfeasibilitiesUp,
347                double changeDown, int numberInfeasibilitiesDown) = 0 ;
348
349  /** \brief Compare N branching objects. Return index of best
350      and sets way of branching in chosen object.
351   
352    This routine is used only after strong branching.
353    This is reccommended version as it can be more sophisticated
354  */
355
356  virtual int
357  bestBranch (CbcBranchingObject ** objects, int numberObjects, int numberUnsatisfied,
358              double * changeUp, int * numberInfeasibilitiesUp,
359              double * changeDown, int * numberInfeasibilitiesDown,
360              double objectiveValue) ;
361
362
363
364private:
365 
366  /// Assignment is illegal
367  CbcBranchDecision & operator=(const CbcBranchDecision& rhs);
368 
369};
370
371#endif
Note: See TracBrowser for help on using the repository browser.