1 /* MIP_Problem class declaration. 2 Copyright (C) 2001-2010 Roberto Bagnara <bagnara@cs.unipr.it> 3 Copyright (C) 2010-2016 BUGSENG srl (http://bugseng.com) 4 5 This file is part of the Parma Polyhedra Library (PPL). 6 7 The PPL is free software; you can redistribute it and/or modify it 8 under the terms of the GNU General Public License as published by the 9 Free Software Foundation; either version 3 of the License, or (at your 10 option) any later version. 11 12 The PPL is distributed in the hope that it will be useful, but WITHOUT 13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with this program; if not, write to the Free Software Foundation, 19 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA. 20 21 For the most up-to-date information see the Parma Polyhedra Library 22 site: http://bugseng.com/products/ppl/ . */ 23 24 #ifndef PPL_MIP_Problem_defs_hh 25 #define PPL_MIP_Problem_defs_hh 1 26 27 #include "MIP_Problem_types.hh" 28 #include "globals_types.hh" 29 #include "Matrix_defs.hh" 30 #include "Linear_Expression_defs.hh" 31 #include "Constraint_types.hh" 32 #include "Constraint_System_types.hh" 33 #include "Generator_defs.hh" 34 #include "Variables_Set_defs.hh" 35 #include "Dense_Row_defs.hh" 36 #include "Sparse_Row_defs.hh" 37 #include <vector> 38 #include <deque> 39 #include <iterator> 40 #include <iosfwd> 41 42 namespace Parma_Polyhedra_Library { 43 44 namespace IO_Operators { 45 46 //! Output operator. 47 /*! \relates Parma_Polyhedra_Library::MIP_Problem */ 48 std::ostream& 49 operator<<(std::ostream& s, const MIP_Problem& mip); 50 51 } // namespace IO_Operators 52 53 //! Swaps \p x with \p y. 54 /*! \relates MIP_Problem */ 55 void swap(MIP_Problem& x, MIP_Problem& y); 56 57 } // namespace Parma_Polyhedra_Library 58 59 //! A Mixed Integer (linear) Programming problem. 60 /*! \ingroup PPL_CXX_interface 61 An object of this class encodes a mixed integer (linear) programming 62 problem. 63 The MIP problem is specified by providing: 64 - the dimension of the vector space; 65 - the feasible region, by means of a finite set of linear equality 66 and non-strict inequality constraints; 67 - the subset of the unknown variables that range over the integers 68 (the other variables implicitly ranging over the reals); 69 - the objective function, described by a Linear_Expression; 70 - the optimization mode (either maximization or minimization). 71 72 The class provides support for the (incremental) solution of the 73 MIP problem based on variations of the revised simplex method and 74 on branch-and-bound techniques. The result of the resolution 75 process is expressed in terms of an enumeration, encoding the 76 feasibility and the unboundedness of the optimization problem. 77 The class supports simple feasibility tests (i.e., no optimization), 78 as well as the extraction of an optimal (resp., feasible) point, 79 provided the MIP_Problem is optimizable (resp., feasible). 80 81 By exploiting the incremental nature of the solver, it is possible 82 to reuse part of the computational work already done when solving 83 variants of a given MIP_Problem: currently, incremental resolution 84 supports the addition of space dimensions, the addition of constraints, 85 the change of objective function and the change of optimization mode. 86 */ 87 class Parma_Polyhedra_Library::MIP_Problem { 88 public: 89 //! Builds a trivial MIP problem. 90 /*! 91 A trivial MIP problem requires to maximize the objective function 92 \f$0\f$ on a vector space under no constraints at all: 93 the origin of the vector space is an optimal solution. 94 95 \param dim 96 The dimension of the vector space enclosing \p *this 97 (optional argument with default value \f$0\f$). 98 99 \exception std::length_error 100 Thrown if \p dim exceeds <CODE>max_space_dimension()</CODE>. 101 */ 102 explicit MIP_Problem(dimension_type dim = 0); 103 104 /*! \brief 105 Builds an MIP problem having space dimension \p dim 106 from the sequence of constraints in the range 107 \f$[\mathrm{first}, \mathrm{last})\f$, 108 the objective function \p obj and optimization mode \p mode; 109 those dimensions whose indices occur in \p int_vars are 110 constrained to take an integer value. 111 112 \param dim 113 The dimension of the vector space enclosing \p *this. 114 115 \param first 116 An input iterator to the start of the sequence of constraints. 117 118 \param last 119 A past-the-end input iterator to the sequence of constraints. 120 121 \param int_vars 122 The set of variables' indexes that are constrained to take integer values. 123 124 \param obj 125 The objective function (optional argument with default value \f$0\f$). 126 127 \param mode 128 The optimization mode (optional argument with default value 129 <CODE>MAXIMIZATION</CODE>). 130 131 \exception std::length_error 132 Thrown if \p dim exceeds <CODE>max_space_dimension()</CODE>. 133 134 \exception std::invalid_argument 135 Thrown if a constraint in the sequence is a strict inequality, 136 if the space dimension of a constraint (resp., of the 137 objective function or of the integer variables) or the space dimension 138 of the integer variable set is strictly greater than \p dim. 139 */ 140 template <typename In> 141 MIP_Problem(dimension_type dim, 142 In first, In last, 143 const Variables_Set& int_vars, 144 const Linear_Expression& obj = Linear_Expression::zero(), 145 Optimization_Mode mode = MAXIMIZATION); 146 147 /*! \brief 148 Builds an MIP problem having space dimension \p dim 149 from the sequence of constraints in the range 150 \f$[\mathrm{first}, \mathrm{last})\f$, 151 the objective function \p obj and optimization mode \p mode. 152 153 \param dim 154 The dimension of the vector space enclosing \p *this. 155 156 \param first 157 An input iterator to the start of the sequence of constraints. 158 159 \param last 160 A past-the-end input iterator to the sequence of constraints. 161 162 \param obj 163 The objective function (optional argument with default value \f$0\f$). 164 165 \param mode 166 The optimization mode (optional argument with default value 167 <CODE>MAXIMIZATION</CODE>). 168 169 \exception std::length_error 170 Thrown if \p dim exceeds <CODE>max_space_dimension()</CODE>. 171 172 \exception std::invalid_argument 173 Thrown if a constraint in the sequence is a strict inequality 174 or if the space dimension of a constraint (resp., of the 175 objective function or of the integer variables) is strictly 176 greater than \p dim. 177 */ 178 template <typename In> 179 MIP_Problem(dimension_type dim, 180 In first, In last, 181 const Linear_Expression& obj = Linear_Expression::zero(), 182 Optimization_Mode mode = MAXIMIZATION); 183 184 /*! \brief 185 Builds an MIP problem having space dimension \p dim from the constraint 186 system \p cs, the objective function \p obj and optimization mode \p mode. 187 188 \param dim 189 The dimension of the vector space enclosing \p *this. 190 191 \param cs 192 The constraint system defining the feasible region. 193 194 \param obj 195 The objective function (optional argument with default value \f$0\f$). 196 197 \param mode 198 The optimization mode (optional argument with default value 199 <CODE>MAXIMIZATION</CODE>). 200 201 \exception std::length_error 202 Thrown if \p dim exceeds <CODE>max_space_dimension()</CODE>. 203 204 \exception std::invalid_argument 205 Thrown if the constraint system contains any strict inequality 206 or if the space dimension of the constraint system (resp., the 207 objective function) is strictly greater than \p dim. 208 */ 209 MIP_Problem(dimension_type dim, 210 const Constraint_System& cs, 211 const Linear_Expression& obj = Linear_Expression::zero(), 212 Optimization_Mode mode = MAXIMIZATION); 213 214 //! Ordinary copy constructor. 215 MIP_Problem(const MIP_Problem& y); 216 217 //! Destructor. 218 ~MIP_Problem(); 219 220 //! Assignment operator. 221 MIP_Problem& operator=(const MIP_Problem& y); 222 223 //! Returns the maximum space dimension an MIP_Problem can handle. 224 static dimension_type max_space_dimension(); 225 226 //! Returns the space dimension of the MIP problem. 227 dimension_type space_dimension() const; 228 229 /*! \brief 230 Returns a set containing all the variables' indexes constrained 231 to be integral. 232 */ 233 const Variables_Set& integer_space_dimensions() const; 234 235 private: 236 //! A type alias for a sequence of constraints. 237 typedef std::vector<Constraint*> Constraint_Sequence; 238 239 public: 240 //! A read-only iterator on the constraints defining the feasible region. 241 class const_iterator { 242 private: 243 typedef Constraint_Sequence::const_iterator Base; 244 typedef std::iterator_traits<Base> Base_Traits; 245 246 public: 247 typedef Base_Traits::iterator_category iterator_category; 248 typedef Base_Traits::difference_type difference_type; 249 typedef const Constraint value_type; 250 typedef const Constraint* pointer; 251 typedef const Constraint& reference; 252 253 //! Iterator difference: computes distances. 254 difference_type operator-(const const_iterator& y) const; 255 256 //! Prefix increment. 257 const_iterator& operator++(); 258 259 //! Prefix decrement. 260 const_iterator& operator--(); 261 262 //! Postfix increment. 263 const_iterator operator++(int); 264 265 //! Postfix decrement. 266 const_iterator operator--(int); 267 268 //! Moves iterator forward of \p n positions. 269 const_iterator& operator+=(difference_type n); 270 271 //! Moves iterator backward of \p n positions. 272 const_iterator& operator-=(difference_type n); 273 274 //! Returns an iterator \p n positions forward. 275 const_iterator operator+(difference_type n) const; 276 277 //! Returns an iterator \p n positions backward. 278 const_iterator operator-(difference_type n) const; 279 280 //! Returns a reference to the "pointed" object. 281 reference operator*() const; 282 283 //! Returns the address of the "pointed" object. 284 pointer operator->() const; 285 286 //! Compares \p *this with y. 287 /*! 288 \param y 289 The %iterator that will be compared with *this. 290 */ 291 bool operator==(const const_iterator& y) const; 292 293 //! Compares \p *this with y. 294 /*! 295 \param y 296 The %iterator that will be compared with *this. 297 */ 298 bool operator!=(const const_iterator& y) const; 299 300 private: 301 //! Constructor from a Base iterator. 302 explicit const_iterator(Base b); 303 304 //! The Base iterator on the Constraint_Sequence. 305 Base itr; 306 307 friend class MIP_Problem; 308 }; 309 310 /*! \brief 311 Returns a read-only iterator to the first constraint defining 312 the feasible region. 313 */ 314 const_iterator constraints_begin() const; 315 316 /*! \brief 317 Returns a past-the-end read-only iterator to the sequence of 318 constraints defining the feasible region. 319 */ 320 const_iterator constraints_end() const; 321 322 //! Returns the objective function. 323 const Linear_Expression& objective_function() const; 324 325 //! Returns the optimization mode. 326 Optimization_Mode optimization_mode() const; 327 328 //! Resets \p *this to be equal to the trivial MIP problem. 329 /*! 330 The space dimension is reset to \f$0\f$. 331 */ 332 void clear(); 333 334 /*! \brief 335 Adds \p m new space dimensions and embeds the old MIP problem 336 in the new vector space. 337 338 \param m 339 The number of dimensions to add. 340 341 \exception std::length_error 342 Thrown if adding \p m new space dimensions would cause the 343 vector space to exceed dimension <CODE>max_space_dimension()</CODE>. 344 345 The new space dimensions will be those having the highest indexes 346 in the new MIP problem; they are initially unconstrained. 347 */ 348 void add_space_dimensions_and_embed(dimension_type m); 349 350 /*! \brief 351 Sets the variables whose indexes are in set \p i_vars to be 352 integer space dimensions. 353 354 \exception std::invalid_argument 355 Thrown if some index in \p i_vars does not correspond to 356 a space dimension in \p *this. 357 */ 358 void add_to_integer_space_dimensions(const Variables_Set& i_vars); 359 360 /*! \brief 361 Adds a copy of constraint \p c to the MIP problem. 362 363 \exception std::invalid_argument 364 Thrown if the constraint \p c is a strict inequality or if its space 365 dimension is strictly greater than the space dimension of \p *this. 366 */ 367 void add_constraint(const Constraint& c); 368 369 /*! \brief 370 Adds a copy of the constraints in \p cs to the MIP problem. 371 372 \exception std::invalid_argument 373 Thrown if the constraint system \p cs contains any strict inequality 374 or if its space dimension is strictly greater than the space dimension 375 of \p *this. 376 */ 377 void add_constraints(const Constraint_System& cs); 378 379 //! Sets the objective function to \p obj. 380 /*! 381 \exception std::invalid_argument 382 Thrown if the space dimension of \p obj is strictly greater than 383 the space dimension of \p *this. 384 */ 385 void set_objective_function(const Linear_Expression& obj); 386 387 //! Sets the optimization mode to \p mode. 388 void set_optimization_mode(Optimization_Mode mode); 389 390 //! Checks satisfiability of \p *this. 391 /*! 392 \return 393 <CODE>true</CODE> if and only if the MIP problem is satisfiable. 394 */ 395 bool is_satisfiable() const; 396 397 //! Optimizes the MIP problem. 398 /*! 399 \return 400 An MIP_Problem_Status flag indicating the outcome of the optimization 401 attempt (unfeasible, unbounded or optimized problem). 402 */ 403 MIP_Problem_Status solve() const; 404 405 /*! \brief 406 Sets \p num and \p denom so that 407 \f$\frac{\mathtt{numer}}{\mathtt{denom}}\f$ is the result of 408 evaluating the objective function on \p evaluating_point. 409 410 \param evaluating_point 411 The point on which the objective function will be evaluated. 412 413 \param numer 414 On exit will contain the numerator of the evaluated value. 415 416 \param denom 417 On exit will contain the denominator of the evaluated value. 418 419 \exception std::invalid_argument 420 Thrown if \p *this and \p evaluating_point are dimension-incompatible 421 or if the generator \p evaluating_point is not a point. 422 */ 423 void evaluate_objective_function(const Generator& evaluating_point, 424 Coefficient& numer, 425 Coefficient& denom) const; 426 427 //! Returns a feasible point for \p *this, if it exists. 428 /*! 429 \exception std::domain_error 430 Thrown if the MIP problem is not satisfiable. 431 */ 432 const Generator& feasible_point() const; 433 434 //! Returns an optimal point for \p *this, if it exists. 435 /*! 436 \exception std::domain_error 437 Thrown if \p *this does not not have an optimizing point, i.e., 438 if the MIP problem is unbounded or not satisfiable. 439 */ 440 const Generator& optimizing_point() const; 441 442 /*! \brief 443 Sets \p numer and \p denom so that 444 \f$\frac{\mathtt{numer}}{\mathtt{denom}}\f$ is the solution of the 445 optimization problem. 446 447 \exception std::domain_error 448 Thrown if \p *this does not not have an optimizing point, i.e., 449 if the MIP problem is unbounded or not satisfiable. 450 */ 451 void optimal_value(Coefficient& numer, Coefficient& denom) const; 452 453 //! Checks if all the invariants are satisfied. 454 bool OK() const; 455 456 PPL_OUTPUT_DECLARATIONS 457 458 /*! \brief 459 Loads from \p s an ASCII representation (as produced by 460 ascii_dump(std::ostream&) const) and sets \p *this accordingly. 461 Returns <CODE>true</CODE> if successful, <CODE>false</CODE> otherwise. 462 */ 463 bool ascii_load(std::istream& s); 464 465 //! Returns the total size in bytes of the memory occupied by \p *this. 466 memory_size_type total_memory_in_bytes() const; 467 468 //! Returns the size in bytes of the memory managed by \p *this. 469 memory_size_type external_memory_in_bytes() const; 470 471 //! Swaps \p *this with \p y. 472 void m_swap(MIP_Problem& y); 473 474 //! Names of MIP problems' control parameters. 475 enum Control_Parameter_Name { 476 //! The pricing rule. 477 PRICING 478 }; 479 480 //! Possible values for MIP problem's control parameters. 481 enum Control_Parameter_Value { 482 //! Steepest edge pricing method, using floating points (default). 483 PRICING_STEEPEST_EDGE_FLOAT, 484 //! Steepest edge pricing method, using Coefficient. 485 PRICING_STEEPEST_EDGE_EXACT, 486 //! Textbook pricing method. 487 PRICING_TEXTBOOK 488 }; 489 490 //! Returns the value of the control parameter \p name. 491 Control_Parameter_Value 492 get_control_parameter(Control_Parameter_Name name) const; 493 494 //! Sets control parameter \p value. 495 void set_control_parameter(Control_Parameter_Value value); 496 497 private: 498 //! The dimension of the vector space. 499 dimension_type external_space_dim; 500 501 /*! \brief 502 The space dimension of the current (partial) solution of the 503 MIP problem; it may be smaller than \p external_space_dim. 504 */ 505 dimension_type internal_space_dim; 506 507 #if PPL_USE_SPARSE_MATRIX 508 typedef Sparse_Row Row; 509 #else 510 typedef Dense_Row Row; 511 #endif 512 513 //! The matrix encoding the current feasible region in tableau form. 514 Matrix<Row> tableau; 515 516 typedef Row working_cost_type; 517 518 //! The working cost function. 519 working_cost_type working_cost; 520 521 //! A map between the variables of `input_cs' and `tableau'. 522 /*! 523 Contains all the pairs (i, j) such that mapping[i].first encodes the index 524 of the column in the tableau where input_cs[i] is stored; if 525 mapping[i].second is not a zero, it encodes the split part of the tableau 526 of input_cs[i]. 527 The "positive" one is represented by mapping[i].first and the "negative" 528 one is represented by mapping[i].second. 529 */ 530 std::vector<std::pair<dimension_type, dimension_type> > mapping; 531 532 //! The current basic solution. 533 std::vector<dimension_type> base; 534 535 //! An enumerated type describing the internal status of the MIP problem. 536 enum Status { 537 //! The MIP problem is unsatisfiable. 538 UNSATISFIABLE, 539 //! The MIP problem is satisfiable; a feasible solution has been computed. 540 SATISFIABLE, 541 //! The MIP problem is unbounded; a feasible solution has been computed. 542 UNBOUNDED, 543 //! The MIP problem is optimized; an optimal solution has been computed. 544 OPTIMIZED, 545 /*! \brief 546 The feasible region of the MIP problem has been changed by adding 547 new space dimensions or new constraints; a feasible solution for 548 the old feasible region is still available. 549 */ 550 PARTIALLY_SATISFIABLE 551 }; 552 553 //! The internal state of the MIP problem. 554 Status status; 555 556 // TODO: merge `status', `initialized', `pricing' and (maybe) `opt_mode' 557 // into a single bitset status word, so as to save space and allow 558 // for other control parameters. 559 560 //! The pricing method in use. 561 Control_Parameter_Value pricing; 562 563 /*! \brief 564 A Boolean encoding whether or not internal data structures have 565 already been properly sized and populated: useful to allow for 566 deeper checks in method OK(). 567 */ 568 bool initialized; 569 570 //! The sequence of constraints describing the feasible region. 571 std::vector<Constraint*> input_cs; 572 573 /*! \brief 574 The number of constraints that are inherited from our parent 575 in the recursion tree built when solving via branch-and-bound. 576 577 The first \c inherited_constraints elements in \c input_cs point to 578 the inherited constraints, whose resources are owned by our ancestors. 579 The resources of the other elements in \c input_cs are owned by \c *this 580 and should be appropriately released on destruction. 581 */ 582 dimension_type inherited_constraints; 583 584 //! The first index of `input_cs' containing a pending constraint. 585 dimension_type first_pending_constraint; 586 587 //! The objective function to be optimized. 588 Linear_Expression input_obj_function; 589 590 //! The optimization mode requested. 591 Optimization_Mode opt_mode; 592 593 //! The last successfully computed feasible or optimizing point. 594 Generator last_generator; 595 596 /*! \brief 597 A set containing all the indexes of variables that are constrained 598 to have an integer value. 599 */ 600 Variables_Set i_variables; 601 602 //! A helper class to temporarily relax a MIP problem using RAII. 603 struct RAII_Temporary_Real_Relaxation { 604 MIP_Problem& lp; 605 Variables_Set i_vars; 606 RAII_Temporary_Real_RelaxationParma_Polyhedra_Library::MIP_Problem::RAII_Temporary_Real_Relaxation607 RAII_Temporary_Real_Relaxation(MIP_Problem& mip) 608 : lp(mip), i_vars() { 609 // Turn mip into an LP problem (saving i_variables in i_vars). 610 using std::swap; 611 swap(i_vars, lp.i_variables); 612 } 613 ~RAII_Temporary_Real_RelaxationParma_Polyhedra_Library::MIP_Problem::RAII_Temporary_Real_Relaxation614 ~RAII_Temporary_Real_Relaxation() { 615 // Restore the original set of integer variables. 616 using std::swap; 617 swap(i_vars, lp.i_variables); 618 } 619 }; 620 friend struct RAII_Temporary_Real_Relaxation; 621 622 //! A tag type to distinguish normal vs. inheriting copy constructor. 623 struct Inherit_Constraints {}; 624 625 //! Copy constructor inheriting constraints. 626 MIP_Problem(const MIP_Problem& y, Inherit_Constraints); 627 628 //! Helper method: implements exception safe addition. 629 void add_constraint_helper(const Constraint& c); 630 631 //! Processes the pending constraints of \p *this. 632 void process_pending_constraints(); 633 634 /*! \brief 635 Optimizes the MIP problem using the second phase of the 636 primal simplex algorithm. 637 */ 638 void second_phase(); 639 640 /*! \brief 641 Assigns to \p this->tableau a simplex tableau representing the 642 MIP problem, inserting into \p this->mapping the information 643 that is required to recover the original MIP problem. 644 645 \return 646 <CODE>UNFEASIBLE_MIP_PROBLEM</CODE> if the constraint system contains 647 any trivially unfeasible constraint (tableau was not computed); 648 <CODE>UNBOUNDED_MIP_PROBLEM</CODE> if the problem is trivially unbounded 649 (the computed tableau contains no constraints); 650 <CODE>OPTIMIZED_MIP_PROBLEM></CODE> if the problem is neither trivially 651 unfeasible nor trivially unbounded (the tableau was computed 652 successfully). 653 */ 654 MIP_Problem_Status 655 compute_tableau(std::vector<dimension_type>& worked_out_row); 656 657 /*! \brief 658 Parses the pending constraints to gather information on 659 how to resize the tableau. 660 661 \note 662 All of the method parameters are output parameters; their value 663 is only meaningful when the function exit returning value \c true. 664 665 \return 666 \c false if a trivially false constraint is detected, \c true otherwise. 667 668 \param additional_tableau_rows 669 On exit, this will store the number of rows that have to be added 670 to the original tableau. 671 672 \param additional_slack_variables 673 This will store the number of slack variables that have to be added 674 to the original tableau. 675 676 \param is_tableau_constraint 677 This container of Boolean flags is initially empty. On exit, it size 678 will be equal to the number of pending constraints in \c input_cs. 679 For each pending constraint index \c i, the corresponding element 680 of this container (having index <CODE>i - first_pending_constraint</CODE>) 681 will be set to \c true if and only if the constraint has to be included 682 in the tableau. 683 684 \param is_satisfied_inequality 685 This container of Boolean flags is initially empty. On exit, its size 686 will be equal to the number of pending constraints in \c input_cs. 687 For each pending constraint index \c i, the corresponding element 688 of this container (having index <CODE>i - first_pending_constraint</CODE>) 689 will be set to \c true if and only if it is an inequality and it 690 is already satisfied by \c last_generator (hence it does not require 691 the introduction of an artificial variable). 692 693 \param is_nonnegative_variable 694 This container of Boolean flags is initially empty. 695 On exit, it size is equal to \c external_space_dim. 696 For each variable (index), the corresponding element of this container 697 is \c true if the variable is known to be nonnegative (and hence should 698 not be split into a positive and a negative part). 699 700 \param is_remergeable_variable 701 This container of Boolean flags is initially empty. 702 On exit, it size is equal to \c internal_space_dim. 703 For each variable (index), the corresponding element of this container 704 is \c true if the variable was previously split into positive and 705 negative parts that can now be merged back, since it is known 706 that the variable is nonnegative. 707 */ 708 bool parse_constraints(dimension_type& additional_tableau_rows, 709 dimension_type& additional_slack_variables, 710 std::deque<bool>& is_tableau_constraint, 711 std::deque<bool>& is_satisfied_inequality, 712 std::deque<bool>& is_nonnegative_variable, 713 std::deque<bool>& is_remergeable_variable) const; 714 715 /*! \brief 716 Computes the row index of the variable exiting the base 717 of the MIP problem. Implemented with anti-cycling rule. 718 719 \return 720 The row index of the variable exiting the base. 721 722 \param entering_var_index 723 The column index of the variable entering the base. 724 */ 725 dimension_type 726 get_exiting_base_index(dimension_type entering_var_index) const; 727 728 //! Linearly combines \p x with \p y so that <CODE>*this[k]</CODE> is 0. 729 /*! 730 \param x 731 The row that will be combined with \p y object. 732 733 \param y 734 The row that will be combined with \p x object. 735 736 \param k 737 The position of \p *this that have to be \f$0\f$. 738 739 Computes a linear combination of \p x and \p y having 740 the element of index \p k equal to \f$0\f$. Then it assigns 741 the resulting Row to \p x and normalizes it. 742 */ 743 static void linear_combine(Row& x, const Row& y, const dimension_type k); 744 745 // TODO: Remove this when the sparse working cost has been tested enough. 746 #if PPL_USE_SPARSE_MATRIX 747 748 //! Linearly combines \p x with \p y so that <CODE>*this[k]</CODE> is 0. 749 /*! 750 \param x 751 The row that will be combined with \p y object. 752 753 \param y 754 The row that will be combined with \p x object. 755 756 \param k 757 The position of \p *this that have to be \f$0\f$. 758 759 Computes a linear combination of \p x and \p y having 760 the element of index \p k equal to \f$0\f$. Then it assigns 761 the resulting Dense_Row to \p x and normalizes it. 762 */ 763 static void linear_combine(Dense_Row& x, const Sparse_Row& y, 764 const dimension_type k); 765 766 #endif // defined(PPL_USE_SPARSE_MATRIX) 767 768 static bool is_unbounded_obj_function( 769 const Linear_Expression& obj_function, 770 const std::vector<std::pair<dimension_type, dimension_type> >& mapping, 771 Optimization_Mode optimization_mode); 772 773 /*! \brief 774 Performs the pivoting operation on the tableau. 775 776 \param entering_var_index 777 The index of the variable entering the base. 778 779 \param exiting_base_index 780 The index of the row exiting the base. 781 */ 782 void pivot(dimension_type entering_var_index, 783 dimension_type exiting_base_index); 784 785 /*! \brief 786 Computes the column index of the variable entering the base, 787 using the textbook algorithm with anti-cycling rule. 788 789 \return 790 The column index of the variable that enters the base. 791 If no such variable exists, optimality was achieved 792 and <CODE>0</CODE> is returned. 793 */ 794 dimension_type textbook_entering_index() const; 795 796 /*! \brief 797 Computes the column index of the variable entering the base, 798 using an exact steepest-edge algorithm with anti-cycling rule. 799 800 \return 801 The column index of the variable that enters the base. 802 If no such variable exists, optimality was achieved 803 and <CODE>0</CODE> is returned. 804 805 To compute the entering_index, the steepest edge algorithm chooses 806 the index `j' such that \f$\frac{d_{j}}{\|\Delta x^{j} \|}\f$ is the 807 largest in absolute value, where 808 \f[ 809 \|\Delta x^{j} \| 810 = \left( 811 1+\sum_{i=1}^{m} \alpha_{ij}^2 812 \right)^{\frac{1}{2}}. 813 \f] 814 Recall that, due to the exact integer implementation of the algorithm, 815 our tableau does not contain the ``real'' \f$\alpha\f$ values, but these 816 can be computed dividing the value of the coefficient by the value of 817 the variable in base. Obviously the result may not be an integer, so 818 we will proceed in another way: we compute the lcm of all the variables 819 in base to get the good ``weight'' of each Coefficient of the tableau. 820 */ 821 dimension_type steepest_edge_exact_entering_index() const; 822 823 /*! \brief 824 Same as steepest_edge_exact_entering_index, 825 but using floating points. 826 827 \note 828 Due to rounding errors, the index of the variable entering the base 829 of the MIP problem is not predictable across different architectures. 830 Hence, the overall simplex computation may differ in the path taken 831 to reach the optimum. Anyway, the exact final result will be computed 832 for the MIP_Problem. 833 */ 834 dimension_type steepest_edge_float_entering_index() const; 835 836 /*! \brief 837 Returns <CODE>true</CODE> if and if only the algorithm successfully 838 computed a feasible solution. 839 840 \note 841 Uses an exact pricing method (either textbook or exact steepest edge), 842 so that the result is deterministic across different architectures. 843 */ 844 bool compute_simplex_using_exact_pricing(); 845 846 /*! \brief 847 Returns <CODE>true</CODE> if and if only the algorithm successfully 848 computed a feasible solution. 849 850 \note 851 Uses a floating point implementation of the steepest edge pricing 852 method, so that the result is correct, but not deterministic across 853 different architectures. 854 */ 855 bool compute_simplex_using_steepest_edge_float(); 856 857 /*! \brief 858 Drop unnecessary artificial variables from the tableau and get ready 859 for the second phase of the simplex algorithm. 860 861 \note 862 The two parameters denote a STL-like half-open range. 863 It is assumed that \p begin_artificials is strictly greater than 0 864 and smaller than \p end_artificials. 865 866 \param begin_artificials 867 The start of the tableau column index range for artificial variables. 868 869 \param end_artificials 870 The end of the tableau column index range for artificial variables. 871 Note that column index end_artificial is \e excluded from the range. 872 */ 873 void erase_artificials(dimension_type begin_artificials, 874 dimension_type end_artificials); 875 876 bool is_in_base(dimension_type var_index, 877 dimension_type& row_index) const; 878 879 /*! \brief 880 Computes a valid generator that satisfies all the constraints of the 881 Linear Programming problem associated to \p *this. 882 */ 883 void compute_generator() const; 884 885 /*! \brief 886 Merges back the positive and negative part of a (previously split) 887 variable after detecting a corresponding nonnegativity constraint. 888 889 \return 890 If the negative part of \p var_index was in base, the index of 891 the corresponding tableau row (which has become non-feasible); 892 otherwise \c not_a_dimension(). 893 894 \param var_index 895 The index of the variable that has to be merged. 896 */ 897 dimension_type merge_split_variable(dimension_type var_index); 898 899 //! Returns <CODE>true</CODE> if and only if \p c is satisfied by \p g. 900 static bool is_satisfied(const Constraint& c, const Generator& g); 901 902 //! Returns <CODE>true</CODE> if and only if \p c is saturated by \p g. 903 static bool is_saturated(const Constraint& c, const Generator& g); 904 905 /*! \brief 906 Returns a status that encodes the solution of the MIP problem. 907 908 \param have_incumbent_solution 909 It is used to store if the solving process has found a provisional 910 optimum point. 911 912 \param incumbent_solution_value 913 Encodes the evaluated value of the provisional optimum point found. 914 915 \param incumbent_solution_point 916 If the method returns `OPTIMIZED', this will contain the optimality point. 917 918 \param mip 919 The problem that has to be solved. 920 921 \param i_vars 922 The variables that are constrained to take an integer value. 923 */ 924 static MIP_Problem_Status solve_mip(bool& have_incumbent_solution, 925 mpq_class& incumbent_solution_value, 926 Generator& incumbent_solution_point, 927 MIP_Problem& mip, 928 const Variables_Set& i_vars); 929 930 /*! \brief 931 Returns \c true if and if only the LP problem is satisfiable. 932 */ 933 bool is_lp_satisfiable() const; 934 935 /*! \brief 936 Returns \c true if and if only the MIP problem \p mip is satisfiable 937 when variables in \p i_vars can only take integral values. 938 939 \param mip 940 The MIP problem. This is assumed to have no integral space dimension 941 (so that it is a pure LP problem). 942 943 \param i_vars 944 The variables that are constrained to take integral values. 945 946 \param p 947 If \c true is returned, it will encode a feasible point. 948 */ 949 static bool is_mip_satisfiable(MIP_Problem& mip, 950 const Variables_Set& i_vars, 951 Generator& p); 952 953 /*! \brief 954 Returns \c true if and if only \c mip.last_generator satisfies all the 955 integrality conditions implicitly stated using by \p i_vars. 956 957 \param mip 958 The MIP problem. This is assumed to have no integral space dimension 959 (so that it is a pure LP problem). 960 961 \param i_vars 962 The variables that are constrained to take an integer value. 963 964 \param branching_index 965 If \c false is returned, this will encode the non-integral variable 966 index on which the `branch and bound' algorithm should be applied. 967 */ 968 static bool choose_branching_variable(const MIP_Problem& mip, 969 const Variables_Set& i_vars, 970 dimension_type& branching_index); 971 }; 972 973 #include "MIP_Problem_inlines.hh" 974 #include "MIP_Problem_templates.hh" 975 976 #endif // !defined(PPL_MIP_Problem_defs_hh) 977