SoPlex Documentation
Loading...
Searching...
No Matches
spxmainsm.h
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the class library */
4/* SoPlex --- the Sequential object-oriented simPlex. */
5/* */
6/* Copyright (c) 1996-2024 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"
36#include "soplex/array.h"
37#include "soplex/exceptions.h"
38
39namespace 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*/
70template <class R>
71class SPxMainSM : public SPxSimplifier<R>
72{
73private:
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 */
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 {
112 }
113 /// assignment operator
114 PostStep& operator=(const PostStep& /*rhs*/)
115 {
116 return *this;
117 }
118 /// destructor.
119 virtual ~PostStep()
120 {
121 m_name = nullptr;
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
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
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 ///
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 */
203 {
204 private:
205 int m_i;
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
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
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 ///
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 */
255 {
256 private:
257 int m_i;
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
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
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 ///
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 */
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;
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
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)
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
363 {
364 if(this != &rhs)
365 {
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 ///
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 */
387 {
388 private:
389 const int m_i;
390 const int m_old_i;
391 const R m_lRhs;
396 const bool m_lhsFixed;
397 const bool m_maxSense;
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
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)
446 , m_lhs(old.m_lhs)
447 , m_rhs(old.m_rhs)
448 , m_rowobj(old.m_rowobj)
449 {}
450 /// assignment operator
452 {
453 if(this != &rhs)
454 {
456 m_row = rhs.m_row;
457 m_objs = rhs.m_objs;
458 m_fixed = rhs.m_fixed;
459 m_cols = rhs.m_cols;
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 ///
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?
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
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)
518 , m_col(old.m_col)
519 {}
520 /// assignment operator
522 {
523 if(this != &rhs)
524 {
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 ///
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;
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()))
559 else if(EQrel(val, lp.lower(j), this->feastol()))
561 else if(EQrel(val, lp.upper(j), this->feastol()))
563 else if(lp.lower(j) <= R(-infinity) && lp.upper(j) >= R(infinity))
565 else
566 {
567 throw SPxInternalCodeException("XMAISM14 This should never happen.");
568 }
569 }
570 /// copy constructor
572 : PostStep(old)
573 , m_j(old.m_j)
574 , m_status(old.m_status)
575 {}
576 /// assignment operator
578 {
579 if(this != &rhs)
580 {
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 = nullptr;
591 spx_alloc(FixBoundsPSptr);
592 return new(FixBoundsPSptr) FixBoundsPS(*this);
593 }
594 ///
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 */
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;
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
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
661 {
662 if(this != &rhs)
663 {
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 = nullptr;
677 spx_alloc(FreeZeroObjVariablePSptr);
678 return new(FreeZeroObjVariablePSptr) FreeZeroObjVariablePS(*this);
679 }
680 ///
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 */
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;
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
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
729 {
730 if(this != &rhs)
731 {
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 = nullptr;
742 spx_alloc(ZeroObjColSingletonPSptr);
743 return new(ZeroObjColSingletonPSptr) ZeroObjColSingletonPS(*this);
744 }
745 ///
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 */
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;
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
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
800 {
801 if(this != &rhs)
802 {
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 = nullptr;
813 spx_alloc(FreeColSingletonPSptr);
814 return new(FreeColSingletonPSptr) FreeColSingletonPS(*this);
815 }
816 ///
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 */
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;
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
875 : PostStep(old)
876 , m_j(old.m_j)
877 , m_k(old.m_k)
878 , m_i(old.m_i)
880 , m_jFixed(old.m_jFixed)
881 , m_jObj(old.m_jObj)
882 , m_kObj(old.m_kObj)
883 , m_aij(old.m_aij)
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
898 {
899 if(this != &rhs)
900 {
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 = nullptr;
911 spx_alloc(DoubletonEquationPSptr);
912 return new(DoubletonEquationPSptr) DoubletonEquationPS(*this);
913 }
914 ///
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 */
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;
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
973 : PostStep(old)
974 , m_i(old.m_i)
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)
986 , m_perm(old.m_perm)
988 {}
989 /// assignment operator
991 {
992 if(this != &rhs)
993 {
995 m_scale = rhs.m_scale;
996 m_rowObj = rhs.m_rowObj;
998 m_perm = rhs.m_perm;
1000 }
1001
1002 return *this;
1003 }
1004 /// clone function for polymorphism
1005 inline virtual PostStep* clone() const
1006 {
1007 DuplicateRowsPS* DuplicateRowsPSptr = nullptr;
1008 spx_alloc(DuplicateRowsPSptr);
1009 return new(DuplicateRowsPSptr) DuplicateRowsPS(*this);
1010 }
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 */
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;
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
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
1064 {
1065 if(this != &rhs)
1066 {
1068 }
1069
1070 return *this;
1071 }
1072 /// clone function for polymorphism
1073 inline virtual PostStep* clone() const
1074 {
1075 DuplicateColsPS* DuplicateColsPSptr = nullptr;
1076 spx_alloc(DuplicateColsPSptr);
1077 return new(DuplicateColsPSptr) DuplicateColsPS(*this);
1078 }
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 */
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;
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
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
1141 {
1142 if(this != &rhs)
1143 {
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 = nullptr;
1155 spx_alloc(AggregationPSptr);
1156 return new(AggregationPSptr) AggregationPS(*this);
1157 }
1158 ///
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 */
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;
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
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
1222 {
1223 if(this != &rhs)
1224 {
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 = nullptr;
1236 spx_alloc(MultiAggregationPSptr);
1237 return new(MultiAggregationPSptr) MultiAggregationPS(*this);
1238 }
1239 ///
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 */
1249 {
1250 private:
1251 const int m_j;
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
1267 : PostStep(old)
1268 , m_j(old.m_j)
1271 {}
1272 /// assignment operator
1274 {
1275 return *this;
1276 }
1277 /// clone function for polymorphism
1278 inline virtual PostStep* clone() const
1279 {
1280 TightenBoundsPS* TightenBoundsPSptr = nullptr;
1281 spx_alloc(TightenBoundsPSptr);
1282 return new(TightenBoundsPSptr) TightenBoundsPS(*this);
1283 }
1284 ///
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;
1300 friend class DuplicateRowsPS;
1301 friend class DuplicateColsPS;
1302 friend class AggregationPS;
1303
1304private:
1305 //------------------------------------
1306 ///@name Types
1307 ///@{
1308 /// Different simplification steps.
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>.
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.
1345 m_classSetRows; ///< stores parallel classes with non-zero colum entry
1347 m_classSetCols; ///< stores parallel classes with non-zero row entry
1349 m_dupRows; ///< arrange duplicate rows using bucket sort w.r.t. their pClass values
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
1362private:
1363 //------------------------------------
1364 ///@name Private helpers
1365 ///@{
1366 /// handle row objectives
1368
1369 /// handles extreme values by setting them to zero or R(infinity).
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
1382
1383 /// checks a solution for feasibility
1385
1386 /// tightens variable bounds by propagating the pseudo objective function value.
1388
1389 /// removed empty rows and empty columns.
1391
1392 /// remove row singletons.
1394 int& i);
1395
1396 /// aggregate two variables that appear in an equation.
1398 int& i);
1399
1400 /// performs simplification steps on the rows of the LP.
1402
1403 /// performs simplification steps on the columns of the LP.
1405
1406 /// performs simplification steps on the LP based on dual concepts.
1408
1409 /// performs multi-aggregations of variable based upon constraint activitu.
1411
1412 /// removes duplicate rows.
1414
1415 /// removes duplicate columns
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
1445protected:
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
1463public:
1464
1465 //------------------------------------
1466 ///@name Constructors / destructors
1467 ///@{
1468 /// default constructor.
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.
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)
1489 , m_cIdx(old.m_cIdx)
1490 , m_rIdx(old.m_rIdx)
1491 , m_hist(old.m_hist)
1493 , m_stat(old.m_stat)
1494 , m_thesense(old.m_thesense)
1497 , m_result(old.m_result)
1500 {
1501 ;
1502 }
1503 /// assignment operator
1505 {
1506 if(this != &rhs)
1507 {
1509 m_prim = rhs.m_prim;
1510 m_slack = rhs.m_slack;
1511 m_dual = rhs.m_dual;
1512 m_redCost = rhs.m_redCost;
1515 m_cIdx = rhs.m_cIdx;
1516 m_rIdx = rhs.m_rIdx;
1518 m_stat = rhs.m_stat;
1519 m_thesense = rhs.m_thesense;
1522 m_result = rhs.m_result;
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.
1569 {
1570 assert(m_postsolved);
1571 return m_prim;
1572 }
1573 /// returns a reference to the unsimplified dual solution.
1575 {
1576 assert(m_postsolved);
1577 return m_dual;
1578 }
1579 /// returns a reference to the unsimplified slack values.
1581 {
1582 assert(m_postsolved);
1583 return m_slack;
1584 }
1585 /// returns a reference to the unsimplified reduced costs.
1587 {
1588 assert(m_postsolved);
1589 return m_redCost;
1590 }
1591 /// gets basis status for a single row.
1593 {
1594 assert(m_postsolved);
1595 return m_rBasisStat[i];
1596 }
1597 /// gets basis status for a single column.
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
1619private:
1620 //------------------------------------
1621 //**@name Types */
1622 ///@{
1623 /// comparator for class SVectorBase<R>::Element: compare nonzeros according to value
1625 {
1626 public:
1628
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
1648 {
1649 public:
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_
Save arrays of arbitrary types.
Safe arrays of arbitrary types.
Definition array.h:73
Dynamic sparse vectors.
Safe arrays of data objects.
Definition dataarray.h:75
Sparse vector nonzero element.
Definition svectorbase.h:47
int idx
Index of nonzero element.
Definition svectorbase.h:51
R val
Value of nonzero element.
Definition svectorbase.h:50
Exception class for things that should NEVER happen.
Definition exceptions.h:119
Saving LPs in a form suitable for SoPlex.
Definition spxscaler.h:46
const VectorBase< R > & rhs() const
Returns right hand side vector.
Definition spxlpbase.h:260
SPxSense spxSense() const
Returns the optimization sense.
Definition spxlpbase.h:554
const VectorBase< R > & lhs() const
Returns left hand side vector.
Definition spxlpbase.h:294
SPxSense
Optimization sense.
Definition spxlpbase.h:125
virtual void removeRow(int i)
Removes i 'th row.
Definition spxlpbase.h:972
virtual void removeCol(int i)
Removes i 'th column.
Definition spxlpbase.h:1072
const VectorBase< R > & lower() const
Returns (internal and possibly scaled) lower bound vector.
Definition spxlpbase.h:527
R obj(int i) const
Returns objective value of column i.
Definition spxlpbase.h:446
int nCols() const
Returns number of columns in LP.
Definition spxlpbase.h:197
const SVectorBase< R > & rowVector(int i) const
Gets row vector of row i.
Definition spxlpbase.h:245
R rowObj(int i) const
Definition spxlpbase.h:321
const VectorBase< R > & upper() const
Returns upper bound vector.
Definition spxlpbase.h:500
int nRows() const
Returns number of rows in LP.
Definition spxlpbase.h:191
const SVectorBase< R > & colVector(int i) const
Returns column vector of column i.
Definition spxlpbase.h:416
Postsolves aggregation.
Definition spxmainsm.h:1088
AggregationPS & operator=(const AggregationPS &rhs)
assignment operator
Definition spxmainsm.h:1140
virtual void execute(VectorBase< R > &x, VectorBase< R > &y, VectorBase< R > &s, VectorBase< R > &r, DataArray< typename SPxSolverBase< R >::VarStatus > &cBasis, DataArray< typename SPxSolverBase< R >::VarStatus > &rBasis, bool isOptimal) const
AggregationPS(const AggregationPS &old)
copy constructor
Definition spxmainsm.h:1124
AggregationPS(const SPxLPBase< R > &lp, int _i, int _j, R rhs, R oldupper, R oldlower, std::shared_ptr< Tolerances > tols)
Definition spxmainsm.h:1105
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:1152
Postsolves doubleton equations combined with a column singleton.
Definition spxmainsm.h:826
DoubletonEquationPS(const DoubletonEquationPS &old)
copy constructor
Definition spxmainsm.h:874
DoubletonEquationPS & operator=(const DoubletonEquationPS &rhs)
assignment operator
Definition spxmainsm.h:897
virtual void execute(VectorBase< R > &x, VectorBase< R > &y, VectorBase< R > &s, VectorBase< R > &r, DataArray< typename SPxSolverBase< R >::VarStatus > &cBasis, DataArray< typename SPxSolverBase< R >::VarStatus > &rBasis, bool isOptimal) const
DoubletonEquationPS(const SPxLPBase< R > &lp, int _j, int _k, int _i, R oldLo, R oldUp, std::shared_ptr< Tolerances > tols)
Definition spxmainsm.h:850
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:908
Postsolves duplicate columns.
Definition spxmainsm.h:1020
DuplicateColsPS(const DuplicateColsPS &old)
copy constructor
Definition spxmainsm.h:1049
DuplicateColsPS(const SPxLPBase< R > &lp, int _j, int _k, R scale, DataArray< int > perm, std::shared_ptr< Tolerances > tols, bool isFirst=false, bool isTheLast=false)
Definition spxmainsm.h:1034
virtual void execute(VectorBase< R > &x, VectorBase< R > &y, VectorBase< R > &s, VectorBase< R > &r, DataArray< typename SPxSolverBase< R >::VarStatus > &cBasis, DataArray< typename SPxSolverBase< R >::VarStatus > &rBasis, bool isOptimal) const
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:1073
DuplicateColsPS & operator=(const DuplicateColsPS &rhs)
assignment operator
Definition spxmainsm.h:1063
Postsolves duplicate rows.
Definition spxmainsm.h:924
DataArray< bool > m_isLhsEqualRhs
Definition spxmainsm.h:939
DuplicateRowsPS(const DuplicateRowsPS &old)
copy constructor
Definition spxmainsm.h:972
DuplicateRowsPS(const SPxLPBase< R > &lp, int _i, int maxLhsIdx, int minRhsIdx, const DSVectorBase< R > &dupRows, const Array< R > scale, const DataArray< int > perm, const DataArray< bool > isLhsEqualRhs, bool isTheLast, bool isFixedRow, std::shared_ptr< Tolerances > tols, bool isFirst=false)
Definition spxmainsm.h:942
virtual void execute(VectorBase< R > &x, VectorBase< R > &y, VectorBase< R > &s, VectorBase< R > &r, DataArray< typename SPxSolverBase< R >::VarStatus > &cBasis, DataArray< typename SPxSolverBase< R >::VarStatus > &rBasis, bool isOptimal) const
DuplicateRowsPS & operator=(const DuplicateRowsPS &rhs)
assignment operator
Definition spxmainsm.h:990
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:1005
Postsolves empty constraints.
Definition spxmainsm.h:255
EmptyConstraintPS(const SPxLPBase< R > &lp, int _i, std::shared_ptr< Tolerances > tols)
Definition spxmainsm.h:263
virtual void execute(VectorBase< R > &x, VectorBase< R > &y, VectorBase< R > &s, VectorBase< R > &r, DataArray< typename SPxSolverBase< R >::VarStatus > &cBasis, DataArray< typename SPxSolverBase< R >::VarStatus > &rBasis, bool isOptimal) const
EmptyConstraintPS & operator=(const EmptyConstraintPS &rhs)
assignment operator
Definition spxmainsm.h:277
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:293
EmptyConstraintPS(const EmptyConstraintPS &old)
copy constructor
Definition spxmainsm.h:270
Postsolves variable bound fixing.
Definition spxmainsm.h:546
SPxSolverBase< R >::VarStatus m_status
Definition spxmainsm.h:549
FixBoundsPS(const SPxLPBase< R > &lp, int j, R val, std::shared_ptr< Tolerances > tols)
Definition spxmainsm.h:553
FixBoundsPS(const FixBoundsPS &old)
copy constructor
Definition spxmainsm.h:571
FixBoundsPS & operator=(const FixBoundsPS &rhs)
assignment operator
Definition spxmainsm.h:577
virtual void execute(VectorBase< R > &x, VectorBase< R > &y, VectorBase< R > &s, VectorBase< R > &r, DataArray< typename SPxSolverBase< R >::VarStatus > &cBasis, DataArray< typename SPxSolverBase< R >::VarStatus > &rBasis, bool isOptimal) const
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:588
Postsolves variable fixing.
Definition spxmainsm.h:481
DSVectorBase< R > m_col
does the index mapping have to be updated in postsolving?
Definition spxmainsm.h:490
FixVariablePS(const SPxLPBase< R > &lp, SPxMainSM &simplifier, int _j, const R val, std::shared_ptr< Tolerances > tols, bool correctIdx=true)
Definition spxmainsm.h:494
FixVariablePS(const FixVariablePS &old)
copy constructor
Definition spxmainsm.h:509
virtual void execute(VectorBase< R > &x, VectorBase< R > &y, VectorBase< R > &s, VectorBase< R > &r, DataArray< typename SPxSolverBase< R >::VarStatus > &cBasis, DataArray< typename SPxSolverBase< R >::VarStatus > &rBasis, bool isOptimal) const
FixVariablePS & operator=(const FixVariablePS &rhs)
assignment operator
Definition spxmainsm.h:521
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:532
Postsolves forcing constraints.
Definition spxmainsm.h:387
ForceConstraintPS(const ForceConstraintPS &old)
copy constructor
Definition spxmainsm.h:433
ForceConstraintPS & operator=(const ForceConstraintPS &rhs)
assignment operator
Definition spxmainsm.h:451
ForceConstraintPS(const SPxLPBase< R > &lp, int _i, bool lhsFixed, DataArray< bool > &fixCols, Array< R > &lo, Array< R > &up, std::shared_ptr< Tolerances > tols)
Definition spxmainsm.h:406
virtual void execute(VectorBase< R > &x, VectorBase< R > &y, VectorBase< R > &s, VectorBase< R > &r, DataArray< typename SPxSolverBase< R >::VarStatus > &cBasis, DataArray< typename SPxSolverBase< R >::VarStatus > &rBasis, bool isOptimal) const
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:467
Array< DSVectorBase< R > > m_cols
Definition spxmainsm.h:395
Postsolves free column singletons.
Definition spxmainsm.h:755
virtual void execute(VectorBase< R > &x, VectorBase< R > &y, VectorBase< R > &s, VectorBase< R > &r, DataArray< typename SPxSolverBase< R >::VarStatus > &cBasis, DataArray< typename SPxSolverBase< R >::VarStatus > &rBasis, bool isOptimal) const
FreeColSingletonPS & operator=(const FreeColSingletonPS &rhs)
assignment operator
Definition spxmainsm.h:799
FreeColSingletonPS(const SPxLPBase< R > &lp, SPxMainSM &simplifier, int _j, int _i, R slackVal, std::shared_ptr< Tolerances > tols)
Definition spxmainsm.h:769
FreeColSingletonPS(const FreeColSingletonPS &old)
copy constructor
Definition spxmainsm.h:786
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:810
Postsolves unconstraint constraints.
Definition spxmainsm.h:203
FreeConstraintPS(const SPxLPBase< R > &lp, int _i, std::shared_ptr< Tolerances > tols)
Definition spxmainsm.h:212
FreeConstraintPS(const FreeConstraintPS &old)
copy constructor
Definition spxmainsm.h:220
virtual void execute(VectorBase< R > &x, VectorBase< R > &y, VectorBase< R > &s, VectorBase< R > &r, DataArray< typename SPxSolverBase< R >::VarStatus > &cBasis, DataArray< typename SPxSolverBase< R >::VarStatus > &rBasis, bool isOptimal) const
FreeConstraintPS & operator=(const FreeConstraintPS &rhs)
assignment operator
Definition spxmainsm.h:228
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:245
Postsolves the case when constraints are removed due to a variable with zero objective that is free i...
Definition spxmainsm.h:605
FreeZeroObjVariablePS(const FreeZeroObjVariablePS &old)
copy constructor
Definition spxmainsm.h:647
FreeZeroObjVariablePS & operator=(const FreeZeroObjVariablePS &rhs)
assignment operator
Definition spxmainsm.h:660
FreeZeroObjVariablePS(const SPxLPBase< R > &lp, int _j, bool loFree, DSVectorBase< R > col_idx_sorted, std::shared_ptr< Tolerances > tols)
Definition spxmainsm.h:619
virtual void execute(VectorBase< R > &x, VectorBase< R > &y, VectorBase< R > &s, VectorBase< R > &r, DataArray< typename SPxSolverBase< R >::VarStatus > &cBasis, DataArray< typename SPxSolverBase< R >::VarStatus > &rBasis, bool isOptimal) const
Array< DSVectorBase< R > > m_rows
Definition spxmainsm.h:614
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:674
Postsolves multi aggregation.
Definition spxmainsm.h:1168
MultiAggregationPS(const SPxLPBase< R > &lp, SPxMainSM &simplifier, int _i, int _j, R constant, std::shared_ptr< Tolerances > tols)
Definition spxmainsm.h:1185
virtual void execute(VectorBase< R > &x, VectorBase< R > &y, VectorBase< R > &s, VectorBase< R > &r, DataArray< typename SPxSolverBase< R >::VarStatus > &cBasis, DataArray< typename SPxSolverBase< R >::VarStatus > &rBasis, bool isOptimal) const
MultiAggregationPS(const MultiAggregationPS &old)
copy constructor
Definition spxmainsm.h:1205
MultiAggregationPS & operator=(const MultiAggregationPS &rhs)
assignment operator
Definition spxmainsm.h:1221
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:1233
Base class for postsolving operations.
Definition spxmainsm.h:85
int nRows
number of rows
Definition spxmainsm.h:92
virtual R feastol() const
Definition spxmainsm.h:144
PostStep(const char *p_name, std::shared_ptr< Tolerances > tols, int nR=0, int nC=0)
constructor.
Definition spxmainsm.h:98
int nCols
number of cols
Definition spxmainsm.h:90
virtual void execute(VectorBase< R > &x, VectorBase< R > &y, VectorBase< R > &s, VectorBase< R > &r, DataArray< typename SPxSolverBase< R >::VarStatus > &cBasis, DataArray< typename SPxSolverBase< R >::VarStatus > &rBasis, bool isOptimal) const =0
executes the postsolving.
virtual const char * getName() const
get name of simplifying step.
Definition spxmainsm.h:124
virtual R epsilon() const
Definition spxmainsm.h:149
std::shared_ptr< Tolerances > _tolerances
0-epsilon of this poststep
Definition spxmainsm.h:94
virtual bool checkBasisDim(DataArray< typename SPxSolverBase< R >::VarStatus > rows, DataArray< typename SPxSolverBase< R >::VarStatus > cols) const
virtual PostStep * clone() const =0
clone function for polymorphism
const char * m_name
name of the simplifier
Definition spxmainsm.h:88
PostStep & operator=(const PostStep &)
assignment operator
Definition spxmainsm.h:114
PostStep(const PostStep &old)
copy constructor.
Definition spxmainsm.h:106
virtual ~PostStep()
destructor.
Definition spxmainsm.h:119
Postsolves row objectives.
Definition spxmainsm.h:159
int m_j
slack column index
Definition spxmainsm.h:162
RowObjPS(const SPxLPBase< R > &lp, int _i, int _j, std::shared_ptr< Tolerances > tols)
Definition spxmainsm.h:166
RowObjPS & operator=(const RowObjPS &rhs)
assignment operator
Definition spxmainsm.h:178
RowObjPS(const RowObjPS &old)
copy constructor
Definition spxmainsm.h:172
virtual void execute(VectorBase< R > &x, VectorBase< R > &y, VectorBase< R > &s, VectorBase< R > &r, DataArray< typename SPxSolverBase< R >::VarStatus > &cBasis, DataArray< typename SPxSolverBase< R >::VarStatus > &rBasis, bool isOptimal) const
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:193
Postsolves row singletons.
Definition spxmainsm.h:303
RowSingletonPS(const RowSingletonPS &old)
copy constructor
Definition spxmainsm.h:343
virtual void execute(VectorBase< R > &x, VectorBase< R > &y, VectorBase< R > &s, VectorBase< R > &r, DataArray< typename SPxSolverBase< R >::VarStatus > &cBasis, DataArray< typename SPxSolverBase< R >::VarStatus > &rBasis, bool isOptimal) const
RowSingletonPS & operator=(const RowSingletonPS &rhs)
assignment operator
Definition spxmainsm.h:362
RowSingletonPS(const SPxLPBase< R > &lp, int _i, int _j, bool strictLo, bool strictUp, R newLo, R newUp, R oldLo, R oldUp, std::shared_ptr< Tolerances > tols)
Definition spxmainsm.h:323
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:373
Postsolves variable bound tightening from pseudo objective propagation.
Definition spxmainsm.h:1249
TightenBoundsPS(const TightenBoundsPS &old)
copy constructor
Definition spxmainsm.h:1266
virtual void execute(VectorBase< R > &x, VectorBase< R > &y, VectorBase< R > &s, VectorBase< R > &r, DataArray< typename SPxSolverBase< R >::VarStatus > &cBasis, DataArray< typename SPxSolverBase< R >::VarStatus > &rBasis, bool isOptimal) const
TightenBoundsPS & operator=(const TightenBoundsPS &rhs)
assignment operator
Definition spxmainsm.h:1273
TightenBoundsPS(const SPxLPBase< R > &lp, int j, R origupper, R origlower, std::shared_ptr< Tolerances > tols)
Definition spxmainsm.h:1257
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:1278
Postsolves column singletons with zero objective.
Definition spxmainsm.h:690
virtual void execute(VectorBase< R > &x, VectorBase< R > &y, VectorBase< R > &s, VectorBase< R > &r, DataArray< typename SPxSolverBase< R >::VarStatus > &cBasis, DataArray< typename SPxSolverBase< R >::VarStatus > &rBasis, bool isOptimal) const
ZeroObjColSingletonPS & operator=(const ZeroObjColSingletonPS &rhs)
assignment operator
Definition spxmainsm.h:728
ZeroObjColSingletonPS(const ZeroObjColSingletonPS &old)
copy constructor
Definition spxmainsm.h:716
ZeroObjColSingletonPS(const SPxLPBase< R > &lp, const SPxMainSM &, int _j, int _i, std::shared_ptr< Tolerances > tols)
Definition spxmainsm.h:703
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:739
LP simplifier for removing uneccessary row/columns.
Definition spxmainsm.h:72
int cIdx(int j) const
returns for a given column index of the (reduced) LP the corresponding column index in the unsimplifi...
Definition spxmainsm.h:1439
friend class FixVariablePS
Definition spxmainsm.h:1294
friend class FreeColSingletonPS
Definition spxmainsm.h:1298
SPxMainSM(Timer::TYPE ttype=Timer::USER_TIME)
Definition spxmainsm.h:1469
void removeRow(SPxLPBase< R > &lp, int i)
removes a row in the LP.
Definition spxmainsm.h:1422
void handleExtremes(SPxLPBase< R > &lp)
handles extreme values by setting them to zero or R(infinity).
void propagatePseudoobj(SPxLPBase< R > &lp)
tightens variable bounds by propagating the pseudo objective function value.
SPxMainSM(const SPxMainSM &old)
copy constructor.
Definition spxmainsm.h:1481
Array< DSVectorBase< R > > m_classSetRows
stores parallel classes with non-zero colum entry
Definition spxmainsm.h:1345
VectorBase< R > m_slack
unsimplified slack VectorBase<R>.
Definition spxmainsm.h:1336
friend class FixBoundsPS
Definition spxmainsm.h:1295
SPxSimplifier< R >::Result simplifyDual(SPxLPBase< R > &lp, bool &again)
performs simplification steps on the LP based on dual concepts.
void fixColumn(SPxLPBase< R > &lp, int i, bool correctIdx=true)
handles the fixing of a variable. correctIdx is true iff the index mapping has to be updated.
friend class EmptyConstraintPS
Definition spxmainsm.h:1291
virtual ~SPxMainSM()
destructor.
Definition spxmainsm.h:1532
SPxSimplifier< R >::Result duplicateCols(SPxLPBase< R > &lp, bool &again)
removes duplicate columns
friend class RowSingletonPS
Definition spxmainsm.h:1292
friend class ZeroObjColSingletonPS
Definition spxmainsm.h:1297
SPxSimplifier< R >::Result removeRowSingleton(SPxLPBase< R > &lp, const SVectorBase< R > &row, int &i)
remove row singletons.
R epsZero() const
Definition spxmainsm.h:1448
SPxSimplifier< R >::Result duplicateRows(SPxLPBase< R > &lp, bool &again)
removes duplicate rows.
void computeMinMaxValues(SPxLPBase< R > &lp, R side, R val, R minRes, R maxRes, R &minVal, R &maxVal)
calculate min/max value for the multi aggregated variables
friend class DoubletonEquationPS
Definition spxmainsm.h:1299
VectorBase< R > m_dual
unsimplified dual solution VectorBase<R>.
Definition spxmainsm.h:1337
int rIdx(int i) const
returns for a given row index of the (reduced) LP the corresponding row index in the unsimplified LP.
Definition spxmainsm.h:1434
SPxSimplifier< R >::Result multiaggregation(SPxLPBase< R > &lp, bool &again)
performs multi-aggregations of variable based upon constraint activitu.
friend class DuplicateColsPS
Definition spxmainsm.h:1301
Array< DSVectorBase< R > > m_dupCols
arrange duplicate columns w.r.t. their pClass values
Definition spxmainsm.h:1351
friend class AggregationPS
Definition spxmainsm.h:1302
virtual const VectorBase< R > & unsimplifiedSlacks()
returns a reference to the unsimplified slack values.
Definition spxmainsm.h:1580
R m_cutoffbound
the cutoff bound that is found by heuristics
Definition spxmainsm.h:1358
SPxSimplifier< R >::Result simplifyCols(SPxLPBase< R > &lp, bool &again)
performs simplification steps on the columns of the LP.
void trivialHeuristic(SPxLPBase< R > &lp)
tries to find good lower bound solutions by applying some trivial heuristics
SPxSimplifier< R >::Result m_result
result of the simplification.
Definition spxmainsm.h:1357
virtual const VectorBase< R > & unsimplifiedRedCost()
returns a reference to the unsimplified reduced costs.
Definition spxmainsm.h:1586
VectorBase< R > m_prim
unsimplified primal solution VectorBase<R>.
Definition spxmainsm.h:1335
friend class FreeConstraintPS
Definition spxmainsm.h:1290
SPxSimplifier< R >::Result aggregateVars(SPxLPBase< R > &lp, const SVectorBase< R > &row, int &i)
aggregate two variables that appear in an equation.
SPxSimplifier< R >::Result removeEmpty(SPxLPBase< R > &lp)
removed empty rows and empty columns.
Array< DSVectorBase< R > > m_dupRows
arrange duplicate rows using bucket sort w.r.t. their pClass values
Definition spxmainsm.h:1349
bool checkSolution(SPxLPBase< R > &lp, VectorBase< R > sol)
checks a solution for feasibility
Array< DSVectorBase< R > > m_classSetCols
stores parallel classes with non-zero row entry
Definition spxmainsm.h:1347
virtual SPxSolverBase< R >::VarStatus getBasisColStatus(int j) const
gets basis status for a single column.
Definition spxmainsm.h:1598
virtual SPxSimplifier< R >::Result result() const
returns result status of the simplification
Definition spxmainsm.h:1557
Array< std::shared_ptr< PostStep > > m_hist
VectorBase<R> of presolve history.
Definition spxmainsm.h:1343
virtual const VectorBase< R > & unsimplifiedDual()
returns a reference to the unsimplified dual solution.
Definition spxmainsm.h:1574
SPxSimplifier< R >::Result simplifyRows(SPxLPBase< R > &lp, bool &again)
performs simplification steps on the rows of the LP.
DataArray< typename SPxSolverBase< R >::VarStatus > m_rBasisStat
basis status of rows.
Definition spxmainsm.h:1340
virtual SPxSimplifier< R >::Result simplify(SPxLPBase< R > &lp, Real remainingTime, bool keepbounds=false, uint32_t seed=0)
simplify SPxLPBase<R> lp.
DataArray< int > m_stat
preprocessing history.
Definition spxmainsm.h:1353
VectorBase< R > m_redCost
unsimplified reduced cost VectorBase<R>.
Definition spxmainsm.h:1338
DataArray< int > m_cIdx
column index VectorBase<R> in original LP.
Definition spxmainsm.h:1341
R feastol() const
Definition spxmainsm.h:1453
friend class DuplicateRowsPS
Definition spxmainsm.h:1300
int m_addedcols
columns added by handleRowObjectives()
Definition spxmainsm.h:1356
friend class FreeZeroObjVariablePS
Definition spxmainsm.h:1296
friend class ForceConstraintPS
Definition spxmainsm.h:1293
void removeCol(SPxLPBase< R > &lp, int j)
removes a column in the LP.
Definition spxmainsm.h:1428
virtual SPxSolverBase< R >::VarStatus getBasisRowStatus(int i) const
gets basis status for a single row.
Definition spxmainsm.h:1592
bool m_postsolved
status of postsolving.
Definition spxmainsm.h:1352
virtual void getBasis(typename SPxSolverBase< R >::VarStatus rows[], typename SPxSolverBase< R >::VarStatus cols[], const int rowsSize=-1, const int colsSize=-1) const
get optimal basis.
Definition spxmainsm.h:1604
SPxMainSM & operator=(const SPxMainSM &rhs)
assignment operator
Definition spxmainsm.h:1504
void handleRowObjectives(SPxLPBase< R > &lp)
DataArray< int > m_rIdx
row index VectorBase<R> in original LP.
Definition spxmainsm.h:1342
virtual SPxSimplifier< R > * clone() const
clone function for polymorphism
Definition spxmainsm.h:1537
void computeMinMaxResidualActivity(SPxLPBase< R > &lp, int rowNumber, int colNumber, R &minAct, R &maxAct)
computes the minimum and maximum residual activity for a given row and column. If colNumber is set to...
virtual void unsimplify(const VectorBase< R > &x, const VectorBase< R > &y, const VectorBase< R > &s, const VectorBase< R > &r, const typename SPxSolverBase< R >::VarStatus rows[], const typename SPxSolverBase< R >::VarStatus cols[], bool isOptimal=true)
reconstructs an optimal solution for the unsimplified LP.
virtual const VectorBase< R > & unsimplifiedPrimal()
returns a reference to the unsimplified primal solution.
Definition spxmainsm.h:1568
SPxLPBase< R >::SPxSense m_thesense
optimization sense.
Definition spxmainsm.h:1354
virtual bool isUnsimplified() const
specifies whether an optimal solution has already been unsimplified.
Definition spxmainsm.h:1563
bool m_keepbounds
keep some bounds (for boundflipping)
Definition spxmainsm.h:1355
DataArray< typename SPxSolverBase< R >::VarStatus > m_cBasisStat
basis status of columns.
Definition spxmainsm.h:1339
R m_pseudoobj
the pseudo objective function value
Definition spxmainsm.h:1359
LP simplification abstract base class.
virtual void addObjoffset(const R val)
add objective offset.
Result
Result of the simplification.
@ OKAY
simplification could be done
const std::shared_ptr< Tolerances > tolerances() const
get the _tolerances member variable
SPxSimplifier & operator=(const SPxSimplifier &rhs)
assignment operator
Sequential object-oriented SimPlex.
Definition spxsolver.h:104
Sparse vectors.
Definition vectorbase.h:44
int & index(int n)
Reference to index of n 'th nonzero.
int size() const
Number of used indices.
TYPE
types of timers
Definition timer.h:109
Dense vector.
Definition vectorbase.h:86
Exception classes for SoPlex.
Everything should be within this namespace.
double Real
Definition spxdefines.h:269
bool EQ(int a, int b)
SOPLEX_THREADLOCAL const Real infinity
void spx_alloc(T &p, int n=1)
Allocate memory.
Definition spxalloc.h:58
Debugging, floating point type and parameter definitions.
LP simplification base class.
comparator for class SVectorBase<R>::Element: compare nonzeros according to value
Definition spxmainsm.h:1625
int operator()(const typename SVectorBase< R >::Element &e1, const typename SVectorBase< R >::Element &e2) const
Definition spxmainsm.h:1634
comparator for class SVectorBase<R>::Element: compare nonzeros according to index
Definition spxmainsm.h:1648
int operator()(const typename SVectorBase< R >::Element &e1, const typename SVectorBase< R >::Element &e2) const
Definition spxmainsm.h:1652