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

Last change on this file since 400 was 356, checked in by ladanyi, 14 years ago

finishing conversion to svn

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