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