Changeset 1351 for branches/sandbox/Cbc/src/CbcBranchCut.cpp
 Timestamp:
 Dec 4, 2009 11:26:41 AM (10 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

branches/sandbox/Cbc/src/CbcBranchCut.cpp
r1305 r1351 125 125 } 126 126 127 // Default Constructor 128 CbcCutBranchingObject::CbcCutBranchingObject() 129 : CbcBranchingObject() 130 { 131 down_ = OsiRowCut(); 132 up_ = OsiRowCut(); 133 canFix_ = false; 134 } 135 136 // Useful constructor 137 CbcCutBranchingObject::CbcCutBranchingObject (CbcModel * model, 138 OsiRowCut & down, 139 OsiRowCut &up, 140 bool canFix) 141 : CbcBranchingObject(model, 0, 1, 0.0) 142 { 143 down_ = down; 144 up_ = up; 145 canFix_ = canFix; 146 } 147 148 // Copy constructor 149 CbcCutBranchingObject::CbcCutBranchingObject ( const CbcCutBranchingObject & rhs) : CbcBranchingObject(rhs) 150 { 151 down_ = rhs.down_; 152 up_ = rhs.up_; 153 canFix_ = rhs.canFix_; 154 } 155 156 // Assignment operator 157 CbcCutBranchingObject & 158 CbcCutBranchingObject::operator=( const CbcCutBranchingObject & rhs) 159 { 160 if (this != &rhs) { 161 CbcBranchingObject::operator=(rhs); 162 down_ = rhs.down_; 163 up_ = rhs.up_; 164 canFix_ = rhs.canFix_; 165 } 166 return *this; 167 } 168 CbcBranchingObject * 169 CbcCutBranchingObject::clone() const 170 { 171 return (new CbcCutBranchingObject(*this)); 172 } 173 174 175 // Destructor 176 CbcCutBranchingObject::~CbcCutBranchingObject () 177 { 178 } 179 180 /* 181 Perform a branch by adjusting bounds and/or adding a cut. Note 182 that each arm of the branch advances the object to the next arm by 183 advancing the value of way_. 184 185 Returns change in guessed objective on next branch 186 */ 187 double 188 CbcCutBranchingObject::branch() 189 { 190 decrementNumberBranchesLeft(); 191 OsiRowCut * cut; 192 if (way_ < 0) { 193 cut = &down_; 194 way_ = 1; 195 } else { 196 cut = &up_; 197 way_ = 1; // Swap direction 198 } 199 printf("CUT %s ", (way_ == 1) ? "up" : "down"); 200 cut>print(); 201 // See if cut just fixes variables 202 double lb = cut>lb(); 203 double ub = cut>ub(); 204 int n = cut>row().getNumElements(); 205 const int * column = cut>row().getIndices(); 206 const double * element = cut>row().getElements(); 207 OsiSolverInterface * solver = model_>solver(); 208 const double * upper = solver>getColUpper(); 209 const double * lower = solver>getColLower(); 210 double low = 0.0; 211 double high = 0.0; 212 for (int i = 0; i < n; i++) { 213 int iColumn = column[i]; 214 double value = element[i]; 215 if (value > 0.0) { 216 high += upper[iColumn] * value; 217 low += lower[iColumn] * value; 218 } else { 219 high += lower[iColumn] * value; 220 low += upper[iColumn] * value; 221 } 222 } 223 // leave as cut 224 //model_>setNextRowCut(*cut); 225 //return 0.0; 226 // assume cut was cunningly constructed so we need not worry too much about tolerances 227 if (low + 1.0e8 >= ub && canFix_) { 228 // fix 229 for (int i = 0; i < n; i++) { 230 int iColumn = column[i]; 231 double value = element[i]; 232 if (value > 0.0) { 233 solver>setColUpper(iColumn, lower[iColumn]); 234 } else { 235 solver>setColLower(iColumn, upper[iColumn]); 236 } 237 } 238 } else if (high  1.0e8 <= lb && canFix_) { 239 // fix 240 for (int i = 0; i < n; i++) { 241 int iColumn = column[i]; 242 double value = element[i]; 243 if (value > 0.0) { 244 solver>setColLower(iColumn, upper[iColumn]); 245 } else { 246 solver>setColUpper(iColumn, lower[iColumn]); 247 } 248 } 249 } else { 250 // leave as cut 251 model_>setNextRowCut(*cut); 252 } 253 return 0.0; 254 } 255 // Print what would happen 256 void 257 CbcCutBranchingObject::print() 258 { 259 OsiRowCut * cut; 260 if (way_ < 0) { 261 cut = &down_; 262 printf("CbcCut would branch down"); 263 } else { 264 cut = &up_; 265 printf("CbcCut would branch up"); 266 } 267 double lb = cut>lb(); 268 double ub = cut>ub(); 269 int n = cut>row().getNumElements(); 270 const int * column = cut>row().getIndices(); 271 const double * element = cut>row().getElements(); 272 if (n > 5) { 273 printf("  %d elements, lo=%g, up=%g\n", n, lb, ub); 274 } else { 275 printf("  %g <=", lb); 276 for (int i = 0; i < n; i++) { 277 int iColumn = column[i]; 278 double value = element[i]; 279 printf(" (%d,%g)", iColumn, value); 280 } 281 printf(" <= %g\n", ub); 282 } 283 } 284 285 // Return true if branch should fix variables 286 bool 287 CbcCutBranchingObject::boundBranch() const 288 { 289 return false; 290 } 291 292 /** Compare the original object of \c this with the original object of \c 293 brObj. Assumes that there is an ordering of the original objects. 294 This method should be invoked only if \c this and brObj are of the same 295 type. 296 Return negative/0/positive depending on whether \c this is 297 smaller/same/larger than the argument. 298 */ 299 int 300 CbcCutBranchingObject::compareOriginalObject 301 (const CbcBranchingObject* brObj) const 302 { 303 const CbcCutBranchingObject* br = 304 dynamic_cast<const CbcCutBranchingObject*>(brObj); 305 assert(br); 306 const OsiRowCut& r0 = way_ == 1 ? down_ : up_; 307 const OsiRowCut& r1 = br>way_ == 1 ? br>down_ : br>up_; 308 return r0.row().compare(r1.row()); 309 } 310 311 /** Compare the \c this with \c brObj. \c this and \c brObj must be os the 312 same type and must have the same original object, but they may have 313 different feasible regions. 314 Return the appropriate CbcRangeCompare value (first argument being the 315 sub/superset if that's the case). In case of overlap (and if \c 316 replaceIfOverlap is true) replace the current branching object with one 317 whose feasible region is the overlap. 318 */ 319 320 CbcRangeCompare 321 CbcCutBranchingObject::compareBranchingObject 322 (const CbcBranchingObject* brObj, const bool replaceIfOverlap) 323 { 324 const CbcCutBranchingObject* br = 325 dynamic_cast<const CbcCutBranchingObject*>(brObj); 326 assert(br); 327 OsiRowCut& r0 = way_ == 1 ? down_ : up_; 328 const OsiRowCut& r1 = br>way_ == 1 ? br>down_ : br>up_; 329 double thisBd[2]; 330 thisBd[0] = r0.lb(); 331 thisBd[1] = r0.ub(); 332 double otherBd[2]; 333 otherBd[0] = r1.lb(); 334 otherBd[1] = r1.ub(); 335 CbcRangeCompare comp = CbcCompareRanges(thisBd, otherBd, replaceIfOverlap); 336 if (comp != CbcRangeOverlap  (comp == CbcRangeOverlap && !replaceIfOverlap)) { 337 return comp; 338 } 339 r0.setLb(thisBd[0]); 340 r0.setUb(thisBd[1]); 341 return comp; 342 }
Note: See TracChangeset
for help on using the changeset viewer.