source: trunk/Cbc/src/CbcBranchBase.hpp @ 862

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

changes to heuristics and allow collection of more statistics

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