1 // $Id$ 2 // Copyright (C) 2002, International Business Machines 3 // Corporation and others. All Rights Reserved. 4 // This code is licensed under the terms of the Eclipse Public License (EPL). 5 6 // Edwin 11/12/2009 carved from CbcBranchBase 7 8 #ifndef CbcBranchingObject_H 9 #define CbcBranchingObject_H 10 11 #include <string> 12 #include <vector> 13 #include "CbcBranchBase.hpp" 14 #include "OsiBranchingObject.hpp" 15 16 // The types of objects that will be derived from this class. 17 enum CbcBranchObjType { 18 SimpleIntegerBranchObj = 100, 19 SimpleIntegerDynamicPseudoCostBranchObj = 101, 20 CliqueBranchObj = 102, 21 LongCliqueBranchObj = 103, 22 SoSBranchObj = 104, 23 NWayBranchObj = 105, 24 FollowOnBranchObj = 106, 25 DummyBranchObj = 107, 26 GeneralDepthBranchObj = 108, 27 OneGeneralBranchingObj = 110, 28 CutBranchingObj = 200, 29 LotsizeBranchObj = 300, 30 DynamicPseudoCostBranchObj = 400 31 }; 32 33 /** \brief Abstract branching object base class 34 Now just difference with OsiBranchingObject 35 36 In the abstract, an CbcBranchingObject contains instructions for how to 37 branch. We want an abstract class so that we can describe how to branch on 38 simple objects (<i>e.g.</i>, integers) and more exotic objects 39 (<i>e.g.</i>, cliques or hyperplanes). 40 41 The #branch() method is the crucial routine: it is expected to be able to 42 step through a set of branch arms, executing the actions required to create 43 each subproblem in turn. The base class is primarily virtual to allow for 44 a wide range of problem modifications. 45 46 See CbcObject for an overview of the three classes (CbcObject, 47 CbcBranchingObject, and CbcBranchDecision) which make up cbc's branching 48 model. 49 */ 50 51 class CbcBranchingObject : public OsiBranchingObject { 52 53 public: 54 /// Default Constructor 55 CbcBranchingObject(); 56 57 /// Constructor 58 CbcBranchingObject(CbcModel *model, int variable, int way, double value); 59 60 /// Copy constructor 61 CbcBranchingObject(const CbcBranchingObject &); 62 63 /// Assignment operator 64 CbcBranchingObject &operator=(const CbcBranchingObject &rhs); 65 66 /// Clone 67 virtual CbcBranchingObject *clone() const = 0; 68 69 /// Destructor 70 virtual ~CbcBranchingObject(); 71 72 /** Some branchingObjects may claim to be able to skip 73 strong branching. If so they have to fill in CbcStrongInfo. 74 The object mention in incoming CbcStrongInfo must match. 75 Returns nonzero if skip is wanted */ fillStrongInfo(CbcStrongInfo &)76 virtual int fillStrongInfo(CbcStrongInfo &) 77 { 78 return 0; 79 } 80 /// Reset number of branches left to original resetNumberBranchesLeft()81 inline void resetNumberBranchesLeft() 82 { 83 branchIndex_ = 0; 84 } 85 /// Set number of branches to do setNumberBranches(int value)86 inline void setNumberBranches(int value) 87 { 88 branchIndex_ = 0; 89 numberBranches_ = value; 90 } 91 92 /** \brief Execute the actions required to branch, as specified by the 93 current state of the branching object, and advance the object's 94 state. Mainly for diagnostics, whether it is true branch or 95 strong branching is also passed. 96 Returns change in guessed objective on next branch 97 */ 98 virtual double branch() = 0; 99 /** \brief Execute the actions required to branch, as specified by the 100 current state of the branching object, and advance the object's 101 state. Mainly for diagnostics, whether it is true branch or 102 strong branching is also passed. 103 Returns change in guessed objective on next branch 104 */ branch(OsiSolverInterface *)105 virtual double branch(OsiSolverInterface *) 106 { 107 return branch(); 108 } 109 /** Update bounds in solver as in 'branch' and update given bounds. 110 branchState is -1 for 'down' +1 for 'up' */ fix(OsiSolverInterface *,double *,double *,int) const111 virtual void fix(OsiSolverInterface *, 112 double *, double *, 113 int) const {} 114 115 /** Change (tighten) bounds in object to reflect bounds in solver. 116 Return true if now fixed */ tighten(OsiSolverInterface *)117 virtual bool tighten(OsiSolverInterface *) { return false; } 118 119 /** Reset every information so that the branching object appears to point to 120 the previous child. This method does not need to modify anything in any 121 solver. */ previousBranch()122 virtual void previousBranch() 123 { 124 assert(branchIndex_ > 0); 125 branchIndex_--; 126 way_ = -way_; 127 } 128 129 using OsiBranchingObject::print; 130 /** \brief Print something about branch - only if log level high 131 */ print() const132 virtual void print() const {} 133 134 /** \brief Index identifying the associated CbcObject within its class. 135 136 The name is misleading, and typically the index will <i>not</i> refer 137 directly to a variable. 138 Rather, it identifies an CbcObject within the class of similar 139 CbcObjects 140 141 <i>E.g.</i>, for an CbcSimpleInteger, variable() is the index of the 142 integer variable in the set of integer variables (<i>not</i> the index of 143 the variable in the set of all variables). 144 */ variable() const145 inline int variable() const 146 { 147 return variable_; 148 } 149 150 /** Get the state of the branching object 151 152 Returns a code indicating the active arm of the branching object. 153 The precise meaning is defined in the derived class. 154 155 \sa #way_ 156 */ way() const157 inline int way() const 158 { 159 return way_; 160 } 161 162 /** Set the state of the branching object. 163 164 See #way() 165 */ way(int way)166 inline void way(int way) 167 { 168 way_ = way; 169 } 170 171 /// update model setModel(CbcModel * model)172 inline void setModel(CbcModel *model) 173 { 174 model_ = model; 175 } 176 /// Return model model() const177 inline CbcModel *model() const 178 { 179 return model_; 180 } 181 182 /// Return pointer back to object which created object() const183 inline CbcObject *object() const 184 { 185 return originalCbcObject_; 186 } 187 /// Set pointer back to object which created setOriginalObject(CbcObject * object)188 inline void setOriginalObject(CbcObject *object) 189 { 190 originalCbcObject_ = object; 191 } 192 193 // Methods used in heuristics 194 195 /** Return the type (an integer identifier) of \c this. 196 See definition of CbcBranchObjType above for possibilities 197 */ 198 199 virtual CbcBranchObjType type() const = 0; 200 201 /** Compare the original object of \c this with the original object of \c 202 brObj. Assumes that there is an ordering of the original objects. 203 This method should be invoked only if \c this and brObj are of the same 204 type. 205 Return negative/0/positive depending on whether \c this is 206 smaller/same/larger than the argument. 207 */ compareOriginalObject(const CbcBranchingObject * brObj) const208 virtual int compareOriginalObject(const CbcBranchingObject *brObj) const 209 { 210 const CbcBranchingObject *br = dynamic_cast< const CbcBranchingObject * >(brObj); 211 return variable() - br->variable(); 212 } 213 214 /** Compare the \c this with \c brObj. \c this and \c brObj must be of the 215 same type and must have the same original object, but they may have 216 different feasible regions. 217 Return the appropriate CbcRangeCompare value (first argument being the 218 sub/superset if that's the case). In case of overlap (and if \c 219 replaceIfOverlap is true) replace the current branching object with one 220 whose feasible region is the overlap. 221 */ 222 virtual CbcRangeCompare compareBranchingObject(const CbcBranchingObject *brObj, const bool replaceIfOverlap = false) = 0; 223 224 protected: 225 /// The model that owns this branching object 226 CbcModel *model_; 227 /// Pointer back to object which created 228 CbcObject *originalCbcObject_; 229 230 /// Branching variable (0 is first integer) 231 int variable_; 232 // was - Way to branch - -1 down (first), 1 up, -2 down (second), 2 up (second) 233 /** The state of the branching object. 234 235 Specifies the active arm of the branching object. Coded as -1 to take 236 the `down' arm, +1 for the `up' arm. `Down' and `up' are defined based on 237 the natural meaning (floor and ceiling, respectively) for a simple integer. 238 The precise meaning is defined in the derived class. 239 */ 240 int way_; 241 }; 242 #endif 243 244 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2 245 */ 246