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

Last change on this file since 1148 was 1148, checked in by forrest, 11 years ago

changes to use heuristics with SOS etc

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 21.9 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  /** Set identifier (normally column number in matrix)
218      but 1000000000 to 1100000000 means optional branching object
219      i.e. code would work without it */
220  inline void setId(int value)
221  { id_ = value;}
222 
223  /** Return true if optional branching object
224      i.e. code would work without it */
225  inline bool optionalObject() const
226  { return (id_ >= 1000000000 && id_ < 1100000000);}
227 
228  /// Get position in object_ list
229  inline int position() const
230  { return position_;}
231 
232  /// Set position in object_ list
233  inline void setPosition(int position)
234  { position_ = position;}
235 
236   /// update model
237  inline void setModel(CbcModel * model)
238  { model_ = model;}
239 
240  /// Return model
241  inline CbcModel * model() const
242  {return  model_;}
243
244  /// If -1 down always chosen first, +1 up always, 0 normal
245  inline int preferredWay() const
246  { return preferredWay_;}
247  /// Set -1 down always chosen first, +1 up always, 0 normal
248  inline void setPreferredWay(int value)
249  { preferredWay_=value;}
250  /// Redoes data when sequence numbers change
251  virtual void redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns) {}
252 
253protected:
254  /// data
255
256  /// Model
257  CbcModel * model_;
258  /// Identifier (normally column number in matrix)
259  int id_;
260  /// Position in object list
261  int position_;
262  /// If -1 down always chosen first, +1 up always, 0 normal
263  int preferredWay_;
264
265};
266
267/** \brief Abstract branching object base class
268    Now just difference with OsiBranchingObject
269
270  In the abstract, an CbcBranchingObject contains instructions for how to
271  branch. We want an abstract class so that we can describe how to branch on
272  simple objects (<i>e.g.</i>, integers) and more exotic objects
273  (<i>e.g.</i>, cliques or hyperplanes).
274
275  The #branch() method is the crucial routine: it is expected to be able to
276  step through a set of branch arms, executing the actions required to create
277  each subproblem in turn. The base class is primarily virtual to allow for
278  a wide range of problem modifications.
279
280  See CbcObject for an overview of the three classes (CbcObject,
281  CbcBranchingObject, and CbcBranchDecision) which make up cbc's branching
282  model.
283*/
284
285class CbcBranchingObject : public OsiBranchingObject {
286
287public:
288
289  /// Default Constructor
290  CbcBranchingObject ();
291
292  /// Constructor
293  CbcBranchingObject (CbcModel * model, int variable, int way , double value);
294 
295  /// Copy constructor
296  CbcBranchingObject ( const CbcBranchingObject &);
297   
298  /// Assignment operator
299  CbcBranchingObject & operator=( const CbcBranchingObject& rhs);
300
301  /// Clone
302  virtual CbcBranchingObject * clone() const=0;
303
304  /// Destructor
305  virtual ~CbcBranchingObject ();
306
307  /** Some branchingObjects may claim to be able to skip
308      strong branching.  If so they ahve to fill in CbcStrongInfo.
309      The object mention in incoming CbcStrongInfo must match.
310      Returns nonzero if skip is wanted */
311  virtual int fillStrongInfo( CbcStrongInfo & info) {return 0;}
312  /// Reset number of branches left to original
313  inline void resetNumberBranchesLeft()
314  { branchIndex_=0;}
315  /// Set number of branches to do
316  inline void setNumberBranches(int value)
317  { branchIndex_=0;numberBranches_=value;}
318
319  /** \brief Execute the actions required to branch, as specified by the
320             current state of the branching object, and advance the object's
321             state.  Mainly for diagnostics, whether it is true branch or
322             strong branching is also passed.
323             Returns change in guessed objective on next branch
324  */
325  virtual double branch()=0;
326  /** \brief Execute the actions required to branch, as specified by the
327             current state of the branching object, and advance the object's
328             state.  Mainly for diagnostics, whether it is true branch or
329             strong branching is also passed.
330             Returns change in guessed objective on next branch
331  */
332  virtual double branch(OsiSolverInterface * solver)
333  { return branch();}
334  /** Update bounds in solver as in 'branch' and update given bounds.
335      branchState is -1 for 'down' +1 for 'up' */
336  virtual void fix(OsiSolverInterface * solver,
337                   double * lower, double * upper,
338                   int branchState) const {}
339
340  /** Reset every information so that the branching object appears to point to
341      the previous child. This method does not need to modify anything in any
342      solver. */
343  virtual void previousBranch() {
344    assert(branchIndex_ > 0);
345    branchIndex_--;
346    way_ = -way_;
347  }
348
349  using OsiBranchingObject::print ;
350  /** \brief Print something about branch - only if log level high
351  */
352  virtual void print() const {}
353
354  /** \brief Index identifying the associated CbcObject within its class.
355 
356    The name is misleading, and typically the index will <i>not</i> refer
357    directly to a variable.
358    Rather, it identifies an CbcObject within the class of similar
359    CbcObjects
360   
361    <i>E.g.</i>, for an CbcSimpleInteger, variable() is the index of the
362    integer variable in the set of integer variables (<i>not</i> the index of
363    the variable in the set of all variables).
364  */
365  inline int variable() const
366  {return variable_;}
367
368  /** Get the state of the branching object
369 
370    Returns a code indicating the active arm of the branching object.
371    The precise meaning is defined in the derived class.
372
373    \sa #way_
374  */
375  inline int way() const
376  {return way_;}
377
378  /** Set the state of the branching object.
379
380    See #way()
381  */
382  inline void way(int way)
383  {way_=way;}
384
385   /// update model
386  inline void setModel(CbcModel * model)
387  { model_ = model;}
388  /// Return model
389  inline CbcModel * model() const
390  {return  model_;}
391
392  /// Return pointer back to object which created
393  inline CbcObject * object() const
394  {return  originalCbcObject_;}
395  /// Set pointer back to object which created
396  inline void setOriginalObject(CbcObject * object)
397  {originalCbcObject_=object;}
398
399  // Methods used in heuristics
400 
401  /** Return the type (an integer identifier) of \c this */
402  virtual int type() const = 0;
403
404  /** Compare the original object of \c this with the original object of \c
405      brObj. Assumes that there is an ordering of the original objects.
406      This method should be invoked only if \c this and brObj are of the same
407      type.
408      Return negative/0/positive depending on whether \c this is
409      smaller/same/larger than the argument.
410  */
411  virtual int compareOriginalObject(const CbcBranchingObject* brObj) const
412  {
413    const CbcBranchingObject* br=dynamic_cast<const CbcBranchingObject*>(brObj);
414    return variable() - br->variable();
415  }
416
417  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
418      same type and must have the same original object, but they may have
419      different feasible regions.
420      Return the appropriate CbcRangeCompare value (first argument being the
421      sub/superset if that's the case). In case of overlap (and if \c
422      replaceIfOverlap is true) replace the current branching object with one
423      whose feasible region is the overlap.
424   */
425  virtual CbcRangeCompare compareBranchingObject
426  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false) = 0;
427
428protected:
429
430  /// The model that owns this branching object
431  CbcModel * model_;
432  /// Pointer back to object which created
433  CbcObject * originalCbcObject_;
434
435  /// Branching variable (0 is first integer)
436  int variable_;
437  // was - Way to branch - -1 down (first), 1 up, -2 down (second), 2 up (second)
438  /** The state of the branching object.
439
440    Specifies the active arm of the branching object. Coded as -1 to take
441    the `down' arm, +1 for the `up' arm. `Down' and `up' are defined based on
442    the natural meaning (floor and ceiling, respectively) for a simple integer.
443    The precise meaning is defined in the derived class.
444  */
445  int way_;
446
447};
448
449
450/** Abstract branching decision base class
451
452  In the abstract, an CbcBranchDecision object is expected to be able to
453  compare two possible branching choices.
454
455  The #betterBranch() method is the crucial routine. It is expected to be able
456  to compare two \link CbcBranchingObject CbcBranchingObjects \endlink.
457
458  See CbcObject for an overview of the three classes (CbcObject,
459  CbcBranchingObject, and CbcBranchDecision) which make up cbc's branching
460  model.
461*/
462
463class CbcBranchDecision {
464public:
465  /// Default Constructor
466  CbcBranchDecision ();
467
468  // Copy constructor
469  CbcBranchDecision ( const CbcBranchDecision &);
470   
471  /// Destructor
472  virtual ~CbcBranchDecision();
473
474 /// Clone
475  virtual CbcBranchDecision * clone() const = 0;
476
477  /// Initialize <i>e.g.</i> before starting to choose a branch at a node
478  virtual void initialize(CbcModel * model) = 0;
479
480  /** \brief Compare two branching objects. Return nonzero if branching
481             using \p thisOne is better than branching using \p bestSoFar.
482   
483    If \p bestSoFar is NULL, the routine should return a nonzero value.
484    This routine is used only after strong branching.
485    Either this or bestBranch is used depending which user wants.
486
487 */
488
489  virtual int
490  betterBranch (CbcBranchingObject * thisOne,
491                CbcBranchingObject * bestSoFar,
492                double changeUp, int numberInfeasibilitiesUp,
493                double changeDown, int numberInfeasibilitiesDown) = 0 ;
494
495  /** \brief Compare N branching objects. Return index of best
496      and sets way of branching in chosen object.
497   
498    Either this or betterBranch is used depending which user wants.
499  */
500
501  virtual int
502  bestBranch (CbcBranchingObject ** objects, int numberObjects, int numberUnsatisfied,
503              double * changeUp, int * numberInfeasibilitiesUp,
504              double * changeDown, int * numberInfeasibilitiesDown,
505              double objectiveValue) ;
506
507  /** Says whether this method can handle both methods -
508      1 better, 2 best, 3 both */
509  virtual int whichMethod() {return 2;}
510
511  /** Saves a clone of current branching object.  Can be used to update
512      information on object causing branch - after branch */
513  virtual void saveBranchingObject(OsiBranchingObject * object) {}
514  /** Pass in information on branch just done.
515      assumes object can get information from solver */
516  virtual void updateInformation(OsiSolverInterface * solver, 
517                                 const CbcNode * node) {}
518  /** Sets or gets best criterion so far */
519  virtual void setBestCriterion(double value) {}
520  virtual double getBestCriterion() const {return 0.0;}
521  /// Create C++ lines to get to current state
522  virtual void generateCpp( FILE * fp) {}
523  /// Model
524  inline CbcModel * cbcModel() const
525  { return model_;}
526  /* If chooseMethod_ id non-null then the rest is fairly pointless
527     as choosemethod_ will be doing all work
528  */
529  OsiChooseVariable * chooseMethod() const
530  { return chooseMethod_;}
531  /// Set (clone) chooseMethod
532  void setChooseMethod(const OsiChooseVariable & method);
533
534protected:
535 
536  // Clone of branching object
537  CbcBranchingObject * object_;
538  /// Pointer to model
539  CbcModel * model_;
540  /* If chooseMethod_ id non-null then the rest is fairly pointless
541     as choosemethod_ will be doing all work
542  */
543  OsiChooseVariable * chooseMethod_;
544private:
545  /// Assignment is illegal
546  CbcBranchDecision & operator=(const CbcBranchDecision& rhs);
547 
548};
549/** Abstract base class for consequent bounds.
550    When a variable is branched on it normally interacts with other variables by
551    means of equations.  There are cases where we want to step outside LP and do something
552    more directly e.g. fix bounds.  This class is for that.
553
554    At present it need not be virtual as only instance is CbcFixVariable, but ...
555
556 */
557
558class CbcConsequence {
559
560public:
561
562  // Default Constructor
563  CbcConsequence ();
564
565  // Copy constructor
566  CbcConsequence ( const CbcConsequence & rhs);
567   
568  // Assignment operator
569  CbcConsequence & operator=( const CbcConsequence & rhs);
570
571  /// Clone
572  virtual CbcConsequence * clone() const=0;
573
574  /// Destructor
575  virtual ~CbcConsequence ();
576
577  /** Apply to an LP solver.  Action depends on state
578   */
579  virtual void applyToSolver(OsiSolverInterface * solver, int state) const=0;
580 
581protected:
582};
583/*  This stores data so an object can be updated
584 */
585class CbcObjectUpdateData {
586
587public:
588
589  /// Default Constructor
590  CbcObjectUpdateData ();
591
592  /// Useful constructor
593  CbcObjectUpdateData (CbcObject * object,
594                       int way,
595                       double change,
596                       int status,
597                       int intDecrease_,
598                       double branchingValue);
599 
600  /// Copy constructor
601  CbcObjectUpdateData ( const CbcObjectUpdateData &);
602   
603  /// Assignment operator
604  CbcObjectUpdateData & operator=( const CbcObjectUpdateData& rhs);
605
606  /// Destructor
607  virtual ~CbcObjectUpdateData ();
608
609 
610public:
611  /// data
612
613  /// Object
614  CbcObject * object_;
615  /// Branch as defined by instance of CbcObject
616  int way_;
617  /// Object number
618  int objectNumber_;
619  /// Change in objective
620  double change_;
621  /// Status 0 Optimal, 1 infeasible, 2 unknown
622  int status_;
623  /// Decrease in number unsatisfied
624  int intDecrease_;
625  /// Branching value
626  double branchingValue_;
627  /// Objective value before branching
628  double originalObjective_;
629  /// Current cutoff
630  double cutoff_;
631
632};
633
634//##############################################################################
635
636/** Compare two ranges. The two bounds arrays are both of size two and
637    describe closed intervals. Return the appropriate CbcRangeCompare value
638    (first argument being the sub/superset if that's the case). In case of
639    overlap (and if \c replaceIfOverlap is true) replace the content of thisBd
640    with the intersection of the ranges.
641*/
642static inline CbcRangeCompare
643CbcCompareRanges(double* thisBd, const double* otherBd,
644                 const bool replaceIfOverlap)
645{
646  const double lbDiff = thisBd[0] - otherBd[0];
647  if (lbDiff < 0) { // lb of this < lb of other
648    if (thisBd[1] >= otherBd[1]) { // ub of this >= ub of other
649      return CbcRangeSuperset;
650    } else if (thisBd[1] < otherBd[0]) {
651      return CbcRangeDisjoint;
652    } else {
653      // overlap
654      if (replaceIfOverlap) {
655        thisBd[0] = otherBd[0];
656      }
657      return CbcRangeOverlap;
658    }
659  } else if (lbDiff > 0) { // lb of this > lb of other
660    if (thisBd[1] <= otherBd[1]) { // ub of this <= ub of other
661      return CbcRangeSubset;
662    } else if (thisBd[0] > otherBd[1]) {
663      return CbcRangeDisjoint;
664    } else {
665      // overlap
666      if (replaceIfOverlap) {
667        thisBd[1] = otherBd[1];
668      }
669      return CbcRangeOverlap;
670    }
671  } else { // lb of this == lb of other
672    if (thisBd[1] == otherBd[1]) {
673      return CbcRangeSame;
674    }
675    return thisBd[1] < otherBd[1] ? CbcRangeSubset : CbcRangeSuperset;
676  }
677
678  return CbcRangeSame; // fake return
679
680}
681
682//#############################################################################
683
684#endif
Note: See TracBrowser for help on using the repository browser.