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

Last change on this file since 435 was 424, checked in by forrest, 13 years ago

many changes

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 14.6 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  /** \brief Return true if object can take part in normal heuristics
150  */
151  virtual bool canDoHeuristics() const 
152  {return true;};
153  /** Returns floor and ceiling i.e. closest valid points
154  */
155  virtual void floorCeiling(double & floorValue, double & ceilingValue, double value,
156                            double tolerance) const;
157
158  /// Identifier (normally column number in matrix)
159  inline int id() const
160  { return id_;};
161  /// Return Priority
162  inline int priority() const
163  { return priority_;};
164  /// Set priority
165  inline void setPriority(int priority)
166  { priority_ = priority;};
167 
168  /// Column number if single column object -1 otherwise
169  virtual int columnNumber() const;
170
171 
172   /// update model
173  inline void setModel(CbcModel * model)
174  { model_ = model;};
175 
176  /// Return model
177  inline CbcModel * model() const
178  {return  model_;};
179
180  /// Return "up" estimate (default 1.0e-5)
181  virtual double upEstimate() const;
182  /// Return "down" estimate (default 1.0e-5)
183  virtual double downEstimate() const;
184  /// If -1 down always chosen first, +1 up always, 0 normal
185  inline int preferredWay() const
186  { return preferredWay_;};
187  /// Set -1 down always chosen first, +1 up always, 0 normal
188  inline void setPreferredWay(int value)
189  { preferredWay_=value;};
190  /// Redoes data when sequence numbers change
191  virtual void redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns) {};
192 
193protected:
194  /// data
195
196  /// Model
197  CbcModel * model_;
198  /// Identifier (normally column number in matrix)
199  int id_;
200  /// Priority
201  int priority_;
202  /// If -1 down always chosen first, +1 up always, 0 normal
203  int preferredWay_;
204
205};
206
207/** \brief Abstract branching object base class
208
209  In the abstract, an CbcBranchingObject contains instructions for how to
210  branch. We want an abstract class so that we can describe how to branch on
211  simple objects (<i>e.g.</i>, integers) and more exotic objects
212  (<i>e.g.</i>, cliques or hyperplanes).
213
214  The #branch() method is the crucial routine: it is expected to be able to
215  step through a set of branch arms, executing the actions required to create
216  each subproblem in turn. The base class is primarily virtual to allow for
217  a wide range of problem modifications.
218
219  See CbcObject for an overview of the three classes (CbcObject,
220  CbcBranchingObject, and CbcBranchDecision) which make up cbc's branching
221  model.
222*/
223
224class CbcBranchingObject {
225
226public:
227
228  /// Default Constructor
229  CbcBranchingObject ();
230
231  /// Constructor
232  CbcBranchingObject (CbcModel * model, int variable, int way , double value);
233 
234  /// Copy constructor
235  CbcBranchingObject ( const CbcBranchingObject &);
236   
237  /// Assignment operator
238  CbcBranchingObject & operator=( const CbcBranchingObject& rhs);
239
240  /// Clone
241  virtual CbcBranchingObject * clone() const=0;
242
243  /// Destructor
244  virtual ~CbcBranchingObject ();
245
246  /** Some branchingObjects may claim to be able to skip
247      strong branching.  If so they ahve to fill in CbcStrongInfo.
248      The object mention in incoming CbcStrongInfo must match.
249      Returns nonzero if skip is wanted */
250  virtual int fillStrongInfo( CbcStrongInfo & info) {return 0;};
251  /** The number of branch arms created for this branching object
252
253    \todo The hardwired `2' has to be changed before cbc can do branches with
254          more than two arms.
255  */
256  virtual int numberBranches() const
257  {return 2;};
258
259  /// The number of branch arms left to be evaluated
260  virtual int numberBranchesLeft() const
261  {return numberBranchesLeft_;};
262  /// Reset number of branches left to original
263  inline void resetNumberBranchesLeft()
264  { numberBranchesLeft_ = numberBranches();};
265
266  /** \brief Execute the actions required to branch, as specified by the
267             current state of the branching object, and advance the object's
268             state.  Mainly for diagnostics, whether it is true branch or
269             strong branching is also passed.
270             Returns change in guessed objective on next branch
271  */
272  virtual double branch(bool normalBranch=false)=0;
273
274  /** \brief Print something about branch - only if log level high
275  */
276  virtual void print(bool normalBranch) {};
277
278  /** \brief Return true if branch should fix variables
279  */
280  virtual bool boundBranch() const 
281  {return true;};
282
283  /** \brief Index identifying the associated CbcObject within its class.
284 
285    The name is misleading, and typically the index will <i>not</i> refer
286    directly to a variable.
287    Rather, it identifies an CbcObject within the class of similar
288    CbcObjects
289   
290    <i>E.g.</i>, for an CbcSimpleInteger, variable() is the index of the
291    integer variable in the set of integer variables (<i>not</i> the index of
292    the variable in the set of all variables).
293  */
294  inline int variable() const
295  {return variable_;};
296
297  /** Get the state of the branching object
298 
299    Returns a code indicating the active arm of the branching object.
300    The precise meaning is defined in the derived class.
301
302    \sa #way_
303  */
304  inline int way() const
305  {return way_;};
306
307  /** Set the state of the branching object.
308
309    See #way()
310  */
311  inline void way(int way)
312  {way_=way;};
313
314  /// Current value
315  inline double value() const
316  {return value_;};
317 
318  /// Return model
319  inline CbcModel * model() const
320  {return  model_;};
321
322  /// Return pointer back to object which created
323  inline CbcObject * object() const
324  {return  originalObject_;};
325  /// Set pointer back to object which created
326  inline void setOriginalObject(CbcObject * object)
327  {originalObject_=object;};
328
329protected:
330
331  /// The model that owns this branching object
332  CbcModel * model_;
333  /// Pointer back to object which created
334  CbcObject * originalObject_;
335
336  /// Branching variable (0 is first integer)
337  int variable_;
338  // was - Way to branch - -1 down (first), 1 up, -2 down (second), 2 up (second)
339  /** The state of the branching object.
340
341    Specifies the active arm of the branching object. Coded as -1 to take
342    the `down' arm, +1 for the `up' arm. `Down' and `up' are defined based on
343    the natural meaning (floor and ceiling, respectively) for a simple integer.
344    The precise meaning is defined in the derived class.
345  */
346  int way_;
347
348  /// Current value
349  double value_;
350
351  /** Number of arms remaining to be evaluated
352
353    \todo Compare with CbcNodeInfo::numberBranchesLeft_, and check for
354          redundancy.
355  */
356  int numberBranchesLeft_;
357
358};
359
360
361/** Abstract branching decision base class
362
363  In the abstract, an CbcBranchDecision object is expected to be able to
364  compare two possible branching choices.
365
366  The #betterBranch() method is the crucial routine. It is expected to be able
367  to compare two \link CbcBranchingObject CbcBranchingObjects \endlink.
368
369  See CbcObject for an overview of the three classes (CbcObject,
370  CbcBranchingObject, and CbcBranchDecision) which make up cbc's branching
371  model.
372*/
373
374class CbcBranchDecision {
375public:
376  /// Default Constructor
377  CbcBranchDecision ();
378
379  /// Destructor
380  virtual ~CbcBranchDecision();
381
382 /// Clone
383  virtual CbcBranchDecision * clone() const = 0;
384
385  /// Initialize <i>e.g.</i> before starting to choose a branch at a node
386  virtual void initialize(CbcModel * model) = 0;
387
388  /** \brief Compare two branching objects. Return nonzero if branching
389             using \p thisOne is better than branching using \p bestSoFar.
390   
391    If \p bestSoFar is NULL, the routine should return a nonzero value.
392    This routine is used only after strong branching.
393    Either this or bestBranch is used depending which user wants.
394
395 */
396
397  virtual int
398  betterBranch (CbcBranchingObject * thisOne,
399                CbcBranchingObject * bestSoFar,
400                double changeUp, int numberInfeasibilitiesUp,
401                double changeDown, int numberInfeasibilitiesDown) = 0 ;
402
403  /** \brief Compare N branching objects. Return index of best
404      and sets way of branching in chosen object.
405   
406    Either this or betterBranch is used depending which user wants.
407  */
408
409  virtual int
410  bestBranch (CbcBranchingObject ** objects, int numberObjects, int numberUnsatisfied,
411              double * changeUp, int * numberInfeasibilitiesUp,
412              double * changeDown, int * numberInfeasibilitiesDown,
413              double objectiveValue) ;
414
415  /** Says whether this method can handle both methods -
416      1 better, 2 best, 3 both */
417  virtual int whichMethod() {return 2;};
418
419  /** Saves a clone of current branching object.  Can be used to update
420      information on object causing branch - after branch */
421  virtual void saveBranchingObject(CbcBranchingObject * object) {};
422  /** Pass in information on branch just done.
423      assumes object can get information from solver */
424  virtual void updateInformation(OsiSolverInterface * solver, 
425                                 const CbcNode * node) {};
426  /** Sets or gets best criterion so far */
427  virtual void setBestCriterion(double value) {};
428  virtual double getBestCriterion() const {return 0.0;};
429  /// Create C++ lines to get to current state
430  virtual void generateCpp( FILE * fp) {};
431
432protected:
433 
434  // Clone of branching object
435  CbcBranchingObject * object_;
436private:
437  /// Assignment is illegal
438  CbcBranchDecision & operator=(const CbcBranchDecision& rhs);
439 
440};
441/** Abstract base class for consequent bounds.
442    When a variable is branched on it normally interacts with other variables by
443    means of equations.  There are cases where we want to step outside LP and do something
444    more directly e.g. fix bounds.  This class is for that.
445
446    At present it need not be virtual as only instance is CbcFixVariable, but ...
447
448 */
449
450class CbcConsequence {
451
452public:
453
454  // Default Constructor
455  CbcConsequence ();
456
457  // Copy constructor
458  CbcConsequence ( const CbcConsequence & rhs);
459   
460  // Assignment operator
461  CbcConsequence & operator=( const CbcConsequence & rhs);
462
463  /// Clone
464  virtual CbcConsequence * clone() const=0;
465
466  /// Destructor
467  virtual ~CbcConsequence ();
468
469  /** Apply to an LP solver.  Action depends on state
470   */
471  virtual void applyToSolver(OsiSolverInterface * solver, int state) const=0;
472 
473protected:
474};
475
476#endif
Note: See TracBrowser for help on using the repository browser.