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

Last change on this file since 912 was 912, checked in by ladanyi, 13 years ago

Incorporated changes from branches/heur

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