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 CbcObject_H 9 #define CbcObject_H 10 11 #include <string> 12 #include <vector> 13 #include "OsiBranchingObject.hpp" 14 class OsiSolverInterface; 15 class OsiSolverBranch; 16 17 class CbcModel; 18 class CbcNode; 19 class CbcNodeInfo; 20 class CbcBranchingObject; 21 class OsiChooseVariable; 22 class CbcObjectUpdateData; 23 //############################################################################# 24 25 /** Abstract base class for `objects'. 26 It now just has stuff that OsiObject does not have 27 28 The branching model used in Cbc is based on the idea of an <i>object</i>. 29 In the abstract, an object is something that has a feasible region, can be 30 evaluated for infeasibility, can be branched on (<i>i.e.</i>, there's some 31 constructive action to be taken to move toward feasibility), and allows 32 comparison of the effect of branching. 33 34 This class (CbcObject) is the base class for an object. To round out the 35 branching model, the class CbcBranchingObject describes how to perform a 36 branch, and the class CbcBranchDecision describes how to compare two 37 CbcBranchingObjects. 38 39 To create a new type of object you need to provide three methods: 40 #infeasibility(), #feasibleRegion(), and #createCbcBranch(), described below. 41 42 This base class is primarily virtual to allow for any form of structure. 43 Any form of discontinuity is allowed. 44 45 \todo The notion that all branches are binary (two arms) is wired into the 46 implementation of CbcObject, CbcBranchingObject, and 47 CbcBranchDecision. Changing this will require a moderate amount of 48 recoding. 49 */ 50 // This can be used if object wants to skip strong branching 51 typedef struct { 52 CbcBranchingObject *possibleBranch; // what a branch would do 53 double upMovement; // cost going up (and initial away from feasible) 54 double downMovement; // cost going down 55 int numIntInfeasUp; // without odd ones 56 int numObjInfeasUp; // just odd ones 57 bool finishedUp; // true if solver finished 58 int numItersUp; // number of iterations in solver 59 int numIntInfeasDown; // without odd ones 60 int numObjInfeasDown; // just odd ones 61 bool finishedDown; // true if solver finished 62 int numItersDown; // number of iterations in solver 63 int objectNumber; // Which object it is 64 int fix; // 0 if no fix, 1 if we can fix up, -1 if we can fix down 65 } CbcStrongInfo; 66 67 class CbcObject : public OsiObject { 68 69 public: 70 // Default Constructor 71 CbcObject(); 72 73 // Useful constructor 74 CbcObject(CbcModel *model); 75 76 // Copy constructor 77 CbcObject(const CbcObject &); 78 79 // Assignment operator 80 CbcObject &operator=(const CbcObject &rhs); 81 82 /// Clone 83 virtual CbcObject *clone() const = 0; 84 85 /// Destructor 86 virtual ~CbcObject(); 87 88 /** Infeasibility of the object 89 90 This is some measure of the infeasibility of the object. It should be 91 scaled to be in the range [0.0, 0.5], with 0.0 indicating the object 92 is satisfied. 93 94 The preferred branching direction is returned in preferredWay, 95 96 This is used to prepare for strong branching but should also think of 97 case when no strong branching 98 99 The object may also compute an estimate of cost of going "up" or "down". 100 This will probably be based on pseudo-cost ideas 101 */ 102 #ifdef CBC_NEW_STYLE_BRANCH 103 virtual double infeasibility(const OsiBranchingInformation *info, 104 int &preferredWay) const = 0; 105 #else infeasibility(const OsiBranchingInformation *,int & preferredWay) const106 virtual double infeasibility(const OsiBranchingInformation * /*info*/, 107 int &preferredWay) const 108 { 109 return infeasibility(preferredWay); 110 } infeasibility(int &) const111 virtual double infeasibility(int & /*preferredWay*/) const 112 { 113 throw CoinError("Need code", "infeasibility", "CbcBranchBase"); 114 } 115 #endif 116 117 /** For the variable(s) referenced by the object, 118 look at the current solution and set bounds to match the solution. 119 */ 120 virtual void feasibleRegion() = 0; 121 /// Dummy one for compatibility 122 virtual double feasibleRegion(OsiSolverInterface *solver, const OsiBranchingInformation *info) const; 123 124 /** For the variable(s) referenced by the object, 125 look at the current solution and set bounds to match the solution. 126 Returns measure of how much it had to move solution to make feasible 127 */ 128 virtual double feasibleRegion(OsiSolverInterface *solver) const; 129 130 /** Create a branching object and indicate which way to branch first. 131 132 The branching object has to know how to create branches (fix 133 variables, etc.) 134 */ 135 #ifdef CBC_NEW_STYLE_BRANCH 136 virtual CbcBranchingObject *createCbcBranch(OsiSolverInterface *solver, const OsiBranchingInformation *info, int way) = 0; 137 #else createCbcBranch(OsiSolverInterface *,const OsiBranchingInformation *,int)138 virtual CbcBranchingObject *createCbcBranch(OsiSolverInterface * 139 /* solver */, 140 const OsiBranchingInformation * 141 /* info */, 142 int /* way */) 143 { 144 // return createBranch(solver, info, way); 145 return NULL; 146 } createBranch(OsiSolverInterface *,const OsiBranchingInformation *,int) const147 virtual OsiBranchingObject *createBranch(OsiSolverInterface * /*solver*/, 148 const OsiBranchingInformation * /*info*/, int /*way*/) const 149 { 150 throw CoinError("Need code", "createBranch", "CbcBranchBase"); 151 } 152 #endif 153 /** Create an Osibranching object and indicate which way to branch first. 154 155 The branching object has to know how to create branches (fix 156 variables, etc.) 157 */ 158 virtual OsiBranchingObject *createOsiBranch(OsiSolverInterface *solver, const OsiBranchingInformation *info, int way) const; 159 /** Create an OsiSolverBranch object 160 161 This returns NULL if branch not represented by bound changes 162 */ 163 virtual OsiSolverBranch *solverBranch() const; 164 165 /** \brief Given a valid solution (with reduced costs, etc.), 166 return a branching object which would give a new feasible 167 point in a good direction. 168 169 If the method cannot generate a feasible point (because there aren't 170 any, or because it isn't bright enough to find one), it should 171 return null. 172 */ preferredNewFeasible() const173 virtual CbcBranchingObject *preferredNewFeasible() const 174 { 175 return NULL; 176 } 177 178 /** \brief Given a valid solution (with reduced costs, etc.), 179 return a branching object which would give a new feasible 180 point in a bad direction. 181 182 If the method cannot generate a feasible point (because there aren't 183 any, or because it isn't bright enough to find one), it should 184 return null. 185 */ notPreferredNewFeasible() const186 virtual CbcBranchingObject *notPreferredNewFeasible() const 187 { 188 return NULL; 189 } 190 191 /** Reset variable bounds to their original values. 192 193 Bounds may be tightened, so it may be good to be able to set this info in object. 194 */ resetBounds(const OsiSolverInterface *)195 virtual void resetBounds(const OsiSolverInterface *) {} 196 197 /** Returns floor and ceiling i.e. closest valid points 198 */ 199 virtual void floorCeiling(double &floorValue, double &ceilingValue, double value, 200 double tolerance) const; 201 202 /** Pass in information on branch just done and create CbcObjectUpdateData instance. 203 If object does not need data then backward pointer will be NULL. 204 Assumes can get information from solver */ 205 virtual CbcObjectUpdateData createUpdateInformation(const OsiSolverInterface *solver, 206 const CbcNode *node, 207 const CbcBranchingObject *branchingObject); 208 209 /// Update object by CbcObjectUpdateData updateInformation(const CbcObjectUpdateData &)210 virtual void updateInformation(const CbcObjectUpdateData &) {} 211 212 /// Identifier (normally column number in matrix) id() const213 inline int id() const 214 { 215 return id_; 216 } 217 218 /** Set identifier (normally column number in matrix) 219 but 1000000000 to 1100000000 means optional branching object 220 i.e. code would work without it */ setId(int value)221 inline void setId(int value) 222 { 223 id_ = value; 224 } 225 226 /** Return true if optional branching object 227 i.e. code would work without it */ optionalObject() const228 inline bool optionalObject() const 229 { 230 return (id_ >= 1000000000 && id_ < 1100000000); 231 } 232 233 /// Get position in object_ list position() const234 inline int position() const 235 { 236 return position_; 237 } 238 239 /// Set position in object_ list setPosition(int position)240 inline void setPosition(int position) 241 { 242 position_ = position; 243 } 244 245 /// update model setModel(CbcModel * model)246 inline void setModel(CbcModel *model) 247 { 248 model_ = model; 249 } 250 251 /// Return model model() const252 inline CbcModel *model() const 253 { 254 return model_; 255 } 256 257 /// If -1 down always chosen first, +1 up always, 0 normal preferredWay() const258 inline int preferredWay() const 259 { 260 return preferredWay_; 261 } 262 /// Set -1 down always chosen first, +1 up always, 0 normal setPreferredWay(int value)263 inline void setPreferredWay(int value) 264 { 265 preferredWay_ = value; 266 } 267 /// Redoes data when sequence numbers change redoSequenceEtc(CbcModel *,int,const int *)268 virtual void redoSequenceEtc(CbcModel *, int, const int *) {} 269 /// Initialize for branching initializeForBranching(CbcModel *)270 virtual void initializeForBranching(CbcModel *) {} 271 272 protected: 273 /// data 274 275 /// Model 276 CbcModel *model_; 277 /// Identifier (normally column number in matrix) 278 int id_; 279 /// Position in object list 280 int position_; 281 /// If -1 down always chosen first, +1 up always, 0 normal 282 int preferredWay_; 283 }; 284 285 #endif 286 287 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2 288 */ 289