1 // Copyright (C) 2006, International Business Machines 2 // Corporation and others. All Rights Reserved. 3 // This code is licensed under the terms of the Eclipse Public License (EPL). 4 5 #ifndef OsiBranchingObject_H 6 #define OsiBranchingObject_H 7 8 #include <cassert> 9 #include <string> 10 #include <vector> 11 12 #include "CoinError.hpp" 13 #include "CoinTypes.hpp" 14 15 class OsiSolverInterface; 16 class OsiSolverBranch; 17 18 class OsiBranchingObject; 19 class OsiBranchingInformation; 20 21 //############################################################################# 22 //This contains the abstract base class for an object and for branching. 23 //It also contains a simple integer class 24 //############################################################################# 25 26 /** Abstract base class for `objects'. 27 28 The branching model used in Osi is based on the idea of an <i>object</i>. 29 In the abstract, an object is something that has a feasible region, can be 30 evaluated for infeasibility, can be branched on (<i>i.e.</i>, there's some 31 constructive action to be taken to move toward feasibility), and allows 32 comparison of the effect of branching. 33 34 This class (OsiObject) is the base class for an object. To round out the 35 branching model, the class OsiBranchingObject describes how to perform a 36 branch, and the class OsiBranchDecision describes how to compare two 37 OsiBranchingObjects. 38 39 To create a new type of object you need to provide three methods: 40 #infeasibility(), #feasibleRegion(), and #createBranch(), described below. 41 42 This base class is primarily virtual to allow for any form of structure. 43 Any form of discontinuity is allowed. 44 45 As there is an overhead in getting information from solvers and because 46 other useful information is available there is also an OsiBranchingInformation 47 class which can contain pointers to information. 48 If used it must at minimum contain pointers to current value of objective, 49 maximum allowed objective and pointers to arrays for bounds and solution 50 and direction of optimization. Also integer and primal tolerance. 51 52 Classes which inherit might have other information such as depth, number of 53 solutions, pseudo-shadow prices etc etc. 54 May be easier just to throw in here - as I keep doing 55 */ 56 class OsiObject { 57 58 public: 59 60 /// Default Constructor 61 OsiObject (); 62 63 /// Copy constructor 64 OsiObject ( const OsiObject &); 65 66 /// Assignment operator 67 OsiObject & operator=( const OsiObject& rhs); 68 69 /// Clone 70 virtual OsiObject * clone() const=0; 71 72 /// Destructor 73 virtual ~OsiObject (); 74 75 /** Infeasibility of the object 76 77 This is some measure of the infeasibility of the object. 0.0 78 indicates that the object is satisfied. 79 80 The preferred branching direction is returned in whichWay, where for 81 normal two-way branching 0 is down, 1 is up 82 83 This is used to prepare for strong branching but should also think of 84 case when no strong branching 85 86 The object may also compute an estimate of cost of going "up" or "down". 87 This will probably be based on pseudo-cost ideas 88 89 This should also set mutable infeasibility_ and whichWay_ 90 This is for instant re-use for speed 91 92 Default for this just calls infeasibility with OsiBranchingInformation 93 NOTE - Convention says that an infeasibility of COIN_DBL_MAX means 94 object has worked out it can't be satisfied! 95 */ 96 double infeasibility(const OsiSolverInterface * solver,int &whichWay) const ; 97 // Faster version when more information available 98 virtual double infeasibility(const OsiBranchingInformation * info, int &whichWay) const =0; 99 // This does NOT set mutable stuff 100 virtual double checkInfeasibility(const OsiBranchingInformation * info) const; 101 102 /** For the variable(s) referenced by the object, 103 look at the current solution and set bounds to match the solution. 104 Returns measure of how much it had to move solution to make feasible 105 */ 106 virtual double feasibleRegion(OsiSolverInterface * solver) const ; 107 /** For the variable(s) referenced by the object, 108 look at the current solution and set bounds to match the solution. 109 Returns measure of how much it had to move solution to make feasible 110 Faster version 111 */ 112 virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const =0; 113 114 /** Create a branching object and indicate which way to branch first. 115 116 The branching object has to know how to create branches (fix 117 variables, etc.) 118 */ createBranch(OsiSolverInterface *,const OsiBranchingInformation *,int) const119 virtual OsiBranchingObject * createBranch(OsiSolverInterface * /*solver*/, 120 const OsiBranchingInformation * /*info*/, 121 int /*way*/) const {throw CoinError("Need code","createBranch","OsiBranchingObject"); return nullptr; } 122 123 /** \brief Return true if object can take part in normal heuristics 124 */ canDoHeuristics() const125 virtual bool canDoHeuristics() const 126 {return true;} 127 /** \brief Return true if object can take part in move to nearest heuristic 128 */ canMoveToNearest() const129 virtual bool canMoveToNearest() const 130 {return false;} 131 /** Column number if single column object -1 otherwise, 132 Used by heuristics 133 */ 134 virtual int columnNumber() const; 135 /// Return Priority - note 1 is highest priority priority() const136 inline int priority() const 137 { return priority_;} 138 /// Set priority setPriority(int priority)139 inline void setPriority(int priority) 140 { priority_ = priority;} 141 /** \brief Return true if branch should only bound variables 142 */ boundBranch() const143 virtual bool boundBranch() const 144 {return true;} 145 /// Return true if knows how to deal with Pseudo Shadow Prices canHandleShadowPrices() const146 virtual bool canHandleShadowPrices() const 147 { return false;} 148 /// Return maximum number of ways branch may have numberWays() const149 inline int numberWays() const 150 { return numberWays_;} 151 /// Set maximum number of ways branch may have setNumberWays(int numberWays)152 inline void setNumberWays(int numberWays) 153 { numberWays_ = static_cast<short int>(numberWays) ; } 154 /** Return preferred way to branch. If two 155 then way=0 means down and 1 means up, otherwise 156 way points to preferred branch 157 */ setWhichWay(int way)158 inline void setWhichWay(int way) 159 { whichWay_ = static_cast<short int>(way) ; } 160 /** Return current preferred way to branch. If two 161 then way=0 means down and 1 means up, otherwise 162 way points to preferred branch 163 */ whichWay() const164 inline int whichWay() const 165 { return whichWay_;} 166 /// Get pre-emptive preferred way of branching - -1 off, 0 down, 1 up (for 2-way) preferredWay() const167 virtual int preferredWay() const 168 { return -1;} 169 /// Return infeasibility infeasibility() const170 inline double infeasibility() const 171 { return infeasibility_;} 172 /// Return "up" estimate (default 1.0e-5) 173 virtual double upEstimate() const; 174 /// Return "down" estimate (default 1.0e-5) 175 virtual double downEstimate() const; 176 /** Reset variable bounds to their original values. 177 Bounds may be tightened, so it may be good to be able to reset them to 178 their original values. 179 */ resetBounds(const OsiSolverInterface *)180 virtual void resetBounds(const OsiSolverInterface * ) {} 181 /** Change column numbers after preprocessing 182 */ resetSequenceEtc(int,const int *)183 virtual void resetSequenceEtc(int , const int * ) {} 184 /// Updates stuff like pseudocosts before threads updateBefore(const OsiObject *)185 virtual void updateBefore(const OsiObject * ) {} 186 /// Updates stuff like pseudocosts after threads finished updateAfter(const OsiObject *,const OsiObject *)187 virtual void updateAfter(const OsiObject * , const OsiObject * ) {} 188 189 protected: 190 /// data 191 192 /// Computed infeasibility 193 mutable double infeasibility_; 194 /// Computed preferred way to branch 195 mutable short whichWay_; 196 /// Maximum number of ways on branch 197 short numberWays_; 198 /// Priority 199 int priority_; 200 201 }; 202 /// Define a class to add a bit of complexity to OsiObject 203 /// This assumes 2 way branching 204 205 206 class OsiObject2 : public OsiObject { 207 208 public: 209 210 /// Default Constructor 211 OsiObject2 (); 212 213 /// Copy constructor 214 OsiObject2 ( const OsiObject2 &); 215 216 /// Assignment operator 217 OsiObject2 & operator=( const OsiObject2& rhs); 218 219 /// Destructor 220 virtual ~OsiObject2 (); 221 222 /// Set preferred way of branching - -1 off, 0 down, 1 up (for 2-way) setPreferredWay(int value)223 inline void setPreferredWay(int value) 224 {preferredWay_=value;} 225 226 /// Get preferred way of branching - -1 off, 0 down, 1 up (for 2-way) preferredWay() const227 virtual int preferredWay() const override 228 { return preferredWay_;} 229 protected: 230 /// Preferred way of branching - -1 off, 0 down, 1 up (for 2-way) 231 int preferredWay_; 232 /// "Infeasibility" on other way 233 mutable double otherInfeasibility_; 234 235 }; 236 237 /** \brief Abstract branching object base class 238 239 In the abstract, an OsiBranchingObject contains instructions for how to 240 branch. We want an abstract class so that we can describe how to branch on 241 simple objects (<i>e.g.</i>, integers) and more exotic objects 242 (<i>e.g.</i>, cliques or hyperplanes). 243 244 The #branch() method is the crucial routine: it is expected to be able to 245 step through a set of branch arms, executing the actions required to create 246 each subproblem in turn. The base class is primarily virtual to allow for 247 a wide range of problem modifications. 248 249 See OsiObject for an overview of the two classes (OsiObject and 250 OsiBranchingObject) which make up Osi's branching 251 model. 252 */ 253 254 class OsiBranchingObject { 255 256 public: 257 258 /// Default Constructor 259 OsiBranchingObject (); 260 261 /// Constructor 262 OsiBranchingObject (OsiSolverInterface * solver, double value); 263 264 /// Copy constructor 265 OsiBranchingObject ( const OsiBranchingObject &); 266 267 /// Assignment operator 268 OsiBranchingObject & operator=( const OsiBranchingObject& rhs); 269 270 /// Clone 271 virtual OsiBranchingObject * clone() const=0; 272 273 /// Destructor 274 virtual ~OsiBranchingObject (); 275 276 /// The number of branch arms created for this branching object numberBranches() const277 inline int numberBranches() const 278 {return numberBranches_;} 279 280 /// The number of branch arms left for this branching object numberBranchesLeft() const281 inline int numberBranchesLeft() const 282 {return numberBranches_-branchIndex_;} 283 284 /// Increment the number of branch arms left for this branching object incrementNumberBranchesLeft()285 inline void incrementNumberBranchesLeft() 286 { numberBranches_ ++;} 287 288 /** Set the number of branch arms left for this branching object 289 Just for forcing 290 */ setNumberBranchesLeft(int)291 inline void setNumberBranchesLeft(int /*value*/) 292 {/*assert (value==1&&!branchIndex_);*/ numberBranches_=1;} 293 294 /// Decrement the number of branch arms left for this branching object decrementNumberBranchesLeft()295 inline void decrementNumberBranchesLeft() 296 {branchIndex_++;} 297 298 /** \brief Execute the actions required to branch, as specified by the 299 current state of the branching object, and advance the object's 300 state. 301 Returns change in guessed objective on next branch 302 */ 303 virtual double branch(OsiSolverInterface * solver)=0; 304 /** \brief Execute the actions required to branch, as specified by the 305 current state of the branching object, and advance the object's 306 state. 307 Returns change in guessed objective on next branch 308 */ branch()309 virtual double branch() {return branch(nullptr);} 310 /** \brief Return true if branch should fix variables 311 */ boundBranch() const312 virtual bool boundBranch() const 313 {return true;} 314 /** Get the state of the branching object 315 This is just the branch index 316 */ branchIndex() const317 inline int branchIndex() const 318 {return branchIndex_;} 319 320 /** Set the state of the branching object. 321 */ setBranchingIndex(int branchIndex)322 inline void setBranchingIndex(int branchIndex) 323 { branchIndex_ = static_cast<short int>(branchIndex) ; } 324 325 /// Current value value() const326 inline double value() const 327 {return value_;} 328 329 /// Return pointer back to object which created originalObject() const330 inline const OsiObject * originalObject() const 331 {return originalObject_;} 332 /// Set pointer back to object which created setOriginalObject(const OsiObject * object)333 inline void setOriginalObject(const OsiObject * object) 334 {originalObject_=object;} 335 /** Double checks in case node can change its mind! 336 Returns objective value 337 Can change objective etc */ checkIsCutoff(double)338 virtual void checkIsCutoff(double ) {} 339 /// For debug 340 int columnNumber() const; 341 /** \brief Print something about branch - only if log level high 342 */ print(const OsiSolverInterface * =nullptr) const343 virtual void print(const OsiSolverInterface * =nullptr) const {} 344 345 protected: 346 347 /// Current value - has some meaning about branch 348 double value_; 349 350 /// Pointer back to object which created 351 const OsiObject * originalObject_; 352 353 /** Number of branches 354 */ 355 int numberBranches_; 356 357 /** The state of the branching object. i.e. branch index 358 This starts at 0 when created 359 */ 360 short branchIndex_; 361 362 }; 363 /* This contains information 364 This could also contain pseudo shadow prices 365 or information for dealing with computing and trusting pseudo-costs 366 */ 367 class OsiBranchingInformation { 368 369 public: 370 371 /// Default Constructor 372 OsiBranchingInformation (); 373 374 /** Useful Constructor 375 (normalSolver true if has matrix etc etc) 376 copySolution true if constructot should make a copy 377 */ 378 OsiBranchingInformation (const OsiSolverInterface * solver, bool normalSolver,bool copySolution=false); 379 380 /// Copy constructor 381 OsiBranchingInformation ( const OsiBranchingInformation &); 382 383 /// Assignment operator 384 OsiBranchingInformation & operator=( const OsiBranchingInformation& rhs); 385 386 /// Clone 387 virtual OsiBranchingInformation * clone() const; 388 389 /// Destructor 390 virtual ~OsiBranchingInformation (); 391 392 // Note public 393 public: 394 /// data 395 396 /** State of search 397 0 - no solution 398 1 - only heuristic solutions 399 2 - branched to a solution 400 3 - no solution but many nodes 401 */ 402 int stateOfSearch_; 403 /// Value of objective function (in minimization sense) 404 double objectiveValue_; 405 /// Value of objective cutoff (in minimization sense) 406 double cutoff_; 407 /// Direction 1.0 for minimization, -1.0 for maximization 408 double direction_; 409 /// Integer tolerance 410 double integerTolerance_; 411 /// Primal tolerance 412 double primalTolerance_; 413 /// Maximum time remaining before stopping on time 414 double timeRemaining_; 415 /// Dual to use if row bound violated (if negative then pseudoShadowPrices off) 416 double defaultDual_; 417 /// Pointer to solver 418 mutable const OsiSolverInterface * solver_; 419 /// The number of columns 420 int numberColumns_; 421 /// Pointer to current lower bounds on columns 422 mutable const double * lower_; 423 /// Pointer to current solution 424 mutable const double * solution_; 425 /// Pointer to current upper bounds on columns 426 mutable const double * upper_; 427 /// Highly optional target (hot start) solution 428 const double * hotstartSolution_; 429 /// Pointer to duals 430 const double * pi_; 431 /// Pointer to row activity 432 const double * rowActivity_; 433 /// Objective 434 const double * objective_; 435 /// Pointer to current lower bounds on rows 436 const double * rowLower_; 437 /// Pointer to current upper bounds on rows 438 const double * rowUpper_; 439 /// Elements in column copy of matrix 440 const double * elementByColumn_; 441 /// Column starts 442 const CoinBigIndex * columnStart_; 443 /// Column lengths 444 const int * columnLength_; 445 /// Row indices 446 const int * row_; 447 /** Useful region of length CoinMax(numberColumns,2*numberRows) 448 This is allocated and deleted before OsiObject::infeasibility 449 It is zeroed on entry and should be so on exit 450 It only exists if defaultDual_>=0.0 451 */ 452 double * usefulRegion_; 453 /// Useful index region to go with usefulRegion_ 454 int * indexRegion_; 455 /// Number of solutions found 456 int numberSolutions_; 457 /// Number of branching solutions found (i.e. exclude heuristics) 458 int numberBranchingSolutions_; 459 /// Depth in tree 460 int depth_; 461 /// TEMP 462 bool owningSolution_; 463 }; 464 465 /// This just adds two-wayness to a branching object 466 467 class OsiTwoWayBranchingObject : public OsiBranchingObject { 468 469 public: 470 471 /// Default constructor 472 OsiTwoWayBranchingObject (); 473 474 /** Create a standard tw0-way branch object 475 476 Specifies a simple two-way branch. 477 Specify way = -1 to set the object state to perform the down arm first, 478 way = 1 for the up arm. 479 */ 480 OsiTwoWayBranchingObject (OsiSolverInterface *solver,const OsiObject * originalObject, 481 int way , double value) ; 482 483 /// Copy constructor 484 OsiTwoWayBranchingObject ( const OsiTwoWayBranchingObject &); 485 486 /// Assignment operator 487 OsiTwoWayBranchingObject & operator= (const OsiTwoWayBranchingObject& rhs); 488 489 /// Destructor 490 virtual ~OsiTwoWayBranchingObject (); 491 492 using OsiBranchingObject::branch ; 493 /** \brief Sets the bounds for the variable according to the current arm 494 of the branch and advances the object state to the next arm. 495 state. 496 Returns change in guessed objective on next branch 497 */ 498 virtual double branch(OsiSolverInterface * solver)=0; 499 firstBranch() const500 inline int firstBranch() const { return firstBranch_; } 501 /// Way returns -1 on down +1 on up way() const502 inline int way() const 503 { return !branchIndex_ ? firstBranch_ : -firstBranch_;} 504 protected: 505 /// Which way was first branch -1 = down, +1 = up 506 int firstBranch_; 507 }; 508 /// Define a single integer class 509 510 511 class OsiSimpleInteger : public OsiObject2 { 512 513 public: 514 515 /// Default Constructor 516 OsiSimpleInteger (); 517 518 /// Useful constructor - passed solver index 519 OsiSimpleInteger (const OsiSolverInterface * solver, int iColumn); 520 521 /// Useful constructor - passed solver index and original bounds 522 OsiSimpleInteger (int iColumn, double lower, double upper); 523 524 /// Copy constructor 525 OsiSimpleInteger ( const OsiSimpleInteger &); 526 527 /// Clone 528 virtual OsiObject * clone() const override; 529 530 /// Assignment operator 531 OsiSimpleInteger & operator=( const OsiSimpleInteger& rhs); 532 533 /// Destructor 534 virtual ~OsiSimpleInteger (); 535 536 using OsiObject::infeasibility ; 537 /// Infeasibility - large is 0.5 538 virtual double infeasibility(const OsiBranchingInformation * info, int & whichWay) const override; 539 540 using OsiObject::feasibleRegion ; 541 /** Set bounds to fix the variable at the current (integer) value. 542 543 Given an integer value, set the lower and upper bounds to fix the 544 variable. Returns amount it had to move variable. 545 */ 546 virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const override; 547 548 /** Creates a branching object 549 550 The preferred direction is set by \p way, 0 for down, 1 for up. 551 */ 552 virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) const override; 553 554 555 /// Set solver column number setColumnNumber(int value)556 inline void setColumnNumber(int value) 557 {columnNumber_=value;} 558 559 /** Column number if single column object -1 otherwise, 560 so returns >= 0 561 Used by heuristics 562 */ 563 virtual int columnNumber() const override; 564 565 /// Original bounds originalLowerBound() const566 inline double originalLowerBound() const 567 { return originalLower_;} setOriginalLowerBound(double value)568 inline void setOriginalLowerBound(double value) 569 { originalLower_=value;} originalUpperBound() const570 inline double originalUpperBound() const 571 { return originalUpper_;} setOriginalUpperBound(double value)572 inline void setOriginalUpperBound(double value) 573 { originalUpper_=value;} 574 /** Reset variable bounds to their original values. 575 Bounds may be tightened, so it may be good to be able to reset them to 576 their original values. 577 */ 578 virtual void resetBounds(const OsiSolverInterface * solver) override ; 579 /** Change column numbers after preprocessing 580 */ 581 virtual void resetSequenceEtc(int numberColumns, const int * originalColumns) override; 582 583 /// Return "up" estimate (default 1.0e-5) 584 virtual double upEstimate() const override; 585 /// Return "down" estimate (default 1.0e-5) 586 virtual double downEstimate() const override; 587 /// Return true if knows how to deal with Pseudo Shadow Prices canHandleShadowPrices() const588 virtual bool canHandleShadowPrices() const override 589 { return false;} 590 protected: 591 /// data 592 /// Original lower bound 593 double originalLower_; 594 /// Original upper bound 595 double originalUpper_; 596 /// Column number in solver 597 int columnNumber_; 598 599 }; 600 /** Simple branching object for an integer variable 601 602 This object can specify a two-way branch on an integer variable. For each 603 arm of the branch, the upper and lower bounds on the variable can be 604 independently specified. 0 -> down, 1-> up. 605 */ 606 607 class OsiIntegerBranchingObject : public OsiTwoWayBranchingObject { 608 609 public: 610 611 /// Default constructor 612 OsiIntegerBranchingObject (); 613 614 /** Create a standard floor/ceiling branch object 615 616 Specifies a simple two-way branch. Let \p value = x*. One arm of the 617 branch will be lb <= x <= floor(x*), the other ceil(x*) <= x <= ub. 618 Specify way = -1 to set the object state to perform the down arm first, 619 way = 1 for the up arm. 620 */ 621 OsiIntegerBranchingObject (OsiSolverInterface *solver,const OsiSimpleInteger * originalObject, 622 int way , double value) ; 623 /** Create a standard floor/ceiling branch object 624 625 Specifies a simple two-way branch in a more flexible way. One arm of the 626 branch will be lb <= x <= downUpperBound, the other upLowerBound <= x <= ub. 627 Specify way = -1 to set the object state to perform the down arm first, 628 way = 1 for the up arm. 629 */ 630 OsiIntegerBranchingObject (OsiSolverInterface *solver,const OsiSimpleInteger * originalObject, 631 int way , double value, double downUpperBound, double upLowerBound) ; 632 633 /// Copy constructor 634 OsiIntegerBranchingObject ( const OsiIntegerBranchingObject &); 635 636 /// Assignment operator 637 OsiIntegerBranchingObject & operator= (const OsiIntegerBranchingObject& rhs); 638 639 /// Clone 640 virtual OsiBranchingObject * clone() const override; 641 642 /// Destructor 643 virtual ~OsiIntegerBranchingObject (); 644 645 using OsiBranchingObject::branch ; 646 /** \brief Sets the bounds for the variable according to the current arm 647 of the branch and advances the object state to the next arm. 648 state. 649 Returns change in guessed objective on next branch 650 */ 651 virtual double branch(OsiSolverInterface * solver) override; 652 653 using OsiBranchingObject::print ; 654 /** \brief Print something about branch - only if log level high 655 */ 656 virtual void print(const OsiSolverInterface * solver=nullptr); 657 658 protected: 659 // Probably could get away with just value which is already stored 660 /// Lower [0] and upper [1] bounds for the down arm (way_ = -1) 661 double down_[2]; 662 /// Lower [0] and upper [1] bounds for the up arm (way_ = 1) 663 double up_[2]; 664 }; 665 666 667 /** Define Special Ordered Sets of type 1 and 2. These do not have to be 668 integer - so do not appear in lists of integers. 669 670 which_ points columns of matrix 671 */ 672 673 674 class OsiSOS : public OsiObject2 { 675 676 public: 677 678 // Default Constructor 679 OsiSOS (); 680 681 /** Useful constructor - which are indices 682 and weights are also given. If null then 0,1,2.. 683 type is SOS type 684 */ 685 OsiSOS (const OsiSolverInterface * solver, int numberMembers, 686 const int * which, const double * weights, int type=1); 687 688 // Copy constructor 689 OsiSOS ( const OsiSOS &); 690 691 /// Clone 692 virtual OsiObject * clone() const override; 693 694 // Assignment operator 695 OsiSOS & operator=( const OsiSOS& rhs); 696 697 // Destructor 698 virtual ~OsiSOS (); 699 700 using OsiObject::infeasibility ; 701 /// Infeasibility - large is 0.5 702 virtual double infeasibility(const OsiBranchingInformation * info,int & whichWay) const override; 703 704 using OsiObject::feasibleRegion ; 705 /** Set bounds to fix the variable at the current (integer) value. 706 707 Given an integer value, set the lower and upper bounds to fix the 708 variable. Returns amount it had to move variable. 709 */ 710 virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const override; 711 712 /** Creates a branching object 713 714 The preferred direction is set by \p way, 0 for down, 1 for up. 715 */ 716 virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) const override; 717 /// Return "up" estimate (default 1.0e-5) 718 virtual double upEstimate() const override; 719 /// Return "down" estimate (default 1.0e-5) 720 virtual double downEstimate() const override; 721 722 /// Redoes data when sequence numbers change 723 virtual void resetSequenceEtc(int numberColumns, const int * originalColumns) override; 724 725 /// Number of members numberMembers() const726 inline int numberMembers() const 727 {return numberMembers_;} 728 729 /// Members (indices in range 0 ... numberColumns-1) members() const730 inline const int * members() const 731 {return members_;} 732 733 /// SOS type sosType() const734 inline int sosType() const 735 {return sosType_;} 736 737 /// SOS type setType() const738 inline int setType() const 739 {return sosType_;} 740 741 /** Array of weights */ weights() const742 inline const double * weights() const 743 { return weights_;} 744 745 /** \brief Return true if object can take part in normal heuristics 746 */ canDoHeuristics() const747 virtual bool canDoHeuristics() const override 748 {return (sosType_==1&&integerValued_);} 749 /// Set whether set is integer valued or not setIntegerValued(bool yesNo)750 inline void setIntegerValued(bool yesNo) 751 { integerValued_=yesNo;} 752 /// Return true if knows how to deal with Pseudo Shadow Prices canHandleShadowPrices() const753 virtual bool canHandleShadowPrices() const override 754 { return true;} 755 /// Set number of members setNumberMembers(int value)756 inline void setNumberMembers(int value) 757 {numberMembers_=value;} 758 759 /// Members (indices in range 0 ... numberColumns-1) mutableMembers() const760 inline int * mutableMembers() const 761 {return members_;} 762 763 /// Set SOS type setSosType(int value)764 inline void setSosType(int value) 765 {sosType_=value;} 766 767 /** Array of weights */ mutableWeights() const768 inline double * mutableWeights() const 769 { return weights_;} 770 protected: 771 /// data 772 773 /// Members (indices in range 0 ... numberColumns-1) 774 int * members_; 775 /// Weights 776 double * weights_; 777 778 /// Number of members 779 int numberMembers_; 780 /// SOS type 781 int sosType_; 782 /// Whether integer valued 783 bool integerValued_; 784 }; 785 786 /** Branching object for Special ordered sets 787 788 */ 789 class OsiSOSBranchingObject : public OsiTwoWayBranchingObject { 790 791 public: 792 793 // Default Constructor 794 OsiSOSBranchingObject (); 795 796 // Useful constructor 797 OsiSOSBranchingObject (OsiSolverInterface * solver, const OsiSOS * originalObject, 798 int way, 799 double separator); 800 801 // Copy constructor 802 OsiSOSBranchingObject ( const OsiSOSBranchingObject &); 803 804 // Assignment operator 805 OsiSOSBranchingObject & operator=( const OsiSOSBranchingObject& rhs); 806 807 /// Clone 808 virtual OsiBranchingObject * clone() const override; 809 810 // Destructor 811 virtual ~OsiSOSBranchingObject (); 812 813 using OsiBranchingObject::branch ; 814 /// Does next branch and updates state 815 virtual double branch(OsiSolverInterface * solver) override; 816 817 using OsiBranchingObject::print ; 818 /** \brief Print something about branch - only if log level high 819 */ 820 virtual void print(const OsiSolverInterface * solver=nullptr); 821 private: 822 /// data 823 }; 824 /** Lotsize class */ 825 826 827 class OsiLotsize : public OsiObject2 { 828 829 public: 830 831 // Default Constructor 832 OsiLotsize (); 833 834 /* Useful constructor - passed model index. 835 Also passed valid values - if range then pairs 836 */ 837 OsiLotsize (const OsiSolverInterface * solver, int iColumn, 838 int numberPoints, const double * points, bool range=false); 839 840 // Copy constructor 841 OsiLotsize ( const OsiLotsize &); 842 843 /// Clone 844 virtual OsiObject * clone() const override; 845 846 // Assignment operator 847 OsiLotsize & operator=( const OsiLotsize& rhs); 848 849 // Destructor 850 ~OsiLotsize (); 851 852 using OsiObject::infeasibility ; 853 /// Infeasibility - large is 0.5 854 virtual double infeasibility(const OsiBranchingInformation * info, int & whichWay) const override; 855 856 using OsiObject::feasibleRegion ; 857 /** Set bounds to contain the current solution. 858 859 More precisely, for the variable associated with this object, take the 860 value given in the current solution, force it within the current bounds 861 if required, then set the bounds to fix the variable at the integer 862 nearest the solution value. Returns amount it had to move variable. 863 */ 864 virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const override; 865 866 /** Creates a branching object 867 868 The preferred direction is set by \p way, 0 for down, 1 for up. 869 */ 870 virtual OsiBranchingObject * createBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) const override; 871 872 873 /// Set solver column number setColumnNumber(int value)874 inline void setColumnNumber(int value) 875 {columnNumber_=value;} 876 877 /** Column number if single column object -1 otherwise, 878 so returns >= 0 879 Used by heuristics 880 */ 881 virtual int columnNumber() const override; 882 /** Reset original upper and lower bound values from the solver. 883 884 Handy for updating bounds held in this object after bounds held in the 885 solver have been tightened. 886 */ 887 virtual void resetBounds(const OsiSolverInterface * solver) override; 888 889 /** Finds range of interest so value is feasible in range range_ or infeasible 890 between hi[range_] and lo[range_+1]. Returns true if feasible. 891 */ 892 bool findRange(double value, double integerTolerance) const; 893 894 /** Returns floor and ceiling 895 */ 896 virtual void floorCeiling(double & floorLotsize, double & ceilingLotsize, double value, 897 double tolerance) const; 898 899 /// Original bounds originalLowerBound() const900 inline double originalLowerBound() const 901 { return bound_[0];} originalUpperBound() const902 inline double originalUpperBound() const 903 { return bound_[rangeType_*numberRanges_-1];} 904 /// Type - 1 points, 2 ranges rangeType() const905 inline int rangeType() const 906 { return rangeType_;} 907 /// Number of points numberRanges() const908 inline int numberRanges() const 909 { return numberRanges_;} 910 /// Ranges bound() const911 inline double * bound() const 912 { return bound_;} 913 /** Change column numbers after preprocessing 914 */ 915 virtual void resetSequenceEtc(int numberColumns, const int * originalColumns) override; 916 917 /// Return "up" estimate (default 1.0e-5) 918 virtual double upEstimate() const override; 919 /// Return "down" estimate (default 1.0e-5) 920 virtual double downEstimate() const override; 921 /// Return true if knows how to deal with Pseudo Shadow Prices canHandleShadowPrices() const922 virtual bool canHandleShadowPrices() const override 923 { return true;} 924 /** \brief Return true if object can take part in normal heuristics 925 */ canDoHeuristics() const926 virtual bool canDoHeuristics() const override 927 {return false;} 928 929 private: 930 /// data 931 932 /// Column number in model 933 int columnNumber_; 934 /// Type - 1 points, 2 ranges 935 int rangeType_; 936 /// Number of points 937 int numberRanges_; 938 // largest gap 939 double largestGap_; 940 /// Ranges 941 double * bound_; 942 /// Current range 943 mutable int range_; 944 }; 945 946 947 /** Lotsize branching object 948 949 This object can specify a two-way branch on an integer variable. For each 950 arm of the branch, the upper and lower bounds on the variable can be 951 independently specified. 952 953 Variable_ holds the index of the integer variable in the integerVariable_ 954 array of the model. 955 */ 956 957 class OsiLotsizeBranchingObject : public OsiTwoWayBranchingObject { 958 959 public: 960 961 /// Default constructor 962 OsiLotsizeBranchingObject (); 963 964 /** Create a lotsize floor/ceiling branch object 965 966 Specifies a simple two-way branch. Let \p value = x*. One arm of the 967 branch will be is lb <= x <= valid range below(x*), the other valid range above(x*) <= x <= ub. 968 Specify way = -1 to set the object state to perform the down arm first, 969 way = 1 for the up arm. 970 */ 971 OsiLotsizeBranchingObject (OsiSolverInterface *solver,const OsiLotsize * originalObject, 972 int way , double value) ; 973 974 /// Copy constructor 975 OsiLotsizeBranchingObject ( const OsiLotsizeBranchingObject &); 976 977 /// Assignment operator 978 OsiLotsizeBranchingObject & operator= (const OsiLotsizeBranchingObject& rhs); 979 980 /// Clone 981 virtual OsiBranchingObject * clone() const override; 982 983 /// Destructor 984 virtual ~OsiLotsizeBranchingObject (); 985 986 using OsiBranchingObject::branch ; 987 /** \brief Sets the bounds for the variable according to the current arm 988 of the branch and advances the object state to the next arm. 989 state. 990 Returns change in guessed objective on next branch 991 */ 992 virtual double branch(OsiSolverInterface * solver) override; 993 994 using OsiBranchingObject::print ; 995 /** \brief Print something about branch - only if log level high 996 */ 997 virtual void print(const OsiSolverInterface * solver=nullptr); 998 999 protected: 1000 /// Lower [0] and upper [1] bounds for the down arm (way_ = -1) 1001 double down_[2]; 1002 /// Lower [0] and upper [1] bounds for the up arm (way_ = 1) 1003 double up_[2]; 1004 }; 1005 #endif 1006