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

Last change on this file since 642 was 642, checked in by forrest, 12 years ago

update branches/devel for threads

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 16.2 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   /// update model
326  inline void setModel(CbcModel * model)
327  { model_ = model;};
328  /// Return model
329  inline CbcModel * model() const
330  {return  model_;};
331
332  /// Return pointer back to object which created
333  inline CbcObject * object() const
334  {return  originalCbcObject_;};
335  /// Set pointer back to object which created
336  inline void setOriginalObject(CbcObject * object)
337  {originalCbcObject_=object;};
338
339protected:
340
341  /// The model that owns this branching object
342  CbcModel * model_;
343  /// Pointer back to object which created
344  CbcObject * originalCbcObject_;
345
346  /// Branching variable (0 is first integer)
347  int variable_;
348  // was - Way to branch - -1 down (first), 1 up, -2 down (second), 2 up (second)
349  /** The state of the branching object.
350
351    Specifies the active arm of the branching object. Coded as -1 to take
352    the `down' arm, +1 for the `up' arm. `Down' and `up' are defined based on
353    the natural meaning (floor and ceiling, respectively) for a simple integer.
354    The precise meaning is defined in the derived class.
355  */
356  int way_;
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  // Copy constructor
380  CbcBranchDecision ( const CbcBranchDecision &);
381   
382  /// Destructor
383  virtual ~CbcBranchDecision();
384
385 /// Clone
386  virtual CbcBranchDecision * clone() const = 0;
387
388  /// Initialize <i>e.g.</i> before starting to choose a branch at a node
389  virtual void initialize(CbcModel * model) = 0;
390
391  /** \brief Compare two branching objects. Return nonzero if branching
392             using \p thisOne is better than branching using \p bestSoFar.
393   
394    If \p bestSoFar is NULL, the routine should return a nonzero value.
395    This routine is used only after strong branching.
396    Either this or bestBranch is used depending which user wants.
397
398 */
399
400  virtual int
401  betterBranch (CbcBranchingObject * thisOne,
402                CbcBranchingObject * bestSoFar,
403                double changeUp, int numberInfeasibilitiesUp,
404                double changeDown, int numberInfeasibilitiesDown) = 0 ;
405
406  /** \brief Compare N branching objects. Return index of best
407      and sets way of branching in chosen object.
408   
409    Either this or betterBranch is used depending which user wants.
410  */
411
412  virtual int
413  bestBranch (CbcBranchingObject ** objects, int numberObjects, int numberUnsatisfied,
414              double * changeUp, int * numberInfeasibilitiesUp,
415              double * changeDown, int * numberInfeasibilitiesDown,
416              double objectiveValue) ;
417
418  /** Says whether this method can handle both methods -
419      1 better, 2 best, 3 both */
420  virtual int whichMethod() {return 2;};
421
422  /** Saves a clone of current branching object.  Can be used to update
423      information on object causing branch - after branch */
424  virtual void saveBranchingObject(OsiBranchingObject * object) {};
425  /** Pass in information on branch just done.
426      assumes object can get information from solver */
427  virtual void updateInformation(OsiSolverInterface * solver, 
428                                 const CbcNode * node) {};
429  /** Sets or gets best criterion so far */
430  virtual void setBestCriterion(double value) {};
431  virtual double getBestCriterion() const {return 0.0;};
432  /// Create C++ lines to get to current state
433  virtual void generateCpp( FILE * fp) {};
434  /// Model
435  inline CbcModel * cbcModel() const
436  { return model_;}
437  /* If chooseMethod_ id non-null then the rest is fairly pointless
438     as choosemethod_ will be doing all work
439  */
440  OsiChooseVariable * chooseMethod() const
441  { return chooseMethod_;};
442  /// Set (clone) chooseMethod
443  void setChooseMethod(const OsiChooseVariable & method);
444
445protected:
446 
447  // Clone of branching object
448  CbcBranchingObject * object_;
449  /// Pointer to model
450  CbcModel * model_;
451  /* If chooseMethod_ id non-null then the rest is fairly pointless
452     as choosemethod_ will be doing all work
453  */
454  OsiChooseVariable * chooseMethod_;
455private:
456  /// Assignment is illegal
457  CbcBranchDecision & operator=(const CbcBranchDecision& rhs);
458 
459};
460/** Abstract base class for consequent bounds.
461    When a variable is branched on it normally interacts with other variables by
462    means of equations.  There are cases where we want to step outside LP and do something
463    more directly e.g. fix bounds.  This class is for that.
464
465    At present it need not be virtual as only instance is CbcFixVariable, but ...
466
467 */
468
469class CbcConsequence {
470
471public:
472
473  // Default Constructor
474  CbcConsequence ();
475
476  // Copy constructor
477  CbcConsequence ( const CbcConsequence & rhs);
478   
479  // Assignment operator
480  CbcConsequence & operator=( const CbcConsequence & rhs);
481
482  /// Clone
483  virtual CbcConsequence * clone() const=0;
484
485  /// Destructor
486  virtual ~CbcConsequence ();
487
488  /** Apply to an LP solver.  Action depends on state
489   */
490  virtual void applyToSolver(OsiSolverInterface * solver, int state) const=0;
491 
492protected:
493};
494
495#endif
Note: See TracBrowser for help on using the repository browser.