source: trunk/include/CbcBranchBase.hpp @ 74

Last change on this file since 74 was 74, checked in by forrest, 17 years ago

adding something to say if object a column

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