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

Last change on this file since 1121 was 1121, checked in by forrest, 10 years ago

compiler warnings, deterministic parallel and stability

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