source: stable/2.4/Cbc/src/CbcBranchBase.hpp @ 1271

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

Creating new stable branch 2.4 from trunk (rev 1270)

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