1 // $Id$ 2 // Copyright (C) 2005, 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/17/2009 - carved out of CbcBranchDynamic 7 8 #ifndef CbcSimpleIntegerDynamicPseudoCost_H 9 #define CbcSimpleIntegerDynamicPseudoCost_H 10 11 #include "CbcSimpleInteger.hpp" 12 13 #define TYPERATIO 0.9 14 #define MINIMUM_MOVEMENT 0.1 15 #define TYPE2 0 16 // was 1 - but that looks flakey 17 #define INFEAS 1 18 #define MOD_SHADOW 1 19 // weight at 1.0 is max min 20 #define WEIGHT_AFTER 0.8 21 #define WEIGHT_BEFORE 0.1 22 //Stolen from Constraint Integer Programming book (with epsilon change) 23 #define WEIGHT_PRODUCT 24 25 /** Define a single integer class but with dynamic pseudo costs. 26 Based on work by Achterberg, Koch and Martin. 27 28 It is wild overkill but to keep design all twiddly things are in each. 29 This could be used for fine tuning. 30 31 */ 32 33 class CbcSimpleIntegerDynamicPseudoCost : public CbcSimpleInteger { 34 35 public: 36 // Default Constructor 37 CbcSimpleIntegerDynamicPseudoCost(); 38 39 // Useful constructor - passed model index 40 CbcSimpleIntegerDynamicPseudoCost(CbcModel *model, int iColumn, double breakEven = 0.5); 41 42 // Useful constructor - passed model index and pseudo costs 43 CbcSimpleIntegerDynamicPseudoCost(CbcModel *model, int iColumn, 44 double downDynamicPseudoCost, double upDynamicPseudoCost); 45 46 // Useful constructor - passed model index and pseudo costs 47 CbcSimpleIntegerDynamicPseudoCost(CbcModel *model, int dummy, int iColumn, 48 double downDynamicPseudoCost, double upDynamicPseudoCost); 49 50 // Copy constructor 51 CbcSimpleIntegerDynamicPseudoCost(const CbcSimpleIntegerDynamicPseudoCost &); 52 53 /// Clone 54 virtual CbcObject *clone() const; 55 56 // Assignment operator 57 CbcSimpleIntegerDynamicPseudoCost &operator=(const CbcSimpleIntegerDynamicPseudoCost &rhs); 58 59 // Destructor 60 virtual ~CbcSimpleIntegerDynamicPseudoCost(); 61 62 /// Infeasibility - large is 0.5 63 virtual double infeasibility(const OsiBranchingInformation *info, 64 int &preferredWay) const; 65 66 /// Creates a branching object 67 virtual CbcBranchingObject *createCbcBranch(OsiSolverInterface *solver, const OsiBranchingInformation *info, int way); 68 69 /// Fills in a created branching object 70 // void fillCreateBranch(CbcIntegerBranchingObject * branching, 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 /// Copy some information i.e. just variable stuff 81 void copySome(const CbcSimpleIntegerDynamicPseudoCost *otherObject); 82 /// Updates stuff like pseudocosts before threads 83 virtual void updateBefore(const OsiObject *rhs); 84 /// Updates stuff like pseudocosts after threads finished 85 virtual void updateAfter(const OsiObject *rhs, const OsiObject *baseObject); 86 /// Updates stuff like pseudocosts after mini branch and bound 87 void updateAfterMini(int numberDown, int numberDownInfeasible, double sumDown, 88 int numberUp, int numberUpInfeasible, double sumUp); 89 90 using CbcSimpleInteger::solverBranch; 91 /** Create an OsiSolverBranch object 92 93 This returns NULL if branch not represented by bound changes 94 */ 95 virtual OsiSolverBranch *solverBranch() const; 96 97 /// Down pseudo cost downDynamicPseudoCost() const98 inline double downDynamicPseudoCost() const 99 { 100 return downDynamicPseudoCost_; 101 } 102 /// Set down pseudo cost 103 void setDownDynamicPseudoCost(double value); 104 /// Modify down pseudo cost in a slightly different way 105 void updateDownDynamicPseudoCost(double value); 106 107 /// Up pseudo cost upDynamicPseudoCost() const108 inline double upDynamicPseudoCost() const 109 { 110 return upDynamicPseudoCost_; 111 } 112 /// Set up pseudo cost 113 void setUpDynamicPseudoCost(double value); 114 /// Modify up pseudo cost in a slightly different way 115 void updateUpDynamicPseudoCost(double value); 116 117 /// Down pseudo shadow price cost downShadowPrice() const118 inline double downShadowPrice() const 119 { 120 return downShadowPrice_; 121 } 122 /// Set down pseudo shadow price cost setDownShadowPrice(double value)123 inline void setDownShadowPrice(double value) 124 { 125 downShadowPrice_ = value; 126 } 127 /// Up pseudo shadow price cost upShadowPrice() const128 inline double upShadowPrice() const 129 { 130 return upShadowPrice_; 131 } 132 /// Set up pseudo shadow price cost setUpShadowPrice(double value)133 inline void setUpShadowPrice(double value) 134 { 135 upShadowPrice_ = value; 136 } 137 138 /// Up down separator upDownSeparator() const139 inline double upDownSeparator() const 140 { 141 return upDownSeparator_; 142 } 143 /// Set up down separator setUpDownSeparator(double value)144 inline void setUpDownSeparator(double value) 145 { 146 upDownSeparator_ = value; 147 } 148 149 /// Down sum cost sumDownCost() const150 inline double sumDownCost() const 151 { 152 return sumDownCost_; 153 } 154 /// Set down sum cost setSumDownCost(double value)155 inline void setSumDownCost(double value) 156 { 157 sumDownCost_ = value; 158 } 159 /// Add to down sum cost and set last and square addToSumDownCost(double value)160 inline void addToSumDownCost(double value) 161 { 162 sumDownCost_ += value; 163 lastDownCost_ = value; 164 } 165 166 /// Up sum cost sumUpCost() const167 inline double sumUpCost() const 168 { 169 return sumUpCost_; 170 } 171 /// Set up sum cost setSumUpCost(double value)172 inline void setSumUpCost(double value) 173 { 174 sumUpCost_ = value; 175 } 176 /// Add to up sum cost and set last and square addToSumUpCost(double value)177 inline void addToSumUpCost(double value) 178 { 179 sumUpCost_ += value; 180 lastUpCost_ = value; 181 } 182 183 /// Down sum change sumDownChange() const184 inline double sumDownChange() const 185 { 186 return sumDownChange_; 187 } 188 /// Set down sum change setSumDownChange(double value)189 inline void setSumDownChange(double value) 190 { 191 sumDownChange_ = value; 192 } 193 /// Add to down sum change addToSumDownChange(double value)194 inline void addToSumDownChange(double value) 195 { 196 sumDownChange_ += value; 197 } 198 199 /// Up sum change sumUpChange() const200 inline double sumUpChange() const 201 { 202 return sumUpChange_; 203 } 204 /// Set up sum change setSumUpChange(double value)205 inline void setSumUpChange(double value) 206 { 207 sumUpChange_ = value; 208 } 209 /// Add to up sum change and set last and square addToSumUpChange(double value)210 inline void addToSumUpChange(double value) 211 { 212 sumUpChange_ += value; 213 } 214 215 /// Sum down decrease number infeasibilities from strong or actual sumDownDecrease() const216 inline double sumDownDecrease() const 217 { 218 return sumDownDecrease_; 219 } 220 /// Set sum down decrease number infeasibilities from strong or actual setSumDownDecrease(double value)221 inline void setSumDownDecrease(double value) 222 { 223 sumDownDecrease_ = value; 224 } 225 /// Add to sum down decrease number infeasibilities from strong or actual addToSumDownDecrease(double value)226 inline void addToSumDownDecrease(double value) 227 { 228 sumDownDecrease_ += value; /*lastDownDecrease_ = (int) value;*/ 229 } 230 231 /// Sum up decrease number infeasibilities from strong or actual sumUpDecrease() const232 inline double sumUpDecrease() const 233 { 234 return sumUpDecrease_; 235 } 236 /// Set sum up decrease number infeasibilities from strong or actual setSumUpDecrease(double value)237 inline void setSumUpDecrease(double value) 238 { 239 sumUpDecrease_ = value; 240 } 241 /// Add to sum up decrease number infeasibilities from strong or actual addToSumUpDecrease(double value)242 inline void addToSumUpDecrease(double value) 243 { 244 sumUpDecrease_ += value; /*lastUpDecrease_ = (int) value;*/ 245 } 246 247 /// Down number times numberTimesDown() const248 inline int numberTimesDown() const 249 { 250 return numberTimesDown_; 251 } 252 /// Set down number times setNumberTimesDown(int value)253 inline void setNumberTimesDown(int value) 254 { 255 numberTimesDown_ = value; 256 } 257 /// Increment down number times incrementNumberTimesDown()258 inline void incrementNumberTimesDown() 259 { 260 numberTimesDown_++; 261 } 262 263 /// Up number times numberTimesUp() const264 inline int numberTimesUp() const 265 { 266 return numberTimesUp_; 267 } 268 /// Set up number times setNumberTimesUp(int value)269 inline void setNumberTimesUp(int value) 270 { 271 numberTimesUp_ = value; 272 } 273 /// Increment up number times incrementNumberTimesUp()274 inline void incrementNumberTimesUp() 275 { 276 numberTimesUp_++; 277 } 278 279 /// Number times branched numberTimesBranched() const280 inline int numberTimesBranched() const 281 { 282 return numberTimesDown_ + numberTimesUp_; 283 } 284 /// Down number times infeasible numberTimesDownInfeasible() const285 inline int numberTimesDownInfeasible() const 286 { 287 return numberTimesDownInfeasible_; 288 } 289 /// Set down number times infeasible setNumberTimesDownInfeasible(int value)290 inline void setNumberTimesDownInfeasible(int value) 291 { 292 numberTimesDownInfeasible_ = value; 293 } 294 /// Increment down number times infeasible incrementNumberTimesDownInfeasible()295 inline void incrementNumberTimesDownInfeasible() 296 { 297 numberTimesDownInfeasible_++; 298 } 299 300 /// Up number times infeasible numberTimesUpInfeasible() const301 inline int numberTimesUpInfeasible() const 302 { 303 return numberTimesUpInfeasible_; 304 } 305 /// Set up number times infeasible setNumberTimesUpInfeasible(int value)306 inline void setNumberTimesUpInfeasible(int value) 307 { 308 numberTimesUpInfeasible_ = value; 309 } 310 /// Increment up number times infeasible incrementNumberTimesUpInfeasible()311 inline void incrementNumberTimesUpInfeasible() 312 { 313 numberTimesUpInfeasible_++; 314 } 315 316 /// Number of times before trusted numberBeforeTrust() const317 inline int numberBeforeTrust() const 318 { 319 return numberBeforeTrust_; 320 } 321 /// Set number of times before trusted setNumberBeforeTrust(int value)322 inline void setNumberBeforeTrust(int value) 323 { 324 numberBeforeTrust_ = value; 325 } 326 /// Increment number of times before trusted incrementNumberBeforeTrust()327 inline void incrementNumberBeforeTrust() 328 { 329 numberBeforeTrust_++; 330 } 331 332 /// Return "up" estimate 333 virtual double upEstimate() const; 334 /// Return "down" estimate (default 1.0e-5) 335 virtual double downEstimate() const; 336 337 /// method - see below for details method() const338 inline int method() const 339 { 340 return method_; 341 } 342 /// Set method setMethod(int value)343 inline void setMethod(int value) 344 { 345 method_ = value; 346 } 347 348 /// Pass in information on a down branch 349 void setDownInformation(double changeObjectiveDown, int changeInfeasibilityDown); 350 /// Pass in information on a up branch 351 void setUpInformation(double changeObjectiveUp, int changeInfeasibilityUp); 352 /// Pass in probing information 353 void setProbingInformation(int fixedDown, int fixedUp); 354 355 /// Print - 0 -summary, 1 just before strong 356 void print(int type = 0, double value = 0.0) const; 357 /// Same - returns true if contents match(ish) 358 bool same(const CbcSimpleIntegerDynamicPseudoCost *obj) const; 359 360 protected: 361 /// data 362 363 /// Down pseudo cost 364 double downDynamicPseudoCost_; 365 /// Up pseudo cost 366 double upDynamicPseudoCost_; 367 /** Up/down separator 368 If >0.0 then do first branch up if value-floor(value) 369 >= this value 370 */ 371 double upDownSeparator_; 372 /// Sum down cost from strong or actual 373 double sumDownCost_; 374 /// Sum up cost from strong or actual 375 double sumUpCost_; 376 /// Sum of all changes to x when going down 377 double sumDownChange_; 378 /// Sum of all changes to x when going up 379 double sumUpChange_; 380 /// Current pseudo-shadow price estimate down 381 mutable double downShadowPrice_; 382 /// Current pseudo-shadow price estimate up 383 mutable double upShadowPrice_; 384 /// Sum down decrease number infeasibilities from strong or actual 385 double sumDownDecrease_; 386 /// Sum up decrease number infeasibilities from strong or actual 387 double sumUpDecrease_; 388 /// Last down cost from strong (i.e. as computed by last strong) 389 double lastDownCost_; 390 /// Last up cost from strong (i.e. as computed by last strong) 391 double lastUpCost_; 392 /// Last down decrease number infeasibilities from strong (i.e. as computed by last strong) 393 mutable int lastDownDecrease_; 394 /// Last up decrease number infeasibilities from strong (i.e. as computed by last strong) 395 mutable int lastUpDecrease_; 396 /// Number of times we have gone down 397 int numberTimesDown_; 398 /// Number of times we have gone up 399 int numberTimesUp_; 400 /// Number of times we have been infeasible going down 401 int numberTimesDownInfeasible_; 402 /// Number of times we have been infeasible going up 403 int numberTimesUpInfeasible_; 404 /// Number of branches before we trust 405 int numberBeforeTrust_; 406 /// Number of local probing fixings going down 407 int numberTimesDownLocalFixed_; 408 /// Number of local probing fixings going up 409 int numberTimesUpLocalFixed_; 410 /// Number of total probing fixings going down 411 double numberTimesDownTotalFixed_; 412 /// Number of total probing fixings going up 413 double numberTimesUpTotalFixed_; 414 /// Number of times probing done 415 int numberTimesProbingTotal_; 416 /// Number of times infeasible when tested 417 /** Method - 418 0 - pseudo costs 419 1 - probing 420 */ 421 int method_; 422 }; 423 /** Simple branching object for an integer variable with pseudo costs 424 425 This object can specify a two-way branch on an integer variable. For each 426 arm of the branch, the upper and lower bounds on the variable can be 427 independently specified. 428 429 Variable_ holds the index of the integer variable in the integerVariable_ 430 array of the model. 431 */ 432 433 class CbcIntegerPseudoCostBranchingObject : public CbcIntegerBranchingObject { 434 435 public: 436 /// Default constructor 437 CbcIntegerPseudoCostBranchingObject(); 438 439 /** Create a standard floor/ceiling branch object 440 441 Specifies a simple two-way branch. Let \p value = x*. One arm of the 442 branch will be is lb <= x <= floor(x*), the other ceil(x*) <= x <= ub. 443 Specify way = -1 to set the object state to perform the down arm first, 444 way = 1 for the up arm. 445 */ 446 CbcIntegerPseudoCostBranchingObject(CbcModel *model, int variable, 447 int way, double value); 448 449 /** Create a degenerate branch object 450 451 Specifies a `one-way branch'. Calling branch() for this object will 452 always result in lowerValue <= x <= upperValue. Used to fix a variable 453 when lowerValue = upperValue. 454 */ 455 456 CbcIntegerPseudoCostBranchingObject(CbcModel *model, int variable, int way, 457 double lowerValue, double upperValue); 458 459 /// Copy constructor 460 CbcIntegerPseudoCostBranchingObject(const CbcIntegerPseudoCostBranchingObject &); 461 462 /// Assignment operator 463 CbcIntegerPseudoCostBranchingObject &operator=(const CbcIntegerPseudoCostBranchingObject &rhs); 464 465 /// Clone 466 virtual CbcBranchingObject *clone() const; 467 468 /// Destructor 469 virtual ~CbcIntegerPseudoCostBranchingObject(); 470 471 using CbcBranchingObject::branch; 472 /** \brief Sets the bounds for the variable according to the current arm 473 of the branch and advances the object state to the next arm. 474 This version also changes guessed objective value 475 */ 476 virtual double branch(); 477 478 /// Change in guessed changeInGuessed() const479 inline double changeInGuessed() const 480 { 481 return changeInGuessed_; 482 } 483 /// Set change in guessed setChangeInGuessed(double value)484 inline void setChangeInGuessed(double value) 485 { 486 changeInGuessed_ = value; 487 } 488 489 /** Return the type (an integer identifier) of \c this */ type() const490 virtual CbcBranchObjType type() const 491 { 492 return SimpleIntegerDynamicPseudoCostBranchObj; 493 } 494 495 /** Compare the \c this with \c brObj. \c this and \c brObj must be os the 496 same type and must have the same original object, but they may have 497 different feasible regions. 498 Return the appropriate CbcRangeCompare value (first argument being the 499 sub/superset if that's the case). In case of overlap (and if \c 500 replaceIfOverlap is true) replace the current branching object with one 501 whose feasible region is the overlap. 502 */ 503 virtual CbcRangeCompare compareBranchingObject(const CbcBranchingObject *brObj, const bool replaceIfOverlap = false); 504 505 protected: 506 /// Change in guessed objective value for next branch 507 double changeInGuessed_; 508 }; 509 #ifdef SWITCH_VARIABLES 510 /** Define a single integer class but with associated switched variable 511 So Binary variable switches on/off a continuous variable 512 designed for badly scaled problems 513 */ 514 515 class CbcSwitchingBinary : public CbcSimpleIntegerDynamicPseudoCost { 516 517 public: 518 // Default Constructor 519 CbcSwitchingBinary(); 520 521 // Useful constructor 522 CbcSwitchingBinary(CbcSimpleIntegerDynamicPseudoCost *oldObject, 523 int nOdd, const int *other, const int *otherRow); 524 525 // Copy constructor 526 CbcSwitchingBinary(const CbcSwitchingBinary &); 527 528 /// Clone 529 virtual CbcObject *clone() const; 530 531 // Assignment operator 532 CbcSwitchingBinary &operator=(const CbcSwitchingBinary &rhs); 533 534 // Destructor 535 virtual ~CbcSwitchingBinary(); 536 537 /// Add in zero switches 538 void addZeroSwitches(int nAdd, const int *columns); 539 /// Infeasibility - large is 0.5 540 virtual double infeasibility(const OsiBranchingInformation *info, 541 int &preferredWay) const; 542 543 /// Same - returns true if contents match(ish) 544 bool same(const CbcSwitchingBinary *obj) const; 545 /// Set associated bounds 546 virtual int setAssociatedBounds(OsiSolverInterface *solver = NULL, 547 int cleanBasis = 0) const; 548 /// Check associated bounds 549 int checkAssociatedBounds(const OsiSolverInterface *solver, const double *solution, 550 int printLevel, int state[3], int &nBadFixed) const; 551 /// Lower bound when binary zero zeroLowerBound() const552 inline const double *zeroLowerBound() const 553 { 554 return zeroLowerBound_; 555 } 556 /// Lower bound when binary one oneLowerBound() const557 inline const double *oneLowerBound() const 558 { 559 return oneLowerBound_; 560 } 561 /// Upper bound when binary zero zeroUpperBound() const562 inline const double *zeroUpperBound() const 563 { 564 return zeroUpperBound_; 565 } 566 /// Upper bound when binary one oneUpperBound() const567 inline const double *oneUpperBound() const 568 { 569 return oneUpperBound_; 570 } 571 /** Continuous variable - 572 */ otherVariable() const573 inline const int *otherVariable() const 574 { 575 return otherVariable_; 576 } 577 /// Number of other variables numberOther() const578 inline int numberOther() const 579 { 580 return numberOther_; 581 } 582 /** Type 583 1 - single switch 584 2 - double switch 585 3 - both 586 */ type() const587 inline int type() const 588 { 589 return type_; 590 } 591 592 protected: 593 /// data 594 595 /// Lower bound when binary zero 596 double *zeroLowerBound_; 597 /// Lower bound when binary one 598 double *oneLowerBound_; 599 /// Upper bound when binary zero 600 double *zeroUpperBound_; 601 /// Upper bound when binary one 602 double *oneUpperBound_; 603 /** Continuous variable - 604 */ 605 int *otherVariable_; 606 /// Number of other variables 607 int numberOther_; 608 /** Type 609 1 - single switch 610 2 - double switch 611 3 - both 612 */ 613 int type_; 614 }; 615 #endif 616 #endif 617 618 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2 619 */ 620