1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the class library */ 4 /* SoPlex --- the Sequential object-oriented simPlex. */ 5 /* */ 6 /* Copyright (c) 1996-2023 Zuse Institute Berlin (ZIB) */ 7 /* */ 8 /* Licensed under the Apache License, Version 2.0 (the "License"); */ 9 /* you may not use this file except in compliance with the License. */ 10 /* You may obtain a copy of the License at */ 11 /* */ 12 /* http://www.apache.org/licenses/LICENSE-2.0 */ 13 /* */ 14 /* Unless required by applicable law or agreed to in writing, software */ 15 /* distributed under the License is distributed on an "AS IS" BASIS, */ 16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ 17 /* See the License for the specific language governing permissions and */ 18 /* limitations under the License. */ 19 /* */ 20 /* You should have received a copy of the Apache-2.0 license */ 21 /* along with SoPlex; see the file LICENSE. If not email to soplex@zib.de. */ 22 /* */ 23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 24 25 /**@file spxmainsm.h 26 * @brief General methods in LP preprocessing. 27 */ 28 #ifndef _SPXMAINSM_H_ 29 #define _SPXMAINSM_H_ 30 31 #include <assert.h> 32 #include <memory> 33 34 #include "soplex/spxdefines.h" 35 #include "soplex/spxsimplifier.h" 36 #include "soplex/array.h" 37 #include "soplex/exceptions.h" 38 39 namespace soplex 40 { 41 //--------------------------------------------------------------------- 42 // class SPxMainSM 43 //--------------------------------------------------------------------- 44 45 /**@brief LP simplifier for removing uneccessary row/columns. 46 @ingroup Algo 47 48 This #SPxSimplifier is mainly based on the paper "Presolving in 49 linear programming" by E. Andersen and K. Andersen (Mathematical 50 Programming, 1995). It implements all proposed methods and some 51 other preprocessing techniques for removing redundant rows and 52 columns and bounds. Also infeasibility and unboundedness may be 53 detected. 54 55 Removed are: 56 - empty rows / columns 57 - unconstraint rows 58 - row singletons 59 - forcing rows 60 - zero objective column singletons 61 - (implied) free column singletons 62 - doubleton equations combined with a column singleton 63 - (implicitly) fixed columns 64 - redundant lhs / rhs 65 - redundant variable bounds 66 - variables that are free in one direction 67 - (weakly) dominated columns 68 - duplicate rows / columns 69 */ 70 template <class R> 71 class SPxMainSM : public SPxSimplifier<R> 72 { 73 private: 74 //--------------------------------------------------------------------- 75 // class PostsolveStep 76 //--------------------------------------------------------------------- 77 78 /**@brief Base class for postsolving operations. 79 @ingroup Algo 80 81 Class #PostStep is an abstract base class providing the 82 interface for operations in the postsolving process. 83 */ 84 class PostStep 85 { 86 private: 87 /// name of the simplifier 88 const char* m_name; 89 /// number of cols 90 int nCols; 91 /// number of rows 92 int nRows; 93 /// 0-epsilon of this poststep 94 std::shared_ptr<Tolerances> _tolerances; 95 96 public: 97 /// constructor. 98 PostStep(const char* p_name, std::shared_ptr<Tolerances> tols, int nR = 0, int nC = 0) 99 : m_name(p_name) 100 , nCols(nC) 101 , nRows(nR) 102 { 103 _tolerances = tols; 104 } 105 /// copy constructor. 106 PostStep(const PostStep& old) 107 : m_name(old.m_name) 108 , nCols(old.nCols) 109 , nRows(old.nRows) 110 { 111 _tolerances = old._tolerances; 112 } 113 /// assignment operator 114 PostStep& operator=(const PostStep& /*rhs*/) 115 { 116 return *this; 117 } 118 /// destructor. 119 virtual ~PostStep() 120 { 121 m_name = 0; 122 } 123 /// get name of simplifying step. 124 virtual const char* getName() const 125 { 126 return m_name; 127 } 128 /// clone function for polymorphism 129 virtual PostStep* clone() const = 0; 130 /// executes the postsolving. 131 virtual void execute( 132 VectorBase<R>& x, //*< Primal solution VectorBase<R> */ 133 VectorBase<R>& y, //*< Dual solution VectorBase<R> */ 134 VectorBase<R>& s, //*< VectorBase<R> of slacks */ 135 VectorBase<R>& r, //*< Reduced cost VectorBase<R> */ 136 DataArray<typename SPxSolverBase<R>::VarStatus>& cBasis, //*< Basis status of column basis */ 137 DataArray<typename SPxSolverBase<R>::VarStatus>& rBasis, //*< Basis status of row basis */ 138 bool isOptimal 139 ) const = 0; 140 141 virtual bool checkBasisDim(DataArray<typename SPxSolverBase<R>::VarStatus> rows, 142 DataArray<typename SPxSolverBase<R>::VarStatus> cols) const; 143 144 virtual R feastol() const 145 { 146 // todo change to feastol 147 return _tolerances->floatingPointFeastol(); 148 } 149 virtual R epsilon() const 150 { 151 return _tolerances->epsilon(); 152 } 153 }; 154 155 /**@brief Postsolves row objectives. 156 @ingroup Algo 157 */ 158 class RowObjPS : public PostStep 159 { 160 private: 161 int m_i; ///< row index 162 int m_j; ///< slack column index 163 164 public: 165 /// 166 RowObjPS(const SPxLPBase<R>& lp, int _i, int _j, std::shared_ptr<Tolerances> tols) 167 : PostStep("RowObj", tols, lp.nRows(), lp.nCols()) 168 , m_i(_i) 169 , m_j(_j) 170 {} 171 /// copy constructor 172 RowObjPS(const RowObjPS& old) 173 : PostStep(old) 174 , m_i(old.m_i) 175 , m_j(old.m_j) 176 {} 177 /// assignment operator 178 RowObjPS& operator=(const RowObjPS& rhs) 179 { 180 if(this != &rhs) 181 { 182 m_i = rhs.m_i; 183 m_j = rhs.m_j; 184 } 185 186 return *this; 187 } 188 /// 189 virtual void execute(VectorBase<R>& x, VectorBase<R>& y, VectorBase<R>& s, VectorBase<R>& r, 190 DataArray<typename SPxSolverBase<R>::VarStatus>& cBasis, 191 DataArray<typename SPxSolverBase<R>::VarStatus>& rBasis, bool isOptimal) const; 192 /// clone function for polymorphism 193 inline virtual PostStep* clone() const 194 { 195 return new RowObjPS(*this); 196 } 197 }; 198 199 /**@brief Postsolves unconstraint constraints. 200 @ingroup Algo 201 */ 202 class FreeConstraintPS : public PostStep 203 { 204 private: 205 int m_i; 206 int m_old_i; 207 DSVectorBase<R> m_row; 208 R m_row_obj; 209 210 public: 211 /// 212 FreeConstraintPS(const SPxLPBase<R>& lp, int _i, std::shared_ptr<Tolerances> tols) 213 : PostStep("FreeConstraint", tols, lp.nRows(), lp.nCols()) 214 , m_i(_i) 215 , m_old_i(lp.nRows() - 1) 216 , m_row(lp.rowVector(_i)) 217 , m_row_obj(lp.rowObj(_i)) 218 {} 219 /// copy constructor 220 FreeConstraintPS(const FreeConstraintPS& old) 221 : PostStep(old) 222 , m_i(old.m_i) 223 , m_old_i(old.m_old_i) 224 , m_row(old.m_row) 225 , m_row_obj(old.m_row_obj) 226 {} 227 /// assignment operator 228 FreeConstraintPS& operator=(const FreeConstraintPS& rhs) 229 { 230 if(this != &rhs) 231 { 232 m_i = rhs.m_i; 233 m_old_i = rhs.m_old_i; 234 m_row = rhs.m_row; 235 m_row_obj = rhs.m_row_obj; 236 } 237 238 return *this; 239 } 240 /// 241 virtual void execute(VectorBase<R>& x, VectorBase<R>& y, VectorBase<R>& s, VectorBase<R>& r, 242 DataArray<typename SPxSolverBase<R>::VarStatus>& cBasis, 243 DataArray<typename SPxSolverBase<R>::VarStatus>& rBasis, bool isOptimal) const; 244 /// clone function for polymorphism 245 inline virtual PostStep* clone() const 246 { 247 return new FreeConstraintPS(*this); 248 } 249 }; 250 251 /**@brief Postsolves empty constraints. 252 @ingroup Algo 253 */ 254 class EmptyConstraintPS : public PostStep 255 { 256 private: 257 int m_i; 258 int m_old_i; 259 R m_row_obj; 260 261 public: 262 /// 263 EmptyConstraintPS(const SPxLPBase<R>& lp, int _i, std::shared_ptr<Tolerances> tols) 264 : PostStep("EmptyConstraint", tols, lp.nRows(), lp.nCols()) 265 , m_i(_i) 266 , m_old_i(lp.nRows() - 1) 267 , m_row_obj(lp.rowObj(_i)) 268 {} 269 /// copy constructor 270 EmptyConstraintPS(const EmptyConstraintPS& old) 271 : PostStep(old) 272 , m_i(old.m_i) 273 , m_old_i(old.m_old_i) 274 , m_row_obj(old.m_row_obj) 275 {} 276 /// assignment operator 277 EmptyConstraintPS& operator=(const EmptyConstraintPS& rhs) 278 { 279 if(this != &rhs) 280 { 281 m_i = rhs.m_i; 282 m_old_i = rhs.m_old_i; 283 m_row_obj = rhs.m_row_obj; 284 } 285 286 return *this; 287 } 288 /// 289 virtual void execute(VectorBase<R>& x, VectorBase<R>& y, VectorBase<R>& s, VectorBase<R>& r, 290 DataArray<typename SPxSolverBase<R>::VarStatus>& cBasis, 291 DataArray<typename SPxSolverBase<R>::VarStatus>& rBasis, bool isOptimal) const; 292 /// clone function for polymorphism 293 inline virtual PostStep* clone() const 294 { 295 return new EmptyConstraintPS(*this); 296 } 297 }; 298 299 /**@brief Postsolves row singletons. 300 @ingroup Algo 301 */ 302 class RowSingletonPS : public PostStep 303 { 304 private: 305 const int m_i; 306 const int m_old_i; 307 const int m_j; 308 const R m_lhs; 309 const R m_rhs; 310 const bool m_strictLo; 311 const bool m_strictUp; 312 const bool m_maxSense; 313 const R m_obj; 314 DSVectorBase<R> m_col; 315 const R m_newLo; 316 const R m_newUp; 317 const R m_oldLo; 318 const R m_oldUp; 319 const R m_row_obj; 320 321 public: 322 /// 323 RowSingletonPS(const SPxLPBase<R>& lp, int _i, int _j, bool strictLo, bool strictUp, 324 R newLo, R newUp, R oldLo, R oldUp, std::shared_ptr<Tolerances> tols) 325 : PostStep("RowSingleton", tols, lp.nRows(), lp.nCols()) 326 , m_i(_i) 327 , m_old_i(lp.nRows() - 1) 328 , m_j(_j) 329 , m_lhs(lp.lhs(_i)) 330 , m_rhs(lp.rhs(_i)) 331 , m_strictLo(strictLo) 332 , m_strictUp(strictUp) 333 , m_maxSense(lp.spxSense() == SPxLPBase<R>::MAXIMIZE) 334 , m_obj(lp.spxSense() == SPxLPBase<R>::MINIMIZE ? lp.obj(_j) : -lp.obj(_j)) 335 , m_col(lp.colVector(_j)) 336 , m_newLo(newLo) 337 , m_newUp(newUp) 338 , m_oldLo(oldLo) 339 , m_oldUp(oldUp) 340 , m_row_obj(lp.rowObj(_i)) 341 {} 342 /// copy constructor 343 RowSingletonPS(const RowSingletonPS& old) 344 : PostStep(old) 345 , m_i(old.m_i) 346 , m_old_i(old.m_old_i) 347 , m_j(old.m_j) 348 , m_lhs(old.m_lhs) 349 , m_rhs(old.m_rhs) 350 , m_strictLo(old.m_strictLo) 351 , m_strictUp(old.m_strictUp) 352 , m_maxSense(old.m_maxSense) 353 , m_obj(old.m_obj) 354 , m_col(old.m_col) 355 , m_newLo(old.m_newLo) 356 , m_newUp(old.m_newUp) 357 , m_oldLo(old.m_oldLo) 358 , m_oldUp(old.m_oldUp) 359 , m_row_obj(old.m_row_obj) 360 {} 361 /// assignment operator 362 RowSingletonPS& operator=(const RowSingletonPS& rhs) 363 { 364 if(this != &rhs) 365 { 366 PostStep::operator=(rhs); 367 m_col = rhs.m_col; 368 } 369 370 return *this; 371 } 372 /// clone function for polymorphism 373 inline virtual PostStep* clone() const 374 { 375 return new RowSingletonPS(*this); 376 } 377 /// 378 virtual void execute(VectorBase<R>& x, VectorBase<R>& y, VectorBase<R>& s, VectorBase<R>& r, 379 DataArray<typename SPxSolverBase<R>::VarStatus>& cBasis, 380 DataArray<typename SPxSolverBase<R>::VarStatus>& rBasis, bool isOptimal) const; 381 }; 382 383 /**@brief Postsolves forcing constraints. 384 @ingroup Algo 385 */ 386 class ForceConstraintPS : public PostStep 387 { 388 private: 389 const int m_i; 390 const int m_old_i; 391 const R m_lRhs; 392 DSVectorBase<R> m_row; 393 Array<R> m_objs; 394 DataArray<bool> m_fixed; 395 Array<DSVectorBase<R>> m_cols; 396 const bool m_lhsFixed; 397 const bool m_maxSense; 398 Array<R> m_oldLowers; 399 Array<R> m_oldUppers; 400 const R m_lhs; 401 const R m_rhs; 402 const R m_rowobj; 403 404 public: 405 /// 406 ForceConstraintPS(const SPxLPBase<R>& lp, int _i, bool lhsFixed, 407 DataArray<bool>& fixCols, 408 Array<R>& lo, Array<R>& up, std::shared_ptr<Tolerances> tols) 409 : PostStep("ForceConstraint", tols, lp.nRows(), lp.nCols()) 410 , m_i(_i) 411 , m_old_i(lp.nRows() - 1) 412 , m_lRhs(lhsFixed ? lp.lhs(_i) : lp.rhs(_i)) 413 , m_row(lp.rowVector(_i)) 414 , m_objs(lp.rowVector(_i).size()) 415 , m_fixed(fixCols) 416 , m_cols(lp.rowVector(_i).size()) 417 , m_lhsFixed(lhsFixed) 418 , m_maxSense(lp.spxSense() == SPxLPBase<R>::MAXIMIZE) 419 , m_oldLowers(lo) 420 , m_oldUppers(up) 421 , m_lhs(lp.lhs(_i)) 422 , m_rhs(lp.rhs(_i)) 423 , m_rowobj(lp.rowObj(_i)) 424 { 425 for(int k = 0; k < m_row.size(); ++k) 426 { 427 m_objs[k] = (lp.spxSense() == SPxLPBase<R>::MINIMIZE ? lp.obj(m_row.index(k)) : -lp.obj(m_row.index( 428 k))); 429 m_cols[k] = lp.colVector(m_row.index(k)); 430 } 431 } 432 /// copy constructor 433 ForceConstraintPS(const ForceConstraintPS& old) 434 : PostStep(old) 435 , m_i(old.m_i) 436 , m_old_i(old.m_old_i) 437 , m_lRhs(old.m_lRhs) 438 , m_row(old.m_row) 439 , m_objs(old.m_objs) 440 , m_fixed(old.m_fixed) 441 , m_cols(old.m_cols) 442 , m_lhsFixed(old.m_lhsFixed) 443 , m_maxSense(old.m_maxSense) 444 , m_oldLowers(old.m_oldLowers) 445 , m_oldUppers(old.m_oldUppers) 446 , m_lhs(old.m_lhs) 447 , m_rhs(old.m_rhs) 448 , m_rowobj(old.m_rowobj) 449 {} 450 /// assignment operator 451 ForceConstraintPS& operator=(const ForceConstraintPS& rhs) 452 { 453 if(this != &rhs) 454 { 455 PostStep::operator=(rhs); 456 m_row = rhs.m_row; 457 m_objs = rhs.m_objs; 458 m_fixed = rhs.m_fixed; 459 m_cols = rhs.m_cols; 460 m_oldLowers = rhs.m_oldLowers; 461 m_oldUppers = rhs.m_oldUppers; 462 } 463 464 return *this; 465 } 466 /// clone function for polymorphism 467 inline virtual PostStep* clone() const 468 { 469 return new ForceConstraintPS(*this); 470 } 471 /// 472 virtual void execute(VectorBase<R>& x, VectorBase<R>& y, VectorBase<R>& s, VectorBase<R>& r, 473 DataArray<typename SPxSolverBase<R>::VarStatus>& cBasis, 474 DataArray<typename SPxSolverBase<R>::VarStatus>& rBasis, bool isOptimal) const; 475 }; 476 477 /**@brief Postsolves variable fixing. 478 @ingroup Algo 479 */ 480 class FixVariablePS : public PostStep 481 { 482 private: 483 const int m_j; 484 const int m_old_j; 485 const R m_val; 486 const R m_obj; 487 const R m_lower; 488 const R m_upper; 489 const bool m_correctIdx; /// does the index mapping have to be updated in postsolving? 490 DSVectorBase<R> m_col; 491 492 public: 493 /// 494 FixVariablePS(const SPxLPBase<R>& lp, SPxMainSM& simplifier, int _j, const R val, 495 std::shared_ptr<Tolerances> tols, bool correctIdx = true) 496 : PostStep("FixVariable", tols, lp.nRows(), lp.nCols()) 497 , m_j(_j) 498 , m_old_j(lp.nCols() - 1) 499 , m_val(val) 500 , m_obj(lp.spxSense() == SPxLPBase<R>::MINIMIZE ? lp.obj(_j) : -lp.obj(_j)) 501 , m_lower(lp.lower(_j)) 502 , m_upper(lp.upper(_j)) 503 , m_correctIdx(correctIdx) 504 , m_col(lp.colVector(_j)) 505 { 506 simplifier.addObjoffset(m_val * lp.obj(m_j)); 507 } 508 /// copy constructor 509 FixVariablePS(const FixVariablePS& old) 510 : PostStep(old) 511 , m_j(old.m_j) 512 , m_old_j(old.m_old_j) 513 , m_val(old.m_val) 514 , m_obj(old.m_obj) 515 , m_lower(old.m_lower) 516 , m_upper(old.m_upper) 517 , m_correctIdx(old.m_correctIdx) 518 , m_col(old.m_col) 519 {} 520 /// assignment operator 521 FixVariablePS& operator=(const FixVariablePS& rhs) 522 { 523 if(this != &rhs) 524 { 525 PostStep::operator=(rhs); 526 m_col = rhs.m_col; 527 } 528 529 return *this; 530 } 531 /// clone function for polymorphism 532 inline virtual PostStep* clone() const 533 { 534 return new FixVariablePS(*this); 535 } 536 /// 537 virtual void execute(VectorBase<R>& x, VectorBase<R>& y, VectorBase<R>& s, VectorBase<R>& r, 538 DataArray<typename SPxSolverBase<R>::VarStatus>& cBasis, 539 DataArray<typename SPxSolverBase<R>::VarStatus>& rBasis, bool isOptimal) const; 540 }; 541 542 /**@brief Postsolves variable bound fixing. 543 @ingroup Algo 544 */ 545 class FixBoundsPS : public PostStep 546 { 547 private: 548 const int m_j; 549 typename SPxSolverBase<R>::VarStatus m_status; 550 551 public: 552 /// 553 FixBoundsPS(const SPxLPBase<R>& lp, int j, R val, std::shared_ptr<Tolerances> tols) 554 : PostStep("FixBounds", tols, lp.nRows(), lp.nCols()) 555 , m_j(j) 556 { 557 if(EQrel(lp.lower(j), lp.upper(j), this->feastol())) 558 m_status = SPxSolverBase<R>::FIXED; 559 else if(EQrel(val, lp.lower(j), this->feastol())) 560 m_status = SPxSolverBase<R>::ON_LOWER; 561 else if(EQrel(val, lp.upper(j), this->feastol())) 562 m_status = SPxSolverBase<R>::ON_UPPER; 563 else if(lp.lower(j) <= R(-infinity) && lp.upper(j) >= R(infinity)) 564 m_status = SPxSolverBase<R>::ZERO; 565 else 566 { 567 throw SPxInternalCodeException("XMAISM14 This should never happen."); 568 } 569 } 570 /// copy constructor 571 FixBoundsPS(const FixBoundsPS& old) 572 : PostStep(old) 573 , m_j(old.m_j) 574 , m_status(old.m_status) 575 {} 576 /// assignment operator 577 FixBoundsPS& operator=(const FixBoundsPS& rhs) 578 { 579 if(this != &rhs) 580 { 581 PostStep::operator=(rhs); 582 m_status = rhs.m_status; 583 } 584 585 return *this; 586 } 587 /// clone function for polymorphism 588 inline virtual PostStep* clone() const 589 { 590 FixBoundsPS* FixBoundsPSptr = 0; 591 spx_alloc(FixBoundsPSptr); 592 return new(FixBoundsPSptr) FixBoundsPS(*this); 593 } 594 /// 595 virtual void execute(VectorBase<R>& x, VectorBase<R>& y, VectorBase<R>& s, VectorBase<R>& r, 596 DataArray<typename SPxSolverBase<R>::VarStatus>& cBasis, 597 DataArray<typename SPxSolverBase<R>::VarStatus>& rBasis, bool isOptimal) const; 598 }; 599 600 /**@brief Postsolves the case when constraints are removed due to a 601 variable with zero objective that is free in one direction. 602 @ingroup Algo 603 */ 604 class FreeZeroObjVariablePS : public PostStep 605 { 606 private: 607 const int m_j; 608 const int m_old_j; 609 const int m_old_i; 610 const R m_bnd; 611 DSVectorBase<R> m_col; 612 DSVectorBase<R> m_lRhs; 613 DSVectorBase<R> m_rowObj; 614 Array<DSVectorBase<R>> m_rows; 615 const bool m_loFree; 616 617 public: 618 /// 619 FreeZeroObjVariablePS(const SPxLPBase<R>& lp, int _j, bool loFree, 620 DSVectorBase<R> col_idx_sorted, std::shared_ptr<Tolerances> tols) 621 : PostStep("FreeZeroObjVariable", tols, lp.nRows(), lp.nCols()) 622 , m_j(_j) 623 , m_old_j(lp.nCols() - 1) 624 , m_old_i(lp.nRows() - 1) 625 , m_bnd(loFree ? lp.upper(_j) : lp.lower(_j)) 626 , m_col(col_idx_sorted) 627 , m_lRhs(lp.colVector(_j).size()) 628 , m_rowObj(lp.colVector(_j).size()) 629 , m_rows(lp.colVector(_j).size()) 630 , m_loFree(loFree) 631 { 632 for(int k = 0; k < m_col.size(); ++k) 633 { 634 int r = m_col.index(k); 635 636 if((m_loFree && m_col.value(k) > 0) || 637 (!m_loFree && m_col.value(k) < 0)) 638 m_lRhs.add(k, lp.rhs(r)); 639 else 640 m_lRhs.add(k, lp.lhs(r)); 641 642 m_rows[k] = lp.rowVector(r); 643 m_rowObj.add(k, lp.rowObj(r)); 644 } 645 } 646 /// copy constructor 647 FreeZeroObjVariablePS(const FreeZeroObjVariablePS& old) 648 : PostStep(old) 649 , m_j(old.m_j) 650 , m_old_j(old.m_old_j) 651 , m_old_i(old.m_old_i) 652 , m_bnd(old.m_bnd) 653 , m_col(old.m_col) 654 , m_lRhs(old.m_lRhs) 655 , m_rowObj(old.m_rowObj) 656 , m_rows(old.m_rows) 657 , m_loFree(old.m_loFree) 658 {} 659 /// assignment operator 660 FreeZeroObjVariablePS& operator=(const FreeZeroObjVariablePS& rhs) 661 { 662 if(this != &rhs) 663 { 664 PostStep::operator=(rhs); 665 m_col = rhs.m_col; 666 m_lRhs = rhs.m_lRhs; 667 m_rowObj = rhs.m_rowObj; 668 m_rows = rhs.m_rows; 669 } 670 671 return *this; 672 } 673 /// clone function for polymorphism 674 inline virtual PostStep* clone() const 675 { 676 FreeZeroObjVariablePS* FreeZeroObjVariablePSptr = 0; 677 spx_alloc(FreeZeroObjVariablePSptr); 678 return new(FreeZeroObjVariablePSptr) FreeZeroObjVariablePS(*this); 679 } 680 /// 681 virtual void execute(VectorBase<R>& x, VectorBase<R>& y, VectorBase<R>& s, VectorBase<R>& r, 682 DataArray<typename SPxSolverBase<R>::VarStatus>& cBasis, 683 DataArray<typename SPxSolverBase<R>::VarStatus>& rBasis, bool isOptimal) const; 684 }; 685 686 /**@brief Postsolves column singletons with zero objective. 687 @ingroup Algo 688 */ 689 class ZeroObjColSingletonPS : public PostStep 690 { 691 private: 692 const int m_j; 693 const int m_i; 694 const int m_old_j; 695 const R m_lhs; 696 const R m_rhs; 697 const R m_lower; 698 const R m_upper; 699 DSVectorBase<R> m_row; 700 701 public: 702 /// 703 ZeroObjColSingletonPS(const SPxLPBase<R>& lp, const SPxMainSM&, int _j, int _i, 704 std::shared_ptr<Tolerances> tols) 705 : PostStep("ZeroObjColSingleton", tols, lp.nRows(), lp.nCols()) 706 , m_j(_j) 707 , m_i(_i) 708 , m_old_j(lp.nCols() - 1) 709 , m_lhs(lp.lhs(_i)) 710 , m_rhs(lp.rhs(_i)) 711 , m_lower(lp.lower(_j)) 712 , m_upper(lp.upper(_j)) 713 , m_row(lp.rowVector(_i)) 714 {} 715 /// copy constructor 716 ZeroObjColSingletonPS(const ZeroObjColSingletonPS& old) 717 : PostStep(old) 718 , m_j(old.m_j) 719 , m_i(old.m_i) 720 , m_old_j(old.m_old_j) 721 , m_lhs(old.m_lhs) 722 , m_rhs(old.m_rhs) 723 , m_lower(old.m_lower) 724 , m_upper(old.m_upper) 725 , m_row(old.m_row) 726 {} 727 /// assignment operator 728 ZeroObjColSingletonPS& operator=(const ZeroObjColSingletonPS& rhs) 729 { 730 if(this != &rhs) 731 { 732 PostStep::operator=(rhs); 733 m_row = rhs.m_row; 734 } 735 736 return *this; 737 } 738 /// clone function for polymorphism 739 inline virtual PostStep* clone() const 740 { 741 ZeroObjColSingletonPS* ZeroObjColSingletonPSptr = 0; 742 spx_alloc(ZeroObjColSingletonPSptr); 743 return new(ZeroObjColSingletonPSptr) ZeroObjColSingletonPS(*this); 744 } 745 /// 746 virtual void execute(VectorBase<R>& x, VectorBase<R>& y, VectorBase<R>& s, VectorBase<R>& r, 747 DataArray<typename SPxSolverBase<R>::VarStatus>& cBasis, 748 DataArray<typename SPxSolverBase<R>::VarStatus>& rBasis, bool isOptimal) const; 749 }; 750 751 /**@brief Postsolves free column singletons. 752 @ingroup Algo 753 */ 754 class FreeColSingletonPS : public PostStep 755 { 756 private: 757 const int m_j; 758 const int m_i; 759 const int m_old_j; 760 const int m_old_i; 761 const R m_obj; 762 const R m_lRhs; 763 const bool m_onLhs; 764 const bool m_eqCons; 765 DSVectorBase<R> m_row; 766 767 public: 768 /// 769 FreeColSingletonPS(const SPxLPBase<R>& lp, SPxMainSM& simplifier, int _j, int _i, 770 R slackVal, std::shared_ptr<Tolerances> tols) 771 : PostStep("FreeColSingleton", tols, lp.nRows(), lp.nCols()) 772 , m_j(_j) 773 , m_i(_i) 774 , m_old_j(lp.nCols() - 1) 775 , m_old_i(lp.nRows() - 1) 776 , m_obj(lp.spxSense() == SPxLPBase<R>::MINIMIZE ? lp.obj(_j) : -lp.obj(_j)) 777 , m_lRhs(slackVal) 778 , m_onLhs(EQ(slackVal, lp.lhs(_i), this->epsilon())) 779 , m_eqCons(EQ(lp.lhs(_i), lp.rhs(_i), this->epsilon())) 780 , m_row(lp.rowVector(_i)) 781 { 782 assert(m_row[m_j] != 0.0); 783 simplifier.addObjoffset(m_lRhs * (lp.obj(m_j) / m_row[m_j])); 784 } 785 /// copy constructor 786 FreeColSingletonPS(const FreeColSingletonPS& old) 787 : PostStep(old) 788 , m_j(old.m_j) 789 , m_i(old.m_i) 790 , m_old_j(old.m_old_j) 791 , m_old_i(old.m_old_i) 792 , m_obj(old.m_obj) 793 , m_lRhs(old.m_lRhs) 794 , m_onLhs(old.m_onLhs) 795 , m_eqCons(old.m_eqCons) 796 , m_row(old.m_row) 797 {} 798 /// assignment operator 799 FreeColSingletonPS& operator=(const FreeColSingletonPS& rhs) 800 { 801 if(this != &rhs) 802 { 803 PostStep::operator=(rhs); 804 m_row = rhs.m_row; 805 } 806 807 return *this; 808 } 809 /// clone function for polymorphism 810 inline virtual PostStep* clone() const 811 { 812 FreeColSingletonPS* FreeColSingletonPSptr = 0; 813 spx_alloc(FreeColSingletonPSptr); 814 return new(FreeColSingletonPSptr) FreeColSingletonPS(*this); 815 } 816 /// 817 virtual void execute(VectorBase<R>& x, VectorBase<R>& y, VectorBase<R>& s, VectorBase<R>& r, 818 DataArray<typename SPxSolverBase<R>::VarStatus>& cBasis, 819 DataArray<typename SPxSolverBase<R>::VarStatus>& rBasis, bool isOptimal) const; 820 }; 821 822 /**@brief Postsolves doubleton equations combined with a column singleton. 823 @ingroup Algo 824 */ 825 class DoubletonEquationPS : public PostStep 826 { 827 private: 828 const int m_j; 829 const int m_k; 830 const int m_i; 831 const bool m_maxSense; 832 const bool m_jFixed; 833 const R m_jObj; 834 const R m_kObj; 835 const R m_aij; 836 const bool m_strictLo; 837 const bool m_strictUp; 838 const R m_newLo; 839 const R m_newUp; 840 const R m_oldLo; 841 const R m_oldUp; 842 const R m_Lo_j; 843 const R m_Up_j; 844 const R m_lhs; 845 const R m_rhs; 846 DSVectorBase<R> m_col; 847 848 public: 849 /// 850 DoubletonEquationPS(const SPxLPBase<R>& lp, int _j, int _k, int _i, R oldLo, R oldUp, 851 std::shared_ptr<Tolerances> tols) 852 : PostStep("DoubletonEquation", tols, lp.nRows(), lp.nCols()) 853 , m_j(_j) 854 , m_k(_k) 855 , m_i(_i) 856 , m_maxSense(lp.spxSense() == SPxLPBase<R>::MAXIMIZE) 857 , m_jFixed(EQ(lp.lower(_j), lp.upper(_j), this->epsilon())) 858 , m_jObj(lp.spxSense() == SPxLPBase<R>::MINIMIZE ? lp.obj(_j) : -lp.obj(_j)) 859 , m_kObj(lp.spxSense() == SPxLPBase<R>::MINIMIZE ? lp.obj(_k) : -lp.obj(_k)) 860 , m_aij(lp.colVector(_j).value(0)) 861 , m_strictLo(lp.lower(_k) > oldLo) 862 , m_strictUp(lp.upper(_k) < oldUp) 863 , m_newLo(lp.lower(_k)) 864 , m_newUp(lp.upper(_k)) 865 , m_oldLo(oldLo) 866 , m_oldUp(oldUp) 867 , m_Lo_j(lp.lower(_j)) 868 , m_Up_j(lp.upper(_j)) 869 , m_lhs(lp.lhs(_i)) 870 , m_rhs(lp.rhs(_i)) 871 , m_col(lp.colVector(_k)) 872 {} 873 /// copy constructor 874 DoubletonEquationPS(const DoubletonEquationPS& old) 875 : PostStep(old) 876 , m_j(old.m_j) 877 , m_k(old.m_k) 878 , m_i(old.m_i) 879 , m_maxSense(old.m_maxSense) 880 , m_jFixed(old.m_jFixed) 881 , m_jObj(old.m_jObj) 882 , m_kObj(old.m_kObj) 883 , m_aij(old.m_aij) 884 , m_strictLo(old.m_strictLo) 885 , m_strictUp(old.m_strictUp) 886 , m_newLo(old.m_newLo) 887 , m_newUp(old.m_newUp) 888 , m_oldLo(old.m_oldLo) 889 , m_oldUp(old.m_oldUp) 890 , m_Lo_j(old.m_Lo_j) 891 , m_Up_j(old.m_Up_j) 892 , m_lhs(old.m_lhs) 893 , m_rhs(old.m_rhs) 894 , m_col(old.m_col) 895 {} 896 /// assignment operator 897 DoubletonEquationPS& operator=(const DoubletonEquationPS& rhs) 898 { 899 if(this != &rhs) 900 { 901 PostStep::operator=(rhs); 902 m_col = rhs.m_col; 903 } 904 905 return *this; 906 } 907 /// clone function for polymorphism 908 inline virtual PostStep* clone() const 909 { 910 DoubletonEquationPS* DoubletonEquationPSptr = 0; 911 spx_alloc(DoubletonEquationPSptr); 912 return new(DoubletonEquationPSptr) DoubletonEquationPS(*this); 913 } 914 /// 915 virtual void execute(VectorBase<R>& x, VectorBase<R>& y, VectorBase<R>& s, VectorBase<R>& r, 916 DataArray<typename SPxSolverBase<R>::VarStatus>& cBasis, 917 DataArray<typename SPxSolverBase<R>::VarStatus>& rBasis, bool isOptimal) const; 918 }; 919 920 /**@brief Postsolves duplicate rows. 921 @ingroup Algo 922 */ 923 class DuplicateRowsPS : public PostStep 924 { 925 private: 926 const int m_i; 927 const R m_i_rowObj; 928 const int m_maxLhsIdx; 929 const int m_minRhsIdx; 930 const bool m_maxSense; 931 const bool m_isFirst; 932 const bool m_isLast; 933 const bool m_fixed; 934 const int m_nCols; 935 DSVectorBase<R> m_scale; 936 DSVectorBase<R> m_rowObj; 937 DataArray<int> m_rIdxLocalOld; 938 DataArray<int> m_perm; 939 DataArray<bool> m_isLhsEqualRhs; 940 941 public: 942 DuplicateRowsPS(const SPxLPBase<R>& lp, int _i, 943 int maxLhsIdx, int minRhsIdx, const DSVectorBase<R>& dupRows, 944 const Array<R> scale, const DataArray<int> perm, const DataArray<bool> isLhsEqualRhs, 945 bool isTheLast, bool isFixedRow, std::shared_ptr<Tolerances> tols, bool isFirst = false) 946 : PostStep("DuplicateRows", tols, lp.nRows(), lp.nCols()) 947 , m_i(_i) 948 , m_i_rowObj(lp.rowObj(_i)) 949 , m_maxLhsIdx((maxLhsIdx == -1) ? -1 : maxLhsIdx) 950 , m_minRhsIdx((minRhsIdx == -1) ? -1 : minRhsIdx) 951 , m_maxSense(lp.spxSense() == SPxLPBase<R>::MAXIMIZE) 952 , m_isFirst(isFirst) 953 , m_isLast(isTheLast) 954 , m_fixed(isFixedRow) 955 , m_nCols(lp.nCols()) 956 , m_scale(dupRows.size()) 957 , m_rowObj(dupRows.size()) 958 , m_rIdxLocalOld(dupRows.size()) 959 , m_perm(perm) 960 , m_isLhsEqualRhs(isLhsEqualRhs) 961 { 962 R rowScale = scale[_i]; 963 964 for(int k = 0; k < dupRows.size(); ++k) 965 { 966 m_scale.add(dupRows.index(k), rowScale / scale[dupRows.index(k)]); 967 m_rowObj.add(dupRows.index(k), lp.rowObj(dupRows.index(k))); 968 m_rIdxLocalOld[k] = dupRows.index(k); 969 } 970 } 971 /// copy constructor 972 DuplicateRowsPS(const DuplicateRowsPS& old) 973 : PostStep(old) 974 , m_i(old.m_i) 975 , m_i_rowObj(old.m_i_rowObj) 976 , m_maxLhsIdx(old.m_maxLhsIdx) 977 , m_minRhsIdx(old.m_minRhsIdx) 978 , m_maxSense(old.m_maxSense) 979 , m_isFirst(old.m_isFirst) 980 , m_isLast(old.m_isLast) 981 , m_fixed(old.m_fixed) 982 , m_nCols(old.m_nCols) 983 , m_scale(old.m_scale) 984 , m_rowObj(old.m_rowObj) 985 , m_rIdxLocalOld(old.m_rIdxLocalOld) 986 , m_perm(old.m_perm) 987 , m_isLhsEqualRhs(old.m_isLhsEqualRhs) 988 {} 989 /// assignment operator 990 DuplicateRowsPS& operator=(const DuplicateRowsPS& rhs) 991 { 992 if(this != &rhs) 993 { 994 PostStep::operator=(rhs); 995 m_scale = rhs.m_scale; 996 m_rowObj = rhs.m_rowObj; 997 m_rIdxLocalOld = rhs.m_rIdxLocalOld; 998 m_perm = rhs.m_perm; 999 m_isLhsEqualRhs = rhs.m_isLhsEqualRhs; 1000 } 1001 1002 return *this; 1003 } 1004 /// clone function for polymorphism 1005 inline virtual PostStep* clone() const 1006 { 1007 DuplicateRowsPS* DuplicateRowsPSptr = 0; 1008 spx_alloc(DuplicateRowsPSptr); 1009 return new(DuplicateRowsPSptr) DuplicateRowsPS(*this); 1010 } 1011 virtual void execute(VectorBase<R>& x, VectorBase<R>& y, VectorBase<R>& s, VectorBase<R>& r, 1012 DataArray<typename SPxSolverBase<R>::VarStatus>& cBasis, 1013 DataArray<typename SPxSolverBase<R>::VarStatus>& rBasis, bool isOptimal) const; 1014 }; 1015 1016 /**@brief Postsolves duplicate columns. 1017 @ingroup Algo 1018 */ 1019 class DuplicateColsPS : public PostStep 1020 { 1021 private: 1022 const int m_j; 1023 const int m_k; 1024 const R m_loJ; 1025 const R m_upJ; 1026 const R m_loK; 1027 const R m_upK; 1028 const R m_scale; 1029 const bool m_isFirst; 1030 const bool m_isLast; 1031 DataArray<int> m_perm; 1032 1033 public: 1034 DuplicateColsPS(const SPxLPBase<R>& lp, int _j, int _k, R scale, DataArray<int> perm, 1035 std::shared_ptr<Tolerances> tols, bool isFirst = false, bool isTheLast = false) 1036 : PostStep("DuplicateCols", tols, lp.nRows(), lp.nCols()) 1037 , m_j(_j) 1038 , m_k(_k) 1039 , m_loJ(lp.lower(_j)) 1040 , m_upJ(lp.upper(_j)) 1041 , m_loK(lp.lower(_k)) 1042 , m_upK(lp.upper(_k)) 1043 , m_scale(scale) 1044 , m_isFirst(isFirst) 1045 , m_isLast(isTheLast) 1046 , m_perm(perm) 1047 {} 1048 /// copy constructor 1049 DuplicateColsPS(const DuplicateColsPS& old) 1050 : PostStep(old) 1051 , m_j(old.m_j) 1052 , m_k(old.m_k) 1053 , m_loJ(old.m_loJ) 1054 , m_upJ(old.m_upJ) 1055 , m_loK(old.m_loK) 1056 , m_upK(old.m_upK) 1057 , m_scale(old.m_scale) 1058 , m_isFirst(old.m_isFirst) 1059 , m_isLast(old.m_isLast) 1060 , m_perm(old.m_perm) 1061 {} 1062 /// assignment operator 1063 DuplicateColsPS& operator=(const DuplicateColsPS& rhs) 1064 { 1065 if(this != &rhs) 1066 { 1067 PostStep::operator=(rhs); 1068 } 1069 1070 return *this; 1071 } 1072 /// clone function for polymorphism 1073 inline virtual PostStep* clone() const 1074 { 1075 DuplicateColsPS* DuplicateColsPSptr = 0; 1076 spx_alloc(DuplicateColsPSptr); 1077 return new(DuplicateColsPSptr) DuplicateColsPS(*this); 1078 } 1079 virtual void execute(VectorBase<R>& x, VectorBase<R>& y, VectorBase<R>& s, VectorBase<R>& r, 1080 DataArray<typename SPxSolverBase<R>::VarStatus>& cBasis, 1081 DataArray<typename SPxSolverBase<R>::VarStatus>& rBasis, bool isOptimal) const; 1082 }; 1083 1084 /**@brief Postsolves aggregation. 1085 @ingroup Algo 1086 */ 1087 class AggregationPS : public PostStep 1088 { 1089 private: 1090 const int m_j; 1091 const int m_i; 1092 const int m_old_j; 1093 const int m_old_i; 1094 const R m_upper; 1095 const R m_lower; 1096 const R m_obj; 1097 const R m_oldupper; 1098 const R m_oldlower; 1099 const R m_rhs; 1100 DSVectorBase<R> m_row; 1101 DSVectorBase<R> m_col; 1102 1103 public: 1104 /// 1105 AggregationPS(const SPxLPBase<R>& lp, int _i, int _j, R rhs, R oldupper, R oldlower, 1106 std::shared_ptr<Tolerances> tols) 1107 : PostStep("Aggregation", tols, lp.nRows(), lp.nCols()) 1108 , m_j(_j) 1109 , m_i(_i) 1110 , m_old_j(lp.nCols() - 1) 1111 , m_old_i(lp.nRows() - 1) 1112 , m_upper(lp.upper(_j)) 1113 , m_lower(lp.lower(_j)) 1114 , m_obj(lp.spxSense() == SPxLPBase<R>::MINIMIZE ? lp.obj(_j) : -lp.obj(_j)) 1115 , m_oldupper(oldupper) 1116 , m_oldlower(oldlower) 1117 , m_rhs(rhs) 1118 , m_row(lp.rowVector(_i)) 1119 , m_col(lp.colVector(_j)) 1120 { 1121 assert(m_row[m_j] != 0.0); 1122 } 1123 /// copy constructor 1124 AggregationPS(const AggregationPS& old) 1125 : PostStep(old) 1126 , m_j(old.m_j) 1127 , m_i(old.m_i) 1128 , m_old_j(old.m_old_j) 1129 , m_old_i(old.m_old_i) 1130 , m_upper(old.m_upper) 1131 , m_lower(old.m_lower) 1132 , m_obj(old.m_obj) 1133 , m_oldupper(old.m_oldupper) 1134 , m_oldlower(old.m_oldlower) 1135 , m_rhs(old.m_rhs) 1136 , m_row(old.m_row) 1137 , m_col(old.m_col) 1138 {} 1139 /// assignment operator 1140 AggregationPS& operator=(const AggregationPS& rhs) 1141 { 1142 if(this != &rhs) 1143 { 1144 PostStep::operator=(rhs); 1145 m_row = rhs.m_row; 1146 m_col = rhs.m_col; 1147 } 1148 1149 return *this; 1150 } 1151 /// clone function for polymorphism 1152 inline virtual PostStep* clone() const 1153 { 1154 AggregationPS* AggregationPSptr = 0; 1155 spx_alloc(AggregationPSptr); 1156 return new(AggregationPSptr) AggregationPS(*this); 1157 } 1158 /// 1159 virtual void execute(VectorBase<R>& x, VectorBase<R>& y, VectorBase<R>& s, VectorBase<R>& r, 1160 DataArray<typename SPxSolverBase<R>::VarStatus>& cBasis, 1161 DataArray<typename SPxSolverBase<R>::VarStatus>& rBasis, bool isOptimal) const; 1162 }; 1163 1164 /**@brief Postsolves multi aggregation. 1165 @ingroup Algo 1166 */ 1167 class MultiAggregationPS : public PostStep 1168 { 1169 private: 1170 const int m_j; 1171 const int m_i; 1172 const int m_old_j; 1173 const int m_old_i; 1174 const R m_upper; 1175 const R m_lower; 1176 const R m_obj; 1177 const R m_const; 1178 const bool m_onLhs; 1179 const bool m_eqCons; 1180 DSVectorBase<R> m_row; 1181 DSVectorBase<R> m_col; 1182 1183 public: 1184 /// 1185 MultiAggregationPS(const SPxLPBase<R>& lp, SPxMainSM& simplifier, int _i, int _j, 1186 R constant, std::shared_ptr<Tolerances> tols) 1187 : PostStep("MultiAggregation", tols, lp.nRows(), lp.nCols()) 1188 , m_j(_j) 1189 , m_i(_i) 1190 , m_old_j(lp.nCols() - 1) 1191 , m_old_i(lp.nRows() - 1) 1192 , m_upper(lp.upper(_j)) 1193 , m_lower(lp.lower(_j)) 1194 , m_obj(lp.spxSense() == SPxLPBase<R>::MINIMIZE ? lp.obj(_j) : -lp.obj(_j)) 1195 , m_const(constant) 1196 , m_onLhs(EQ(constant, lp.lhs(_i), this->epsilon())) 1197 , m_eqCons(EQ(lp.lhs(_i), lp.rhs(_i), this->epsilon())) 1198 , m_row(lp.rowVector(_i)) 1199 , m_col(lp.colVector(_j)) 1200 { 1201 assert(m_row[m_j] != 0.0); 1202 simplifier.addObjoffset(m_obj * m_const / m_row[m_j]); 1203 } 1204 /// copy constructor 1205 MultiAggregationPS(const MultiAggregationPS& old) 1206 : PostStep(old) 1207 , m_j(old.m_j) 1208 , m_i(old.m_i) 1209 , m_old_j(old.m_old_j) 1210 , m_old_i(old.m_old_i) 1211 , m_upper(old.m_upper) 1212 , m_lower(old.m_lower) 1213 , m_obj(old.m_obj) 1214 , m_const(old.m_const) 1215 , m_onLhs(old.m_onLhs) 1216 , m_eqCons(old.m_eqCons) 1217 , m_row(old.m_row) 1218 , m_col(old.m_col) 1219 {} 1220 /// assignment operator 1221 MultiAggregationPS& operator=(const MultiAggregationPS& rhs) 1222 { 1223 if(this != &rhs) 1224 { 1225 PostStep::operator=(rhs); 1226 m_row = rhs.m_row; 1227 m_col = rhs.m_col; 1228 } 1229 1230 return *this; 1231 } 1232 /// clone function for polymorphism 1233 inline virtual PostStep* clone() const 1234 { 1235 MultiAggregationPS* MultiAggregationPSptr = 0; 1236 spx_alloc(MultiAggregationPSptr); 1237 return new(MultiAggregationPSptr) MultiAggregationPS(*this); 1238 } 1239 /// 1240 virtual void execute(VectorBase<R>& x, VectorBase<R>& y, VectorBase<R>& s, VectorBase<R>& r, 1241 DataArray<typename SPxSolverBase<R>::VarStatus>& cBasis, 1242 DataArray<typename SPxSolverBase<R>::VarStatus>& rBasis, bool isOptimal) const; 1243 }; 1244 1245 /**@brief Postsolves variable bound tightening from pseudo objective propagation. 1246 @ingroup Algo 1247 */ 1248 class TightenBoundsPS : public PostStep 1249 { 1250 private: 1251 const int m_j; 1252 const R m_origupper; 1253 const R m_origlower; 1254 1255 public: 1256 /// 1257 TightenBoundsPS(const SPxLPBase<R>& lp, int j, R origupper, R origlower, 1258 std::shared_ptr<Tolerances> tols) 1259 : PostStep("TightenBounds", tols, lp.nRows(), lp.nCols()) 1260 , m_j(j) 1261 , m_origupper(origupper) 1262 , m_origlower(origlower) 1263 { 1264 } 1265 /// copy constructor 1266 TightenBoundsPS(const TightenBoundsPS& old) 1267 : PostStep(old) 1268 , m_j(old.m_j) 1269 , m_origupper(old.m_origupper) 1270 , m_origlower(old.m_origlower) 1271 {} 1272 /// assignment operator 1273 TightenBoundsPS& operator=(const TightenBoundsPS& rhs) 1274 { 1275 return *this; 1276 } 1277 /// clone function for polymorphism 1278 inline virtual PostStep* clone() const 1279 { 1280 TightenBoundsPS* TightenBoundsPSptr = 0; 1281 spx_alloc(TightenBoundsPSptr); 1282 return new(TightenBoundsPSptr) TightenBoundsPS(*this); 1283 } 1284 /// 1285 virtual void execute(VectorBase<R>& x, VectorBase<R>& y, VectorBase<R>& s, VectorBase<R>& r, 1286 DataArray<typename SPxSolverBase<R>::VarStatus>& cBasis, 1287 DataArray<typename SPxSolverBase<R>::VarStatus>& rBasis, bool isOptimal) const; 1288 }; 1289 // friends 1290 friend class FreeConstraintPS; 1291 friend class EmptyConstraintPS; 1292 friend class RowSingletonPS; 1293 friend class ForceConstraintPS; 1294 friend class FixVariablePS; 1295 friend class FixBoundsPS; 1296 friend class FreeZeroObjVariablePS; 1297 friend class ZeroObjColSingletonPS; 1298 friend class FreeColSingletonPS; 1299 friend class DoubletonEquationPS; 1300 friend class DuplicateRowsPS; 1301 friend class DuplicateColsPS; 1302 friend class AggregationPS; 1303 1304 private: 1305 //------------------------------------ 1306 ///@name Types 1307 ///@{ 1308 /// Different simplification steps. 1309 enum SimpleStep 1310 { 1311 EMPTY_ROW = 0, 1312 FREE_ROW = 1, 1313 SINGLETON_ROW = 2, 1314 FORCE_ROW = 3, 1315 EMPTY_COL = 4, 1316 FIX_COL = 5, 1317 FREE_ZOBJ_COL = 6, 1318 ZOBJ_SINGLETON_COL = 7, 1319 DOUBLETON_ROW = 8, 1320 FREE_SINGLETON_COL = 9, 1321 DOMINATED_COL = 10, 1322 WEAKLY_DOMINATED_COL = 11, 1323 DUPLICATE_ROW = 12, 1324 FIX_DUPLICATE_COL = 13, 1325 SUB_DUPLICATE_COL = 14, 1326 AGGREGATION = 15, 1327 MULTI_AGG = 16 1328 }; 1329 ///@} 1330 1331 //------------------------------------ 1332 ///@name Data 1333 ///@{ 1334 /// 1335 VectorBase<R> m_prim; ///< unsimplified primal solution VectorBase<R>. 1336 VectorBase<R> m_slack; ///< unsimplified slack VectorBase<R>. 1337 VectorBase<R> m_dual; ///< unsimplified dual solution VectorBase<R>. 1338 VectorBase<R> m_redCost; ///< unsimplified reduced cost VectorBase<R>. 1339 DataArray<typename SPxSolverBase<R>::VarStatus> m_cBasisStat; ///< basis status of columns. 1340 DataArray<typename SPxSolverBase<R>::VarStatus> m_rBasisStat; ///< basis status of rows. 1341 DataArray<int> m_cIdx; ///< column index VectorBase<R> in original LP. 1342 DataArray<int> m_rIdx; ///< row index VectorBase<R> in original LP. 1343 Array<std::shared_ptr<PostStep>>m_hist; ///< VectorBase<R> of presolve history. 1344 Array<DSVectorBase<R>> 1345 m_classSetRows; ///< stores parallel classes with non-zero colum entry 1346 Array<DSVectorBase<R>> 1347 m_classSetCols; ///< stores parallel classes with non-zero row entry 1348 Array<DSVectorBase<R>> 1349 m_dupRows; ///< arrange duplicate rows using bucket sort w.r.t. their pClass values 1350 Array<DSVectorBase<R>> 1351 m_dupCols; ///< arrange duplicate columns w.r.t. their pClass values 1352 bool m_postsolved; ///< status of postsolving. 1353 DataArray<int> m_stat; ///< preprocessing history. 1354 typename SPxLPBase<R>::SPxSense m_thesense; ///< optimization sense. 1355 bool m_keepbounds; ///< keep some bounds (for boundflipping) 1356 int m_addedcols; ///< columns added by handleRowObjectives() 1357 typename SPxSimplifier<R>::Result m_result; ///< result of the simplification. 1358 R m_cutoffbound; ///< the cutoff bound that is found by heuristics 1359 R m_pseudoobj; ///< the pseudo objective function value 1360 ///@} 1361 1362 private: 1363 //------------------------------------ 1364 ///@name Private helpers 1365 ///@{ 1366 /// handle row objectives 1367 void handleRowObjectives(SPxLPBase<R>& lp); 1368 1369 /// handles extreme values by setting them to zero or R(infinity). 1370 void handleExtremes(SPxLPBase<R>& lp); 1371 1372 /// computes the minimum and maximum residual activity for a given row and column. If colNumber is set to -1, then 1373 // the activity of the row is returned. 1374 void computeMinMaxResidualActivity(SPxLPBase<R>& lp, int rowNumber, int colNumber, R& minAct, 1375 R& maxAct); 1376 1377 /// calculate min/max value for the multi aggregated variables 1378 void computeMinMaxValues(SPxLPBase<R>& lp, R side, R val, R minRes, R maxRes, R& minVal, R& maxVal); 1379 1380 /// tries to find good lower bound solutions by applying some trivial heuristics 1381 void trivialHeuristic(SPxLPBase<R>& lp); 1382 1383 /// checks a solution for feasibility 1384 bool checkSolution(SPxLPBase<R>& lp, VectorBase<R> sol); 1385 1386 /// tightens variable bounds by propagating the pseudo objective function value. 1387 void propagatePseudoobj(SPxLPBase<R>& lp); 1388 1389 /// removed empty rows and empty columns. 1390 typename SPxSimplifier<R>::Result removeEmpty(SPxLPBase<R>& lp); 1391 1392 /// remove row singletons. 1393 typename SPxSimplifier<R>::Result removeRowSingleton(SPxLPBase<R>& lp, const SVectorBase<R>& row, 1394 int& i); 1395 1396 /// aggregate two variables that appear in an equation. 1397 typename SPxSimplifier<R>::Result aggregateVars(SPxLPBase<R>& lp, const SVectorBase<R>& row, 1398 int& i); 1399 1400 /// performs simplification steps on the rows of the LP. 1401 typename SPxSimplifier<R>::Result simplifyRows(SPxLPBase<R>& lp, bool& again); 1402 1403 /// performs simplification steps on the columns of the LP. 1404 typename SPxSimplifier<R>::Result simplifyCols(SPxLPBase<R>& lp, bool& again); 1405 1406 /// performs simplification steps on the LP based on dual concepts. 1407 typename SPxSimplifier<R>::Result simplifyDual(SPxLPBase<R>& lp, bool& again); 1408 1409 /// performs multi-aggregations of variable based upon constraint activitu. 1410 typename SPxSimplifier<R>::Result multiaggregation(SPxLPBase<R>& lp, bool& again); 1411 1412 /// removes duplicate rows. 1413 typename SPxSimplifier<R>::Result duplicateRows(SPxLPBase<R>& lp, bool& again); 1414 1415 /// removes duplicate columns 1416 typename SPxSimplifier<R>::Result duplicateCols(SPxLPBase<R>& lp, bool& again); 1417 1418 /// handles the fixing of a variable. correctIdx is true iff the index mapping has to be updated. 1419 void fixColumn(SPxLPBase<R>& lp, int i, bool correctIdx = true); 1420 1421 /// removes a row in the LP. 1422 void removeRow(SPxLPBase<R>& lp, int i) 1423 { 1424 m_rIdx[i] = m_rIdx[lp.nRows() - 1]; 1425 lp.removeRow(i); 1426 } 1427 /// removes a column in the LP. 1428 void removeCol(SPxLPBase<R>& lp, int j) 1429 { 1430 m_cIdx[j] = m_cIdx[lp.nCols() - 1]; 1431 lp.removeCol(j); 1432 } 1433 /// returns for a given row index of the (reduced) LP the corresponding row index in the unsimplified LP. 1434 int rIdx(int i) const 1435 { 1436 return m_rIdx[i]; 1437 } 1438 /// returns for a given column index of the (reduced) LP the corresponding column index in the unsimplified LP. 1439 int cIdx(int j) const 1440 { 1441 return m_cIdx[j]; 1442 } 1443 ///@} 1444 1445 protected: 1446 1447 /// 1448 R epsZero() const 1449 { 1450 return this->tolerances()->epsilon(); 1451 } 1452 /// 1453 R feastol() const 1454 { 1455 return this->tolerances()->floatingPointFeastol(); 1456 } 1457 /// 1458 R opttol() const 1459 { 1460 return this->tolerances()->floatingPointOpttol(); 1461 } 1462 1463 public: 1464 1465 //------------------------------------ 1466 ///@name Constructors / destructors 1467 ///@{ 1468 /// default constructor. 1469 SPxMainSM(Timer::TYPE ttype = Timer::USER_TIME) 1470 : SPxSimplifier<R>("MainSM", ttype) 1471 , m_postsolved(0) 1472 , m_stat(16) 1473 , m_thesense(SPxLPBase<R>::MAXIMIZE) 1474 , m_keepbounds(false) 1475 , m_addedcols(0) 1476 , m_result(this->OKAY) 1477 , m_cutoffbound(R(-infinity)) 1478 , m_pseudoobj(R(-infinity)) 1479 {} 1480 /// copy constructor. 1481 SPxMainSM(const SPxMainSM& old) 1482 : SPxSimplifier<R>(old) 1483 , m_prim(old.m_prim) 1484 , m_slack(old.m_slack) 1485 , m_dual(old.m_dual) 1486 , m_redCost(old.m_redCost) 1487 , m_cBasisStat(old.m_cBasisStat) 1488 , m_rBasisStat(old.m_rBasisStat) 1489 , m_cIdx(old.m_cIdx) 1490 , m_rIdx(old.m_rIdx) 1491 , m_hist(old.m_hist) 1492 , m_postsolved(old.m_postsolved) 1493 , m_stat(old.m_stat) 1494 , m_thesense(old.m_thesense) 1495 , m_keepbounds(old.m_keepbounds) 1496 , m_addedcols(old.m_addedcols) 1497 , m_result(old.m_result) 1498 , m_cutoffbound(old.m_cutoffbound) 1499 , m_pseudoobj(old.m_pseudoobj) 1500 { 1501 ; 1502 } 1503 /// assignment operator 1504 SPxMainSM& operator=(const SPxMainSM& rhs) 1505 { 1506 if(this != &rhs) 1507 { 1508 SPxSimplifier<R>::operator=(rhs); 1509 m_prim = rhs.m_prim; 1510 m_slack = rhs.m_slack; 1511 m_dual = rhs.m_dual; 1512 m_redCost = rhs.m_redCost; 1513 m_cBasisStat = rhs.m_cBasisStat; 1514 m_rBasisStat = rhs.m_rBasisStat; 1515 m_cIdx = rhs.m_cIdx; 1516 m_rIdx = rhs.m_rIdx; 1517 m_postsolved = rhs.m_postsolved; 1518 m_stat = rhs.m_stat; 1519 m_thesense = rhs.m_thesense; 1520 m_keepbounds = rhs.m_keepbounds; 1521 m_addedcols = rhs.m_addedcols; 1522 m_result = rhs.m_result; 1523 m_cutoffbound = rhs.m_cutoffbound; 1524 m_pseudoobj = rhs.m_pseudoobj; 1525 m_hist = rhs.m_hist; 1526 } 1527 1528 1529 return *this; 1530 } 1531 /// destructor. 1532 virtual ~SPxMainSM() 1533 { 1534 ; 1535 } 1536 /// clone function for polymorphism 1537 inline virtual SPxSimplifier<R>* clone() const 1538 { 1539 return new SPxMainSM(*this); 1540 } 1541 ///@} 1542 1543 //------------------------------------ 1544 //**@name LP simplification */ 1545 ///@{ 1546 /// simplify SPxLPBase<R> \p lp. 1547 virtual typename SPxSimplifier<R>::Result simplify(SPxLPBase<R>& lp, Real remainingTime, 1548 bool keepbounds = false, uint32_t seed = 0); 1549 1550 /// reconstructs an optimal solution for the unsimplified LP. 1551 virtual void unsimplify(const VectorBase<R>& x, const VectorBase<R>& y, const VectorBase<R>& s, 1552 const VectorBase<R>& r, 1553 const typename SPxSolverBase<R>::VarStatus rows[], 1554 const typename SPxSolverBase<R>::VarStatus cols[], bool isOptimal = true); 1555 1556 /// returns result status of the simplification 1557 virtual typename SPxSimplifier<R>::Result result() const 1558 { 1559 return m_result; 1560 } 1561 1562 /// specifies whether an optimal solution has already been unsimplified. 1563 virtual bool isUnsimplified() const 1564 { 1565 return m_postsolved; 1566 } 1567 /// returns a reference to the unsimplified primal solution. 1568 virtual const VectorBase<R>& unsimplifiedPrimal() 1569 { 1570 assert(m_postsolved); 1571 return m_prim; 1572 } 1573 /// returns a reference to the unsimplified dual solution. 1574 virtual const VectorBase<R>& unsimplifiedDual() 1575 { 1576 assert(m_postsolved); 1577 return m_dual; 1578 } 1579 /// returns a reference to the unsimplified slack values. 1580 virtual const VectorBase<R>& unsimplifiedSlacks() 1581 { 1582 assert(m_postsolved); 1583 return m_slack; 1584 } 1585 /// returns a reference to the unsimplified reduced costs. 1586 virtual const VectorBase<R>& unsimplifiedRedCost() 1587 { 1588 assert(m_postsolved); 1589 return m_redCost; 1590 } 1591 /// gets basis status for a single row. 1592 virtual typename SPxSolverBase<R>::VarStatus getBasisRowStatus(int i) const 1593 { 1594 assert(m_postsolved); 1595 return m_rBasisStat[i]; 1596 } 1597 /// gets basis status for a single column. 1598 virtual typename SPxSolverBase<R>::VarStatus getBasisColStatus(int j) const 1599 { 1600 assert(m_postsolved); 1601 return m_cBasisStat[j]; 1602 } 1603 /// get optimal basis. 1604 virtual void getBasis(typename SPxSolverBase<R>::VarStatus rows[], 1605 typename SPxSolverBase<R>::VarStatus cols[], const int rowsSize = -1, const int colsSize = -1) const 1606 { 1607 assert(m_postsolved); 1608 assert(rowsSize < 0 || rowsSize >= m_rBasisStat.size()); 1609 assert(colsSize < 0 || colsSize >= m_cBasisStat.size()); 1610 1611 for(int i = 0; i < m_rBasisStat.size(); ++i) 1612 rows[i] = m_rBasisStat[i]; 1613 1614 for(int j = 0; j < m_cBasisStat.size(); ++j) 1615 cols[j] = m_cBasisStat[j]; 1616 } 1617 ///@} 1618 1619 private: 1620 //------------------------------------ 1621 //**@name Types */ 1622 ///@{ 1623 /// comparator for class SVectorBase<R>::Element: compare nonzeros according to value 1624 struct ElementCompare 1625 { 1626 public: 1627 R epsiloncompare; 1628 1629 ElementCompare(R eps) 1630 { 1631 this->epsiloncompare = eps; 1632 } 1633 1634 int operator()(const typename SVectorBase<R>::Element& e1, 1635 const typename SVectorBase<R>::Element& e2) const 1636 { 1637 if(EQ(e1.val, e2.val, this->epsiloncompare)) 1638 return 0; 1639 1640 if(e1.val < e2.val) 1641 return -1; 1642 else // (e1.val > e2.val) 1643 return 1; 1644 } 1645 }; 1646 /// comparator for class SVectorBase<R>::Element: compare nonzeros according to index 1647 struct IdxCompare 1648 { 1649 public: 1650 IdxCompare() {} 1651 1652 int operator()(const typename SVectorBase<R>::Element& e1, 1653 const typename SVectorBase<R>::Element& e2) const 1654 { 1655 if(EQ(e1.idx, e2.idx)) 1656 return 0; 1657 1658 if(e1.idx < e2.idx) 1659 return -1; 1660 else // (e1.idx > e2.idx) 1661 return 1; 1662 } 1663 }; 1664 ///@} 1665 }; 1666 1667 } // namespace soplex 1668 1669 // For including general templated functions 1670 #include "spxmainsm.hpp" 1671 1672 #endif // _SPXMAINSM_H_ 1673