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

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

faster parallel?

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 17.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#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  /** \brief Print something about branch - only if log level high
302  */
303  virtual void print() const {};
304
305  /** \brief Index identifying the associated CbcObject within its class.
306 
307    The name is misleading, and typically the index will <i>not</i> refer
308    directly to a variable.
309    Rather, it identifies an CbcObject within the class of similar
310    CbcObjects
311   
312    <i>E.g.</i>, for an CbcSimpleInteger, variable() is the index of the
313    integer variable in the set of integer variables (<i>not</i> the index of
314    the variable in the set of all variables).
315  */
316  inline int variable() const
317  {return variable_;};
318
319  /** Get the state of the branching object
320 
321    Returns a code indicating the active arm of the branching object.
322    The precise meaning is defined in the derived class.
323
324    \sa #way_
325  */
326  inline int way() const
327  {return way_;};
328
329  /** Set the state of the branching object.
330
331    See #way()
332  */
333  inline void way(int way)
334  {way_=way;};
335
336   /// update model
337  inline void setModel(CbcModel * model)
338  { model_ = model;};
339  /// Return model
340  inline CbcModel * model() const
341  {return  model_;};
342
343  /// Return pointer back to object which created
344  inline CbcObject * object() const
345  {return  originalCbcObject_;};
346  /// Set pointer back to object which created
347  inline void setOriginalObject(CbcObject * object)
348  {originalCbcObject_=object;};
349
350protected:
351
352  /// The model that owns this branching object
353  CbcModel * model_;
354  /// Pointer back to object which created
355  CbcObject * originalCbcObject_;
356
357  /// Branching variable (0 is first integer)
358  int variable_;
359  // was - Way to branch - -1 down (first), 1 up, -2 down (second), 2 up (second)
360  /** The state of the branching object.
361
362    Specifies the active arm of the branching object. Coded as -1 to take
363    the `down' arm, +1 for the `up' arm. `Down' and `up' are defined based on
364    the natural meaning (floor and ceiling, respectively) for a simple integer.
365    The precise meaning is defined in the derived class.
366  */
367  int way_;
368
369};
370
371
372/** Abstract branching decision base class
373
374  In the abstract, an CbcBranchDecision object is expected to be able to
375  compare two possible branching choices.
376
377  The #betterBranch() method is the crucial routine. It is expected to be able
378  to compare two \link CbcBranchingObject CbcBranchingObjects \endlink.
379
380  See CbcObject for an overview of the three classes (CbcObject,
381  CbcBranchingObject, and CbcBranchDecision) which make up cbc's branching
382  model.
383*/
384
385class CbcBranchDecision {
386public:
387  /// Default Constructor
388  CbcBranchDecision ();
389
390  // Copy constructor
391  CbcBranchDecision ( const CbcBranchDecision &);
392   
393  /// Destructor
394  virtual ~CbcBranchDecision();
395
396 /// Clone
397  virtual CbcBranchDecision * clone() const = 0;
398
399  /// Initialize <i>e.g.</i> before starting to choose a branch at a node
400  virtual void initialize(CbcModel * model) = 0;
401
402  /** \brief Compare two branching objects. Return nonzero if branching
403             using \p thisOne is better than branching using \p bestSoFar.
404   
405    If \p bestSoFar is NULL, the routine should return a nonzero value.
406    This routine is used only after strong branching.
407    Either this or bestBranch is used depending which user wants.
408
409 */
410
411  virtual int
412  betterBranch (CbcBranchingObject * thisOne,
413                CbcBranchingObject * bestSoFar,
414                double changeUp, int numberInfeasibilitiesUp,
415                double changeDown, int numberInfeasibilitiesDown) = 0 ;
416
417  /** \brief Compare N branching objects. Return index of best
418      and sets way of branching in chosen object.
419   
420    Either this or betterBranch is used depending which user wants.
421  */
422
423  virtual int
424  bestBranch (CbcBranchingObject ** objects, int numberObjects, int numberUnsatisfied,
425              double * changeUp, int * numberInfeasibilitiesUp,
426              double * changeDown, int * numberInfeasibilitiesDown,
427              double objectiveValue) ;
428
429  /** Says whether this method can handle both methods -
430      1 better, 2 best, 3 both */
431  virtual int whichMethod() {return 2;};
432
433  /** Saves a clone of current branching object.  Can be used to update
434      information on object causing branch - after branch */
435  virtual void saveBranchingObject(OsiBranchingObject * object) {};
436  /** Pass in information on branch just done.
437      assumes object can get information from solver */
438  virtual void updateInformation(OsiSolverInterface * solver, 
439                                 const CbcNode * node) {};
440  /** Sets or gets best criterion so far */
441  virtual void setBestCriterion(double value) {};
442  virtual double getBestCriterion() const {return 0.0;};
443  /// Create C++ lines to get to current state
444  virtual void generateCpp( FILE * fp) {};
445  /// Model
446  inline CbcModel * cbcModel() const
447  { return 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() const
452  { return chooseMethod_;};
453  /// Set (clone) chooseMethod
454  void setChooseMethod(const OsiChooseVariable & method);
455
456protected:
457 
458  // Clone of branching object
459  CbcBranchingObject * object_;
460  /// Pointer to model
461  CbcModel * model_;
462  /* If chooseMethod_ id non-null then the rest is fairly pointless
463     as choosemethod_ will be doing all work
464  */
465  OsiChooseVariable * chooseMethod_;
466private:
467  /// Assignment is illegal
468  CbcBranchDecision & operator=(const CbcBranchDecision& rhs);
469 
470};
471/** Abstract base class for consequent bounds.
472    When a variable is branched on it normally interacts with other variables by
473    means of equations.  There are cases where we want to step outside LP and do something
474    more directly e.g. fix bounds.  This class is for that.
475
476    At present it need not be virtual as only instance is CbcFixVariable, but ...
477
478 */
479
480class CbcConsequence {
481
482public:
483
484  // Default Constructor
485  CbcConsequence ();
486
487  // Copy constructor
488  CbcConsequence ( const CbcConsequence & rhs);
489   
490  // Assignment operator
491  CbcConsequence & operator=( const CbcConsequence & rhs);
492
493  /// Clone
494  virtual CbcConsequence * clone() const=0;
495
496  /// Destructor
497  virtual ~CbcConsequence ();
498
499  /** Apply to an LP solver.  Action depends on state
500   */
501  virtual void applyToSolver(OsiSolverInterface * solver, int state) const=0;
502 
503protected:
504};
505/*  This stores data so an object can be updated
506 */
507class CbcObjectUpdateData {
508
509public:
510
511  /// Default Constructor
512  CbcObjectUpdateData ();
513
514  /// Useful constructor
515  CbcObjectUpdateData (CbcObject * object,
516                       int way,
517                       double change,
518                       int status,
519                       int intDecrease_,
520                       double branchingValue);
521 
522  /// Copy constructor
523  CbcObjectUpdateData ( const CbcObjectUpdateData &);
524   
525  /// Assignment operator
526  CbcObjectUpdateData & operator=( const CbcObjectUpdateData& rhs);
527
528  /// Destructor
529  virtual ~CbcObjectUpdateData ();
530
531 
532public:
533  /// data
534
535  /// Object
536  CbcObject * object_;
537  /// Branch as defined by instance of CbcObject
538  int way_;
539  /// Object number
540  int objectNumber_;
541  /// Change in objective
542  double change_;
543  /// Status 0 Optimal, 1 infeasible, 2 unknown
544  int status_;
545  /// Decrease in number unsatisfied
546  int intDecrease_;
547  /// Branching value
548  double branchingValue_;
549
550};
551
552#endif
Note: See TracBrowser for help on using the repository browser.