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

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

towards common use with other solvers

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