[1573] | 1 | // $Id: CbcSimpleInteger.cpp 1902 2013-04-10 16:58:16Z stefan $ |
---|
| 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 | |
---|
[1357] | 6 | // Edwin 11/9/2009-- carved out of CbcBranchActual |
---|
[1573] | 7 | |
---|
[1357] | 8 | #if defined(_MSC_VER) |
---|
| 9 | // Turn off compiler warning about long names |
---|
| 10 | # pragma warning(disable:4786) |
---|
| 11 | #endif |
---|
| 12 | #include <cassert> |
---|
| 13 | #include <cstdlib> |
---|
| 14 | #include <cmath> |
---|
| 15 | #include <cfloat> |
---|
| 16 | //#define CBC_DEBUG |
---|
| 17 | |
---|
| 18 | #include "CoinTypes.hpp" |
---|
| 19 | #include "OsiSolverInterface.hpp" |
---|
| 20 | #include "OsiSolverBranch.hpp" |
---|
| 21 | #include "CbcModel.hpp" |
---|
| 22 | #include "CbcMessage.hpp" |
---|
| 23 | #include "CbcSimpleInteger.hpp" |
---|
| 24 | #include "CbcBranchActual.hpp" |
---|
| 25 | #include "CoinSort.hpp" |
---|
| 26 | #include "CoinError.hpp" |
---|
| 27 | |
---|
| 28 | |
---|
| 29 | //############################################################################## |
---|
| 30 | |
---|
| 31 | /** Default Constructor |
---|
| 32 | |
---|
| 33 | Equivalent to an unspecified binary variable. |
---|
| 34 | */ |
---|
| 35 | CbcSimpleInteger::CbcSimpleInteger () |
---|
| 36 | : CbcObject(), |
---|
| 37 | originalLower_(0.0), |
---|
| 38 | originalUpper_(1.0), |
---|
| 39 | breakEven_(0.5), |
---|
| 40 | columnNumber_(-1), |
---|
| 41 | preferredWay_(0) |
---|
| 42 | { |
---|
| 43 | } |
---|
| 44 | |
---|
| 45 | /** Useful constructor |
---|
| 46 | |
---|
| 47 | Loads actual upper & lower bounds for the specified variable. |
---|
| 48 | */ |
---|
| 49 | CbcSimpleInteger::CbcSimpleInteger ( CbcModel * model, int iColumn, double breakEven) |
---|
| 50 | : CbcObject(model) |
---|
| 51 | { |
---|
| 52 | columnNumber_ = iColumn ; |
---|
| 53 | originalLower_ = model->solver()->getColLower()[columnNumber_] ; |
---|
| 54 | originalUpper_ = model->solver()->getColUpper()[columnNumber_] ; |
---|
| 55 | breakEven_ = breakEven; |
---|
| 56 | assert (breakEven_ > 0.0 && breakEven_ < 1.0); |
---|
| 57 | preferredWay_ = 0; |
---|
| 58 | } |
---|
| 59 | |
---|
| 60 | |
---|
| 61 | // Copy constructor |
---|
| 62 | CbcSimpleInteger::CbcSimpleInteger ( const CbcSimpleInteger & rhs) |
---|
| 63 | : CbcObject(rhs) |
---|
| 64 | |
---|
| 65 | { |
---|
| 66 | columnNumber_ = rhs.columnNumber_; |
---|
| 67 | originalLower_ = rhs.originalLower_; |
---|
| 68 | originalUpper_ = rhs.originalUpper_; |
---|
| 69 | breakEven_ = rhs.breakEven_; |
---|
| 70 | preferredWay_ = rhs.preferredWay_; |
---|
| 71 | } |
---|
| 72 | |
---|
| 73 | // Clone |
---|
| 74 | CbcObject * |
---|
| 75 | CbcSimpleInteger::clone() const |
---|
| 76 | { |
---|
| 77 | return new CbcSimpleInteger(*this); |
---|
| 78 | } |
---|
| 79 | |
---|
| 80 | // Assignment operator |
---|
| 81 | CbcSimpleInteger & |
---|
| 82 | CbcSimpleInteger::operator=( const CbcSimpleInteger & rhs) |
---|
| 83 | { |
---|
| 84 | if (this != &rhs) { |
---|
| 85 | CbcObject::operator=(rhs); |
---|
| 86 | columnNumber_ = rhs.columnNumber_; |
---|
| 87 | originalLower_ = rhs.originalLower_; |
---|
| 88 | originalUpper_ = rhs.originalUpper_; |
---|
| 89 | breakEven_ = rhs.breakEven_; |
---|
| 90 | preferredWay_ = rhs.preferredWay_; |
---|
| 91 | } |
---|
| 92 | return *this; |
---|
| 93 | } |
---|
| 94 | |
---|
| 95 | // Destructor |
---|
| 96 | CbcSimpleInteger::~CbcSimpleInteger () |
---|
| 97 | { |
---|
| 98 | } |
---|
| 99 | // Construct an OsiSimpleInteger object |
---|
| 100 | OsiSimpleInteger * |
---|
| 101 | CbcSimpleInteger::osiObject() const |
---|
| 102 | { |
---|
| 103 | OsiSimpleInteger * obj = new OsiSimpleInteger(columnNumber_, |
---|
| 104 | originalLower_, originalUpper_); |
---|
| 105 | obj->setPriority(priority()); |
---|
| 106 | return obj; |
---|
| 107 | } |
---|
| 108 | double |
---|
| 109 | CbcSimpleInteger::infeasibility(const OsiBranchingInformation * info, |
---|
| 110 | int &preferredWay) const |
---|
| 111 | { |
---|
| 112 | double value = info->solution_[columnNumber_]; |
---|
| 113 | value = CoinMax(value, info->lower_[columnNumber_]); |
---|
| 114 | value = CoinMin(value, info->upper_[columnNumber_]); |
---|
| 115 | double nearest = floor(value + (1.0 - breakEven_)); |
---|
| 116 | assert (breakEven_ > 0.0 && breakEven_ < 1.0); |
---|
| 117 | if (nearest > value) |
---|
| 118 | preferredWay = 1; |
---|
| 119 | else |
---|
| 120 | preferredWay = -1; |
---|
| 121 | if (preferredWay_) |
---|
| 122 | preferredWay = preferredWay_; |
---|
| 123 | double weight = fabs(value - nearest); |
---|
| 124 | // normalize so weight is 0.5 at break even |
---|
| 125 | if (nearest < value) |
---|
| 126 | weight = (0.5 / breakEven_) * weight; |
---|
| 127 | else |
---|
| 128 | weight = (0.5 / (1.0 - breakEven_)) * weight; |
---|
| 129 | if (fabs(value - nearest) <= info->integerTolerance_) |
---|
| 130 | return 0.0; |
---|
| 131 | else |
---|
| 132 | return weight; |
---|
| 133 | } |
---|
| 134 | double |
---|
| 135 | CbcSimpleInteger::feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const |
---|
| 136 | { |
---|
| 137 | double value = info->solution_[columnNumber_]; |
---|
| 138 | #ifdef COIN_DEVELOP |
---|
| 139 | if (fabs(value - floor(value + 0.5)) > 1.0e-5) |
---|
| 140 | printf("value for %d away from integer %g\n", columnNumber_, value); |
---|
| 141 | #endif |
---|
| 142 | double newValue = CoinMax(value, info->lower_[columnNumber_]); |
---|
| 143 | newValue = CoinMin(newValue, info->upper_[columnNumber_]); |
---|
| 144 | newValue = floor(newValue + 0.5); |
---|
| 145 | solver->setColLower(columnNumber_, newValue); |
---|
| 146 | solver->setColUpper(columnNumber_, newValue); |
---|
| 147 | return fabs(value - newValue); |
---|
| 148 | } |
---|
| 149 | |
---|
| 150 | /* Create an OsiSolverBranch object |
---|
| 151 | |
---|
| 152 | This returns NULL if branch not represented by bound changes |
---|
| 153 | */ |
---|
| 154 | OsiSolverBranch * |
---|
| 155 | CbcSimpleInteger::solverBranch(OsiSolverInterface * /*solver*/, |
---|
| 156 | const OsiBranchingInformation * info) const |
---|
| 157 | { |
---|
| 158 | double value = info->solution_[columnNumber_]; |
---|
| 159 | value = CoinMax(value, info->lower_[columnNumber_]); |
---|
| 160 | value = CoinMin(value, info->upper_[columnNumber_]); |
---|
| 161 | assert (info->upper_[columnNumber_] > info->lower_[columnNumber_]); |
---|
| 162 | #ifndef NDEBUG |
---|
| 163 | double nearest = floor(value + 0.5); |
---|
| 164 | assert (fabs(value - nearest) > info->integerTolerance_); |
---|
| 165 | #endif |
---|
| 166 | OsiSolverBranch * branch = new OsiSolverBranch(); |
---|
| 167 | branch->addBranch(columnNumber_, value); |
---|
| 168 | return branch; |
---|
| 169 | } |
---|
| 170 | // Creates a branching object |
---|
| 171 | CbcBranchingObject * |
---|
| 172 | CbcSimpleInteger::createCbcBranch(OsiSolverInterface * /*solver*/, |
---|
| 173 | const OsiBranchingInformation * info, int way) |
---|
| 174 | { |
---|
| 175 | CbcIntegerBranchingObject * branch = new CbcIntegerBranchingObject(model_, 0, -1, 0.5); |
---|
| 176 | fillCreateBranch(branch, info, way); |
---|
| 177 | return branch; |
---|
| 178 | } |
---|
| 179 | // Fills in a created branching object |
---|
| 180 | void |
---|
| 181 | CbcSimpleInteger::fillCreateBranch(CbcIntegerBranchingObject * branch, const OsiBranchingInformation * info, int way) |
---|
| 182 | { |
---|
| 183 | branch->setOriginalObject(this); |
---|
| 184 | double value = info->solution_[columnNumber_]; |
---|
| 185 | value = CoinMax(value, info->lower_[columnNumber_]); |
---|
| 186 | value = CoinMin(value, info->upper_[columnNumber_]); |
---|
| 187 | assert (info->upper_[columnNumber_] > info->lower_[columnNumber_]); |
---|
| 188 | if (!info->hotstartSolution_ && priority_ != -999) { |
---|
[1839] | 189 | #if 0 // out because of very strong branching ndef NDEBUG |
---|
[1357] | 190 | double nearest = floor(value + 0.5); |
---|
| 191 | assert (fabs(value - nearest) > info->integerTolerance_); |
---|
| 192 | #endif |
---|
| 193 | } else if (info->hotstartSolution_) { |
---|
| 194 | double targetValue = info->hotstartSolution_[columnNumber_]; |
---|
| 195 | if (way > 0) |
---|
| 196 | value = targetValue - 0.1; |
---|
| 197 | else |
---|
| 198 | value = targetValue + 0.1; |
---|
| 199 | } else { |
---|
| 200 | if (value <= info->lower_[columnNumber_]) |
---|
| 201 | value += 0.1; |
---|
| 202 | else if (value >= info->upper_[columnNumber_]) |
---|
| 203 | value -= 0.1; |
---|
| 204 | } |
---|
| 205 | assert (value >= info->lower_[columnNumber_] && |
---|
| 206 | value <= info->upper_[columnNumber_]); |
---|
| 207 | branch->fillPart(columnNumber_, way, value); |
---|
| 208 | } |
---|
| 209 | /* Column number if single column object -1 otherwise, |
---|
| 210 | so returns >= 0 |
---|
| 211 | Used by heuristics |
---|
| 212 | */ |
---|
| 213 | int |
---|
| 214 | CbcSimpleInteger::columnNumber() const |
---|
| 215 | { |
---|
| 216 | return columnNumber_; |
---|
| 217 | } |
---|
| 218 | /* Reset variable bounds to their original values. |
---|
| 219 | |
---|
| 220 | Bounds may be tightened, so it may be good to be able to set this info in object. |
---|
| 221 | */ |
---|
| 222 | void |
---|
| 223 | CbcSimpleInteger::resetBounds(const OsiSolverInterface * solver) |
---|
| 224 | { |
---|
| 225 | originalLower_ = solver->getColLower()[columnNumber_] ; |
---|
| 226 | originalUpper_ = solver->getColUpper()[columnNumber_] ; |
---|
| 227 | } |
---|
| 228 | |
---|
| 229 | /* Change column numbers after preprocessing |
---|
| 230 | */ |
---|
| 231 | void |
---|
| 232 | CbcSimpleInteger::resetSequenceEtc(int /*numberColumns*/, |
---|
| 233 | const int * originalColumns) |
---|
| 234 | { |
---|
| 235 | //assert (numberColumns>0); |
---|
| 236 | int iColumn; |
---|
[1393] | 237 | #ifdef JJF_ZERO |
---|
[1357] | 238 | for (iColumn = 0; iColumn < numberColumns; iColumn++) { |
---|
| 239 | if (columnNumber_ == originalColumns[iColumn]) |
---|
| 240 | break; |
---|
| 241 | } |
---|
| 242 | assert (iColumn < numberColumns); |
---|
| 243 | #else |
---|
| 244 | iColumn = originalColumns[columnNumber_]; |
---|
| 245 | assert (iColumn >= 0); |
---|
| 246 | #endif |
---|
| 247 | columnNumber_ = iColumn; |
---|
| 248 | } |
---|
| 249 | // This looks at solution and sets bounds to contain solution |
---|
| 250 | /** More precisely: it first forces the variable within the existing |
---|
| 251 | bounds, and then tightens the bounds to fix the variable at the |
---|
| 252 | nearest integer value. |
---|
| 253 | */ |
---|
| 254 | void |
---|
| 255 | CbcSimpleInteger::feasibleRegion() |
---|
| 256 | { |
---|
| 257 | abort(); |
---|
| 258 | } |
---|
| 259 | |
---|
| 260 | //############################################################################## |
---|
| 261 | |
---|
| 262 | // Default Constructor |
---|
| 263 | CbcIntegerBranchingObject::CbcIntegerBranchingObject() |
---|
| 264 | : CbcBranchingObject() |
---|
| 265 | { |
---|
| 266 | down_[0] = 0.0; |
---|
| 267 | down_[1] = 0.0; |
---|
| 268 | up_[0] = 0.0; |
---|
| 269 | up_[1] = 0.0; |
---|
[1843] | 270 | #ifdef FUNNY_BRANCHING2 |
---|
[1357] | 271 | variables_ = NULL; |
---|
| 272 | newBounds_ = NULL; |
---|
| 273 | numberExtraChangedBounds_ = 0; |
---|
| 274 | #endif |
---|
| 275 | } |
---|
| 276 | // Useful constructor |
---|
| 277 | CbcIntegerBranchingObject::CbcIntegerBranchingObject (CbcModel * model, |
---|
| 278 | int variable, int way , double value) |
---|
| 279 | : CbcBranchingObject(model, variable, way, value) |
---|
| 280 | { |
---|
| 281 | int iColumn = variable; |
---|
| 282 | assert (model_->solver()->getNumCols() > 0); |
---|
| 283 | down_[0] = model_->solver()->getColLower()[iColumn]; |
---|
| 284 | down_[1] = floor(value_); |
---|
| 285 | up_[0] = ceil(value_); |
---|
| 286 | up_[1] = model->getColUpper()[iColumn]; |
---|
[1843] | 287 | #ifdef FUNNY_BRANCHING2 |
---|
[1357] | 288 | variables_ = NULL; |
---|
| 289 | newBounds_ = NULL; |
---|
| 290 | numberExtraChangedBounds_ = 0; |
---|
| 291 | #endif |
---|
| 292 | } |
---|
| 293 | // Does part of constructor |
---|
| 294 | void |
---|
| 295 | CbcIntegerBranchingObject::fillPart (int variable, |
---|
| 296 | int way , double value) |
---|
| 297 | { |
---|
| 298 | //originalObject_=NULL; |
---|
| 299 | branchIndex_ = 0; |
---|
| 300 | value_ = value; |
---|
| 301 | numberBranches_ = 2; |
---|
| 302 | //model_= model; |
---|
| 303 | //originalCbcObject_=NULL; |
---|
| 304 | variable_ = variable; |
---|
| 305 | way_ = way; |
---|
| 306 | int iColumn = variable; |
---|
| 307 | down_[0] = model_->solver()->getColLower()[iColumn]; |
---|
| 308 | down_[1] = floor(value_); |
---|
| 309 | up_[0] = ceil(value_); |
---|
| 310 | up_[1] = model_->getColUpper()[iColumn]; |
---|
| 311 | } |
---|
| 312 | // Useful constructor for fixing |
---|
| 313 | CbcIntegerBranchingObject::CbcIntegerBranchingObject (CbcModel * model, |
---|
| 314 | int variable, int way, |
---|
| 315 | double lowerValue, |
---|
| 316 | double upperValue) |
---|
| 317 | : CbcBranchingObject(model, variable, way, lowerValue) |
---|
| 318 | { |
---|
| 319 | setNumberBranchesLeft(1); |
---|
| 320 | down_[0] = lowerValue; |
---|
| 321 | down_[1] = upperValue; |
---|
| 322 | up_[0] = lowerValue; |
---|
| 323 | up_[1] = upperValue; |
---|
[1843] | 324 | #ifdef FUNNY_BRANCHING2 |
---|
[1357] | 325 | variables_ = NULL; |
---|
| 326 | newBounds_ = NULL; |
---|
| 327 | numberExtraChangedBounds_ = 0; |
---|
| 328 | #endif |
---|
| 329 | } |
---|
| 330 | |
---|
| 331 | |
---|
| 332 | // Copy constructor |
---|
| 333 | CbcIntegerBranchingObject::CbcIntegerBranchingObject ( const CbcIntegerBranchingObject & rhs) : CbcBranchingObject(rhs) |
---|
| 334 | { |
---|
| 335 | down_[0] = rhs.down_[0]; |
---|
| 336 | down_[1] = rhs.down_[1]; |
---|
| 337 | up_[0] = rhs.up_[0]; |
---|
| 338 | up_[1] = rhs.up_[1]; |
---|
[1843] | 339 | #ifdef FUNNY_BRANCHING2 |
---|
[1357] | 340 | numberExtraChangedBounds_ = rhs.numberExtraChangedBounds_; |
---|
| 341 | int size = numberExtraChangedBounds_ * (sizeof(double) + sizeof(int)); |
---|
| 342 | char * temp = new char [size]; |
---|
| 343 | newBounds_ = (double *) temp; |
---|
| 344 | variables_ = (int *) (newBounds_ + numberExtraChangedBounds_); |
---|
| 345 | |
---|
| 346 | int i ; |
---|
| 347 | for (i = 0; i < numberExtraChangedBounds_; i++) { |
---|
| 348 | variables_[i] = rhs.variables_[i]; |
---|
| 349 | newBounds_[i] = rhs.newBounds_[i]; |
---|
| 350 | } |
---|
| 351 | #endif |
---|
| 352 | } |
---|
| 353 | |
---|
| 354 | // Assignment operator |
---|
| 355 | CbcIntegerBranchingObject & |
---|
| 356 | CbcIntegerBranchingObject::operator=( const CbcIntegerBranchingObject & rhs) |
---|
| 357 | { |
---|
| 358 | if (this != &rhs) { |
---|
| 359 | CbcBranchingObject::operator=(rhs); |
---|
| 360 | down_[0] = rhs.down_[0]; |
---|
| 361 | down_[1] = rhs.down_[1]; |
---|
| 362 | up_[0] = rhs.up_[0]; |
---|
| 363 | up_[1] = rhs.up_[1]; |
---|
[1843] | 364 | #ifdef FUNNY_BRANCHING2 |
---|
[1357] | 365 | delete [] newBounds_; |
---|
| 366 | numberExtraChangedBounds_ = rhs.numberExtraChangedBounds_; |
---|
| 367 | int size = numberExtraChangedBounds_ * (sizeof(double) + sizeof(int)); |
---|
| 368 | char * temp = new char [size]; |
---|
| 369 | newBounds_ = (double *) temp; |
---|
| 370 | variables_ = (int *) (newBounds_ + numberExtraChangedBounds_); |
---|
| 371 | |
---|
| 372 | int i ; |
---|
| 373 | for (i = 0; i < numberExtraChangedBounds_; i++) { |
---|
| 374 | variables_[i] = rhs.variables_[i]; |
---|
| 375 | newBounds_[i] = rhs.newBounds_[i]; |
---|
| 376 | } |
---|
| 377 | #endif |
---|
| 378 | } |
---|
| 379 | return *this; |
---|
| 380 | } |
---|
| 381 | CbcBranchingObject * |
---|
| 382 | CbcIntegerBranchingObject::clone() const |
---|
| 383 | { |
---|
| 384 | return (new CbcIntegerBranchingObject(*this)); |
---|
| 385 | } |
---|
| 386 | |
---|
| 387 | |
---|
| 388 | // Destructor |
---|
| 389 | CbcIntegerBranchingObject::~CbcIntegerBranchingObject () |
---|
| 390 | { |
---|
| 391 | // for debugging threads |
---|
| 392 | way_ = -23456789; |
---|
[1843] | 393 | #ifdef FUNNY_BRANCHING2 |
---|
[1357] | 394 | delete [] newBounds_; |
---|
| 395 | #endif |
---|
| 396 | } |
---|
| 397 | |
---|
| 398 | /* |
---|
| 399 | Perform a branch by adjusting the bounds of the specified variable. Note |
---|
| 400 | that each arm of the branch advances the object to the next arm by |
---|
| 401 | advancing the value of way_. |
---|
| 402 | |
---|
| 403 | Providing new values for the variable's lower and upper bounds for each |
---|
| 404 | branching direction gives a little bit of additional flexibility and will |
---|
| 405 | be easily extensible to multi-way branching. |
---|
| 406 | Returns change in guessed objective on next branch |
---|
| 407 | */ |
---|
| 408 | double |
---|
| 409 | CbcIntegerBranchingObject::branch() |
---|
| 410 | { |
---|
| 411 | // for debugging threads |
---|
| 412 | if (way_ < -1 || way_ > 100000) { |
---|
| 413 | printf("way %d, left %d, iCol %d, variable %d\n", |
---|
| 414 | way_, numberBranchesLeft(), |
---|
| 415 | originalCbcObject_->columnNumber(), variable_); |
---|
| 416 | assert (way_ != -23456789); |
---|
| 417 | } |
---|
| 418 | decrementNumberBranchesLeft(); |
---|
| 419 | if (down_[1] == -COIN_DBL_MAX) |
---|
| 420 | return 0.0; |
---|
| 421 | int iColumn = originalCbcObject_->columnNumber(); |
---|
| 422 | assert (variable_ == iColumn); |
---|
| 423 | double olb, oub ; |
---|
| 424 | olb = model_->solver()->getColLower()[iColumn] ; |
---|
| 425 | oub = model_->solver()->getColUpper()[iColumn] ; |
---|
[1624] | 426 | //#define CBCSIMPLE_TIGHTEN_BOUNDS |
---|
| 427 | #ifndef CBCSIMPLE_TIGHTEN_BOUNDS |
---|
[1357] | 428 | #ifdef COIN_DEVELOP |
---|
| 429 | if (olb != down_[0] || oub != up_[1]) { |
---|
| 430 | if (way_ > 0) |
---|
| 431 | printf("branching up on var %d: [%g,%g] => [%g,%g] - other [%g,%g]\n", |
---|
| 432 | iColumn, olb, oub, up_[0], up_[1], down_[0], down_[1]) ; |
---|
| 433 | else |
---|
| 434 | printf("branching down on var %d: [%g,%g] => [%g,%g] - other [%g,%g]\n", |
---|
| 435 | iColumn, olb, oub, down_[0], down_[1], up_[0], up_[1]) ; |
---|
| 436 | } |
---|
| 437 | #endif |
---|
| 438 | #endif |
---|
| 439 | if (way_ < 0) { |
---|
| 440 | #ifdef CBC_DEBUG |
---|
| 441 | { double olb, oub ; |
---|
| 442 | olb = model_->solver()->getColLower()[iColumn] ; |
---|
| 443 | oub = model_->solver()->getColUpper()[iColumn] ; |
---|
| 444 | printf("branching down on var %d: [%g,%g] => [%g,%g]\n", |
---|
| 445 | iColumn, olb, oub, down_[0], down_[1]) ; |
---|
| 446 | } |
---|
| 447 | #endif |
---|
[1624] | 448 | #ifndef CBCSIMPLE_TIGHTEN_BOUNDS |
---|
[1357] | 449 | model_->solver()->setColLower(iColumn, down_[0]); |
---|
| 450 | #else |
---|
| 451 | model_->solver()->setColLower(iColumn, CoinMax(down_[0], olb)); |
---|
| 452 | #endif |
---|
| 453 | model_->solver()->setColUpper(iColumn, down_[1]); |
---|
[1624] | 454 | //#define CBC_PRINT2 |
---|
[1357] | 455 | #ifdef CBC_PRINT2 |
---|
| 456 | printf("%d branching down has bounds %g %g", iColumn, down_[0], down_[1]); |
---|
| 457 | #endif |
---|
[1843] | 458 | #ifdef FUNNY_BRANCHING2 |
---|
[1357] | 459 | // branch - do extra bounds |
---|
| 460 | for (int i = 0; i < numberExtraChangedBounds_; i++) { |
---|
| 461 | int variable = variables_[i]; |
---|
| 462 | if ((variable&0x40000000) != 0) { |
---|
| 463 | // for going down |
---|
| 464 | int k = variable & 0x3fffffff; |
---|
| 465 | assert (k != iColumn); |
---|
| 466 | if ((variable&0x80000000) == 0) { |
---|
| 467 | // lower bound changing |
---|
| 468 | #ifdef CBC_PRINT2 |
---|
| 469 | printf(" extra for %d changes lower from %g to %g", |
---|
| 470 | k, model_->solver()->getColLower()[k], newBounds_[i]); |
---|
| 471 | #endif |
---|
| 472 | model_->solver()->setColLower(k, newBounds_[i]); |
---|
| 473 | } else { |
---|
| 474 | // upper bound changing |
---|
| 475 | #ifdef CBC_PRINT2 |
---|
| 476 | printf(" extra for %d changes upper from %g to %g", |
---|
| 477 | k, model_->solver()->getColUpper()[k], newBounds_[i]); |
---|
| 478 | #endif |
---|
| 479 | model_->solver()->setColUpper(k, newBounds_[i]); |
---|
| 480 | } |
---|
| 481 | } |
---|
| 482 | } |
---|
| 483 | #endif |
---|
| 484 | #ifdef CBC_PRINT2 |
---|
| 485 | printf("\n"); |
---|
| 486 | #endif |
---|
| 487 | way_ = 1; |
---|
| 488 | } else { |
---|
| 489 | #ifdef CBC_DEBUG |
---|
| 490 | { double olb, oub ; |
---|
| 491 | olb = model_->solver()->getColLower()[iColumn] ; |
---|
| 492 | oub = model_->solver()->getColUpper()[iColumn] ; |
---|
| 493 | printf("branching up on var %d: [%g,%g] => [%g,%g]\n", |
---|
| 494 | iColumn, olb, oub, up_[0], up_[1]) ; |
---|
| 495 | } |
---|
| 496 | #endif |
---|
| 497 | model_->solver()->setColLower(iColumn, up_[0]); |
---|
[1624] | 498 | #ifndef CBCSIMPLE_TIGHTEN_BOUNDS |
---|
[1357] | 499 | model_->solver()->setColUpper(iColumn, up_[1]); |
---|
| 500 | #else |
---|
| 501 | model_->solver()->setColUpper(iColumn, CoinMin(up_[1], oub)); |
---|
| 502 | #endif |
---|
| 503 | #ifdef CBC_PRINT2 |
---|
| 504 | printf("%d branching up has bounds %g %g", iColumn, up_[0], up_[1]); |
---|
| 505 | #endif |
---|
[1843] | 506 | #ifdef FUNNY_BRANCHING2 |
---|
[1357] | 507 | // branch - do extra bounds |
---|
| 508 | for (int i = 0; i < numberExtraChangedBounds_; i++) { |
---|
| 509 | int variable = variables_[i]; |
---|
| 510 | if ((variable&0x40000000) == 0) { |
---|
| 511 | // for going up |
---|
| 512 | int k = variable & 0x3fffffff; |
---|
| 513 | assert (k != iColumn); |
---|
| 514 | if ((variable&0x80000000) == 0) { |
---|
| 515 | // lower bound changing |
---|
| 516 | #ifdef CBC_PRINT2 |
---|
| 517 | printf(" extra for %d changes lower from %g to %g", |
---|
| 518 | k, model_->solver()->getColLower()[k], newBounds_[i]); |
---|
| 519 | #endif |
---|
| 520 | model_->solver()->setColLower(k, newBounds_[i]); |
---|
| 521 | } else { |
---|
| 522 | // upper bound changing |
---|
| 523 | #ifdef CBC_PRINT2 |
---|
| 524 | printf(" extra for %d changes upper from %g to %g", |
---|
| 525 | k, model_->solver()->getColUpper()[k], newBounds_[i]); |
---|
| 526 | #endif |
---|
| 527 | model_->solver()->setColUpper(k, newBounds_[i]); |
---|
| 528 | } |
---|
| 529 | } |
---|
| 530 | } |
---|
| 531 | #endif |
---|
| 532 | #ifdef CBC_PRINT2 |
---|
| 533 | printf("\n"); |
---|
| 534 | #endif |
---|
| 535 | way_ = -1; // Swap direction |
---|
| 536 | } |
---|
| 537 | double nlb = model_->solver()->getColLower()[iColumn]; |
---|
| 538 | double nub = model_->solver()->getColUpper()[iColumn]; |
---|
| 539 | if (nlb < olb) { |
---|
[1608] | 540 | #ifdef CBC_PRINT2 |
---|
[1357] | 541 | printf("bad lb change for column %d from %g to %g\n", iColumn, olb, nlb); |
---|
| 542 | #endif |
---|
[1624] | 543 | //abort(); |
---|
[1357] | 544 | model_->solver()->setColLower(iColumn, CoinMin(olb, nub)); |
---|
| 545 | nlb = olb; |
---|
| 546 | } |
---|
| 547 | if (nub > oub) { |
---|
[1608] | 548 | #ifdef CBC_PRINT2 |
---|
[1357] | 549 | printf("bad ub change for column %d from %g to %g\n", iColumn, oub, nub); |
---|
| 550 | #endif |
---|
[1624] | 551 | //abort(); |
---|
[1357] | 552 | model_->solver()->setColUpper(iColumn, CoinMax(oub, nlb)); |
---|
| 553 | } |
---|
[1608] | 554 | #ifdef CBC_PRINT2 |
---|
[1357] | 555 | if (nlb < olb + 1.0e-8 && nub > oub - 1.0e-8 && false) |
---|
| 556 | printf("bad null change for column %d - bounds %g,%g\n", iColumn, olb, oub); |
---|
| 557 | #endif |
---|
| 558 | return 0.0; |
---|
| 559 | } |
---|
| 560 | /* Update bounds in solver as in 'branch' and update given bounds. |
---|
| 561 | branchState is -1 for 'down' +1 for 'up' */ |
---|
| 562 | void |
---|
| 563 | CbcIntegerBranchingObject::fix(OsiSolverInterface * /*solver*/, |
---|
| 564 | double * lower, double * upper, |
---|
| 565 | int branchState) const |
---|
| 566 | { |
---|
| 567 | int iColumn = originalCbcObject_->columnNumber(); |
---|
| 568 | assert (variable_ == iColumn); |
---|
| 569 | if (branchState < 0) { |
---|
| 570 | model_->solver()->setColLower(iColumn, down_[0]); |
---|
| 571 | lower[iColumn] = down_[0]; |
---|
| 572 | model_->solver()->setColUpper(iColumn, down_[1]); |
---|
| 573 | upper[iColumn] = down_[1]; |
---|
| 574 | } else { |
---|
| 575 | model_->solver()->setColLower(iColumn, up_[0]); |
---|
| 576 | lower[iColumn] = up_[0]; |
---|
| 577 | model_->solver()->setColUpper(iColumn, up_[1]); |
---|
| 578 | upper[iColumn] = up_[1]; |
---|
| 579 | } |
---|
| 580 | } |
---|
[1624] | 581 | // Change (tighten) bounds in object to reflect bounds in solver. |
---|
| 582 | // Return true if now fixed |
---|
| 583 | bool |
---|
| 584 | CbcIntegerBranchingObject::tighten(OsiSolverInterface * solver) |
---|
| 585 | { |
---|
| 586 | double lower = solver->getColLower()[variable_]; |
---|
| 587 | double upper = solver->getColUpper()[variable_]; |
---|
| 588 | assert (upper>lower); |
---|
| 589 | down_[0] = CoinMax(down_[0],lower); |
---|
| 590 | up_[0] = CoinMax(up_[0],lower); |
---|
| 591 | down_[1] = CoinMin(down_[1],upper); |
---|
| 592 | up_[1] = CoinMin(up_[1],upper); |
---|
| 593 | return (down_[0]==up_[1]); |
---|
| 594 | } |
---|
[1843] | 595 | #ifdef FUNNY_BRANCHING2 |
---|
[1357] | 596 | // Deactivate bounds for branching |
---|
| 597 | void |
---|
| 598 | CbcIntegerBranchingObject::deactivate() |
---|
| 599 | { |
---|
| 600 | down_[1] = -COIN_DBL_MAX; |
---|
| 601 | } |
---|
| 602 | int |
---|
| 603 | CbcIntegerBranchingObject::applyExtraBounds(int iColumn, double lower, double upper, int way) |
---|
| 604 | { |
---|
| 605 | // branch - do bounds |
---|
| 606 | |
---|
| 607 | int i; |
---|
| 608 | int found = 0; |
---|
| 609 | if (variable_ == iColumn) { |
---|
| 610 | printf("odd applyExtra %d\n", iColumn); |
---|
| 611 | if (way < 0) { |
---|
| 612 | down_[0] = CoinMax(lower, down_[0]); |
---|
| 613 | down_[1] = CoinMin(upper, down_[1]); |
---|
| 614 | assert (down_[0] <= down_[1]); |
---|
| 615 | } else { |
---|
| 616 | up_[0] = CoinMax(lower, up_[0]); |
---|
| 617 | up_[1] = CoinMin(upper, up_[1]); |
---|
| 618 | assert (up_[0] <= up_[1]); |
---|
| 619 | } |
---|
| 620 | return 0; |
---|
| 621 | } |
---|
| 622 | int check = (way < 0) ? 0x40000000 : 0; |
---|
| 623 | double newLower = lower; |
---|
| 624 | double newUpper = upper; |
---|
| 625 | for (i = 0; i < numberExtraChangedBounds_; i++) { |
---|
| 626 | int variable = variables_[i]; |
---|
| 627 | if ((variable&0x40000000) == check) { |
---|
| 628 | int k = variable & 0x3fffffff; |
---|
| 629 | if (k == iColumn) { |
---|
| 630 | if ((variable&0x80000000) == 0) { |
---|
| 631 | // lower bound changing |
---|
| 632 | found |= 1; |
---|
| 633 | newBounds_[i] = CoinMax(lower, newBounds_[i]); |
---|
| 634 | newLower = newBounds_[i]; |
---|
| 635 | } else { |
---|
| 636 | // upper bound changing |
---|
| 637 | found |= 2; |
---|
| 638 | newBounds_[i] = CoinMin(upper, newBounds_[i]); |
---|
| 639 | newUpper = newBounds_[i]; |
---|
| 640 | } |
---|
| 641 | } |
---|
| 642 | } |
---|
| 643 | } |
---|
| 644 | int nAdd = 0; |
---|
| 645 | if ((found&2) == 0) { |
---|
| 646 | // need to add new upper |
---|
| 647 | nAdd++; |
---|
| 648 | } |
---|
| 649 | if ((found&1) == 0) { |
---|
| 650 | // need to add new lower |
---|
| 651 | nAdd++; |
---|
| 652 | } |
---|
| 653 | if (nAdd) { |
---|
| 654 | int size = (numberExtraChangedBounds_ + nAdd) * (sizeof(double) + sizeof(int)); |
---|
| 655 | char * temp = new char [size]; |
---|
| 656 | double * newBounds = (double *) temp; |
---|
| 657 | int * variables = (int *) (newBounds + numberExtraChangedBounds_ + nAdd); |
---|
| 658 | |
---|
| 659 | int i ; |
---|
| 660 | for (i = 0; i < numberExtraChangedBounds_; i++) { |
---|
| 661 | variables[i] = variables_[i]; |
---|
| 662 | newBounds[i] = newBounds_[i]; |
---|
| 663 | } |
---|
| 664 | delete [] newBounds_; |
---|
| 665 | newBounds_ = newBounds; |
---|
| 666 | variables_ = variables; |
---|
| 667 | if ((found&2) == 0) { |
---|
| 668 | // need to add new upper |
---|
| 669 | int variable = iColumn | 0x80000000; |
---|
| 670 | variables_[numberExtraChangedBounds_] = variable; |
---|
| 671 | newBounds_[numberExtraChangedBounds_++] = newUpper; |
---|
| 672 | } |
---|
| 673 | if ((found&1) == 0) { |
---|
| 674 | // need to add new lower |
---|
| 675 | int variable = iColumn; |
---|
| 676 | variables_[numberExtraChangedBounds_] = variable; |
---|
| 677 | newBounds_[numberExtraChangedBounds_++] = newLower; |
---|
| 678 | } |
---|
| 679 | } |
---|
| 680 | |
---|
| 681 | return (newUpper >= newLower) ? 0 : 1; |
---|
| 682 | } |
---|
| 683 | #endif |
---|
| 684 | // Print what would happen |
---|
| 685 | void |
---|
| 686 | CbcIntegerBranchingObject::print() |
---|
| 687 | { |
---|
| 688 | int iColumn = originalCbcObject_->columnNumber(); |
---|
| 689 | assert (variable_ == iColumn); |
---|
| 690 | if (way_ < 0) { |
---|
| 691 | { |
---|
| 692 | double olb, oub ; |
---|
| 693 | olb = model_->solver()->getColLower()[iColumn] ; |
---|
| 694 | oub = model_->solver()->getColUpper()[iColumn] ; |
---|
| 695 | printf("CbcInteger would branch down on var %d (int var %d): [%g,%g] => [%g,%g]\n", |
---|
| 696 | iColumn, variable_, olb, oub, down_[0], down_[1]) ; |
---|
| 697 | } |
---|
| 698 | } else { |
---|
| 699 | { |
---|
| 700 | double olb, oub ; |
---|
| 701 | olb = model_->solver()->getColLower()[iColumn] ; |
---|
| 702 | oub = model_->solver()->getColUpper()[iColumn] ; |
---|
| 703 | printf("CbcInteger would branch up on var %d (int var %d): [%g,%g] => [%g,%g]\n", |
---|
| 704 | iColumn, variable_, olb, oub, up_[0], up_[1]) ; |
---|
| 705 | } |
---|
| 706 | } |
---|
| 707 | } |
---|
| 708 | |
---|
| 709 | /** Compare the \c this with \c brObj. \c this and \c brObj must be os the |
---|
| 710 | same type and must have the same original object, but they may have |
---|
| 711 | different feasible regions. |
---|
| 712 | Return the appropriate CbcRangeCompare value (first argument being the |
---|
| 713 | sub/superset if that's the case). In case of overlap (and if \c |
---|
| 714 | replaceIfOverlap is true) replace the current branching object with one |
---|
| 715 | whose feasible region is the overlap. |
---|
| 716 | */ |
---|
| 717 | CbcRangeCompare |
---|
| 718 | CbcIntegerBranchingObject::compareBranchingObject |
---|
| 719 | (const CbcBranchingObject* brObj, const bool replaceIfOverlap) |
---|
| 720 | { |
---|
| 721 | const CbcIntegerBranchingObject* br = |
---|
| 722 | dynamic_cast<const CbcIntegerBranchingObject*>(brObj); |
---|
| 723 | assert(br); |
---|
| 724 | double* thisBd = way_ < 0 ? down_ : up_; |
---|
| 725 | const double* otherBd = br->way_ < 0 ? br->down_ : br->up_; |
---|
| 726 | return CbcCompareRanges(thisBd, otherBd, replaceIfOverlap); |
---|
[1432] | 727 | } |
---|
| 728 | |
---|