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