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

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

for osi methods

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 16.1 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 a branching object and indicate which way to branch first.
148     
149      The branching object has to know how to create branches (fix
150      variables, etc.)
151  */
152  virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver,const OsiBranchingInformation * info, int way) const;
153  /** Create an OsiSolverBranch object
154
155      This returns NULL if branch not represented by bound changes
156  */
157  virtual OsiSolverBranch * solverBranch() const;
158 
159  /** \brief Given a valid solution (with reduced costs, etc.),
160      return a branching object which would give a new feasible
161      point in a good direction.
162
163      If the method cannot generate a feasible point (because there aren't
164      any, or because it isn't bright enough to find one), it should
165      return null.
166  */
167  virtual CbcBranchingObject * preferredNewFeasible() const 
168  { return NULL;};
169 
170  /** \brief Given a valid solution (with reduced costs, etc.),
171      return a branching object which would give a new feasible
172      point in a bad direction.
173
174      If the method cannot generate a feasible point (because there aren't
175      any, or because it isn't bright enough to find one), it should
176      return null.
177  */
178  virtual CbcBranchingObject * notPreferredNewFeasible() const 
179  { return NULL;};
180
181  /** Reset variable bounds to their original values.
182 
183    Bounds may be tightened, so it may be good to be able to set this info in object.
184   */
185  virtual void resetBounds(const OsiSolverInterface * solver) {};
186 
187  /** Returns floor and ceiling i.e. closest valid points
188  */
189  virtual void floorCeiling(double & floorValue, double & ceilingValue, double value,
190                            double tolerance) const;
191
192  /// Identifier (normally column number in matrix)
193  inline int id() const
194  { return id_;};
195 
196   /// update model
197  inline void setModel(CbcModel * model)
198  { model_ = model;};
199 
200  /// Return model
201  inline CbcModel * model() const
202  {return  model_;};
203
204  /// If -1 down always chosen first, +1 up always, 0 normal
205  inline int preferredWay() const
206  { return preferredWay_;};
207  /// Set -1 down always chosen first, +1 up always, 0 normal
208  inline void setPreferredWay(int value)
209  { preferredWay_=value;};
210  /// Redoes data when sequence numbers change
211  virtual void redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns) {};
212 
213protected:
214  /// data
215
216  /// Model
217  CbcModel * model_;
218  /// Identifier (normally column number in matrix)
219  int id_;
220  /// If -1 down always chosen first, +1 up always, 0 normal
221  int preferredWay_;
222
223};
224
225/** \brief Abstract branching object base class
226    Now just difference with OsiBranchingObject
227
228  In the abstract, an CbcBranchingObject contains instructions for how to
229  branch. We want an abstract class so that we can describe how to branch on
230  simple objects (<i>e.g.</i>, integers) and more exotic objects
231  (<i>e.g.</i>, cliques or hyperplanes).
232
233  The #branch() method is the crucial routine: it is expected to be able to
234  step through a set of branch arms, executing the actions required to create
235  each subproblem in turn. The base class is primarily virtual to allow for
236  a wide range of problem modifications.
237
238  See CbcObject for an overview of the three classes (CbcObject,
239  CbcBranchingObject, and CbcBranchDecision) which make up cbc's branching
240  model.
241*/
242
243class CbcBranchingObject : public OsiBranchingObject {
244
245public:
246
247  /// Default Constructor
248  CbcBranchingObject ();
249
250  /// Constructor
251  CbcBranchingObject (CbcModel * model, int variable, int way , double value);
252 
253  /// Copy constructor
254  CbcBranchingObject ( const CbcBranchingObject &);
255   
256  /// Assignment operator
257  CbcBranchingObject & operator=( const CbcBranchingObject& rhs);
258
259  /// Clone
260  virtual CbcBranchingObject * clone() const=0;
261
262  /// Destructor
263  virtual ~CbcBranchingObject ();
264
265  /** Some branchingObjects may claim to be able to skip
266      strong branching.  If so they ahve to fill in CbcStrongInfo.
267      The object mention in incoming CbcStrongInfo must match.
268      Returns nonzero if skip is wanted */
269  virtual int fillStrongInfo( CbcStrongInfo & info) {return 0;};
270  /// Reset number of branches left to original
271  inline void resetNumberBranchesLeft()
272  { branchIndex_=0;};
273
274  /** \brief Execute the actions required to branch, as specified by the
275             current state of the branching object, and advance the object's
276             state.  Mainly for diagnostics, whether it is true branch or
277             strong branching is also passed.
278             Returns change in guessed objective on next branch
279  */
280  virtual double branch()=0;
281  /** \brief Execute the actions required to branch, as specified by the
282             current state of the branching object, and advance the object's
283             state.  Mainly for diagnostics, whether it is true branch or
284             strong branching is also passed.
285             Returns change in guessed objective on next branch
286  */
287  virtual double branch(OsiSolverInterface * solver)
288  { return branch();};
289
290  /** \brief Print something about branch - only if log level high
291  */
292  virtual void print() const {};
293
294  /** \brief Index identifying the associated CbcObject within its class.
295 
296    The name is misleading, and typically the index will <i>not</i> refer
297    directly to a variable.
298    Rather, it identifies an CbcObject within the class of similar
299    CbcObjects
300   
301    <i>E.g.</i>, for an CbcSimpleInteger, variable() is the index of the
302    integer variable in the set of integer variables (<i>not</i> the index of
303    the variable in the set of all variables).
304  */
305  inline int variable() const
306  {return variable_;};
307
308  /** Get the state of the branching object
309 
310    Returns a code indicating the active arm of the branching object.
311    The precise meaning is defined in the derived class.
312
313    \sa #way_
314  */
315  inline int way() const
316  {return way_;};
317
318  /** Set the state of the branching object.
319
320    See #way()
321  */
322  inline void way(int way)
323  {way_=way;};
324
325  /// Return model
326  inline CbcModel * model() const
327  {return  model_;};
328
329  /// Return pointer back to object which created
330  inline CbcObject * object() const
331  {return  originalCbcObject_;};
332  /// Set pointer back to object which created
333  inline void setOriginalObject(CbcObject * object)
334  {originalCbcObject_=object;};
335
336protected:
337
338  /// The model that owns this branching object
339  CbcModel * model_;
340  /// Pointer back to object which created
341  CbcObject * originalCbcObject_;
342
343  /// Branching variable (0 is first integer)
344  int variable_;
345  // was - Way to branch - -1 down (first), 1 up, -2 down (second), 2 up (second)
346  /** The state of the branching object.
347
348    Specifies the active arm of the branching object. Coded as -1 to take
349    the `down' arm, +1 for the `up' arm. `Down' and `up' are defined based on
350    the natural meaning (floor and ceiling, respectively) for a simple integer.
351    The precise meaning is defined in the derived class.
352  */
353  int way_;
354
355};
356
357
358/** Abstract branching decision base class
359
360  In the abstract, an CbcBranchDecision object is expected to be able to
361  compare two possible branching choices.
362
363  The #betterBranch() method is the crucial routine. It is expected to be able
364  to compare two \link CbcBranchingObject CbcBranchingObjects \endlink.
365
366  See CbcObject for an overview of the three classes (CbcObject,
367  CbcBranchingObject, and CbcBranchDecision) which make up cbc's branching
368  model.
369*/
370
371class CbcBranchDecision {
372public:
373  /// Default Constructor
374  CbcBranchDecision ();
375
376  // Copy constructor
377  CbcBranchDecision ( const 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(OsiBranchingObject * 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  /// Model
432  inline CbcModel * cbcModel() const
433  { return model_;}
434  /* If chooseMethod_ id non-null then the rest is fairly pointless
435     as choosemethod_ will be doing all work
436  */
437  OsiChooseVariable * chooseMethod() const
438  { return chooseMethod_;};
439  /// Set (clone) chooseMethod
440  void setChooseMethod(const OsiChooseVariable & method);
441
442protected:
443 
444  // Clone of branching object
445  CbcBranchingObject * object_;
446  /// Pointer to model
447  CbcModel * model_;
448  /* If chooseMethod_ id non-null then the rest is fairly pointless
449     as choosemethod_ will be doing all work
450  */
451  OsiChooseVariable * chooseMethod_;
452private:
453  /// Assignment is illegal
454  CbcBranchDecision & operator=(const CbcBranchDecision& rhs);
455 
456};
457/** Abstract base class for consequent bounds.
458    When a variable is branched on it normally interacts with other variables by
459    means of equations.  There are cases where we want to step outside LP and do something
460    more directly e.g. fix bounds.  This class is for that.
461
462    At present it need not be virtual as only instance is CbcFixVariable, but ...
463
464 */
465
466class CbcConsequence {
467
468public:
469
470  // Default Constructor
471  CbcConsequence ();
472
473  // Copy constructor
474  CbcConsequence ( const CbcConsequence & rhs);
475   
476  // Assignment operator
477  CbcConsequence & operator=( const CbcConsequence & rhs);
478
479  /// Clone
480  virtual CbcConsequence * clone() const=0;
481
482  /// Destructor
483  virtual ~CbcConsequence ();
484
485  /** Apply to an LP solver.  Action depends on state
486   */
487  virtual void applyToSolver(OsiSolverInterface * solver, int state) const=0;
488 
489protected:
490};
491
492#endif
Note: See TracBrowser for help on using the repository browser.