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-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"
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
94 public:
95 /// constructor.
96 PostStep(const char* p_name, int nR = 0, int nC = 0)
97 : m_name(p_name)
98 , nCols(nC)
99 , nRows(nR)
100 {}
101 /// copy constructor.
103 : m_name(old.m_name)
104 , nCols(old.nCols)
105 , nRows(old.nRows)
106 {}
107 /// assignment operator
108 PostStep& operator=(const PostStep& /*rhs*/)
109 {
110 return *this;
111 }
112 /// destructor.
113 virtual ~PostStep()
114 {
115 m_name = 0;
116 }
117 /// get name of simplifying step.
118 virtual const char* getName() const
119 {
120 return m_name;
121 }
122 /// clone function for polymorphism
123 virtual PostStep* clone() const = 0;
124 /// executes the postsolving.
125 virtual void execute(
126 VectorBase<R>& x, //*< Primal solution VectorBase<R> */
127 VectorBase<R>& y, //*< Dual solution VectorBase<R> */
128 VectorBase<R>& s, //*< VectorBase<R> of slacks */
129 VectorBase<R>& r, //*< Reduced cost VectorBase<R> */
130 DataArray<typename SPxSolverBase<R>::VarStatus>& cBasis, //*< Basis status of column basis */
131 DataArray<typename SPxSolverBase<R>::VarStatus>& rBasis, //*< Basis status of row basis */
132 bool isOptimal
133 ) const = 0;
134
136 DataArray<typename SPxSolverBase<R>::VarStatus> cols) const;
137
138 static R eps()
139 {
140 return 1e-6;
141 }
142 };
143
144 /**@brief Postsolves row objectives.
145 @ingroup Algo
146 */
147 class RowObjPS : public PostStep
148 {
149 private:
150 int m_i; ///< row index
151 int m_j; ///< slack column index
152
153 public:
154 ///
155 RowObjPS(const SPxLPBase<R>& lp, int _i, int _j)
156 : PostStep("RowObj", lp.nRows(), lp.nCols())
157 , m_i(_i)
158 , m_j(_j)
159 {}
160 /// copy constructor
162 : PostStep(old)
163 , m_i(old.m_i)
164 , m_j(old.m_j)
165 {}
166 /// assignment operator
168 {
169 if(this != &rhs)
170 {
171 m_i = rhs.m_i;
172 m_j = rhs.m_j;
173 }
174
175 return *this;
176 }
177 ///
181 /// clone function for polymorphism
182 inline virtual PostStep* clone() const
183 {
184 return new RowObjPS(*this);
185 }
186 };
187
188 /**@brief Postsolves unconstraint constraints.
189 @ingroup Algo
190 */
192 {
193 private:
194 int m_i;
198
199 public:
200 ///
202 : PostStep("FreeConstraint", lp.nRows(), lp.nCols())
203 , m_i(_i)
204 , m_old_i(lp.nRows() - 1)
205 , m_row(lp.rowVector(_i))
206 , m_row_obj(lp.rowObj(_i))
207 {}
208 /// copy constructor
216 /// assignment operator
218 {
219 if(this != &rhs)
220 {
221 m_i = rhs.m_i;
222 m_old_i = rhs.m_old_i;
223 m_row = rhs.m_row;
224 m_row_obj = rhs.m_row_obj;
225 }
226
227 return *this;
228 }
229 ///
233 /// clone function for polymorphism
234 inline virtual PostStep* clone() const
235 {
236 return new FreeConstraintPS(*this);
237 }
238 };
239
240 /**@brief Postsolves empty constraints.
241 @ingroup Algo
242 */
244 {
245 private:
246 int m_i;
249
250 public:
251 ///
253 : PostStep("EmptyConstraint", lp.nRows(), lp.nCols())
254 , m_i(_i)
255 , m_old_i(lp.nRows() - 1)
256 , m_row_obj(lp.rowObj(_i))
257 {}
258 /// copy constructor
265 /// assignment operator
267 {
268 if(this != &rhs)
269 {
270 m_i = rhs.m_i;
271 m_old_i = rhs.m_old_i;
272 m_row_obj = rhs.m_row_obj;
273 }
274
275 return *this;
276 }
277 ///
281 /// clone function for polymorphism
282 inline virtual PostStep* clone() const
283 {
284 return new EmptyConstraintPS(*this);
285 }
286 };
287
288 /**@brief Postsolves row singletons.
289 @ingroup Algo
290 */
292 {
293 private:
294 const int m_i;
295 const int m_old_i;
296 const int m_j;
297 const R m_lhs;
298 const R m_rhs;
299 const bool m_strictLo;
300 const bool m_strictUp;
301 const bool m_maxSense;
302 const R m_obj;
304 const R m_newLo;
305 const R m_newUp;
306 const R m_oldLo;
307 const R m_oldUp;
309
310 public:
311 ///
312 RowSingletonPS(const SPxLPBase<R>& lp, int _i, int _j, bool strictLo, bool strictUp,
313 R newLo, R newUp, R oldLo, R oldUp)
314 : PostStep("RowSingleton", lp.nRows(), lp.nCols())
315 , m_i(_i)
316 , m_old_i(lp.nRows() - 1)
317 , m_j(_j)
318 , m_lhs(lp.lhs(_i))
319 , m_rhs(lp.rhs(_i))
322 , m_maxSense(lp.spxSense() == SPxLPBase<R>::MAXIMIZE)
323 , m_obj(lp.spxSense() == SPxLPBase<R>::MINIMIZE ? lp.obj(_j) : -lp.obj(_j))
324 , m_col(lp.colVector(_j))
325 , m_newLo(newLo)
326 , m_newUp(newUp)
327 , m_oldLo(oldLo)
328 , m_oldUp(oldUp)
329 , m_row_obj(lp.rowObj(_i))
330 {}
331 /// copy constructor
350 /// assignment operator
352 {
353 if(this != &rhs)
354 {
356 m_col = rhs.m_col;
357 }
358
359 return *this;
360 }
361 /// clone function for polymorphism
362 inline virtual PostStep* clone() const
363 {
364 return new RowSingletonPS(*this);
365 }
366 ///
370 };
371
372 /**@brief Postsolves forcing constraints.
373 @ingroup Algo
374 */
376 {
377 private:
378 const int m_i;
379 const int m_old_i;
380 const R m_lRhs;
385 const bool m_lhsFixed;
386 const bool m_maxSense;
389 const R m_lhs;
390 const R m_rhs;
391 const R m_rowobj;
392
393 public:
394 ///
396 Array<R>& lo, Array<R>& up)
397 : PostStep("ForceConstraint", lp.nRows(), lp.nCols())
398 , m_i(_i)
399 , m_old_i(lp.nRows() - 1)
400 , m_lRhs(lhsFixed ? lp.lhs(_i) : lp.rhs(_i))
401 , m_row(lp.rowVector(_i))
402 , m_objs(lp.rowVector(_i).size())
404 , m_cols(lp.rowVector(_i).size())
406 , m_maxSense(lp.spxSense() == SPxLPBase<R>::MAXIMIZE)
407 , m_oldLowers(lo)
408 , m_oldUppers(up)
409 , m_lhs(lp.lhs(_i))
410 , m_rhs(lp.rhs(_i))
411 , m_rowobj(lp.rowObj(_i))
412 {
413 for(int k = 0; k < m_row.size(); ++k)
414 {
415 m_objs[k] = (lp.spxSense() == SPxLPBase<R>::MINIMIZE ? lp.obj(m_row.index(k)) : -lp.obj(m_row.index(
416 k)));
417 m_cols[k] = lp.colVector(m_row.index(k));
418 }
419 }
420 /// copy constructor
438 /// assignment operator
440 {
441 if(this != &rhs)
442 {
444 m_row = rhs.m_row;
445 m_objs = rhs.m_objs;
446 m_fixed = rhs.m_fixed;
447 m_cols = rhs.m_cols;
450 }
451
452 return *this;
453 }
454 /// clone function for polymorphism
455 inline virtual PostStep* clone() const
456 {
457 return new ForceConstraintPS(*this);
458 }
459 ///
463 };
464
465 /**@brief Postsolves variable fixing.
466 @ingroup Algo
467 */
468 class FixVariablePS : public PostStep
469 {
470 private:
471 const int m_j;
472 const int m_old_j;
473 const R m_val;
474 const R m_obj;
475 const R m_lower;
476 const R m_upper;
477 const bool m_correctIdx; /// does the index mapping have to be updated in postsolving?
479
480 public:
481 ///
483 bool correctIdx = true)
484 : PostStep("FixVariable", lp.nRows(), lp.nCols())
485 , m_j(_j)
486 , m_old_j(lp.nCols() - 1)
487 , m_val(val)
488 , m_obj(lp.spxSense() == SPxLPBase<R>::MINIMIZE ? lp.obj(_j) : -lp.obj(_j))
489 , m_lower(lp.lower(_j))
490 , m_upper(lp.upper(_j))
492 , m_col(lp.colVector(_j))
493 {
494 simplifier.addObjoffset(m_val * lp.obj(m_j));
495 }
496 /// copy constructor
508 /// assignment operator
510 {
511 if(this != &rhs)
512 {
514 m_col = rhs.m_col;
515 }
516
517 return *this;
518 }
519 /// clone function for polymorphism
520 inline virtual PostStep* clone() const
521 {
522 return new FixVariablePS(*this);
523 }
524 ///
528 };
529
530 /**@brief Postsolves variable bound fixing.
531 @ingroup Algo
532 */
533 class FixBoundsPS : public PostStep
534 {
535 private:
536 const int m_j;
538
539 public:
540 ///
541 FixBoundsPS(const SPxLPBase<R>& lp, int j, R val)
542 : PostStep("FixBounds", lp.nRows(), lp.nCols())
543 , m_j(j)
544 {
545 if(EQrel(lp.lower(j), lp.upper(j), this->eps()))
547 else if(EQrel(val, lp.lower(j), this->eps()))
549 else if(EQrel(val, lp.upper(j), this->eps()))
551 else if(lp.lower(j) <= R(-infinity) && lp.upper(j) >= R(infinity))
553 else
554 {
555 throw SPxInternalCodeException("XMAISM14 This should never happen.");
556 }
557 }
558 /// copy constructor
560 : PostStep(old)
561 , m_j(old.m_j)
563 {}
564 /// assignment operator
566 {
567 if(this != &rhs)
568 {
570 m_status = rhs.m_status;
571 }
572
573 return *this;
574 }
575 /// clone function for polymorphism
576 inline virtual PostStep* clone() const
577 {
580 return new(FixBoundsPSptr) FixBoundsPS(*this);
581 }
582 ///
586 };
587
588 /**@brief Postsolves the case when constraints are removed due to a
589 variable with zero objective that is free in one direction.
590 @ingroup Algo
591 */
593 {
594 private:
595 const int m_j;
596 const int m_old_j;
597 const int m_old_i;
598 const R m_bnd;
603 const bool m_loFree;
604
605 public:
606 ///
608 : PostStep("FreeZeroObjVariable", lp.nRows(), lp.nCols())
609 , m_j(_j)
610 , m_old_j(lp.nCols() - 1)
611 , m_old_i(lp.nRows() - 1)
612 , m_bnd(loFree ? lp.upper(_j) : lp.lower(_j))
614 , m_lRhs(lp.colVector(_j).size())
615 , m_rowObj(lp.colVector(_j).size())
616 , m_rows(lp.colVector(_j).size())
618 {
619 for(int k = 0; k < m_col.size(); ++k)
620 {
621 int r = m_col.index(k);
622
623 if((m_loFree && m_col.value(k) > 0) ||
624 (!m_loFree && m_col.value(k) < 0))
625 m_lRhs.add(k, lp.rhs(r));
626 else
627 m_lRhs.add(k, lp.lhs(r));
628
629 m_rows[k] = lp.rowVector(r);
630 m_rowObj.add(k, lp.rowObj(r));
631 }
632 }
633 /// copy constructor
646 /// assignment operator
648 {
649 if(this != &rhs)
650 {
652 m_col = rhs.m_col;
653 m_lRhs = rhs.m_lRhs;
654 m_rowObj = rhs.m_rowObj;
655 m_rows = rhs.m_rows;
656 }
657
658 return *this;
659 }
660 /// clone function for polymorphism
667 ///
671 };
672
673 /**@brief Postsolves column singletons with zero objective.
674 @ingroup Algo
675 */
677 {
678 private:
679 const int m_j;
680 const int m_i;
681 const int m_old_j;
682 const R m_lhs;
683 const R m_rhs;
684 const R m_lower;
685 const R m_upper;
687
688 public:
689 ///
691 : PostStep("ZeroObjColSingleton", lp.nRows(), lp.nCols())
692 , m_j(_j)
693 , m_i(_i)
694 , m_old_j(lp.nCols() - 1)
695 , m_lhs(lp.lhs(_i))
696 , m_rhs(lp.rhs(_i))
697 , m_lower(lp.lower(_j))
698 , m_upper(lp.upper(_j))
699 , m_row(lp.rowVector(_i))
700 {}
701 /// copy constructor
713 /// assignment operator
715 {
716 if(this != &rhs)
717 {
719 m_row = rhs.m_row;
720 }
721
722 return *this;
723 }
724 /// clone function for polymorphism
731 ///
735 };
736
737 /**@brief Postsolves free column singletons.
738 @ingroup Algo
739 */
741 {
742 private:
743 const int m_j;
744 const int m_i;
745 const int m_old_j;
746 const int m_old_i;
747 const R m_obj;
748 const R m_lRhs;
749 const bool m_onLhs;
750 const bool m_eqCons;
752
753 public:
754 ///
756 : PostStep("FreeColSingleton", lp.nRows(), lp.nCols())
757 , m_j(_j)
758 , m_i(_i)
759 , m_old_j(lp.nCols() - 1)
760 , m_old_i(lp.nRows() - 1)
761 , m_obj(lp.spxSense() == SPxLPBase<R>::MINIMIZE ? lp.obj(_j) : -lp.obj(_j))
763 , m_onLhs(EQ(slackVal, lp.lhs(_i)))
764 , m_eqCons(EQ(lp.lhs(_i), lp.rhs(_i)))
765 , m_row(lp.rowVector(_i))
766 {
767 assert(m_row[m_j] != 0.0);
768 simplifier.addObjoffset(m_lRhs * (lp.obj(m_j) / m_row[m_j]));
769 }
770 /// copy constructor
783 /// assignment operator
785 {
786 if(this != &rhs)
787 {
789 m_row = rhs.m_row;
790 }
791
792 return *this;
793 }
794 /// clone function for polymorphism
795 inline virtual PostStep* clone() const
796 {
799 return new(FreeColSingletonPSptr) FreeColSingletonPS(*this);
800 }
801 ///
805 };
806
807 /**@brief Postsolves doubleton equations combined with a column singleton.
808 @ingroup Algo
809 */
811 {
812 private:
813 const int m_j;
814 const int m_k;
815 const int m_i;
816 const bool m_maxSense;
817 const bool m_jFixed;
818 const R m_jObj;
819 const R m_kObj;
820 const R m_aij;
821 const bool m_strictLo;
822 const bool m_strictUp;
823 const R m_newLo;
824 const R m_newUp;
825 const R m_oldLo;
826 const R m_oldUp;
827 const R m_Lo_j;
828 const R m_Up_j;
829 const R m_lhs;
830 const R m_rhs;
832
833 public:
834 ///
836 : PostStep("DoubletonEquation", lp.nRows(), lp.nCols())
837 , m_j(_j)
838 , m_k(_k)
839 , m_i(_i)
840 , m_maxSense(lp.spxSense() == SPxLPBase<R>::MAXIMIZE)
841 , m_jFixed(EQ(lp.lower(_j), lp.upper(_j)))
842 , m_jObj(lp.spxSense() == SPxLPBase<R>::MINIMIZE ? lp.obj(_j) : -lp.obj(_j))
843 , m_kObj(lp.spxSense() == SPxLPBase<R>::MINIMIZE ? lp.obj(_k) : -lp.obj(_k))
844 , m_aij(lp.colVector(_j).value(0))
845 , m_strictLo(lp.lower(_k) > oldLo)
846 , m_strictUp(lp.upper(_k) < oldUp)
847 , m_newLo(lp.lower(_k))
848 , m_newUp(lp.upper(_k))
849 , m_oldLo(oldLo)
850 , m_oldUp(oldUp)
851 , m_Lo_j(lp.lower(_j))
852 , m_Up_j(lp.upper(_j))
853 , m_lhs(lp.lhs(_i))
854 , m_rhs(lp.rhs(_i))
855 , m_col(lp.colVector(_k))
856 {}
857 /// copy constructor
880 /// assignment operator
882 {
883 if(this != &rhs)
884 {
886 m_col = rhs.m_col;
887 }
888
889 return *this;
890 }
891 /// clone function for polymorphism
898 ///
902 };
903
904 /**@brief Postsolves duplicate rows.
905 @ingroup Algo
906 */
908 {
909 private:
910 const int m_i;
912 const int m_maxLhsIdx;
913 const int m_minRhsIdx;
914 const bool m_maxSense;
915 const bool m_isFirst;
916 const bool m_isLast;
917 const bool m_fixed;
918 const int m_nCols;
924
925 public:
928 const Array<R> scale, const DataArray<int> perm, const DataArray<bool> isLhsEqualRhs,
929 bool isTheLast, bool isFixedRow, bool isFirst = false)
930 : PostStep("DuplicateRows", lp.nRows(), lp.nCols())
931 , m_i(_i)
932 , m_i_rowObj(lp.rowObj(_i))
933 , m_maxLhsIdx((maxLhsIdx == -1) ? -1 : maxLhsIdx)
934 , m_minRhsIdx((minRhsIdx == -1) ? -1 : minRhsIdx)
935 , m_maxSense(lp.spxSense() == SPxLPBase<R>::MAXIMIZE)
939 , m_nCols(lp.nCols())
940 , m_scale(dupRows.size())
941 , m_rowObj(dupRows.size())
942 , m_rIdxLocalOld(dupRows.size())
943 , m_perm(perm)
945 {
946 R rowScale = scale[_i];
947
948 for(int k = 0; k < dupRows.size(); ++k)
949 {
950 m_scale.add(dupRows.index(k), rowScale / scale[dupRows.index(k)]);
951 m_rowObj.add(dupRows.index(k), lp.rowObj(dupRows.index(k)));
952 m_rIdxLocalOld[k] = dupRows.index(k);
953 }
954 }
955 /// copy constructor
973 /// assignment operator
975 {
976 if(this != &rhs)
977 {
979 m_scale = rhs.m_scale;
980 m_rowObj = rhs.m_rowObj;
982 m_perm = rhs.m_perm;
984 }
985
986 return *this;
987 }
988 /// clone function for polymorphism
989 inline virtual PostStep* clone() const
990 {
993 return new(DuplicateRowsPSptr) DuplicateRowsPS(*this);
994 }
998 };
999
1000 /**@brief Postsolves duplicate columns.
1001 @ingroup Algo
1002 */
1004 {
1005 private:
1006 const int m_j;
1007 const int m_k;
1008 const R m_loJ;
1009 const R m_upJ;
1010 const R m_loK;
1011 const R m_upK;
1012 const R m_scale;
1013 const bool m_isFirst;
1014 const bool m_isLast;
1016
1017 public:
1018 DuplicateColsPS(const SPxLPBase<R>& lp, int _j, int _k, R scale, DataArray<int> perm,
1019 bool isFirst = false, bool isTheLast = false)
1020 : PostStep("DuplicateCols", lp.nRows(), lp.nCols())
1021 , m_j(_j)
1022 , m_k(_k)
1023 , m_loJ(lp.lower(_j))
1024 , m_upJ(lp.upper(_j))
1025 , m_loK(lp.lower(_k))
1026 , m_upK(lp.upper(_k))
1027 , m_scale(scale)
1030 , m_perm(perm)
1031 {}
1032 /// copy constructor
1034 : PostStep(old)
1035 , m_j(old.m_j)
1036 , m_k(old.m_k)
1037 , m_loJ(old.m_loJ)
1038 , m_upJ(old.m_upJ)
1039 , m_loK(old.m_loK)
1040 , m_upK(old.m_upK)
1044 , m_perm(old.m_perm)
1045 {}
1046 /// assignment operator
1048 {
1049 if(this != &rhs)
1050 {
1052 }
1053
1054 return *this;
1055 }
1056 /// clone function for polymorphism
1057 inline virtual PostStep* clone() const
1058 {
1061 return new(DuplicateColsPSptr) DuplicateColsPS(*this);
1062 }
1065 DataArray<typename SPxSolverBase<R>::VarStatus>& rBasis, bool isOptimal) const;
1066 };
1067
1068 /**@brief Postsolves aggregation.
1069 @ingroup Algo
1070 */
1072 {
1073 private:
1074 const int m_j;
1075 const int m_i;
1076 const int m_old_j;
1077 const int m_old_i;
1078 const R m_upper;
1079 const R m_lower;
1080 const R m_obj;
1083 const R m_rhs;
1086
1087 public:
1088 ///
1090 : PostStep("Aggregation", lp.nRows(), lp.nCols())
1091 , m_j(_j)
1092 , m_i(_i)
1093 , m_old_j(lp.nCols() - 1)
1094 , m_old_i(lp.nRows() - 1)
1095 , m_upper(lp.upper(_j))
1096 , m_lower(lp.lower(_j))
1097 , m_obj(lp.spxSense() == SPxLPBase<R>::MINIMIZE ? lp.obj(_j) : -lp.obj(_j))
1100 , m_rhs(rhs)
1101 , m_row(lp.rowVector(_i))
1102 , m_col(lp.colVector(_j))
1103 {
1104 assert(m_row[m_j] != 0.0);
1105 }
1106 /// copy constructor
1108 : PostStep(old)
1109 , m_j(old.m_j)
1110 , m_i(old.m_i)
1115 , m_obj(old.m_obj)
1118 , m_rhs(old.m_rhs)
1119 , m_row(old.m_row)
1120 , m_col(old.m_col)
1121 {}
1122 /// assignment operator
1124 {
1125 if(this != &rhs)
1126 {
1128 m_row = rhs.m_row;
1129 m_col = rhs.m_col;
1130 }
1131
1132 return *this;
1133 }
1134 /// clone function for polymorphism
1135 inline virtual PostStep* clone() const
1136 {
1139 return new(AggregationPSptr) AggregationPS(*this);
1140 }
1141 ///
1144 DataArray<typename SPxSolverBase<R>::VarStatus>& rBasis, bool isOptimal) const;
1145 };
1146
1147 /**@brief Postsolves multi aggregation.
1148 @ingroup Algo
1149 */
1151 {
1152 private:
1153 const int m_j;
1154 const int m_i;
1155 const int m_old_j;
1156 const int m_old_i;
1157 const R m_upper;
1158 const R m_lower;
1159 const R m_obj;
1160 const R m_const;
1161 const bool m_onLhs;
1162 const bool m_eqCons;
1165
1166 public:
1167 ///
1169 : PostStep("MultiAggregation", lp.nRows(), lp.nCols())
1170 , m_j(_j)
1171 , m_i(_i)
1172 , m_old_j(lp.nCols() - 1)
1173 , m_old_i(lp.nRows() - 1)
1174 , m_upper(lp.upper(_j))
1175 , m_lower(lp.lower(_j))
1176 , m_obj(lp.spxSense() == SPxLPBase<R>::MINIMIZE ? lp.obj(_j) : -lp.obj(_j))
1177 , m_const(constant)
1178 , m_onLhs(EQ(constant, lp.lhs(_i)))
1179 , m_eqCons(EQ(lp.lhs(_i), lp.rhs(_i)))
1180 , m_row(lp.rowVector(_i))
1181 , m_col(lp.colVector(_j))
1182 {
1183 assert(m_row[m_j] != 0.0);
1184 simplifier.addObjoffset(m_obj * m_const / m_row[m_j]);
1185 }
1186 /// copy constructor
1188 : PostStep(old)
1189 , m_j(old.m_j)
1190 , m_i(old.m_i)
1195 , m_obj(old.m_obj)
1199 , m_row(old.m_row)
1200 , m_col(old.m_col)
1201 {}
1202 /// assignment operator
1204 {
1205 if(this != &rhs)
1206 {
1208 m_row = rhs.m_row;
1209 m_col = rhs.m_col;
1210 }
1211
1212 return *this;
1213 }
1214 /// clone function for polymorphism
1215 inline virtual PostStep* clone() const
1216 {
1219 return new(MultiAggregationPSptr) MultiAggregationPS(*this);
1220 }
1221 ///
1224 DataArray<typename SPxSolverBase<R>::VarStatus>& rBasis, bool isOptimal) const;
1225 };
1226
1227 /**@brief Postsolves variable bound tightening from pseudo objective propagation.
1228 @ingroup Algo
1229 */
1231 {
1232 private:
1233 const int m_j;
1236
1237 public:
1238 ///
1240 : PostStep("TightenBounds", lp.nRows(), lp.nCols())
1241 , m_j(j)
1244 {
1245 }
1246 /// copy constructor
1253 /// assignment operator
1255 {
1256 return *this;
1257 }
1258 /// clone function for polymorphism
1259 inline virtual PostStep* clone() const
1260 {
1263 return new(TightenBoundsPSptr) TightenBoundsPS(*this);
1264 }
1265 ///
1268 DataArray<typename SPxSolverBase<R>::VarStatus>& rBasis, bool isOptimal) const;
1269 };
1270 // friends
1271 friend class FreeConstraintPS;
1272 friend class EmptyConstraintPS;
1273 friend class RowSingletonPS;
1274 friend class ForceConstraintPS;
1275 friend class FixVariablePS;
1276 friend class FixBoundsPS;
1281 friend class DuplicateRowsPS;
1282 friend class DuplicateColsPS;
1283 friend class AggregationPS;
1284
1285private:
1286 //------------------------------------
1287 ///@name Types
1288 ///@{
1289 /// Different simplification steps.
1310 ///@}
1311
1312 //------------------------------------
1313 ///@name Data
1314 ///@{
1315 ///
1316 VectorBase<R> m_prim; ///< unsimplified primal solution VectorBase<R>.
1317 VectorBase<R> m_slack; ///< unsimplified slack VectorBase<R>.
1318 VectorBase<R> m_dual; ///< unsimplified dual solution VectorBase<R>.
1319 VectorBase<R> m_redCost; ///< unsimplified reduced cost VectorBase<R>.
1322 DataArray<int> m_cIdx; ///< column index VectorBase<R> in original LP.
1323 DataArray<int> m_rIdx; ///< row index VectorBase<R> in original LP.
1324 Array<std::shared_ptr<PostStep>>m_hist; ///< VectorBase<R> of presolve history.
1326 m_classSetRows; ///< stores parallel classes with non-zero colum entry
1328 m_classSetCols; ///< stores parallel classes with non-zero row entry
1330 m_dupRows; ///< arrange duplicate rows using bucket sort w.r.t. their pClass values
1332 m_dupCols; ///< arrange duplicate columns w.r.t. their pClass values
1333 bool m_postsolved; ///< status of postsolving.
1334 R m_epsilon; ///< epsilon zero.
1335 R m_feastol; ///< primal feasibility tolerance.
1336 R m_opttol; ///< dual feasibility tolerance.
1337 DataArray<int> m_stat; ///< preprocessing history.
1338 typename SPxLPBase<R>::SPxSense m_thesense; ///< optimization sense.
1339 bool m_keepbounds; ///< keep some bounds (for boundflipping)
1340 int m_addedcols; ///< columns added by handleRowObjectives()
1341 typename SPxSimplifier<R>::Result m_result; ///< result of the simplification.
1342 R m_cutoffbound; ///< the cutoff bound that is found by heuristics
1343 R m_pseudoobj; ///< the pseudo objective function value
1344 ///@}
1345
1346private:
1347 //------------------------------------
1348 ///@name Private helpers
1349 ///@{
1350 /// handle row objectives
1352
1353 /// handles extreme values by setting them to zero or R(infinity).
1355
1356 /// computes the minimum and maximum residual activity for a given row and column. If colNumber is set to -1, then
1357 // the activity of the row is returned.
1359 R& maxAct);
1360
1361 /// calculate min/max value for the multi aggregated variables
1363
1364 /// tries to find good lower bound solutions by applying some trivial heuristics
1366
1367 /// checks a solution for feasibility
1369
1370 /// tightens variable bounds by propagating the pseudo objective function value.
1372
1373 /// removed empty rows and empty columns.
1375
1376 /// remove row singletons.
1378 int& i);
1379
1380 /// aggregate two variables that appear in an equation.
1382 int& i);
1383
1384 /// performs simplification steps on the rows of the LP.
1386
1387 /// performs simplification steps on the columns of the LP.
1389
1390 /// performs simplification steps on the LP based on dual concepts.
1392
1393 /// performs multi-aggregations of variable based upon constraint activitu.
1395
1396 /// removes duplicate rows.
1398
1399 /// removes duplicate columns
1401
1402 /// handles the fixing of a variable. correctIdx is true iff the index mapping has to be updated.
1403 void fixColumn(SPxLPBase<R>& lp, int i, bool correctIdx = true);
1404
1405 /// removes a row in the LP.
1407 {
1408 m_rIdx[i] = m_rIdx[lp.nRows() - 1];
1409 lp.removeRow(i);
1410 }
1411 /// removes a column in the LP.
1413 {
1414 m_cIdx[j] = m_cIdx[lp.nCols() - 1];
1415 lp.removeCol(j);
1416 }
1417 /// returns for a given row index of the (reduced) LP the corresponding row index in the unsimplified LP.
1418 int rIdx(int i) const
1419 {
1420 return m_rIdx[i];
1421 }
1422 /// returns for a given column index of the (reduced) LP the corresponding column index in the unsimplified LP.
1423 int cIdx(int j) const
1424 {
1425 return m_cIdx[j];
1426 }
1427 ///@}
1428
1429protected:
1430
1431 ///
1432 R epsZero() const
1433 {
1434 return m_epsilon;
1435 }
1436 ///
1437 R feastol() const
1438 {
1439 return m_feastol;
1440 }
1441 ///
1442 R opttol() const
1443 {
1444 return m_opttol;
1445 }
1446
1447public:
1448
1449 //------------------------------------
1450 ///@name Constructors / destructors
1451 ///@{
1452 /// default constructor.
1467 /// copy constructor.
1493 /// assignment operator
1495 {
1496 if(this != &rhs)
1497 {
1499 m_prim = rhs.m_prim;
1500 m_slack = rhs.m_slack;
1501 m_dual = rhs.m_dual;
1502 m_redCost = rhs.m_redCost;
1505 m_cIdx = rhs.m_cIdx;
1506 m_rIdx = rhs.m_rIdx;
1508 m_epsilon = rhs.m_epsilon;
1509 m_feastol = rhs.m_feastol;
1510 m_opttol = rhs.m_opttol;
1511 m_stat = rhs.m_stat;
1512 m_thesense = rhs.m_thesense;
1515 m_result = rhs.m_result;
1518 m_hist = rhs.m_hist;
1519 }
1520
1521
1522 return *this;
1523 }
1524 /// destructor.
1525 virtual ~SPxMainSM()
1526 {
1527 ;
1528 }
1529 /// clone function for polymorphism
1530 inline virtual SPxSimplifier<R>* clone() const
1531 {
1532 return new SPxMainSM(*this);
1533 }
1534 ///@}
1535
1536 //------------------------------------
1537 //**@name LP simplification */
1538 ///@{
1539 /// simplify SPxLPBase<R> \p lp with identical primal and dual feasibility tolerance.
1540 virtual typename SPxSimplifier<R>::Result simplify(SPxLPBase<R>& lp, R eps, R delta,
1542 {
1543 return simplify(lp, eps, delta, delta, remainingTime);
1544 }
1545 /// simplify SPxLPBase<R> \p lp with independent primal and dual feasibility tolerance.
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 {
1571 return m_prim;
1572 }
1573 /// returns a reference to the unsimplified dual solution.
1575 {
1577 return m_dual;
1578 }
1579 /// returns a reference to the unsimplified slack values.
1581 {
1583 return m_slack;
1584 }
1585 /// returns a reference to the unsimplified reduced costs.
1587 {
1589 return m_redCost;
1590 }
1591 /// gets basis status for a single row.
1593 {
1595 return m_rBasisStat[i];
1596 }
1597 /// gets basis status for a single column.
1599 {
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 {
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 const typename SVectorBase<R>::Element& e2) const
1631 {
1632 if(EQ(e1.val, e2.val))
1633 return 0;
1634
1635 if(e1.val < e2.val)
1636 return -1;
1637 else // (e1.val > e2.val)
1638 return 1;
1639 }
1640 };
1641 /// comparator for class SVectorBase<R>::Element: compare nonzeros according to index
1643 {
1644 public:
1646
1648 const typename SVectorBase<R>::Element& e2) const
1649 {
1650 if(EQ(e1.idx, e2.idx))
1651 return 0;
1652
1653 if(e1.idx < e2.idx)
1654 return -1;
1655 else // (e1.idx > e2.idx)
1656 return 1;
1657 }
1658 };
1659 ///@}
1660};
1661
1662} // namespace soplex
1663
1664// For including general templated functions
1665#include "spxmainsm.hpp"
1666
1667#endif // _SPXMAINSM_H_
Save arrays of arbitrary types.
Safe arrays of data objects.
Definition dataarray.h:75
int size() const
return nr. of elements.
Definition dataarray.h:227
Exception class for things that should NEVER happen.
Definition exceptions.h:119
Saving LPs in a form suitable for SoPlex.
Definition spxlpbase.h:108
SPxSense
Optimization sense.
Definition spxlpbase.h:125
Postsolves aggregation.
Definition spxmainsm.h:1072
AggregationPS(const SPxLPBase< R > &lp, int _i, int _j, R rhs, R oldupper, R oldlower)
Definition spxmainsm.h:1089
AggregationPS & operator=(const AggregationPS &rhs)
assignment operator
Definition spxmainsm.h:1123
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:1107
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:1135
Postsolves doubleton equations combined with a column singleton.
Definition spxmainsm.h:811
DoubletonEquationPS(const SPxLPBase< R > &lp, int _j, int _k, int _i, R oldLo, R oldUp)
Definition spxmainsm.h:835
DoubletonEquationPS(const DoubletonEquationPS &old)
copy constructor
Definition spxmainsm.h:858
DoubletonEquationPS & operator=(const DoubletonEquationPS &rhs)
assignment operator
Definition spxmainsm.h:881
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:892
Postsolves duplicate columns.
Definition spxmainsm.h:1004
DuplicateColsPS(const DuplicateColsPS &old)
copy constructor
Definition spxmainsm.h:1033
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
DuplicateColsPS(const SPxLPBase< R > &lp, int _j, int _k, R scale, DataArray< int > perm, bool isFirst=false, bool isTheLast=false)
Definition spxmainsm.h:1018
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:1057
DuplicateColsPS & operator=(const DuplicateColsPS &rhs)
assignment operator
Definition spxmainsm.h:1047
Postsolves duplicate rows.
Definition spxmainsm.h:908
DataArray< bool > m_isLhsEqualRhs
Definition spxmainsm.h:923
DuplicateRowsPS(const DuplicateRowsPS &old)
copy constructor
Definition spxmainsm.h:956
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:974
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, bool isFirst=false)
Definition spxmainsm.h:926
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:989
Postsolves empty constraints.
Definition spxmainsm.h:244
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(const SPxLPBase< R > &lp, int _i)
Definition spxmainsm.h:252
EmptyConstraintPS & operator=(const EmptyConstraintPS &rhs)
assignment operator
Definition spxmainsm.h:266
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:282
EmptyConstraintPS(const EmptyConstraintPS &old)
copy constructor
Definition spxmainsm.h:259
Postsolves variable bound fixing.
Definition spxmainsm.h:534
SPxSolverBase< R >::VarStatus m_status
Definition spxmainsm.h:537
FixBoundsPS(const FixBoundsPS &old)
copy constructor
Definition spxmainsm.h:559
FixBoundsPS & operator=(const FixBoundsPS &rhs)
assignment operator
Definition spxmainsm.h:565
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
FixBoundsPS(const SPxLPBase< R > &lp, int j, R val)
Definition spxmainsm.h:541
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:576
Postsolves variable fixing.
Definition spxmainsm.h:469
DSVectorBase< R > m_col
does the index mapping have to be updated in postsolving?
Definition spxmainsm.h:478
FixVariablePS(const FixVariablePS &old)
copy constructor
Definition spxmainsm.h:497
FixVariablePS(const SPxLPBase< R > &lp, SPxMainSM &simplifier, int _j, const R val, bool correctIdx=true)
Definition spxmainsm.h:482
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:509
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:520
Postsolves forcing constraints.
Definition spxmainsm.h:376
ForceConstraintPS(const ForceConstraintPS &old)
copy constructor
Definition spxmainsm.h:421
ForceConstraintPS & operator=(const ForceConstraintPS &rhs)
assignment operator
Definition spxmainsm.h:439
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
ForceConstraintPS(const SPxLPBase< R > &lp, int _i, bool lhsFixed, DataArray< bool > &fixCols, Array< R > &lo, Array< R > &up)
Definition spxmainsm.h:395
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:455
Array< DSVectorBase< R > > m_cols
Definition spxmainsm.h:384
Postsolves free column singletons.
Definition spxmainsm.h:741
FreeColSingletonPS(const SPxLPBase< R > &lp, SPxMainSM &simplifier, int _j, int _i, R slackVal)
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:784
FreeColSingletonPS(const FreeColSingletonPS &old)
copy constructor
Definition spxmainsm.h:771
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:795
Postsolves unconstraint constraints.
Definition spxmainsm.h:192
FreeConstraintPS(const SPxLPBase< R > &lp, int _i)
Definition spxmainsm.h:201
FreeConstraintPS(const FreeConstraintPS &old)
copy constructor
Definition spxmainsm.h:209
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:217
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:234
Postsolves the case when constraints are removed due to a variable with zero objective that is free i...
Definition spxmainsm.h:593
FreeZeroObjVariablePS(const FreeZeroObjVariablePS &old)
copy constructor
Definition spxmainsm.h:634
FreeZeroObjVariablePS & operator=(const FreeZeroObjVariablePS &rhs)
assignment operator
Definition spxmainsm.h:647
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
FreeZeroObjVariablePS(const SPxLPBase< R > &lp, int _j, bool loFree, DSVectorBase< R > col_idx_sorted)
Definition spxmainsm.h:607
Array< DSVectorBase< R > > m_rows
Definition spxmainsm.h:602
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:661
Postsolves multi aggregation.
Definition spxmainsm.h:1151
MultiAggregationPS(const SPxLPBase< R > &lp, SPxMainSM &simplifier, int _i, int _j, R constant)
Definition spxmainsm.h:1168
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:1187
MultiAggregationPS & operator=(const MultiAggregationPS &rhs)
assignment operator
Definition spxmainsm.h:1203
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:1215
Base class for postsolving operations.
Definition spxmainsm.h:85
PostStep(const char *p_name, int nR=0, int nC=0)
constructor.
Definition spxmainsm.h:96
int nRows
number of rows
Definition spxmainsm.h:92
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:118
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:108
PostStep(const PostStep &old)
copy constructor.
Definition spxmainsm.h:102
virtual ~PostStep()
destructor.
Definition spxmainsm.h:113
Postsolves row objectives.
Definition spxmainsm.h:148
int m_j
slack column index
Definition spxmainsm.h:151
RowObjPS(const SPxLPBase< R > &lp, int _i, int _j)
Definition spxmainsm.h:155
RowObjPS & operator=(const RowObjPS &rhs)
assignment operator
Definition spxmainsm.h:167
RowObjPS(const RowObjPS &old)
copy constructor
Definition spxmainsm.h:161
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:182
Postsolves row singletons.
Definition spxmainsm.h:292
RowSingletonPS(const SPxLPBase< R > &lp, int _i, int _j, bool strictLo, bool strictUp, R newLo, R newUp, R oldLo, R oldUp)
Definition spxmainsm.h:312
RowSingletonPS(const RowSingletonPS &old)
copy constructor
Definition spxmainsm.h:332
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:351
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:362
Postsolves variable bound tightening from pseudo objective propagation.
Definition spxmainsm.h:1231
TightenBoundsPS(const TightenBoundsPS &old)
copy constructor
Definition spxmainsm.h:1247
TightenBoundsPS(const SPxLPBase< R > &lp, int j, R origupper, R origlower)
Definition spxmainsm.h:1239
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:1254
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:1259
Postsolves column singletons with zero objective.
Definition spxmainsm.h:677
ZeroObjColSingletonPS(const SPxLPBase< R > &lp, const SPxMainSM &, int _j, int _i)
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:714
ZeroObjColSingletonPS(const ZeroObjColSingletonPS &old)
copy constructor
Definition spxmainsm.h:702
virtual PostStep * clone() const
clone function for polymorphism
Definition spxmainsm.h:725
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:1423
friend class FixVariablePS
Definition spxmainsm.h:1275
friend class FreeColSingletonPS
Definition spxmainsm.h:1279
SPxMainSM(Timer::TYPE ttype=Timer::USER_TIME)
Definition spxmainsm.h:1453
void removeRow(SPxLPBase< R > &lp, int i)
removes a row in the LP.
Definition spxmainsm.h:1406
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:1468
Array< DSVectorBase< R > > m_classSetRows
stores parallel classes with non-zero colum entry
Definition spxmainsm.h:1326
VectorBase< R > m_slack
unsimplified slack VectorBase<R>.
Definition spxmainsm.h:1317
friend class FixBoundsPS
Definition spxmainsm.h:1276
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:1272
virtual ~SPxMainSM()
destructor.
Definition spxmainsm.h:1525
SPxSimplifier< R >::Result duplicateCols(SPxLPBase< R > &lp, bool &again)
removes duplicate columns
friend class RowSingletonPS
Definition spxmainsm.h:1273
friend class ZeroObjColSingletonPS
Definition spxmainsm.h:1278
SPxSimplifier< R >::Result removeRowSingleton(SPxLPBase< R > &lp, const SVectorBase< R > &row, int &i)
remove row singletons.
R epsZero() const
Definition spxmainsm.h:1432
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:1280
VectorBase< R > m_dual
unsimplified dual solution VectorBase<R>.
Definition spxmainsm.h:1318
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:1418
SPxSimplifier< R >::Result multiaggregation(SPxLPBase< R > &lp, bool &again)
performs multi-aggregations of variable based upon constraint activitu.
friend class DuplicateColsPS
Definition spxmainsm.h:1282
Array< DSVectorBase< R > > m_dupCols
arrange duplicate columns w.r.t. their pClass values
Definition spxmainsm.h:1332
friend class AggregationPS
Definition spxmainsm.h:1283
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:1342
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:1341
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:1316
friend class FreeConstraintPS
Definition spxmainsm.h:1271
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.
R m_opttol
dual feasibility tolerance.
Definition spxmainsm.h:1336
R m_feastol
primal feasibility tolerance.
Definition spxmainsm.h:1335
Array< DSVectorBase< R > > m_dupRows
arrange duplicate rows using bucket sort w.r.t. their pClass values
Definition spxmainsm.h:1330
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:1328
virtual SPxSolverBase< R >::VarStatus getBasisColStatus(int j) const
gets basis status for a single column.
Definition spxmainsm.h:1598
virtual SPxSimplifier< R >::Result simplify(SPxLPBase< R > &lp, R eps, R delta, Real remainingTime)
simplify SPxLPBase<R> lp with identical primal and dual feasibility tolerance.
Definition spxmainsm.h:1540
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:1324
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:1321
R m_epsilon
epsilon zero.
Definition spxmainsm.h:1334
DataArray< int > m_stat
preprocessing history.
Definition spxmainsm.h:1337
VectorBase< R > m_redCost
unsimplified reduced cost VectorBase<R>.
Definition spxmainsm.h:1319
DataArray< int > m_cIdx
column index VectorBase<R> in original LP.
Definition spxmainsm.h:1322
R feastol() const
Definition spxmainsm.h:1437
friend class DuplicateRowsPS
Definition spxmainsm.h:1281
int m_addedcols
columns added by handleRowObjectives()
Definition spxmainsm.h:1340
friend class FreeZeroObjVariablePS
Definition spxmainsm.h:1277
friend class ForceConstraintPS
Definition spxmainsm.h:1274
void removeCol(SPxLPBase< R > &lp, int j)
removes a column in the LP.
Definition spxmainsm.h:1412
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:1333
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:1494
void handleRowObjectives(SPxLPBase< R > &lp)
DataArray< int > m_rIdx
row index VectorBase<R> in original LP.
Definition spxmainsm.h:1323
virtual SPxSimplifier< R > * clone() const
clone function for polymorphism
Definition spxmainsm.h:1530
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:1338
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:1339
DataArray< typename SPxSolverBase< R >::VarStatus > m_cBasisStat
basis status of columns.
Definition spxmainsm.h:1320
virtual SPxSimplifier< R >::Result simplify(SPxLPBase< R > &lp, R eps, R ftol, R otol, Real remainingTime, bool keepbounds=false, uint32_t seed=0)
simplify SPxLPBase<R> lp with independent primal and dual feasibility tolerance.
R m_pseudoobj
the pseudo objective function value
Definition spxmainsm.h:1343
LP simplification abstract base class.
Result
Result of the simplification.
@ OKAY
simplification could be done
SPxSimplifier & operator=(const SPxSimplifier &rhs)
assignment operator
Sequential object-oriented SimPlex.
Definition spxsolver.h:104
TYPE
types of timers
Definition timer.h:109
Exception classes for SoPlex.
Everything should be within this namespace.
THREADLOCAL const Real infinity
double Real
Definition spxdefines.h:266
bool EQ(int a, int b)
void spx_alloc(T &p, int n=1)
Allocate memory.
Definition spxalloc.h:58
Debugging, floating point type and parameter definitions.
#define DEFAULT_BND_VIOL
default allowed bound violation
Definition spxdefines.h:274
#define DEFAULT_EPS_ZERO
default allowed additive zero: 1.0 + EPS_ZERO == 1.0
Definition spxdefines.h:278
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:1629
comparator for class SVectorBase<R>::Element: compare nonzeros according to index
Definition spxmainsm.h:1643
int operator()(const typename SVectorBase< R >::Element &e1, const typename SVectorBase< R >::Element &e2) const
Definition spxmainsm.h:1647