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/9/2009-- carved out of CbcBranchActual 7 8 #ifndef CbcSOS_H 9 #define CbcSOS_H 10 11 /** \brief Branching object for Special Ordered Sets of type 1 and 2. 12 13 SOS1 are an ordered set of variables where at most one variable can be 14 non-zero. SOS1 are commonly defined with binary variables (interpreted as 15 selection between alternatives) but this is not necessary. An SOS1 with 16 all binary variables is a special case of a clique (setting any one 17 variable to 1 forces all others to 0). 18 19 In theory, the implementation makes no assumptions about integrality in 20 Type 1 sets. In practice, there are places where the code seems to have been 21 written with a binary SOS mindset. Current development of SOS branching 22 objects is proceeding in OsiSOS. 23 24 SOS2 are an ordered set of variables in which at most two consecutive 25 variables can be non-zero and must sum to 1 (interpreted as interpolation 26 between two discrete values). By definition the variables are non-integer. 27 */ 28 29 class CbcSOS : public CbcObject { 30 31 public: 32 // Default Constructor 33 CbcSOS(); 34 35 /** \brief Constructor with SOS type and member information 36 37 Type specifies SOS 1 or 2. Identifier is an arbitrary value. 38 39 Which should be an array of variable indices with numberMembers entries. 40 Weights can be used to assign arbitrary weights to variables, in the order 41 they are specified in which. If no weights are provided, a default array of 42 0, 1, 2, ... is generated. 43 */ 44 45 CbcSOS(CbcModel *model, int numberMembers, 46 const int *which, const double *weights, int identifier, 47 int type = 1); 48 49 // Copy constructor 50 CbcSOS(const CbcSOS &); 51 52 /// Clone 53 virtual CbcObject *clone() const; 54 55 // Assignment operator 56 CbcSOS &operator=(const CbcSOS &rhs); 57 58 // Destructor 59 virtual ~CbcSOS(); 60 61 /// Infeasibility - large is 0.5 62 virtual double infeasibility(const OsiBranchingInformation *info, 63 int &preferredWay) const; 64 65 using CbcObject::feasibleRegion; 66 /// This looks at solution and sets bounds to contain solution 67 virtual void feasibleRegion(); 68 69 /// Creates a branching object 70 virtual CbcBranchingObject *createCbcBranch(OsiSolverInterface *solver, const OsiBranchingInformation *info, int way); 71 72 /** Pass in information on branch just done and create CbcObjectUpdateData instance. 73 If object does not need data then backward pointer will be NULL. 74 Assumes can get information from solver */ 75 virtual CbcObjectUpdateData createUpdateInformation(const OsiSolverInterface *solver, 76 const CbcNode *node, 77 const CbcBranchingObject *branchingObject); 78 /// Update object by CbcObjectUpdateData 79 virtual void updateInformation(const CbcObjectUpdateData &data); 80 using CbcObject::solverBranch; 81 /** Create an OsiSolverBranch object 82 83 This returns NULL if branch not represented by bound changes 84 */ 85 virtual OsiSolverBranch *solverBranch() const; 86 /// Redoes data when sequence numbers change 87 virtual void redoSequenceEtc(CbcModel *model, int numberColumns, const int *originalColumns); 88 89 /// Construct an OsiSOS object 90 OsiSOS *osiObject(const OsiSolverInterface *solver) const; 91 /// Number of members numberMembers() const92 inline int numberMembers() const 93 { 94 return numberMembers_; 95 } 96 97 /// Members (indices in range 0 ... numberColumns-1) members() const98 inline const int *members() const 99 { 100 return members_; 101 } 102 103 /// SOS type sosType() const104 inline int sosType() const 105 { 106 return sosType_; 107 } 108 /// Down number times numberTimesDown() const109 inline int numberTimesDown() const 110 { 111 return numberTimesDown_; 112 } 113 /// Up number times numberTimesUp() const114 inline int numberTimesUp() const 115 { 116 return numberTimesUp_; 117 } 118 119 /** Array of weights */ weights() const120 inline const double *weights() const 121 { 122 return weights_; 123 } 124 125 /// Set number of members setNumberMembers(int n)126 inline void setNumberMembers(int n) 127 { 128 numberMembers_ = n; 129 } 130 131 /// Members (indices in range 0 ... numberColumns-1) mutableMembers() const132 inline int *mutableMembers() const 133 { 134 return members_; 135 } 136 137 /** Array of weights */ mutableWeights() const138 inline double *mutableWeights() const 139 { 140 return weights_; 141 } 142 143 /** \brief Return true if object can take part in normal heuristics 144 */ canDoHeuristics() const145 virtual bool canDoHeuristics() const 146 { 147 return (sosType_ == 1 && integerValued_); 148 } 149 /// Set whether set is integer valued or not setIntegerValued(bool yesNo)150 inline void setIntegerValued(bool yesNo) 151 { 152 integerValued_ = yesNo; 153 } 154 155 protected: 156 /// data 157 158 /// Members (indices in range 0 ... numberColumns-1) 159 int *members_; 160 /** \brief Weights for individual members 161 162 Arbitrary weights for members. Can be used to attach meaning to variable 163 values independent of objective coefficients. For example, if the SOS set 164 comprises binary variables used to choose a facility of a given size, the 165 weight could be the corresponding facilty size. Fractional values of the 166 SOS variables can then be used to estimate ideal facility size. 167 168 Weights cannot be completely arbitrary. From the code, they must be 169 differ by at least 1.0e-7 170 */ 171 172 double *weights_; 173 /// Current pseudo-shadow price estimate down 174 mutable double shadowEstimateDown_; 175 /// Current pseudo-shadow price estimate up 176 mutable double shadowEstimateUp_; 177 /// Down pseudo ratio 178 double downDynamicPseudoRatio_; 179 /// Up pseudo ratio 180 double upDynamicPseudoRatio_; 181 /// Number of times we have gone down 182 int numberTimesDown_; 183 /// Number of times we have gone up 184 int numberTimesUp_; 185 /// Number of members 186 int numberMembers_; 187 /// SOS type 188 int sosType_; 189 /// Whether integer valued 190 bool integerValued_; 191 /// Whether odd values e.g. negative 192 bool oddValues_; 193 }; 194 195 /** Branching object for Special ordered sets 196 197 Variable_ is the set id number (redundant, as the object also holds a 198 pointer to the set. 199 */ 200 class CbcSOSBranchingObject : public CbcBranchingObject { 201 202 public: 203 // Default Constructor 204 CbcSOSBranchingObject(); 205 206 // Useful constructor 207 CbcSOSBranchingObject(CbcModel *model, const CbcSOS *clique, 208 int way, 209 double separator); 210 211 // Copy constructor 212 CbcSOSBranchingObject(const CbcSOSBranchingObject &); 213 214 // Assignment operator 215 CbcSOSBranchingObject &operator=(const CbcSOSBranchingObject &rhs); 216 217 /// Clone 218 virtual CbcBranchingObject *clone() const; 219 220 // Destructor 221 virtual ~CbcSOSBranchingObject(); 222 223 using CbcBranchingObject::branch; 224 /// Does next branch and updates state 225 virtual double branch(); 226 /** Update bounds in solver as in 'branch' and update given bounds. 227 branchState is -1 for 'down' +1 for 'up' */ 228 virtual void fix(OsiSolverInterface *solver, 229 double *lower, double *upper, 230 int branchState) const; 231 232 /** Reset every information so that the branching object appears to point to 233 the previous child. This method does not need to modify anything in any 234 solver. */ previousBranch()235 virtual void previousBranch() 236 { 237 CbcBranchingObject::previousBranch(); 238 computeNonzeroRange(); 239 } 240 241 using CbcBranchingObject::print; 242 /** \brief Print something about branch - only if log level high 243 */ 244 virtual void print(); 245 246 /** Return the type (an integer identifier) of \c this */ type() const247 virtual CbcBranchObjType type() const 248 { 249 return SoSBranchObj; 250 } 251 252 /** Compare the original object of \c this with the original object of \c 253 brObj. Assumes that there is an ordering of the original objects. 254 This method should be invoked only if \c this and brObj are of the same 255 type. 256 Return negative/0/positive depending on whether \c this is 257 smaller/same/larger than the argument. 258 */ 259 virtual int compareOriginalObject(const CbcBranchingObject *brObj) const; 260 261 /** Compare the \c this with \c brObj. \c this and \c brObj must be os the 262 same type and must have the same original object, but they may have 263 different feasible regions. 264 Return the appropriate CbcRangeCompare value (first argument being the 265 sub/superset if that's the case). In case of overlap (and if \c 266 replaceIfOverlap is true) replace the current branching object with one 267 whose feasible region is the overlap. 268 */ 269 virtual CbcRangeCompare compareBranchingObject(const CbcBranchingObject *brObj, const bool replaceIfOverlap = false); 270 271 /** Fill out the \c firstNonzero_ and \c lastNonzero_ data members */ 272 void computeNonzeroRange(); 273 274 protected: 275 /// data 276 const CbcSOS *set_; 277 /// separator 278 double separator_; 279 /** The following two members describe the range in the members_ of the 280 original object that whose upper bound is not fixed to 0. This is not 281 necessary for Cbc to function correctly, this is there for heuristics so 282 that separate branching decisions on the same object can be pooled into 283 one branching object. */ 284 int firstNonzero_; 285 int lastNonzero_; 286 }; 287 #endif 288 289 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2 290 */ 291