SoPlex Documentation
Loading...
Searching...
No Matches
soplex.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 soplex.h
26 * @brief Preconfigured SoPlex LP solver
27 */
28
29#ifndef _SOPLEX_H_
30#define _SOPLEX_H_
31
32#include <string.h>
33
34#include "soplex/spxgithash.h"
35#include "soplex/spxdefines.h"
36#include "soplex/basevectors.h"
37#include "soplex/spxsolver.h"
38#include "soplex/slufactor.h"
40
41///@todo try to move to cpp file by forward declaration
43#include "soplex/spxmainsm.h"
44
45#include "soplex/spxscaler.h"
46#include "soplex/spxequilisc.h"
47#include "soplex/spxleastsqsc.h"
48#include "soplex/spxgeometsc.h"
49
50#include "soplex/spxstarter.h"
51#include "soplex/spxweightst.h"
52#include "soplex/spxsumst.h"
53#include "soplex/spxvectorst.h"
54
55#include "soplex/spxpricer.h"
56#include "soplex/spxautopr.h"
57#include "soplex/spxdantzigpr.h"
58#include "soplex/spxparmultpr.h"
59#include "soplex/spxdevexpr.h"
60#include "soplex/spxsteeppr.h"
61#include "soplex/spxsteepexpr.h"
62#include "soplex/spxhybridpr.h"
63
65#include "soplex/spxdefaultrt.h"
66#include "soplex/spxharrisrt.h"
67#include "soplex/spxfastrt.h"
69
70#include "soplex/solbase.h"
71#include "soplex/sol.h"
72
73#include "soplex/spxlpbase.h"
74
75#include "soplex/spxpapilo.h"
76
77#ifdef SOPLEX_WITH_GMP
78#include <gmp.h>
79#endif
80
81#ifdef SOPLEX_WITH_BOOST
82#ifdef SOPLEX_WITH_MPFR
83// For multiple precision
84#include <boost/multiprecision/mpfr.hpp>
85#endif
86#ifdef SOPLEX_WITH_CPPMPF
87#include <boost/multiprecision/cpp_dec_float.hpp>
88#endif
89
90// An alias for boost multiprecision
91namespace mpf = boost::multiprecision;
92#endif
93
94#define SOPLEX_DEFAULT_RANDOM_SEED 0 // used to suppress output when the seed was not changed
95
96///@todo implement automatic rep switch, based on row/col dim
97///@todo introduce status codes for SoPlex, especially for rational solving
98
99///@todo record and return "best" solutions found during IR (Ambros)
100///@todo implement main IR loop for primal and dual feasible case with fail otherwise (Ambros)
101///@todo implement statistical info (time, factor time, iters, ...) since last call to solveReal() or solveRational() (Ambros?)
102///@todo implement performInfeasibilityIR (Ambros?)
103///@todo extend IR loop to infeasible case (Dan?)
104///@todo extend IR loop to unbounded case (Dan?)
105
106///@todo interface rational reconstruction code for rational vectors
107///@todo integrate rational reconstruction into IR loop
108///@todo integrate rational SPxSolver and distinguish between original and transformed rational LP
109///@todo rational scalers
110///@todo rational simplifier
111
112namespace soplex
113{
114
115/**@class SoPlex
116 * @brief Preconfigured SoPlex LP-solver.
117 * @ingroup Algo
118 */
119template <class R>
121{
122public:
123
124 ///@name Construction and destruction
125 ///@{
126
127 /// default constructor
129
130 /// assignment operator
132
133 /// copy constructor
135
136 /// destructor
137 virtual ~SoPlexBase();
138
139 ///@}
140
141
142 ///@name Access to the real LP
143 ///@{
144
145 /// returns number of rows
146 int numRows() const;
147 int numRowsReal() const; /* For SCIP compatibility */
148 int numRowsRational() const;
149
150 /// Templated function that
151 /// returns number of columns
152 int numCols() const;
153 int numColsReal() const; /* For SCIP compatibility */
154 int numColsRational() const;
155
156 /// returns number of nonzeros
157 int numNonzeros() const;
158
160
161 /// returns smallest non-zero element in absolute value
163
164 /// returns biggest non-zero element in absolute value
166
167 /// returns (unscaled) coefficient
168 R coefReal(int row, int col) const;
169
170 /// returns vector of row \p i, ignoring scaling
172
173 /// gets vector of row \p i
174 void getRowVectorReal(int i, DSVectorBase<R>& row) const;
175
176 /// returns right-hand side vector, ignoring scaling
178
179 /// gets right-hand side vector
180 void getRhsReal(VectorBase<R>& rhs) const;
181
182 /// returns right-hand side of row \p i
183 R rhsReal(int i) const;
184
185 /// returns left-hand side vector, ignoring scaling
187
188 /// gets left-hand side vector
189 void getLhsReal(VectorBase<R>& lhs) const;
190
191 /// returns left-hand side of row \p i
192 R lhsReal(int i) const;
193
194 /// returns inequality type of row \p i
195 typename LPRowBase<R>::Type rowTypeReal(int i) const;
196
197 /// returns vector of col \p i, ignoring scaling
199
200 /// gets vector of col \p i
201 void getColVectorReal(int i, DSVectorBase<R>& col) const;
202
203 /// returns upper bound vector
205
206 /// returns upper bound of column \p i
207 R upperReal(int i) const;
208
209 /// gets upper bound vector
210 void getUpperReal(VectorBase<R>& upper) const;
211
212 /// returns lower bound vector
214
215 /// returns lower bound of column \p i
216 R lowerReal(int i) const;
217
218 /// gets lower bound vector
219 void getLowerReal(VectorBase<R>& lower) const;
220
221 /// gets objective function vector
222 void getObjReal(VectorBase<R>& obj) const;
223
224 /// returns objective value of column \p i
225 R objReal(int i) const;
226
227 /// returns objective function vector after transformation to a maximization problem; since this is how it is stored
228 /// internally, this is generally faster
230
231 /// returns objective value of column \p i after transformation to a maximization problem; since this is how it is
232 /// stored internally, this is generally faster
233 R maxObjReal(int i) const;
234
235 /// gets number of available dual norms
236 void getNdualNorms(int& nnormsRow, int& nnormsCol) const;
237
238 /// gets steepest edge norms and returns false if they are not available
239 bool getDualNorms(int& nnormsRow, int& nnormsCol, R* norms) const;
240
241 /// sets steepest edge norms and returns false if that's not possible
242 bool setDualNorms(int nnormsRow, int nnormsCol, R* norms);
243
244 /// pass integrality information about the variables to the solver
245 void setIntegralityInformation(int ncols, int* intInfo);
246
247 ///@}
248
249
250 ///@name Access to the rational LP
251 ///@{
252
253 /// returns smallest non-zero element in absolute value
255
256 /// returns biggest non-zero element in absolute value
258
259 /// gets row \p i
260 void getRowRational(int i, LPRowRational& lprow) const;
261
262 /// gets rows \p start, ..., \p end.
263 void getRowsRational(int start, int end, LPRowSetRational& lprowset) const;
264
265 /// returns vector of row \p i
267
268 /// returns right-hand side vector
270
271 /// returns right-hand side of row \p i
272 const Rational& rhsRational(int i) const;
273
274 /// returns left-hand side vector
276
277 /// returns left-hand side of row \p i
278 const Rational& lhsRational(int i) const;
279
280 /// returns inequality type of row \p i
282
283 /// gets column \p i
284 void getColRational(int i, LPColRational& lpcol) const;
285
286 /// gets columns \p start, ..., \p end
287 void getColsRational(int start, int end, LPColSetRational& lpcolset) const;
288
289 /// returns vector of column \p i
291
292 /// returns upper bound vector
294
295 /// returns upper bound of column \p i
296 const Rational& upperRational(int i) const;
297
298 /// returns lower bound vector
300
301 /// returns lower bound of column \p i
302 const Rational& lowerRational(int i) const;
303
304 /// gets objective function vector
306
307 /// gets objective value of column \p i
308 void getObjRational(int i, Rational& obj) const;
309
310 /// returns objective value of column \p i
311 Rational objRational(int i) const;
312
313 /// returns objective function vector after transformation to a maximization problem; since this is how it is stored
314 /// internally, this is generally faster
316
317 /// returns objective value of column \p i after transformation to a maximization problem; since this is how it is
318 /// stored internally, this is generally faster
319 const Rational& maxObjRational(int i) const;
320
321 ///@}
322
323
324 ///@name Modification of the real LP
325 ///@{
326
327 /// adds a single row
328 void addRowReal(const LPRowBase<R>& lprow);
329
330 /// adds multiple rows
331 void addRowsReal(const LPRowSetBase<R>& lprowset);
332
333 /// adds a single column
334 void addColReal(const LPColBase<R>& lpcol);
335
336 /// adds multiple columns
337 void addColsReal(const LPColSetBase<R>& lpcolset);
338
339 /// replaces row \p i with \p lprow
340 void changeRowReal(int i, const LPRowBase<R>& lprow);
341
342 /// changes left-hand side vector for constraints to \p lhs
343 void changeLhsReal(const VectorBase<R>& lhs);
344
345 /// changes left-hand side of row \p i to \p lhs
346 void changeLhsReal(int i, const R& lhs);
347
348 /// changes right-hand side vector to \p rhs
349 void changeRhsReal(const VectorBase<R>& rhs);
350
351 /// changes right-hand side of row \p i to \p rhs
352 void changeRhsReal(int i, const R& rhs);
353
354 /// changes left- and right-hand side vectors
355 void changeRangeReal(const VectorBase<R>& lhs, const VectorBase<R>& rhs);
356
357 /// changes left- and right-hand side of row \p i
358 void changeRangeReal(int i, const R& lhs, const R& rhs);
359
360 /// replaces column \p i with \p lpcol
361 void changeColReal(int i, const LPColReal& lpcol);
362
363 /// changes vector of lower bounds to \p lower
364 void changeLowerReal(const VectorBase<R>& lower);
365
366 /// changes lower bound of column i to \p lower
367 void changeLowerReal(int i, const R& lower);
368
369 /// changes vector of upper bounds to \p upper
370 void changeUpperReal(const VectorBase<R>& upper);
371
372 /// changes \p i 'th upper bound to \p upper
373 void changeUpperReal(int i, const R& upper);
374
375 /// changes vectors of column bounds to \p lower and \p upper
376 void changeBoundsReal(const VectorBase<R>& lower, const VectorBase<R>& upper);
377
378 /// changes bounds of column \p i to \p lower and \p upper
379 void changeBoundsReal(int i, const R& lower, const R& upper);
380
381 /// changes objective function vector to \p obj
382 void changeObjReal(const VectorBase<R>& obj);
383
384 /// changes objective coefficient of column i to \p obj
385 void changeObjReal(int i, const R& obj);
386
387 /// changes matrix entry in row \p i and column \p j to \p val
388 void changeElementReal(int i, int j, const R& val);
389
390 /// removes row \p i
391 void removeRowReal(int i);
392
393 /// removes all rows with an index \p i such that \p perm[i] < 0; upon completion, \p perm[i] >= 0 indicates the
394 /// new index where row \p i has been moved to; note that \p perm must point to an array of size at least
395 /// #numRows()
396 void removeRowsReal(int perm[]);
397
398 /// remove all rows with indices in array \p idx of size \p n; an array \p perm of size #numRows() may be passed
399 /// as buffer memory
400 void removeRowsReal(int idx[], int n, int perm[] = 0);
401
402 /// removes rows \p start to \p end including both; an array \p perm of size #numRows() may be passed as buffer
403 /// memory
404 void removeRowRangeReal(int start, int end, int perm[] = 0);
405
406 /// removes column i
407 void removeColReal(int i);
408
409 /// removes all columns with an index \p i such that \p perm[i] < 0; upon completion, \p perm[i] >= 0 indicates the
410 /// new index where column \p i has been moved to; note that \p perm must point to an array of size at least
411 /// #numColsReal()
412 void removeColsReal(int perm[]);
413
414 /// remove all columns with indices in array \p idx of size \p n; an array \p perm of size #numColsReal() may be
415 /// passed as buffer memory
416 void removeColsReal(int idx[], int n, int perm[] = 0);
417
418 /// removes columns \p start to \p end including both; an array \p perm of size #numColsReal() may be passed as
419 /// buffer memory
420 void removeColRangeReal(int start, int end, int perm[] = 0);
421
422 /// clears the LP
424
425 /// synchronizes real LP with rational LP, i.e., copies (rounded) rational LP into real LP, if sync mode is manual
427
428 ///@}
429
430
431 ///@name Modification of the rational LP
432 ///@{
433
434 /// adds a single row
435 void addRowRational(const LPRowRational& lprow);
436
437#ifdef SOPLEX_WITH_GMP
438 /// adds a single row (GMP only method)
439 void addRowRational(const mpq_t* lhs, const mpq_t* rowValues, const int* rowIndices,
440 const int rowSize, const mpq_t* rhs);
441
442 /// adds a set of rows (GMP only method)
443 void addRowsRational(const mpq_t* lhs, const mpq_t* rowValues, const int* rowIndices,
444 const int* rowStarts, const int* rowLengths, const int numRows, const int numValues,
445 const mpq_t* rhs);
446#endif
447
448 /// adds multiple rows
449 void addRowsRational(const LPRowSetRational& lprowset);
450
451 /// adds a single column
452 void addColRational(const LPColRational& lpcol);
453
454#ifdef SOPLEX_WITH_GMP
455 /// adds a single column (GMP only method)
456 void addColRational(const mpq_t* obj, const mpq_t* lower, const mpq_t* colValues,
457 const int* colIndices, const int colSize, const mpq_t* upper);
458
459 /// adds a set of columns (GMP only method)
460 void addColsRational(const mpq_t* obj, const mpq_t* lower, const mpq_t* colValues,
461 const int* colIndices, const int* colStarts, const int* colLengths, const int numCols,
462 const int numValues, const mpq_t* upper);
463#endif
464
465 /// adds multiple columns
466 void addColsRational(const LPColSetRational& lpcolset);
467
468 /// replaces row \p i with \p lprow
469 void changeRowRational(int i, const LPRowRational& lprow);
470
471 /// changes left-hand side vector for constraints to \p lhs
473
474 /// changes left-hand side of row \p i to \p lhs
475 void changeLhsRational(int i, const Rational& lhs);
476
477#ifdef SOPLEX_WITH_GMP
478 /// changes left-hand side of row \p i to \p lhs (GMP only method)
479 void changeLhsRational(int i, const mpq_t* lhs);
480#endif
481
482 /// changes right-hand side vector to \p rhs
484
485#ifdef SOPLEX_WITH_GMP
486 /// changes right-hand side vector to \p rhs (GMP only method)
487 void changeRhsRational(const mpq_t* rhs, int rhsSize);
488#endif
489
490 /// changes right-hand side of row \p i to \p rhs
491 void changeRhsRational(int i, const Rational& rhs);
492
493 /// changes left- and right-hand side vectors
495
496 /// changes left- and right-hand side of row \p i
497 void changeRangeRational(int i, const Rational& lhs, const Rational& rhs);
498
499#ifdef SOPLEX_WITH_GMP
500 /// changes left- and right-hand side of row \p i (GMP only method)
501 void changeRangeRational(int i, const mpq_t* lhs, const mpq_t* rhs);
502#endif
503
504 /// replaces column \p i with \p lpcol
505 void changeColRational(int i, const LPColRational& lpcol);
506
507 /// changes vector of lower bounds to \p lower
509
510 /// changes lower bound of column i to \p lower
511 void changeLowerRational(int i, const Rational& lower);
512
513#ifdef SOPLEX_WITH_GMP
514 /// changes lower bound of column i to \p lower (GMP only method)
515 void changeLowerRational(int i, const mpq_t* lower);
516#endif
517
518 /// changes vector of upper bounds to \p upper
520
521 /// changes \p i 'th upper bound to \p upper
522 void changeUpperRational(int i, const Rational& upper);
523
524#ifdef SOPLEX_WITH_GMP
525 /// changes upper bound of column i to \p upper (GMP only method)
526 void changeUpperRational(int i, const mpq_t* upper);
527#endif
528
529 /// changes vectors of column bounds to \p lower and \p upper
530 void changeBoundsRational(const VectorRational& lower, const VectorRational& upper);
531
532 /// changes bounds of column \p i to \p lower and \p upper
533 void changeBoundsRational(int i, const Rational& lower, const Rational& upper);
534
535#ifdef SOPLEX_WITH_GMP
536 /// changes bounds of column \p i to \p lower and \p upper (GMP only method)
537 void changeBoundsRational(int i, const mpq_t* lower, const mpq_t* upper);
538#endif
539
540 /// changes objective function vector to \p obj
542
543 /// changes objective coefficient of column i to \p obj
544 void changeObjRational(int i, const Rational& obj);
545
546#ifdef SOPLEX_WITH_GMP
547 /// changes objective coefficient of column i to \p obj (GMP only method)
548 void changeObjRational(int i, const mpq_t* obj);
549#endif
550
551 /// changes matrix entry in row \p i and column \p j to \p val
552 void changeElementRational(int i, int j, const Rational& val);
553
554#ifdef SOPLEX_WITH_GMP
555 /// changes matrix entry in row \p i and column \p j to \p val (GMP only method)
556 void changeElementRational(int i, int j, const mpq_t* val);
557#endif
558
559 /// removes row \p i
560 void removeRowRational(int i);
561
562 /// removes all rows with an index \p i such that \p perm[i] < 0; upon completion, \p perm[i] >= 0 indicates the new
563 /// index where row \p i has been moved to; note that \p perm must point to an array of size at least
564 /// #numRowsRational()
565 void removeRowsRational(int perm[]);
566
567 /// remove all rows with indices in array \p idx of size \p n; an array \p perm of size #numRowsRational() may be
568 /// passed as buffer memory
569 void removeRowsRational(int idx[], int n, int perm[] = 0);
570
571 /// removes rows \p start to \p end including both; an array \p perm of size #numRowsRational() may be passed as
572 /// buffer memory
573 void removeRowRangeRational(int start, int end, int perm[] = 0);
574
575 /// removes column i
576 void removeColRational(int i);
577
578 /// removes all columns with an index \p i such that \p perm[i] < 0; upon completion, \p perm[i] >= 0 indicates the
579 /// new index where column \p i has been moved to; note that \p perm must point to an array of size at least
580 /// #numColsRational()
581 void removeColsRational(int perm[]);
582
583 /// remove all columns with indices in array \p idx of size \p n; an array \p perm of size #numColsRational() may be
584 /// passed as buffer memory
585 void removeColsRational(int idx[], int n, int perm[] = 0);
586
587 /// removes columns \p start to \p end including both; an array \p perm of size #numColsRational() may be passed as
588 /// buffer memory
589 void removeColRangeRational(int start, int end, int perm[] = 0);
590
591 /// clears the LP
593
594 /// synchronizes rational LP with real LP, i.e., copies real LP to rational LP, if sync mode is manual
596
597 ///@}
598
599 ///@name Solving and general solution query
600 ///@{
601
602 /// optimize the given LP
603 typename SPxSolverBase<R>::Status optimize(volatile bool* interrupt = NULL);
604
605 // old name for backwards compatibility
606 typename SPxSolverBase<R>::Status solve(volatile bool* interrupt = NULL)
607 {
608 return optimize(interrupt);
609 }
610
611 /// returns the current solver status
613
614 /// is stored primal solution feasible?
615 bool isPrimalFeasible() const;
616
617 /// is a solution available (not neccessarily feasible)?
618 bool hasSol() const;
619
620 /// deprecated: use #hasSol() instead
621 bool hasPrimal() const
622 {
623 return hasSol();
624 }
625
626 /// deprecated: use #hasSol() instead
627 bool hasDual() const
628 {
629 return hasSol();
630 }
631
632 /// is a primal unbounded ray available?
633 bool hasPrimalRay() const;
634
635 /// is stored dual solution feasible?
636 bool isDualFeasible() const;
637
638 /// is Farkas proof of infeasibility available?
639 bool hasDualFarkas() const;
640
641 /// sets the status to OPTIMAL in case the LP has been solved with unscaled violations
643 {
645 {
647 return true;
648 }
649 else
650 return false;
651 }
652 ///@}
653
654
655 ///@name Query for the real solution data
656 ///@{
657
658 /// returns the objective value if a primal solution is available
660
661 /// gets the primal solution vector if available; returns true on success
663 bool getPrimalReal(R* p_vector, int size); // For SCIP compatibility
665
666 /// gets the vector of slack values if available; returns true on success
668 bool getSlacksReal(R* p_vector, int dim);
669
670 /// gets the primal ray if available; returns true on success
672 bool getPrimalRayReal(R* vector, int dim); /* For SCIP compatibility */
674
675 /// gets the dual solution vector if available; returns true on success
676 bool getDual(VectorBase<R>& vector);
677 bool getDualReal(R* p_vector, int dim); /* For SCIP compatibility */
679
680 /// gets the vector of reduced cost values if available; returns true on success
682 bool getRedCostReal(R* vector, int dim); /* For SCIP compatibility */
684
685 /// gets the Farkas proof if available; returns true on success
687 bool getDualFarkasReal(R* vector, int dim);
689
690 /// gets violation of bounds; returns true on success
691 bool getBoundViolation(R& maxviol, R& sumviol);
693
694 /// gets violation of constraints; returns true on success
695 bool getRowViolation(R& maxviol, R& sumviol);
696 bool getRowViolationRational(Rational& maxviol, Rational& sumviol);
697
698 /// gets violation of reduced costs; returns true on success
699 bool getRedCostViolation(R& maxviol, R& sumviol);
701
702 /// gets violation of dual multipliers; returns true on success
703 bool getDualViolation(R& maxviol, R& sumviol);
705
706 ///@}
707
708
709 ///@name Query for the rational solution data
710 ///@{
711
712 /// returns the objective value if a primal solution is available
714
715 /// gets the vector of slack values if available; returns true on success
717
718#ifdef SOPLEX_WITH_GMP
719 /// gets the primal solution vector if available; returns true on success (GMP only method)
720 bool getPrimalRational(mpq_t* vector, const int size);
721
722 /// gets the vector of slack values if available; returns true on success (GMP only method)
723 bool getSlacksRational(mpq_t* vector, const int size);
724
725 /// gets the primal ray if LP is unbounded; returns true on success (GMP only method)
726 bool getPrimalRayRational(mpq_t* vector, const int size);
727
728 /// gets the dual solution vector if available; returns true on success (GMP only method)
729 bool getDualRational(mpq_t* vector, const int size);
730
731 /// gets the vector of reduced cost values if available; returns true on success (GMP only method)
732 bool getRedCostRational(mpq_t* vector, const int size);
733
734 /// gets the Farkas proof if LP is infeasible; returns true on success (GMP only method)
735 bool getDualFarkasRational(mpq_t* vector, const int size);
736#endif
737
738 /// get size of primal solution
739 int totalSizePrimalRational(const int base = 2);
740
741 /// get size of dual solution
742 int totalSizeDualRational(const int base = 2);
743
744 /// get size of least common multiple of denominators in primal solution
745 int dlcmSizePrimalRational(const int base = 2);
746
747 /// get size of least common multiple of denominators in dual solution
748 int dlcmSizeDualRational(const int base = 2);
749
750 /// get size of largest denominator in primal solution
751 int dmaxSizePrimalRational(const int base = 2);
752
753 /// get size of largest denominator in dual solution
754 int dmaxSizeDualRational(const int base = 2);
755
756 ///@}
757
758
759 ///@name Access and modification of basis information
760 ///@{
761
762 /// is an advanced starting basis available?
763 bool hasBasis() const;
764
765 /// returns the current basis status
767
768 /// returns basis status for a single row
770
771 /// returns basis status for a single column
773
774 /// gets current basis via arrays of statuses
776 typename SPxSolverBase<R>::VarStatus cols[]) const;
777
778 /// gets the indices of the basic columns and rows; basic column n gives value n, basic row m gives value -1-m
779 void getBasisInd(int* bind) const;
780
781 /** compute one of several matrix metrics based on the diagonal of the LU factorization
782 * type = 0: max/min ratio
783 * type = 1: trace of U (sum of diagonal elements)
784 * type = 2: determinant (product of diagonal elements)
785 */
786 bool getBasisMetric(R& metric, int type = 0);
787
788 /// computes an estimated condition number for the current basis matrix using the power method; returns true on success
789 bool getEstimatedCondition(R& condition);
790
791 /// computes the exact condition number for the current basis matrix using the power method; returns true on success
792 bool getExactCondition(R& condition);
793
794 /// computes row \p r of basis inverse; returns true on success
795 /// @param r which row of the basis inverse is computed
796 /// @param coef values of result vector (not packed but scattered)
797 /// @param inds indices of result vector (NULL if not to be used)
798 /// @param ninds number of nonzeros in result vector
799 /// @param unscale determines whether the result should be unscaled according to the original LP data
800 bool getBasisInverseRowReal(int r, R* coef, int* inds = NULL, int* ninds = NULL,
801 bool unscale = true);
802
803 /// computes column \p c of basis inverse; returns true on success
804 /// @param c which column of the basis inverse is computed
805 /// @param coef values of result vector (not packed but scattered)
806 /// @param inds indices of result vector (NULL if not to be used)
807 /// @param ninds number of nonzeros in result vector
808 /// @param unscale determines whether the result should be unscaled according to the original LP data
809 bool getBasisInverseColReal(int c, R* coef, int* inds = NULL, int* ninds = NULL,
810 bool unscale = true);
811
812 /// computes dense solution of basis matrix B * \p sol = \p rhs; returns true on success
813 bool getBasisInverseTimesVecReal(R* rhs, R* sol, bool unscale = true);
814
815 /// multiply with basis matrix; B * \p vec (inplace)
816 /// @param vec (dense) vector to be multiplied with
817 /// @param unscale determines whether the result should be unscaled according to the original LP data
818 bool multBasis(R* vec, bool unscale = true);
819
820 /// multiply with transpose of basis matrix; \p vec * B^T (inplace)
821 /// @param vec (dense) vector to be multiplied with
822 /// @param unscale determines whether the result should be unscaled according to the original LP data
823 bool multBasisTranspose(R* vec, bool unscale = true);
824
825 /// compute rational basis inverse; returns true on success
827
828 /// gets an array of indices for the columns of the rational basis matrix; bind[i] >= 0 means that the i-th column of
829 /// the basis matrix contains variable bind[i]; bind[i] < 0 means that the i-th column of the basis matrix contains
830 /// the slack variable for row -bind[i]-1; performs rational factorization if not available; returns true on success
832
833 /// computes row r of basis inverse; performs rational factorization if not available; returns true on success
835
836 /// computes column c of basis inverse; performs rational factorization if not available; returns true on success
838
839 /// computes solution of basis matrix B * sol = rhs; performs rational factorization if not available; returns true
840 /// on success
842
843 /// sets starting basis via arrays of statuses
844 void setBasis(const typename SPxSolverBase<R>::VarStatus rows[],
845 const typename SPxSolverBase<R>::VarStatus cols[]);
846
847 /// clears starting basis
849
850 ///@}
851
852
853 ///@name Statistical information
854 ///@{
855
856 /// number of iterations since last call to solve
857 int numIterations() const;
858
859 /// number of precision boosts since last call to solve
861
862 /// number of iterations in higher precision since last call to solve
864
865 /// time spen in higher precision since last call to solve
867
868 /// time spent in last call to solve
870
871 /// statistical information in form of a string
872 std::string statisticString() const;
873
874 /// name of starter
875 const char* getStarterName();
876
877 /// name of simplifier
878 const char* getSimplifierName();
879
880 /// name of scaling method
881 const char* getScalerName();
882
883 /// name of currently loaded pricer
884 const char* getPricerName();
885
886 /// name of currently loaded ratiotester
887 const char* getRatiotesterName();
888
889 ///@}
890
891
892 ///@name File I/O
893 ///@{
894
895 /// reads LP file in LP or MPS format according to READMODE parameter; gets row names, column names, and
896 /// integer variables if desired; returns true on success
897 bool readFile(const char* filename, NameSet* rowNames = 0, NameSet* colNames = 0,
898 DIdxSet* intVars = 0);
899
900 /// Templated write function
901 /// Real
902 /// writes real LP to file; LP or MPS format is chosen from the extension in \p filename; if \p rowNames and \p
903 /// colNames are \c NULL, default names are used; if \p intVars is not \c NULL, the variables contained in it are
904 /// marked as integer; returns true on success
905 /// Rational
906 /// writes rational LP to file; LP or MPS format is chosen from the extension in \p filename; if \p rowNames and \p
907 /// colNames are \c NULL, default names are used; if \p intVars is not \c NULL, the variables contained in it are
908 /// marked as integer; returns true on success
909 bool writeFile(const char* filename, const NameSet* rowNames = 0, const NameSet* colNames = 0,
910 const DIdxSet* intvars = 0, const bool unscale = true) const;
911
912 bool writeFileRational(const char* filename, const NameSet* rowNames = 0,
913 const NameSet* colNames = 0, const DIdxSet* intvars = 0) const;
914
915 /* For SCIP compatibility */
916 bool writeFileReal(const char* filename, const NameSet* rowNames = 0, const NameSet* colNames = 0,
917 const DIdxSet* intvars = 0, const bool unscale = true) const;
918
919 /// writes the dual of the real LP to file; LP or MPS format is chosen from the extension in \p filename;
920 /// if \p rowNames and \p colNames are \c NULL, default names are used; if \p intVars is not \c NULL,
921 /// the variables contained in it are marked as integer; returns true on success
922 bool writeDualFileReal(const char* filename, const NameSet* rowNames = 0,
923 const NameSet* colNames = 0, const DIdxSet* intvars = 0) const;
924
925 /// reads basis information from \p filename and returns true on success; if \p rowNames and \p colNames are \c NULL,
926 /// default names are assumed; returns true on success
927 bool readBasisFile(const char* filename, const NameSet* rowNames = 0, const NameSet* colNames = 0);
928
929 /// writes basis information to \p filename; if \p rowNames and \p colNames are \c NULL, default names are used;
930 /// returns true on success
931 bool writeBasisFile(const char* filename, const NameSet* rowNames = 0, const NameSet* colNames = 0,
932 const bool cpxFormat = false) const;
933
934 /// writes internal LP, basis information, and parameter settings; if \p rowNames and \p colNames are \c NULL,
935 /// default names are used
936 void writeStateReal(const char* filename, const NameSet* rowNames = 0, const NameSet* colNames = 0,
937 const bool cpxFormat = false) const;
938
939 /// writes internal LP, basis information, and parameter settings; if \p rowNames and \p colNames are \c NULL,
940 /// default names are used
941 void writeStateRational(const char* filename, const NameSet* rowNames = 0,
942 const NameSet* colNames = 0, const bool cpxFormat = false) const;
943
944 ///@}
945
946
947 ///@name Parameters
948 ///@{
949
950 /// boolean parameters
951 typedef enum
952 {
953 /// should lifting be used to reduce range of nonzero matrix coefficients?
955
956 /// should LP be transformed to equality form before a rational solve?
958
959 /// should dual infeasibility be tested in order to try to return a dual solution even if primal infeasible?
961
962 /// should a rational factorization be performed after iterative refinement?
964
965 /// should cycling solutions be accepted during iterative refinement?
967
968 /// apply rational reconstruction after each iterative refinement?
970
971 /// round scaling factors for iterative refinement to powers of two?
973
974 /// continue iterative refinement with exact basic solution if not optimal?
976
977 /// use bound flipping also for row representation?
979
980 /// use persistent scaling?
982
983 /// perturb the entire problem or only the relevant bounds of s single pivot?
985
986 /// re-optimize the original problem to get a proof (ray) of infeasibility/unboundedness?
988
989 /// try to enforce that the optimal solution is a basic solution
991
992 // enable presolver SingletonCols in PaPILO?
994
995 // enable presolver ConstraintPropagation in PaPILO?
997
998 // enable presolver ParallelRowDetection in PaPILO?
1000
1001 // enable presolver ParallelColDetection in PaPILO?
1003
1004 // enable presolver SingletonStuffing in PaPILO?
1006
1007 // enable presolver DualFix in PaPILO?
1009
1010 // enable presolver FixContinuous in PaPILO?
1012
1013 // enable presolver DominatedCols in PaPILO?
1015
1016 // enable iterative refinement ?
1018
1019 /// adapt tolerances to the multiprecision used
1021
1022 /// enable precision boosting ?
1024
1025 /// boosted solver start from last basis
1027
1028 /// try different settings when solve fails
1030
1031 /// store advanced and stable basis met before each simplex iteration, to better warm start
1033
1034 /// number of boolean parameters
1035 BOOLPARAM_COUNT = 27
1037
1038 /// integer parameters
1039 typedef enum
1040 {
1041 /// objective sense
1043
1044 /// type of computational form, i.e., column or row representation
1046
1047 /// type of algorithm, i.e., primal or dual
1049
1050 /// type of LU update
1052
1053 /// maximum number of updates without fresh factorization
1055
1056 /// iteration limit (-1 if unlimited)
1058
1059 /// refinement limit (-1 if unlimited)
1061
1062 /// stalling refinement limit (-1 if unlimited)
1064
1065 /// display frequency
1067
1068 /// verbosity level
1070
1071 /// type of simplifier
1073
1074 /// type of scaler
1076
1077 /// type of starter used to create crash basis
1079
1080 /// type of pricer
1082
1083 /// type of ratio test
1085
1086 /// mode for synchronizing real and rational LP
1088
1089 /// mode for reading LP files
1091
1092 /// mode for iterative refinement strategy
1094
1095 /// mode for a posteriori feasibility checks
1097
1098 /// type of timer
1099 TIMER = 19,
1100
1101 /// mode for hyper sparse pricing
1103
1104 /// minimum number of stalling refinements since last pivot to trigger rational factorization
1106
1107 /// maximum number of conjugate gradient iterations in least square scaling
1109
1110 /// mode for solution polishing
1112
1113 /// print condition number during the solve
1115
1116 /// type of timer for statistics
1118
1119 // maximum number of digits for the multiprecision type
1121
1122 ///@todo precision-boosting find better parameter name
1123 /// after how many simplex pivots do we store the advanced and stable basis, 1 = every iterations
1125
1126 /// number of integer parameters
1127 INTPARAM_COUNT = 28
1129
1130 /// values for parameter OBJSENSE
1131 enum
1132 {
1133 /// minimization
1135
1136 /// maximization
1139
1140 /// values for parameter REPRESENTATION
1141 enum
1142 {
1143 /// automatic choice according to number of rows and columns
1145
1146 /// column representation Ax - s = 0, lower <= x <= upper, lhs <= s <= rhs
1148
1149 /// row representation (lower,lhs) <= (x,Ax) <= (upper,rhs)
1152
1153 /// values for parameter ALGORITHM
1154 enum
1155 {
1156 /// primal simplex algorithm, i.e., entering for column and leaving for row representation
1158
1159 /// dual simplex algorithm, i.e., leaving for column and entering for row representation
1160 ALGORITHM_DUAL = 1
1162
1163 /// values for parameter FACTOR_UPDATE_TYPE
1164 enum
1165 {
1166 /// product form update
1168
1169 /// Forrest-Tomlin type update
1172
1173 /// values for parameter VERBOSITY
1174 enum
1175 {
1176 /// only error output
1178
1179 /// only error and warning output
1181
1182 /// only error, warning, and debug output
1184
1185 /// standard verbosity level
1187
1188 /// high verbosity level
1190
1191 /// full verbosity level
1192 VERBOSITY_FULL = 5
1194
1195 /// values for parameter SIMPLIFIER
1196 enum
1197 {
1198 /// disabling presolving
1200
1201 /// using internal presolving methods
1203
1204 /// using the presolve lib papilo
1206
1207 /// SoPlex chooses automatically (currently always "internal")
1208 SIMPLIFIER_AUTO = 1
1210
1211 /// values for parameter SCALER
1212 enum
1213 {
1214 /// no scaler
1216
1217 /// equilibrium scaling on rows or columns
1219
1220 /// equilibrium scaling on rows and columns
1222
1223 /// geometric mean scaling on rows and columns, max 1 round
1225
1226 /// geometric mean scaling on rows and columns, max 8 rounds
1228
1229 /// least square scaling
1231
1232 /// geometric mean scaling (max 8 rounds) followed by equilibrium scaling (rows and columns)
1233 SCALER_GEOEQUI = 6
1235
1236 /// values for parameter STARTER
1237 enum
1238 {
1239 /// slack basis
1241
1242 /// greedy crash basis weighted by objective, bounds, and sides
1244
1245 /// crash basis from a greedy solution
1247
1248 /// generic solution-based crash basis
1249 STARTER_VECTOR = 3
1251
1252 /// values for parameter PRICER
1253 enum
1254 {
1255 /// automatic pricer
1257
1258 /// Dantzig pricer
1260
1261 /// partial multiple pricer based on Dantzig pricing
1263
1264 /// devex pricer
1266
1267 /// steepest edge pricer with initialization to unit norms
1269
1270 /// steepest edge pricer with exact initialization of norms
1271 PRICER_STEEP = 5
1273
1274 /// values for parameter RATIOTESTER
1275 enum
1276 {
1277 /// textbook ratio test without stabilization
1279
1280 /// standard Harris ratio test
1282
1283 /// modified Harris ratio test
1285
1286 /// bound flipping ratio test for long steps in the dual simplex
1289
1290 /// values for parameter SYNCMODE
1291 enum
1292 {
1293 /// store only real LP
1295
1296 /// automatic sync of real and rational LP
1298
1299 /// user sync of real and rational LP
1300 SYNCMODE_MANUAL = 2
1302
1303 /// values for parameter READMODE
1304 enum
1305 {
1306 /// standard floating-point parsing
1308
1309 /// rational parsing
1312
1313 /// values for parameter SOLVEMODE
1314 enum
1315 {
1316 /// apply standard floating-point algorithm
1318
1319 /// decide depending on tolerances whether to apply iterative refinement
1321
1322 /// force iterative refinement
1325
1326 /// values for parameter CHECKMODE
1327 enum
1328 {
1329 /// floating-point check
1331
1332 /// decide according to READMODE
1334
1335 /// rational check
1338
1339 /// values for parameter TIMER
1340 enum
1341 {
1342 /// disable timing
1344
1345 /// cpu or user time
1347
1348 /// wallclock time
1349 TIMER_WALLCLOCK = 2
1351
1352 /// values for parameter HYPER_PRICING
1353 enum
1354 {
1355 /// never
1357
1358 /// decide according to problem size
1360
1361 /// always
1364
1365 /// values for parameter SOLUTION_POLISHING
1366 enum
1367 {
1368 /// no solution polishing
1370
1371 /// maximize number of basic slack variables, i.e. more variables on bounds
1373
1374 /// minimize number of basic slack variables, i.e. more variables between bounds
1377
1378 /// real parameters
1379 typedef enum
1380 {
1381 /// primal feasibility tolerance
1383
1384 /// dual feasibility tolerance
1386
1387 /// general zero tolerance
1389
1390 /// zero tolerance used in factorization
1392
1393 /// zero tolerance used in update of the factorization
1395
1396 /// pivot zero tolerance used in factorization
1398
1399 /// infinity threshold
1401
1402 /// time limit in seconds (INFTY if unlimited)
1404
1405 /// lower limit on objective value
1407
1408 /// upper limit on objective value
1410
1411 /// working tolerance for feasibility in floating-point solver during iterative refinement
1413
1414 /// working tolerance for optimality in floating-point solver during iterative refinement
1416
1417 /// maximum increase of scaling factors between refinements
1419
1420 /// lower threshold in lifting (nonzero matrix coefficients with smaller absolute value will be reformulated)
1422
1423 /// upper threshold in lifting (nonzero matrix coefficients with larger absolute value will be reformulated)
1425
1426 /// sparse pricing threshold (\#violations < dimension * SPARSITY_THRESHOLD activates sparse pricing)
1428
1429 /// threshold on number of rows vs. number of columns for switching from column to row representations in auto mode
1431
1432 /// geometric frequency at which to apply rational reconstruction
1434
1435 /// minimal reduction (sum of removed rows/cols) to continue simplification
1437
1438 /// refactor threshold for nonzeros in last factorized basis matrix compared to updated basis matrix
1440
1441 /// refactor threshold for fill-in in current factor update compared to fill-in in last factorization
1443
1444 /// refactor threshold for memory growth in factorization since last refactorization
1446
1447 /// accuracy of conjugate gradient method in least squares scaling (higher value leads to more iterations)
1449
1450 /// objective offset
1452
1453 /// minimal Markowitz threshold to control sparsity/stability in LU factorization
1455
1456 /// minimal modification threshold to apply presolve reductions
1458
1459 /// factor by which the precision of the floating-point solver is multiplied
1461
1462 /// number of real parameters
1463 REALPARAM_COUNT = 27
1465
1466#ifdef SOPLEX_WITH_RATIONALPARAM
1467 /// rational parameters
1468 typedef enum
1469 {
1470 /// number of rational parameters
1471 RATIONALPARAM_COUNT = 0
1472 } RationalParam;
1473#endif
1474
1475 /// class of parameter settings
1477 {
1478 public:
1479 static struct BoolParam
1480 {
1481 /// constructor
1483 /// array of names for boolean parameters
1485 /// array of descriptions for boolean parameters
1487 /// array of default values for boolean parameters
1490
1491 static struct IntParam
1492 {
1493 /// constructor
1495 /// array of names for integer parameters
1497 /// array of descriptions for integer parameters
1499 /// array of default values for integer parameters
1501 /// array of lower bounds for int parameter values
1503 /// array of upper bounds for int parameter values
1506
1507 static struct RealParam
1508 {
1509 /// constructor
1511 /// array of names for real parameters
1513 /// array of descriptions for real parameters
1515 /// array of default values for real parameters
1517 /// array of lower bounds for real parameter values
1519 /// array of upper bounds for real parameter values
1522
1523#ifdef SOPLEX_WITH_RATIONALPARAM
1524 static struct RationalParam
1525 {
1526 /// constructor
1527 RationalParam();
1528 /// array of names for rational parameters
1529 std::string name[SoPlexBase<R>::RATIONALPARAM_COUNT];
1530 /// array of descriptions for rational parameters
1531 std::string description[SoPlexBase<R>::RATIONALPARAM_COUNT];
1532 /// array of default values for rational parameters
1534 /// array of lower bounds for rational parameter values
1536 /// array of upper bounds for rational parameter values
1538 } rationalParam;
1539#endif
1540
1541 /// array of current boolean parameter values
1543
1544 /// array of current integer parameter values
1546
1547 /// array of current real parameter values
1549
1550#ifdef SOPLEX_WITH_RATIONALPARAM
1551 /// array of current rational parameter values
1552 Rational _rationalParamValues[SoPlexBase<R>::RATIONALPARAM_COUNT];
1553#endif
1554
1555 /// default constructor initializing default settings
1557
1558 /// copy constructor
1560
1561 /// assignment operator
1563 };
1564
1566
1567 /// returns boolean parameter value
1568 bool boolParam(const BoolParam param) const;
1569
1570 /// returns integer parameter value
1571 int intParam(const IntParam param) const;
1572
1573 /// returns real parameter value
1574 Real realParam(const RealParam param) const;
1575
1576#ifdef SOPLEX_WITH_RATIONALPARAM
1577 /// returns rational parameter value
1578 Rational rationalParam(const RationalParam param) const;
1579#endif
1580
1581 /// returns current parameter settings
1582 const Settings& settings() const;
1583
1584 /// returns current tolerances
1585 const std::shared_ptr<Tolerances> tolerances() const;
1586
1587 /// sets boolean parameter value; returns true on success
1588 bool setBoolParam(const BoolParam param, const bool value, const bool init = true);
1589
1590 /// sets integer parameter value; returns true on success
1591 bool setIntParam(const IntParam param, const int value, const bool init = true);
1592
1593 /// sets real parameter value; returns true on success
1594 bool setRealParam(const RealParam param, const Real value, const bool init = true);
1595
1596#ifdef SOPLEX_WITH_RATIONALPARAM
1597 /// sets rational parameter value; returns true on success
1598 bool setRationalParam(const RationalParam param, const Rational value, const bool init = true);
1599#endif
1600
1601 /// sets parameter settings; returns true on success
1602 bool setSettings(const Settings& newSettings, const bool init = true);
1603
1604 /// resets default parameter settings
1605 void resetSettings(const bool quiet = false, const bool init = true);
1606
1607 /// print non-default parameter values
1609
1610 /// writes settings file; returns true on success
1611 bool saveSettingsFile(const char* filename, const bool onlyChanged = false,
1612 int solvemode = 1) const;
1613
1614 /// reads settings file; returns true on success
1615 bool loadSettingsFile(const char* filename);
1616
1617 /// parses one setting string and returns true on success; note that string is modified
1618 bool parseSettingsString(char* str);
1619
1620 ///@}
1621
1622
1623 ///@name Statistics
1624 ///@{
1625
1626 /// set statistic timers to a certain type
1627 void setTimings(const Timer::TYPE ttype);
1628
1629 /// prints solution statistics
1630 void printSolutionStatistics(std::ostream& os);
1631
1632 /// prints statistics on solving process
1633 void printSolvingStatistics(std::ostream& os);
1634
1635 /// prints short statistics
1636 void printShortStatistics(std::ostream& os);
1637
1638 /// prints complete statistics
1639 void printStatistics(std::ostream& os);
1640
1641 /// prints status
1642
1643 void printStatus(std::ostream& os, typename SPxSolverBase<R>::Status status);
1644
1645 ///@}
1646
1647
1648 ///@name Miscellaneous
1649 ///@{
1650
1651 /// prints version and compilation options
1652 void printVersion() const;
1653
1654 /// checks if real LP and rational LP are in sync; dimensions will always be compared,
1655 /// vector and matrix values only if the respective parameter is set to true.
1656 /// If quiet is set to true the function will only display which vectors are different.
1657 bool areLPsInSync(const bool checkVecVals = true, const bool checkMatVals = false,
1658 const bool quiet = false) const;
1659
1660 /// set the random seeds of the solver instance
1661 void setRandomSeed(unsigned int seed);
1662
1663 /// returns the current random seed of the solver instance
1664 unsigned int randomSeed() const;
1665
1666 ///@}
1667
1668private:
1669
1670 ///@name Statistics on solving process
1671 ///@{
1672
1673 /// class of statistics
1674 class Statistics;
1675
1676 /// statistics since last call to solveReal() or solveRational()
1678
1679 ///@}
1680
1681
1682 ///@name Parameter settings
1683 ///@{
1684
1686
1687 std::shared_ptr<Tolerances> _tolerances;
1688
1694
1695 ///@}
1696
1697
1698 ///@name Data for the real LP
1699 ///@{
1700
1724
1729
1730#ifdef SOPLEX_WITH_BOOST
1731#ifdef SOPLEX_WITH_MPFR
1732 //----------------------------- BOOSTED SOLVER -----------------------------
1733 // multiprecision type used for the boosted solver
1734 using BP = number<mpfr_float_backend<0>, et_off>;
1735#else
1736#ifdef SOPLEX_WITH_GMP
1737 using BP = number<gmp_float<50>, et_off>;
1738#else
1739 using BP = number<cpp_dec_float<50>, et_off>;
1740#endif
1741#endif
1742#else
1743 using BP = double;
1744#endif
1745
1746 // boosted solver object
1748
1749 // ------------- Main attributes for precision boosting
1750
1751 int _initialPrecision = 50; // initial number of digits for multiprecision
1752 bool _boostingLimitReached; // true if BP::default_precision() > max authorized number of digits
1753 bool _switchedToBoosted; // true if _boostedSolver is used instead of _solver to cope with the numerical failure of _solver
1754 // this attribute remembers wether we are testing feasibility (1), unboundedness (2) or neither (0)
1755 // it is used when storing/loading the right basis in precision boosting.
1756 // example: if _certificateMode == 1, it is the basis for the feasibility LP that should be stored/loaded.
1758
1759 // ------------- Buffers for statistics of precision boosting
1760
1761 // ideally these four attributes would be local variables, however the precision boosting loop
1762 // wraps the solve in a way that it is complicated to declare these variables locally.
1763 int _lastStallPrecBoosts; // number of previous stalling precision boosts
1764 bool _factorSolNewBasisPrecBoost; // false if the current basis has already been factorized (no new iterations have been done)
1765 int _nextRatrecPrecBoost; // the iteration during or after which rational reconstruction can be performed
1766 // buffer storing the number of iterations before a given precision boost
1767 // used to detect stalling (_prevIterations < _statistics->iterations)
1769
1770 // ------------- Tolerances Ratios
1771
1772 /// ratios for computing the tolerances for precision boosting
1773 /// ratio denotes the proportion of precision used by the tolerance
1774 /// e.g. ratio = 0.65, precision = 100 digits, new tol = 10^(0.65*100)
1780
1781 // ------------- [Boosted] SLUFactor, Pricers, RatioTesters, Scalers, Simplifiers
1782
1784
1791
1796
1799
1806
1809
1810 //--------------------------------------------------------------------------
1811
1812 bool _isRealLPLoaded; // true indicates that the original LP is loaded in the _solver variable, hence all actions
1813 // are performed on the original LP.
1816
1823
1824 ///@}
1825
1826
1827 ///@name Data for the rational LP
1828 ///@{
1829
1833
1857
1858 /// type of bounds and sides
1859 typedef enum
1860 {
1861 /// both bounds are infinite
1863
1864 /// lower bound is finite, upper bound is infinite
1866
1867 /// upper bound is finite, lower bound is infinite
1869
1870 /// lower and upper bound finite, but different
1872
1873 /// lower bound equals upper bound
1874 RANGETYPE_FIXED = 4
1876
1879
1880 ///@}
1881
1882
1883 ///@name Solution data
1884 ///@{
1885
1888
1891
1892 // indicates wether an old basis is currently stored for warm start
1894 bool _hasOldFeasBasis; // basis for testing feasibility
1895 bool _hasOldUnbdBasis; // basis for testing unboundedness
1896
1897 // these vectors store the last basis met in precision boosting when not testing feasibility or unboundedness.
1900
1901 // these vectors store the last basis met when testing feasibility in precision boosting.
1904
1905 // these vectors store the last basis met when testing unboundedness in precision boosting.
1908
1909 // these vectors don't replace _basisStatusRows and _basisStatusCols
1910 // they aim to overcome the issue of having the enum VarStatus inside SPxSolverBase.
1911 // When calling setBasis or getBasis (from SPxSolverBase class), a specific conversion is needed.
1912 // Function: SPxSolverBase<BP>::setBasis(...)
1913 // Usage: copy _basisStatusRows(Cols) to _tmpBasisStatusRows(Cols) before calling
1914 // mysolver.setBasis(_tmpBasisStatusRows, _tmpBasisStatusCols)
1915 // Function: SPxSolverBase<BP>::getBasis(...)
1916 // Usage: copy _tmpBasisStatusRows(Cols) to _basisStatusRows(Cols) after calling
1917 // mysolver.getBasis(_tmpBasisStatusRows, _tmpBasisStatusCols, _basisStatusRows.size(), _basisStatusCols.size())
1920
1924
1928
1929 ///@}
1930
1931 ///@name Miscellaneous
1932 ///@{
1933
1936
1940
1941 ///@}
1942
1943 ///@name Constant helper methods
1944 ///@{
1945
1946 /// extends sparse vector to hold newmax entries if and only if it holds no more free entries
1947 void _ensureDSVectorRationalMemory(DSVectorRational& vec, const int newmax) const;
1948
1949 /// creates a permutation for removing rows/columns from an array of indices
1950 void _idxToPerm(int* idx, int idxSize, int* perm, int permSize) const;
1951
1952 /// creates a permutation for removing rows/columns from a range of indices
1953 void _rangeToPerm(int start, int end, int* perm, int permSize) const;
1954
1955 /// checks consistency for the boosted solver
1957
1958 /// checks consistency
1959 bool _isConsistent() const;
1960
1961 /// should solving process be stopped?
1962 bool _isSolveStopped(bool& stoppedTime, bool& stoppedIter) const;
1963
1964 /// determines RangeType from real bounds
1965 RangeType _rangeTypeReal(const R& lower, const R& upper) const;
1966
1967 /// determines RangeType from rational bounds
1968 RangeType _rangeTypeRational(const Rational& lower, const Rational& upper) const;
1969
1970 /// switches RANGETYPE_LOWER to RANGETYPE_UPPER and vice versa
1971 RangeType _switchRangeType(const RangeType& rangeType) const;
1972
1973 /// checks whether RangeType corresponds to finite lower bound
1974 bool _lowerFinite(const RangeType& rangeType) const;
1975
1976 /// checks whether RangeType corresponds to finite upper bound
1977 bool _upperFinite(const RangeType& rangeType) const;
1978
1979 ///@}
1980
1981
1982 ///@name Non-constant helper methods
1983 ///@{
1984
1985 /// adds a single row to the real LP and adjusts basis
1986 void _addRowReal(const LPRowBase<R>& lprow);
1987
1988 /// adds a single row to the real LP and adjusts basis
1989 void _addRowReal(R lhs, const SVectorBase<R>& lprow, R rhs);
1990
1991 /// adds multiple rows to the real LP and adjusts basis
1992 void _addRowsReal(const LPRowSetBase<R>& lprowset);
1993
1994 /// adds a single column to the real LP and adjusts basis
1995 void _addColReal(const LPColReal& lpcol);
1996
1997 /// adds a single column to the real LP and adjusts basis
1998 void _addColReal(R obj, R lower, const SVectorBase<R>& lpcol, R upper);
1999
2000 /// adds multiple columns to the real LP and adjusts basis
2001 void _addColsReal(const LPColSetReal& lpcolset);
2002
2003 /// replaces row \p i with \p lprow and adjusts basis
2004 void _changeRowReal(int i, const LPRowBase<R>& lprow);
2005
2006 /// changes left-hand side vector for constraints to \p lhs and adjusts basis
2008
2009 /// changes left-hand side of row \p i to \p lhs and adjusts basis
2010 void _changeLhsReal(int i, const R& lhs);
2011
2012 /// changes right-hand side vector to \p rhs and adjusts basis
2014
2015 /// changes right-hand side of row \p i to \p rhs and adjusts basis
2016 void _changeRhsReal(int i, const R& rhs);
2017
2018 /// changes left- and right-hand side vectors and adjusts basis
2019 void _changeRangeReal(const VectorBase<R>& lhs, const VectorBase<R>& rhs);
2020
2021 /// changes left- and right-hand side of row \p i and adjusts basis
2022 void _changeRangeReal(int i, const R& lhs, const R& rhs);
2023
2024 /// replaces column \p i with \p lpcol and adjusts basis
2025 void _changeColReal(int i, const LPColReal& lpcol);
2026
2027 /// changes vector of lower bounds to \p lower and adjusts basis
2029
2030 /// changes lower bound of column i to \p lower and adjusts basis
2031 void _changeLowerReal(int i, const R& lower);
2032
2033 /// changes vector of upper bounds to \p upper and adjusts basis
2035
2036 /// changes \p i 'th upper bound to \p upper and adjusts basis
2037 void _changeUpperReal(int i, const R& upper);
2038
2039 /// changes vectors of column bounds to \p lower and \p upper and adjusts basis
2040 void _changeBoundsReal(const VectorBase<R>& lower, const VectorBase<R>& upper);
2041
2042 /// changes bounds of column \p i to \p lower and \p upper and adjusts basis
2043 void _changeBoundsReal(int i, const R& lower, const R& upper);
2044
2045 /// changes matrix entry in row \p i and column \p j to \p val and adjusts basis
2046 void _changeElementReal(int i, int j, const R& val);
2047
2048 /// removes row \p i and adjusts basis
2049 void _removeRowReal(int i);
2050
2051 /// removes all rows with an index \p i such that \p perm[i] < 0; upon completion, \p perm[i] >= 0 indicates the
2052 /// new index where row \p i has been moved to; note that \p perm must point to an array of size at least
2053 /// #numRows()
2054 void _removeRowsReal(int perm[]);
2055
2056 /// remove all rows with indices in array \p idx of size \p n; an array \p perm of size #numRows() may be passed
2057 /// as buffer memory
2058 void _removeRowsReal(int idx[], int n, int perm[]);
2059
2060 /// removes rows \p start to \p end including both; an array \p perm of size #numRows() may be passed as buffer
2061 /// memory
2062 void _removeRowRangeReal(int start, int end, int perm[]);
2063
2064 /// removes column i
2065 void _removeColReal(int i);
2066
2067 /// removes all columns with an index \p i such that \p perm[i] < 0; upon completion, \p perm[i] >= 0 indicates the
2068 /// new index where column \p i has been moved to; note that \p perm must point to an array of size at least
2069 /// #numColsReal()
2070 void _removeColsReal(int perm[]);
2071
2072 /// remove all columns with indices in array \p idx of size \p n; an array \p perm of size #numColsReal() may be
2073 /// passed as buffer memory
2074 void _removeColsReal(int idx[], int n, int perm[]);
2075
2076 /// removes columns \p start to \p end including both; an array \p perm of size #numColsReal() may be passed as
2077 /// buffer memory
2078 void _removeColRangeReal(int start, int end, int perm[]);
2079
2080 /// invalidates solution
2082
2083 /// enables simplifier and scaler according to current parameters
2085
2086 /// disables simplifier and scaler
2088
2089 /// ensures that the rational LP is available; performs no sync
2091
2092 /// ensures that the real LP and the basis are loaded in the solver; performs no sync
2094
2095 /// call floating-point solver and update statistics on iterations etc.
2096 void _solveBoostedRealLPAndRecordStatistics(volatile bool* interrupt = NULL);
2097
2098 /// call floating-point solver and update statistics on iterations etc.
2099 void _solveRealLPAndRecordStatistics(volatile bool* interrupt = NULL);
2100
2101 /// reads real LP in LP or MPS format from file and returns true on success; gets row names, column names, and
2102 /// integer variables if desired
2103 bool _readFileReal(const char* filename, NameSet* rowNames = 0, NameSet* colNames = 0,
2104 DIdxSet* intVars = 0);
2105
2106 /// reads rational LP in LP or MPS format from file and returns true on success; gets row names, column names, and
2107 /// integer variables if desired
2108 bool _readFileRational(const char* filename, NameSet* rowNames = 0, NameSet* colNames = 0,
2109 DIdxSet* intVars = 0);
2110
2111 /// completes range type arrays after adding columns and/or rows
2113
2114 /// recomputes range types from scratch using real LP
2116
2117 /// recomputes range types from scratch using rational LP
2119
2120 /// synchronizes real LP with rational LP, i.e., copies (rounded) rational LP into real LP, without looking at the sync mode
2121 void _syncLPReal(bool time = true);
2122
2123 /// synchronizes rational LP with real LP, i.e., copies real LP to rational LP, without looking at the sync mode
2124 void _syncLPRational(bool time = true);
2125
2126 /// synchronizes rational solution with real solution, i.e., copies (rounded) rational solution to real solution
2128
2129 /// synchronizes real solution with rational solution, i.e., copies real solution to rational solution
2131
2132 /// returns pointer to a constant unit vector available until destruction of the SoPlexBase class
2134
2135 /// parses one line in a settings file and returns true on success; note that the string is modified
2136 bool _parseSettingsLine(char* line, const int lineNumber);
2137
2138 ///@}
2139
2140
2141 //**@name Private solving methods implemented in solverational.hpp */
2142 ///@{
2143
2144 /// stores floating-point solution of original LP as current rational solution and ensure that solution vectors have right dimension; ensure that solution is aligned with basis
2145 template <typename T>
2147 SolRational& sol,
2148 VectorBase<T>& primalReal,
2149 VectorBase<T>& dualReal,
2150 int& dualSize);
2151
2152 /// computes violation of bounds during the refinement loop
2153 void _computeBoundsViolation(SolRational& sol, Rational& boundsViolation);
2154
2155 /// computes violation of sides during the refinement loop
2156 void _computeSidesViolation(SolRational& sol, Rational& sideViolation);
2157
2158 /// computes violation of reduced costs during the refinement loop
2160 SolRational& sol,
2161 Rational& redCostViolation,
2162 const bool& maximizing);
2163
2164 /// computes dual violation during the refinement loop
2166 SolRational& sol,
2167 Rational& dualViolation,
2168 const bool& maximizing);
2169
2170 /// checks termination criteria for refinement loop
2172 bool& primalFeasible,
2173 bool& dualFeasible,
2174 Rational& boundsViolation,
2175 Rational& sideViolation,
2176 Rational& redCostViolation,
2177 Rational& dualViolation,
2178 int minIRRoundsRemaining,
2179 bool& stoppedTime,
2180 bool& stoppedIter,
2181 int numFailedRefinements);
2182
2183 /// checks refinement loop progress
2185 Rational& boundsViolation,
2186 Rational& sideViolation,
2187 Rational& redCostViolation,
2188 Rational& dualViolation,
2189 Rational& maxViolation,
2190 Rational& bestViolation,
2191 const Rational& violationImprovementFactor,
2192 int& numFailedRefinements);
2193
2194 /// performs rational reconstruction and/or factorizationd
2196 int& minIRRoundsRemaining,
2197 int& lastStallIterations,
2198 int& numberOfIterations,
2199 bool& factorSolNewBasis,
2200 int& nextRatrec,
2201 const Rational& errorCorrectionFactor,
2202 Rational& errorCorrection,
2203 Rational& maxViolation,
2204 SolRational& sol,
2205 bool& primalFeasible,
2206 bool& dualFeasible,
2207 bool& stoppedTime,
2208 bool& stoppedIter,
2209 bool& error,
2210 bool& breakAfter,
2211 bool& continueAfter);
2212
2213 /// forces value of given nonbasic variable to bound
2215 SolRational& sol,
2216 int& c,
2217 const int& maxDimRational,
2218 bool toLower);
2219
2220 /// computes primal scaling factor; limit increase in scaling by tolerance used in floating point solve
2222 Rational& maxScale,
2223 Rational& primalScale,
2224 Rational& boundsViolation,
2225 Rational& sideViolation,
2226 Rational& redCostViolation);
2227
2228 /// computes dual scaling factor; limit increase in scaling by tolerance used in floating point solve
2230 Rational& maxScale,
2231 Rational& primalScale,
2232 Rational& dualScale,
2233 Rational& redCostViolation,
2234 Rational& dualViolation);
2235
2236 /// applies scaled bounds
2237 template <typename T>
2238 void _applyScaledBounds(SPxSolverBase<T>& solver, Rational& primalScale);
2239
2240 /// applies scaled sides
2241 template <typename T>
2242 void _applyScaledSides(SPxSolverBase<T>& solver, Rational& primalScale);
2243
2244 /// applies scaled objective function
2245 template <typename T>
2246 void _applyScaledObj(SPxSolverBase<T>& solver, Rational& dualScale, SolRational& sol);
2247
2248 /// evaluates result of solve. Return true if the algorithm must to stopped, false otherwise.
2249 template <typename T>
2251 SPxSolverBase<T>& solver,
2252 typename SPxSolverBase<T>::Status result,
2253 bool usingRefinedLP,
2254 SolRational& sol,
2255 VectorBase<T>& dualReal,
2256 bool& infeasible,
2257 bool& unbounded,
2258 bool& stoppedTime,
2259 bool& stoppedIter,
2260 bool& error);
2261
2262 /// corrects primal solution and aligns with basis
2263 template <typename T>
2265 SolRational& sol,
2266 Rational& primalScale,
2267 int& primalSize,
2268 const int& maxDimRational,
2269 VectorBase<T>& primalReal);
2270
2271 /// updates or recomputes slacks depending on which looks faster
2272 void _updateSlacks(SolRational& sol, int& primalSize);
2273
2274 /// corrects dual solution and aligns with basis
2275 template <typename T>
2277 SPxSolverBase<T>& solver,
2278 SolRational& sol,
2279 const bool& maximizing,
2280 VectorBase<T>& dualReal,
2281 Rational& dualScale,
2282 int& dualSize,
2283 const int& maxDimRational);
2284
2285 /// updates or recomputes reduced cost values depending on which looks faster; adding one to the length of the
2286 /// dual vector accounts for the objective function vector
2287 void _updateReducedCosts(SolRational& sol, int& dualSize, const int& numCorrectedPrimals);
2288
2289 ///@todo precision-boosting move some place else
2290 /// converts the given DataArray of VarStatus to boostedPrecision
2292 DataArray< typename SPxSolverBase<R>::VarStatus >& base,
2293 DataArray< typename SPxSolverBase<BP>::VarStatus >& copy);
2294
2295 ///@todo precision-boosting move some place else
2296 /// converts the given DataArray of VarStatus to R precision
2298 DataArray< typename SPxSolverBase<BP>::VarStatus >& base,
2299 DataArray< typename SPxSolverBase<R>::VarStatus >& copy);
2300
2301 /// disable initial precision solver and switch to boosted solver
2303
2304 /// setup boosted solver before launching iteration
2306
2307 /// increase the multiprecision, return false if maximum precision is reached, true otherwise
2309
2310 /// reset the boosted precision to the default value
2312
2313 /// setup recovery mecanism using multiprecision, return false if maximum precision reached, true otherwise
2315
2316 /// return true if slack basis has to be loaded for boosted solver
2317 bool _isBoostedStartingFromSlack(bool initialSolve = true);
2318
2319 /// indicate if we are testing feasibility, unboundedness or neither
2323
2324 /// check if we are testing feasibility, unboundedness or neither
2328
2329 // stores given basis in old basis attributes: _oldBasisStatusRows, _oldFeasBasisStatusRows, _oldUnbdBasisStatusRows (and ...Cols)
2331 DataArray< typename SPxSolverBase<R>::VarStatus >& cols);
2332
2333 // stores given basis in old basis attributes: _oldBasisStatusRows, _oldFeasBasisStatusRows, _oldUnbdBasisStatusRows (and ...Cols)
2335 DataArray< typename SPxSolverBase<BP>::VarStatus >& cols);
2336
2337 // get the last advanced and stable basis stored by the initial solver and store it as old basis, unsimplify basis if simplifier activated
2338 void _storeLastStableBasis(bool vanished);
2339
2340 // get the last advanced and stable basis stored by the boosted solver and store it as old basis, unsimplify basis if simplifier activated
2341 void _storeLastStableBasisBoosted(bool vanished);
2342
2343 // load old basis in solver. The old basis loaded depends on the certificate mode (feasibility, unboundedness, or neither)
2344 bool _loadBasisFromOldBasis(bool boosted);
2345
2346 // update statistics for precision boosting
2348
2349 /// solves current problem using multiprecision floating-point solver
2350 /// return false if a new boosted iteration is necessary, true otherwise
2352 SolRational& sol,
2353 bool& primalFeasible,
2354 bool& dualFeasible,
2355 bool& infeasible,
2356 bool& unbounded,
2357 bool& stoppedTime,
2358 bool& stoppedIter,
2359 bool& error,
2360 bool& needNewBoostedIt);
2361
2362 /// solves current problem with iterative refinement and recovery mechanism using boosted solver
2364 SolRational& sol,
2365 bool acceptUnbounded,
2366 bool acceptInfeasible,
2367 int minIRRoundsRemaining,
2368 bool& primalFeasible,
2369 bool& dualFeasible,
2370 bool& infeasible,
2371 bool& unbounded,
2372 bool& stoppedTime,
2373 bool& stoppedIter,
2374 bool& error,
2375 bool& needNewBoostedIt);
2376
2377 /// perform iterative refinement using the right precision
2379 SolRational& sol,
2380 bool acceptUnbounded,
2381 bool acceptInfeasible,
2382 int minIRRoundsRemaining,
2383 bool& primalFeasible,
2384 bool& dualFeasible,
2385 bool& infeasible,
2386 bool& unbounded,
2387 bool& stoppedTime,
2388 bool& stoppedIter,
2389 bool& error
2390 );
2391
2392 /// solves current problem using double floating-point solver
2394 SolRational& sol,
2395 bool& primalFeasible,
2396 bool& dualFeasible,
2397 bool& infeasible,
2398 bool& unbounded,
2399 bool& stoppedTime,
2400 bool& stoppedIter,
2401 bool& error);
2402
2403 /// solves current problem with iterative refinement and recovery mechanism
2405 bool acceptUnbounded,
2406 bool acceptInfeasible,
2407 int minIRRoundsRemaining,
2408 bool& primalFeasible,
2409 bool& dualFeasible,
2410 bool& infeasible,
2411 bool& unbounded,
2412 bool& stoppedTime,
2413 bool& stoppedIter,
2414 bool& error);
2415
2416 /// performs iterative refinement on the auxiliary problem for testing unboundedness
2417 void _performUnboundedIRStable(SolRational& sol, bool& hasUnboundedRay, bool& stoppedTime,
2418 bool& stoppedIter, bool& error);
2419
2420 /// performs iterative refinement on the auxiliary problem for testing feasibility
2421 void _performFeasIRStable(SolRational& sol, bool& withDualFarkas, bool& stoppedTime,
2422 bool& stoppedIter, bool& error);
2423
2424 /// reduces matrix coefficient in absolute value by the lifting procedure of Thiele et al. 2013
2425 void _lift();
2426
2427 /// undoes lifting
2429
2430 /// store basis
2432
2433 /// restore basis
2435
2436 /// stores objective, bounds, and sides of real LP
2438
2439 /// restores objective, bounds, and sides of real LP
2441
2442 /// introduces slack variables to transform inequality constraints into equations for both rational and real LP,
2443 /// which should be in sync
2445
2446 /// undoes transformation to equality form
2448
2449 /// transforms LP to unboundedness problem by moving the objective function to the constraints, changing right-hand
2450 /// side and bounds to zero, and adding an auxiliary variable for the decrease in the objective function
2452
2453 /// undoes transformation to unboundedness problem
2454 void _untransformUnbounded(SolRational& sol, bool unbounded);
2455
2456 /// transforms LP to feasibility problem by removing the objective function, shifting variables, and homogenizing the
2457 /// right-hand side
2459
2460 /// undoes transformation to feasibility problem
2461 void _untransformFeasibility(SolRational& sol, bool infeasible);
2462
2463 /** computes radius of infeasibility box implied by an approximate Farkas' proof
2464
2465 Given constraints of the form \f$ lhs <= Ax <= rhs \f$, a farkas proof y should satisfy \f$ y^T A = 0 \f$ and
2466 \f$ y_+^T lhs - y_-^T rhs > 0 \f$, where \f$ y_+, y_- \f$ denote the positive and negative parts of \f$ y \f$.
2467 If \f$ y \f$ is approximate, it may not satisfy \f$ y^T A = 0 \f$ exactly, but the proof is still valid as long
2468 as the following holds for all potentially feasible \f$ x \f$:
2469
2470 \f[
2471 y^T Ax < (y_+^T lhs - y_-^T rhs) (*)
2472 \f]
2473
2474 we may therefore calculate \f$ y^T A \f$ and \f$ y_+^T lhs - y_-^T rhs \f$ exactly and check if the upper and lower
2475 bounds on \f$ x \f$ imply that all feasible \f$ x \f$ satisfy (*), and if not then compute bounds on \f$ x \f$ to
2476 guarantee (*). The simplest way to do this is to compute
2477
2478 \f[
2479 B = (y_+^T lhs - y_-^T rhs) / \sum_i(|(y^T A)_i|)
2480 \f]
2481
2482 noting that if every component of \f$ x \f$ has \f$ |x_i| < B \f$, then (*) holds.
2483
2484 \f$ B \f$ can be increased by iteratively including variable bounds smaller than \f$ B \f$. The speed of this
2485 method can be further improved by using interval arithmetic for all computations. For related information see
2486 Sec. 4 of Neumaier and Shcherbina, Mathematical Programming A, 2004.
2487
2488 Set transformed to true if this method is called after _transformFeasibility().
2489 */
2490 void _computeInfeasBox(SolRational& sol, bool transformed);
2491
2492 /// solves real LP during iterative refinement
2494 VectorBase<R>& dual,
2495 DataArray< typename SPxSolverBase<R>::VarStatus >& basisStatusRows,
2496 DataArray< typename SPxSolverBase<R>::VarStatus >& basisStatusCols);
2497
2498 /// solves real LP with recovery mechanism
2499 typename SPxSolverBase<R>::Status _solveRealStable(bool acceptUnbounded, bool acceptInfeasible,
2500 VectorBase<R>& primal, VectorBase<R>& dual,
2501 DataArray< typename SPxSolverBase<R>::VarStatus >& basisStatusRows,
2502 DataArray< typename SPxSolverBase<R>::VarStatus >& basisStatusCols,
2503 const bool forceNoSimplifier = false);
2504
2505 /// solves real LP during iterative refinement
2507 VectorBase<BP>& primal, VectorBase<BP>& dual,
2508 DataArray< typename SPxSolverBase<R>::VarStatus >& basisStatusRows,
2509 DataArray< typename SPxSolverBase<R>::VarStatus >& basisStatusCols,
2510 typename SPxSolverBase<BP>::Status& boostedResult, bool initialSolve);
2511
2512 /// computes rational inverse of basis matrix as defined by _rationalLUSolverBind
2514
2515 /// factorizes rational basis matrix in column representation
2517 DataArray< typename SPxSolverBase<R>::VarStatus >& basisStatusRows,
2518 DataArray< typename SPxSolverBase<R>::VarStatus >& basisStatusCols, bool& stoppedTime,
2519 bool& stoppedIter, bool& error, bool& optimal);
2520
2521 /// attempts rational reconstruction of primal-dual solution
2523 DataArray< typename SPxSolverBase<R>::VarStatus >& basisStatusRows,
2524 DataArray< typename SPxSolverBase<R>::VarStatus >& basisStatusCols,
2525 const Rational& denomBoundSquared);
2526 ///@}
2527
2528 ///@name Private solving methods implemented in solvereal.cpp
2529 ///@{
2530
2531 /// solves the templated LP
2532 void _optimize(volatile bool* interrupt = NULL);
2533
2534 /// temporary fix for Rational
2535 void _optimizeRational(volatile bool* interrupt = NULL);
2536
2537 /// checks result of the solving process and solves again without preprocessing if necessary
2538 void _evaluateSolutionReal(typename SPxSimplifier<R>::Result simplificationStatus);
2539
2540 /// solves real LP with/without preprocessing
2541 void _preprocessAndSolveReal(bool applyPreprocessing, volatile bool* interrupt = NULL);
2542
2543 /// loads original problem into solver and solves again after it has been solved to optimality with preprocessing
2544 void _resolveWithoutPreprocessing(typename SPxSimplifier<R>::Result simplificationStatus);
2545
2546 /// verify computed solution and resolve if necessary
2548
2549 /// verify computed obj stop and resolve if necessary
2551
2552 /// stores solution of the real LP; before calling this, the real LP must be loaded in the solver and solved (again)
2553 void _storeSolutionReal(bool verify = true);
2554
2555 /// stores solution from the simplifier because problem vanished in presolving step
2557
2558 /// unscales stored solution to remove internal or external scaling of LP
2559 void _unscaleSolutionReal(SPxLPBase<R>& LP, bool persistent = true);
2560
2561 /// load original LP and possibly setup a slack basis
2562 void _loadRealLP(bool initBasis);
2563
2564 /// check scaling of LP
2565 void _checkScaling(SPxLPBase<R>* origLP) const;
2566
2567 /// check correctness of (un)scaled basis matrix operations
2569
2570 /// check whether persistent scaling is supposed to be reapplied again after unscaling
2572
2573 /// checks the dual feasibility of the current basis
2575 ///@}
2576};
2577
2578/* Backwards compatibility */
2580// A header file containing all the general templated functions
2581
2582} // namespace soplex
2583
2584// General templated function
2585#include "soplex.hpp"
2586#include "soplex/solverational.hpp"
2587#include "soplex/testsoplex.hpp"
2588#include "soplex/solvereal.hpp"
2589
2590#endif // _SOPLEX_H_
Collection of dense, sparse, and semi-sparse vectors.
Safe arrays of arbitrary types.
Definition array.h:73
Dynamic index set.
Definition didxset.h:52
Dynamic sparse vectors.
Safe arrays of data objects.
Definition dataarray.h:75
LP column.
Definition lpcolbase.h:55
(In)equality for LPs.
Definition lprowbase.h:55
Type
(In)Equality type of an LP row.
Definition lprowbase.h:82
Set of LP rows.
Set of strings.
Definition nameset.h:71
Implementation of Sparse Linear Solver with Rational precision.
Implementation of Sparse Linear Solver.
Definition slufactor.h:51
Auto pricer.
Definition spxautopr.h:52
SPxStatus
basis status.
Definition spxbasis.h:102
Bound flipping ratio test ("long step dual") for SoPlex.
Dantzig pricer.
Textbook ratio test for SoPlex.
Devex pricer.
Definition spxdevexpr.h:54
Equilibrium row/column scaling.
Definition spxequilisc.h:46
Fast shifting ratio test.
Definition spxfastrt.h:54
Geometric mean row/column scaling.
Definition spxgeometsc.h:46
Harris pricing with shifting.
Definition spxharrisrt.h:51
Saving LPs in a form suitable for SoPlex.
Definition spxlpbase.h:108
Least squares scaling.
LP simplifier for removing uneccessary row/columns.
Definition spxmainsm.h:72
Wrapper for several output streams. A verbosity level is used to decide which stream to use and wheth...
Definition spxout.h:78
Partial multiple pricing.
LP scaler abstract base class.
Definition spxscaler.h:87
LP simplification abstract base class.
Result
Result of the simplification.
Sequential object-oriented SimPlex.
Definition spxsolver.h:104
SoPlex start basis generation base class.
Definition spxstarter.h:52
Steepest edge pricer.
Steepest edge pricer.
Definition spxsteeppr.h:52
Simple heuristic SPxStarter.
Definition spxsumst.h:48
Solution vector based start basis.
Definition spxvectorst.h:55
Weighted start basis.
Definition spxweightst.h:67
Sparse vectors.
class of parameter settings
Definition soplex.h:1477
int _intParamValues[SoPlexBase< R >::INTPARAM_COUNT]
array of current integer parameter values
Definition soplex.h:1545
static struct soplex::SoPlexBase::Settings::BoolParam boolParam
bool _boolParamValues[SoPlexBase< R >::BOOLPARAM_COUNT]
array of current boolean parameter values
Definition soplex.h:1542
static struct soplex::SoPlexBase::Settings::IntParam intParam
Settings(const Settings &settings)
copy constructor
Settings & operator=(const Settings &settings)
assignment operator
Real _realParamValues[SoPlexBase< R >::REALPARAM_COUNT]
array of current real parameter values
Definition soplex.h:1548
static struct soplex::SoPlexBase::Settings::RealParam realParam
Settings()
default constructor initializing default settings
int numRows() const
returns number of rows
void _performOptIRStableBoosted(SolRational &sol, bool acceptUnbounded, bool acceptInfeasible, int minIRRoundsRemaining, bool &primalFeasible, bool &dualFeasible, bool &infeasible, bool &unbounded, bool &stoppedTime, bool &stoppedIter, bool &error, bool &needNewBoostedIt)
solves current problem with iterative refinement and recovery mechanism using boosted solver
bool getBasisInverseTimesVecRational(const SVectorRational &rhs, SSVectorRational &sol)
computes solution of basis matrix B * sol = rhs; performs rational factorization if not available; re...
bool _isSolveStopped(bool &stoppedTime, bool &stoppedIter) const
should solving process be stopped?
SPxLeastSqSC< BP > _boostedScalerLeastsq
Definition soplex.h:1805
@ STARTER_VECTOR
generic solution-based crash basis
Definition soplex.h:1249
@ STARTER_WEIGHT
greedy crash basis weighted by objective, bounds, and sides
Definition soplex.h:1243
@ STARTER_SUM
crash basis from a greedy solution
Definition soplex.h:1246
@ STARTER_OFF
slack basis
Definition soplex.h:1240
bool getDualNorms(int &nnormsRow, int &nnormsCol, R *norms) const
gets steepest edge norms and returns false if they are not available
@ CHECKMODE_REAL
floating-point check
Definition soplex.h:1330
@ CHECKMODE_RATIONAL
rational check
Definition soplex.h:1336
@ CHECKMODE_AUTO
decide according to READMODE
Definition soplex.h:1333
VectorRational _modObj
Definition soplex.h:1849
void _changeColReal(int i, const LPColReal &lpcol)
replaces column i with lpcol and adjusts basis
SPxSolverBase< R >::Status _solveRealForRational(bool fromscratch, VectorBase< R > &primal, VectorBase< R > &dual, DataArray< typename SPxSolverBase< R >::VarStatus > &basisStatusRows, DataArray< typename SPxSolverBase< R >::VarStatus > &basisStatusCols)
solves real LP during iterative refinement
void _untransformFeasibility(SolRational &sol, bool infeasible)
undoes transformation to feasibility problem
void _computeDualViolation(SolRational &sol, Rational &dualViolation, const bool &maximizing)
computes dual violation during the refinement loop
@ OBJSENSE_MAXIMIZE
maximization
Definition soplex.h:1137
@ OBJSENSE_MINIMIZE
minimization
Definition soplex.h:1134
bool getRowViolation(R &maxviol, R &sumviol)
gets violation of constraints; returns true on success
void _resolveWithoutPreprocessing(typename SPxSimplifier< R >::Result simplificationStatus)
loads original problem into solver and solves again after it has been solved to optimality with prepr...
R objValueReal()
returns the objective value if a primal solution is available
void _removeRowsReal(int idx[], int n, int perm[])
remove all rows with indices in array idx of size n; an array perm of size numRows() may be passed as...
bool _setupBoostedSolverAfterRecovery()
setup recovery mecanism using multiprecision, return false if maximum precision reached,...
VectorRational _modUpper
Definition soplex.h:1846
void _storeSolutionReal(bool verify=true)
stores solution of the real LP; before calling this, the real LP must be loaded in the solver and sol...
void getObjReal(VectorBase< R > &obj) const
gets objective function vector
void _updateBoostingStatistics()
void _storeLPReal()
stores objective, bounds, and sides of real LP
Real solveTime() const
time spent in last call to solve
void _storeRealSolutionAsRational(SolRational &sol, VectorBase< T > &primalReal, VectorBase< T > &dualReal, int &dualSize)
stores floating-point solution of original LP as current rational solution and ensure that solution v...
void _preprocessAndSolveReal(bool applyPreprocessing, volatile bool *interrupt=NULL)
solves real LP with/without preprocessing
VectorBase< R > _manualRhs
Definition soplex.h:1820
bool multBasisTranspose(R *vec, bool unscale=true)
multiply with transpose of basis matrix; vec * B^T (inplace)
void _removeRowReal(int i)
removes row i and adjusts basis
void _rangeToPerm(int start, int end, int *perm, int permSize) const
creates a permutation for removing rows/columns from a range of indices
void changeColRational(int i, const LPColRational &lpcol)
replaces column i with lpcol
void setTimings(const Timer::TYPE ttype)
set statistic timers to a certain type
SPxWeightST< R > _starterWeight
Definition soplex.h:1711
const VectorBase< R > & lhsRealInternal() const
returns left-hand side vector, ignoring scaling
bool _isBoostedConsistent() const
checks consistency for the boosted solver
R coefReal(int row, int col) const
returns (unscaled) coefficient
VectorRational _unboundedLhs
Definition soplex.h:1837
bool getSlacksReal(VectorBase< R > &vector)
gets the vector of slack values if available; returns true on success
DataArray< typename SPxSolverBase< BP >::VarStatus > _tmpBasisStatusRows
Definition soplex.h:1918
SPxDantzigPR< BP > _boostedPricerDantzig
Definition soplex.h:1786
void _removeColsReal(int idx[], int n, int perm[])
remove all columns with indices in array idx of size n; an array perm of size numColsReal() may be pa...
SPxEquiliSC< R > _scalerBiequi
Definition soplex.h:1706
RealParam
real parameters
Definition soplex.h:1380
@ OPTTOL
dual feasibility tolerance
Definition soplex.h:1385
@ FPOPTTOL
working tolerance for optimality in floating-point solver during iterative refinement
Definition soplex.h:1415
@ PRECISION_BOOSTING_FACTOR
factor by which the precision of the floating-point solver is multiplied
Definition soplex.h:1460
@ SPARSITY_THRESHOLD
sparse pricing threshold (#violations < dimension * SPARSITY_THRESHOLD activates sparse pricing)
Definition soplex.h:1427
@ LIFTMAXVAL
upper threshold in lifting (nonzero matrix coefficients with larger absolute value will be reformulat...
Definition soplex.h:1424
@ EPSILON_ZERO
general zero tolerance
Definition soplex.h:1388
@ EPSILON_FACTORIZATION
zero tolerance used in factorization
Definition soplex.h:1391
@ OBJLIMIT_UPPER
upper limit on objective value
Definition soplex.h:1409
@ FPFEASTOL
working tolerance for feasibility in floating-point solver during iterative refinement
Definition soplex.h:1412
@ RATREC_FREQ
geometric frequency at which to apply rational reconstruction
Definition soplex.h:1433
@ MAXSCALEINCR
maximum increase of scaling factors between refinements
Definition soplex.h:1418
@ TIMELIMIT
time limit in seconds (INFTY if unlimited)
Definition soplex.h:1403
@ LIFTMINVAL
lower threshold in lifting (nonzero matrix coefficients with smaller absolute value will be reformula...
Definition soplex.h:1421
@ REPRESENTATION_SWITCH
threshold on number of rows vs. number of columns for switching from column to row representations in...
Definition soplex.h:1430
@ REFAC_UPDATE_FILL
refactor threshold for fill-in in current factor update compared to fill-in in last factorization
Definition soplex.h:1442
@ REALPARAM_COUNT
number of real parameters
Definition soplex.h:1463
@ MINRED
minimal reduction (sum of removed rows/cols) to continue simplification
Definition soplex.h:1436
@ OBJ_OFFSET
objective offset
Definition soplex.h:1451
@ OBJLIMIT_LOWER
lower limit on objective value
Definition soplex.h:1406
@ FEASTOL
primal feasibility tolerance
Definition soplex.h:1382
@ EPSILON_PIVOT
pivot zero tolerance used in factorization
Definition soplex.h:1397
@ MIN_MARKOWITZ
minimal Markowitz threshold to control sparsity/stability in LU factorization
Definition soplex.h:1454
@ REFAC_MEM_FACTOR
refactor threshold for memory growth in factorization since last refactorization
Definition soplex.h:1445
@ SIMPLIFIER_MODIFYROWFAC
minimal modification threshold to apply presolve reductions
Definition soplex.h:1457
@ EPSILON_UPDATE
zero tolerance used in update of the factorization
Definition soplex.h:1394
@ REFAC_BASIS_NNZ
refactor threshold for nonzeros in last factorized basis matrix compared to updated basis matrix
Definition soplex.h:1439
@ LEASTSQ_ACRCY
accuracy of conjugate gradient method in least squares scaling (higher value leads to more iterations...
Definition soplex.h:1448
@ INFTY
infinity threshold
Definition soplex.h:1400
bool getDualViolation(R &maxviol, R &sumviol)
gets violation of dual multipliers; returns true on success
void _enableSimplifierAndScaler()
enables simplifier and scaler according to current parameters
void _verifyObjLimitReal()
verify computed obj stop and resolve if necessary
bool getSlacksReal(R *p_vector, int dim)
DataArray< typename SPxSolverBase< R >::VarStatus > _basisStatusRows
Definition soplex.h:1889
SoPlexBase()
default constructor
void changeLhsReal(const VectorBase< R > &lhs)
changes left-hand side vector for constraints to lhs
void addRowsRational(const LPRowSetRational &lprowset)
adds multiple rows
@ TIMER_WALLCLOCK
wallclock time
Definition soplex.h:1349
@ TIMER_CPU
cpu or user time
Definition soplex.h:1346
@ TIMER_OFF
disable timing
Definition soplex.h:1343
VectorRational _feasObj
Definition soplex.h:1840
void _solveBoostedRealLPAndRecordStatistics(volatile bool *interrupt=NULL)
call floating-point solver and update statistics on iterations etc.
bool _switchedToBoosted
Definition soplex.h:1753
void changeRhsRational(const VectorRational &rhs)
changes right-hand side vector to rhs
IntParam
integer parameters
Definition soplex.h:1040
@ HYPER_PRICING
mode for hyper sparse pricing
Definition soplex.h:1102
@ DISPLAYFREQ
display frequency
Definition soplex.h:1066
@ TIMER
type of timer
Definition soplex.h:1099
@ CHECKMODE
mode for a posteriori feasibility checks
Definition soplex.h:1096
@ STATTIMER
type of timer for statistics
Definition soplex.h:1117
@ FACTOR_UPDATE_TYPE
type of LU update
Definition soplex.h:1051
@ READMODE
mode for reading LP files
Definition soplex.h:1090
@ STALLREFLIMIT
stalling refinement limit (-1 if unlimited)
Definition soplex.h:1063
@ STARTER
type of starter used to create crash basis
Definition soplex.h:1078
@ REFLIMIT
refinement limit (-1 if unlimited)
Definition soplex.h:1060
@ SYNCMODE
mode for synchronizing real and rational LP
Definition soplex.h:1087
@ PRICER
type of pricer
Definition soplex.h:1081
@ LEASTSQ_MAXROUNDS
maximum number of conjugate gradient iterations in least square scaling
Definition soplex.h:1108
@ ALGORITHM
type of algorithm, i.e., primal or dual
Definition soplex.h:1048
@ INTPARAM_COUNT
number of integer parameters
Definition soplex.h:1127
@ OBJSENSE
objective sense
Definition soplex.h:1042
@ SIMPLIFIER
type of simplifier
Definition soplex.h:1072
@ PRINTBASISMETRIC
print condition number during the solve
Definition soplex.h:1114
@ REPRESENTATION
type of computational form, i.e., column or row representation
Definition soplex.h:1045
@ SOLVEMODE
mode for iterative refinement strategy
Definition soplex.h:1093
@ RATFAC_MINSTALLS
minimum number of stalling refinements since last pivot to trigger rational factorization
Definition soplex.h:1105
@ SOLUTION_POLISHING
mode for solution polishing
Definition soplex.h:1111
@ FACTOR_UPDATE_MAX
maximum number of updates without fresh factorization
Definition soplex.h:1054
@ SCALER
type of scaler
Definition soplex.h:1075
@ ITERLIMIT
iteration limit (-1 if unlimited)
Definition soplex.h:1057
@ RATIOTESTER
type of ratio test
Definition soplex.h:1084
@ VERBOSITY
verbosity level
Definition soplex.h:1069
DSVectorRational _tauColVector
Definition soplex.h:1839
void _removeColReal(int i)
removes column i
void changeUpperRational(const VectorRational &upper)
changes vector of upper bounds to upper
void _convertDataArrayVarStatusToRPrecision(DataArray< typename SPxSolverBase< BP >::VarStatus > &base, DataArray< typename SPxSolverBase< R >::VarStatus > &copy)
SolRational _solRational
Definition soplex.h:1922
void _addColReal(const LPColReal &lpcol)
adds a single column to the real LP and adjusts basis
DataArray< typename SPxSolverBase< R >::VarStatus > _storedBasisStatusRows
Definition soplex.h:1851
bool getDualRational(mpq_t *vector, const int size)
gets the dual solution vector if available; returns true on success (GMP only method)
void changeElementRational(int i, int j, const Rational &val)
changes matrix entry in row i and column j to val
LPRowRational::Type rowTypeRational(int i) const
returns inequality type of row i
void getObjRational(int i, Rational &obj) const
gets objective value of column i
const char * getStarterName()
name of starter
void _storeBasis()
store basis
void _ensureRealLPLoaded()
ensures that the real LP and the basis are loaded in the solver; performs no sync
void changeLhsRational(int i, const mpq_t *lhs)
changes left-hand side of row i to lhs (GMP only method)
SolRational _workSol
Definition soplex.h:1923
const Rational & upperRational(int i) const
returns upper bound of column i
bool getSlacksRational(mpq_t *vector, const int size)
gets the vector of slack values if available; returns true on success (GMP only method)
VectorRational _unboundedLower
Definition soplex.h:1835
void printSolvingStatistics(std::ostream &os)
prints statistics on solving process
const VectorBase< R > & maxObjRealInternal() const
returns objective function vector after transformation to a maximization problem; since this is how i...
void _updateReducedCosts(SolRational &sol, int &dualSize, const int &numCorrectedPrimals)
updates or recomputes reduced cost values depending on which looks faster; adding one to the length o...
int numRowsRational() const
bool checkBasisDualFeasibility(VectorBase< R > feasVec)
checks the dual feasibility of the current basis
void _updateSlacks(SolRational &sol, int &primalSize)
updates or recomputes slacks depending on which looks faster
bool getSlacksRational(VectorRational &vector)
gets the vector of slack values if available; returns true on success
const SVectorBase< R > & rowVectorRealInternal(int i) const
returns vector of row i, ignoring scaling
const VectorBase< R > & lowerRealInternal() const
returns lower bound vector
bool getBasisIndRational(DataArray< int > &bind)
gets an array of indices for the columns of the rational basis matrix; bind[i] >= 0 means that the i-...
bool getBasisInverseTimesVecReal(R *rhs, R *sol, bool unscale=true)
computes dense solution of basis matrix B * sol = rhs; returns true on success
void _applyScaledObj(SPxSolverBase< T > &solver, Rational &dualScale, SolRational &sol)
applies scaled objective function
void _syncLPReal(bool time=true)
synchronizes real LP with rational LP, i.e., copies (rounded) rational LP into real LP,...
void _recomputeRangeTypesRational()
recomputes range types from scratch using rational LP
int numIterations() const
number of iterations since last call to solve
const SVectorBase< R > & colVectorRealInternal(int i) const
returns vector of col i, ignoring scaling
bool setDualNorms(int nnormsRow, int nnormsCol, R *norms)
sets steepest edge norms and returns false if that's not possible
bool _factorSolNewBasisPrecBoost
Definition soplex.h:1764
SPxGeometSC< R > _scalerGeo1
Definition soplex.h:1707
void addRowsReal(const LPRowSetBase< R > &lprowset)
adds multiple rows
void changeBoundsReal(int i, const R &lower, const R &upper)
changes bounds of column i to lower and upper
bool getPrimalRayReal(R *vector, int dim)
void _solveRealForRationalStable(SolRational &sol, bool &primalFeasible, bool &dualFeasible, bool &infeasible, bool &unbounded, bool &stoppedTime, bool &stoppedIter, bool &error)
solves current problem using double floating-point solver
bool parseSettingsString(char *str)
parses one setting string and returns true on success; note that string is modified
int numNonzerosRational() const
const SVectorRational & rowVectorRational(int i) const
returns vector of row i
void writeStateReal(const char *filename, const NameSet *rowNames=0, const NameSet *colNames=0, const bool cpxFormat=false) const
writes internal LP, basis information, and parameter settings; if rowNames and colNames are NULL,...
SPxLPBase< R > _manualRealLP
Definition soplex.h:1822
void changeColReal(int i, const LPColReal &lpcol)
replaces column i with lpcol
void changeObjRational(int i, const Rational &obj)
changes objective coefficient of column i to obj
void _changeBoundsReal(int i, const R &lower, const R &upper)
changes bounds of column i to lower and upper and adjusts basis
bool readFile(const char *filename, NameSet *rowNames=0, NameSet *colNames=0, DIdxSet *intVars=0)
reads LP file in LP or MPS format according to READMODE parameter; gets row names,...
void getBasisInd(int *bind) const
gets the indices of the basic columns and rows; basic column n gives value n, basic row m gives value...
SPxHarrisRT< BP > _boostedRatiotesterHarris
Definition soplex.h:1793
void clearLPRational()
clears the LP
void printStatus(std::ostream &os, typename SPxSolverBase< R >::Status status)
prints status
void changeRhsRational(const mpq_t *rhs, int rhsSize)
changes right-hand side vector to rhs (GMP only method)
void removeColRational(int i)
removes column i
void getBasis(typename SPxSolverBase< R >::VarStatus rows[], typename SPxSolverBase< R >::VarStatus cols[]) const
gets current basis via arrays of statuses
void _syncRealSolution()
synchronizes rational solution with real solution, i.e., copies (rounded) rational solution to real s...
int numColsRational() const
void addColReal(const LPColBase< R > &lpcol)
adds a single column
void getRowRational(int i, LPRowRational &lprow) const
gets row i
SPxLPBase< R > * _realLP
Definition soplex.h:1725
void _changeLhsReal(const VectorBase< R > &lhs)
changes left-hand side vector for constraints to lhs and adjusts basis
@ SYNCMODE_MANUAL
user sync of real and rational LP
Definition soplex.h:1300
@ SYNCMODE_ONLYREAL
store only real LP
Definition soplex.h:1294
@ SYNCMODE_AUTO
automatic sync of real and rational LP
Definition soplex.h:1297
bool boolParam(const BoolParam param) const
returns boolean parameter value
const Rational & lowerRational(int i) const
returns lower bound of column i
int dmaxSizeDualRational(const int base=2)
get size of largest denominator in dual solution
SPxParMultPR< R > _pricerParMult
Definition soplex.h:1716
const char * getPricerName()
name of currently loaded pricer
void addColsRational(const LPColSetRational &lpcolset)
adds multiple columns
VectorRational _feasLhs
Definition soplex.h:1841
bool writeFileRational(const char *filename, const NameSet *rowNames=0, const NameSet *colNames=0, const DIdxSet *intvars=0) const
void changeElementReal(int i, int j, const R &val)
changes matrix entry in row i and column j to val
void changeRangeReal(int i, const R &lhs, const R &rhs)
changes left- and right-hand side of row i
void getColRational(int i, LPColRational &lpcol) const
gets column i
void printUserSettings()
print non-default parameter values
bool _loadBasisFromOldBasis(bool boosted)
void _computePrimalScalingFactor(Rational &maxScale, Rational &primalScale, Rational &boundsViolation, Rational &sideViolation, Rational &redCostViolation)
computes primal scaling factor; limit increase in scaling by tolerance used in floating point solve
VectorRational _feasRhs
Definition soplex.h:1842
VectorRational _feasLower
Definition soplex.h:1843
void _correctDualSolution(SPxSolverBase< T > &solver, SolRational &sol, const bool &maximizing, VectorBase< T > &dualReal, Rational &dualScale, int &dualSize, const int &maxDimRational)
corrects dual solution and aligns with basis
SPxAutoPR< BP > _boostedPricerAuto
Definition soplex.h:1785
int numColsReal() const
bool areLPsInSync(const bool checkVecVals=true, const bool checkMatVals=false, const bool quiet=false) const
checks if real LP and rational LP are in sync; dimensions will always be compared,...
void _loadRealLP(bool initBasis)
load original LP and possibly setup a slack basis
const std::shared_ptr< Tolerances > tolerances() const
returns current tolerances
bool hasDual() const
deprecated: use hasSol() instead
Definition soplex.h:627
bool getDualFarkasReal(R *vector, int dim)
void changeUpperRational(int i, const mpq_t *upper)
changes upper bound of column i to upper (GMP only method)
void addRowsRational(const mpq_t *lhs, const mpq_t *rowValues, const int *rowIndices, const int *rowStarts, const int *rowLengths, const int numRows, const int numValues, const mpq_t *rhs)
adds a set of rows (GMP only method)
void _changeBoundsReal(const VectorBase< R > &lower, const VectorBase< R > &upper)
changes vectors of column bounds to lower and upper and adjusts basis
void _completeRangeTypesRational()
completes range type arrays after adding columns and/or rows
void changeUpperReal(const VectorBase< R > &upper)
changes vector of upper bounds to upper
Rational _rationalNegInfty
Definition soplex.h:1690
Rational _rationalZero
Definition soplex.h:1939
void _invalidateSolution()
invalidates solution
bool _readFileReal(const char *filename, NameSet *rowNames=0, NameSet *colNames=0, DIdxSet *intVars=0)
reads real LP in LP or MPS format from file and returns true on success; gets row names,...
DataArray< RangeType > _colTypes
Definition soplex.h:1877
bool isDualFeasible() const
is stored dual solution feasible?
DataArray< typename SPxSolverBase< R >::VarStatus > _basisStatusCols
Definition soplex.h:1890
void _transformFeasibility()
transforms LP to feasibility problem by removing the objective function, shifting variables,...
bool getBasisMetric(R &metric, int type=0)
SPxDantzigPR< R > _pricerDantzig
Definition soplex.h:1715
Presol< R > _simplifierPaPILO
Definition soplex.h:1704
SPxGeometSC< BP > _boostedScalerGeo8
Definition soplex.h:1803
bool getEstimatedCondition(R &condition)
computes an estimated condition number for the current basis matrix using the power method; returns t...
R lowerReal(int i) const
returns lower bound of column i
void removeRowRational(int i)
removes row i
Rational _rationalPosone
Definition soplex.h:1937
SPxParMultPR< BP > _boostedPricerParMult
Definition soplex.h:1787
bool getPrimalRational(VectorRational &vector)
int totalSizeDualRational(const int base=2)
get size of dual solution
int dlcmSizeDualRational(const int base=2)
get size of least common multiple of denominators in dual solution
SPxSteepPR< R > _pricerQuickSteep
Definition soplex.h:1718
void _project(SolRational &sol)
undoes lifting
bool getRedCostViolation(R &maxviol, R &sumviol)
gets violation of reduced costs; returns true on success
void addColRational(const LPColRational &lpcol)
adds a single column
void removeColsRational(int idx[], int n, int perm[]=0)
remove all columns with indices in array idx of size n; an array perm of size numColsRational() may b...
DSVectorRational _primalDualDiff
Definition soplex.h:1850
DataArray< typename SPxSolverBase< R >::VarStatus > _storedBasisStatusCols
Definition soplex.h:1852
void _computeDualScalingFactor(Rational &maxScale, Rational &primalScale, Rational &dualScale, Rational &redCostViolation, Rational &dualViolation)
computes dual scaling factor; limit increase in scaling by tolerance used in floating point solve
SPxSumST< R > _starterSum
Definition soplex.h:1712
bool ignoreUnscaledViolations()
sets the status to OPTIMAL in case the LP has been solved with unscaled violations
Definition soplex.h:642
bool getDualFarkas(VectorBase< R > &vector)
gets the Farkas proof if available; returns true on success
bool getDualFarkasRational(mpq_t *vector, const int size)
gets the Farkas proof if LP is infeasible; returns true on success (GMP only method)
SLUFactor< R > _slufactor
Definition soplex.h:1702
int numCols() const
Templated function that returns number of columns.
void _applyScaledBounds(SPxSolverBase< T > &solver, Rational &primalScale)
applies scaled bounds
bool _lowerFinite(const RangeType &rangeType) const
checks whether RangeType corresponds to finite lower bound
SPxDevexPR< R > _pricerDevex
Definition soplex.h:1717
void _checkRefinementProgress(Rational &boundsViolation, Rational &sideViolation, Rational &redCostViolation, Rational &dualViolation, Rational &maxViolation, Rational &bestViolation, const Rational &violationImprovementFactor, int &numFailedRefinements)
checks refinement loop progress
void changeObjReal(int i, const R &obj)
changes objective coefficient of column i to obj
Rational objRational(int i) const
returns objective value of column i
VectorBase< R > _manualObj
Definition soplex.h:1821
SLUFactorRational _rationalLUSolver
Definition soplex.h:1831
void setRandomSeed(unsigned int seed)
set the random seeds of the solver instance
void _computeInfeasBox(SolRational &sol, bool transformed)
bool writeBasisFile(const char *filename, const NameSet *rowNames=0, const NameSet *colNames=0, const bool cpxFormat=false) const
writes basis information to filename; if rowNames and colNames are NULL, default names are used; retu...
void printStatistics(std::ostream &os)
prints complete statistics
void _applyScaledSides(SPxSolverBase< T > &solver, Rational &primalScale)
applies scaled sides
int intParam(const IntParam param) const
returns integer parameter value
void changeBoundsRational(const VectorRational &lower, const VectorRational &upper)
changes vectors of column bounds to lower and upper
void _untransformEquality(SolRational &sol)
undoes transformation to equality form
@ SIMPLIFIER_INTERNAL
using internal presolving methods
Definition soplex.h:1202
@ SIMPLIFIER_PAPILO
using the presolve lib papilo
Definition soplex.h:1205
@ SIMPLIFIER_AUTO
SoPlex chooses automatically (currently always "internal")
Definition soplex.h:1208
@ SIMPLIFIER_OFF
disabling presolving
Definition soplex.h:1199
bool writeDualFileReal(const char *filename, const NameSet *rowNames=0, const NameSet *colNames=0, const DIdxSet *intvars=0) const
writes the dual of the real LP to file; LP or MPS format is chosen from the extension in filename; if...
bool writeFile(const char *filename, const NameSet *rowNames=0, const NameSet *colNames=0, const DIdxSet *intvars=0, const bool unscale=true) const
Templated write function Real writes real LP to file; LP or MPS format is chosen from the extension i...
Real _epsPivotPrecisionRatio
Definition soplex.h:1779
const char * getRatiotesterName()
name of currently loaded ratiotester
Rational objValueRational()
returns the objective value if a primal solution is available
void _solveRealForRationalBoosted(VectorBase< BP > &primal, VectorBase< BP > &dual, DataArray< typename SPxSolverBase< R >::VarStatus > &basisStatusRows, DataArray< typename SPxSolverBase< R >::VarStatus > &basisStatusCols, typename SPxSolverBase< BP >::Status &boostedResult, bool initialSolve)
solves real LP during iterative refinement
Real realParam(const RealParam param) const
returns real parameter value
int totalSizePrimalRational(const int base=2)
get size of primal solution
bool getBoundViolation(R &maxviol, R &sumviol)
gets violation of bounds; returns true on success
bool getBoundViolationRational(Rational &maxviol, Rational &sumviol)
void removeColsReal(int idx[], int n, int perm[]=0)
remove all columns with indices in array idx of size n; an array perm of size numColsReal() may be pa...
void changeRangeRational(int i, const mpq_t *lhs, const mpq_t *rhs)
changes left- and right-hand side of row i (GMP only method)
void changeObjRational(int i, const mpq_t *obj)
changes objective coefficient of column i to obj (GMP only method)
bool _upperFinite(const RangeType &rangeType) const
checks whether RangeType corresponds to finite upper bound
bool saveSettingsFile(const char *filename, const bool onlyChanged=false, int solvemode=1) const
writes settings file; returns true on success
SPxEquiliSC< BP > _boostedScalerBiequi
Definition soplex.h:1801
void changeRhsRational(int i, const Rational &rhs)
changes right-hand side of row i to rhs
SPxVectorST< R > _starterVector
Definition soplex.h:1713
void _convertDataArrayVarStatusToBoosted(DataArray< typename SPxSolverBase< R >::VarStatus > &base, DataArray< typename SPxSolverBase< BP >::VarStatus > &copy)
SPxBoundFlippingRT< BP > _boostedRatiotesterBoundFlipping
Definition soplex.h:1795
void _performOptIRStable(SolRational &sol, bool acceptUnbounded, bool acceptInfeasible, int minIRRoundsRemaining, bool &primalFeasible, bool &dualFeasible, bool &infeasible, bool &unbounded, bool &stoppedTime, bool &stoppedIter, bool &error)
solves current problem with iterative refinement and recovery mechanism
void _forceNonbasicToBound(SolRational &sol, int &c, const int &maxDimRational, bool toLower)
forces value of given nonbasic variable to bound
void _changeRangeReal(const VectorBase< R > &lhs, const VectorBase< R > &rhs)
changes left- and right-hand side vectors and adjusts basis
void _transformUnbounded()
transforms LP to unboundedness problem by moving the objective function to the constraints,...
void setBasis(const typename SPxSolverBase< R >::VarStatus rows[], const typename SPxSolverBase< R >::VarStatus cols[])
sets starting basis via arrays of statuses
std::shared_ptr< Tolerances > _tolerances
Definition soplex.h:1687
void _changeLowerReal(const VectorBase< R > &lower)
changes vector of lower bounds to lower and adjusts basis
void _changeUpperReal(const VectorBase< R > &upper)
changes vector of upper bounds to upper and adjusts basis
void removeColReal(int i)
removes column i
int dlcmSizePrimalRational(const int base=2)
get size of least common multiple of denominators in primal solution
void _computeBasisInverseRational()
computes rational inverse of basis matrix as defined by _rationalLUSolverBind
void _computeSidesViolation(SolRational &sol, Rational &sideViolation)
computes violation of sides during the refinement loop
R objReal(int i) const
returns objective value of column i
VectorRational _unboundedRhs
Definition soplex.h:1838
@ SCALER_GEOEQUI
geometric mean scaling (max 8 rounds) followed by equilibrium scaling (rows and columns)
Definition soplex.h:1233
@ SCALER_UNIEQUI
equilibrium scaling on rows or columns
Definition soplex.h:1218
@ SCALER_BIEQUI
equilibrium scaling on rows and columns
Definition soplex.h:1221
@ SCALER_LEASTSQ
least square scaling
Definition soplex.h:1230
@ SCALER_GEO1
geometric mean scaling on rows and columns, max 1 round
Definition soplex.h:1224
@ SCALER_OFF
no scaler
Definition soplex.h:1215
@ SCALER_GEO8
geometric mean scaling on rows and columns, max 8 rounds
Definition soplex.h:1227
SolBase< R > _solReal
Definition soplex.h:1921
SLUFactor< BP > _boostedSlufactor
Definition soplex.h:1783
DataArray< typename SPxSolverBase< R >::VarStatus > _oldFeasBasisStatusRows
Definition soplex.h:1902
void _performUnboundedIRStable(SolRational &sol, bool &hasUnboundedRay, bool &stoppedTime, bool &stoppedIter, bool &error)
performs iterative refinement on the auxiliary problem for testing unboundedness
bool getPrimal(VectorBase< R > &vector)
gets the primal solution vector if available; returns true on success
Settings * _currentSettings
Definition soplex.h:1685
void _switchToBoosted()
disable initial precision solver and switch to boosted solver
bool readBasisFile(const char *filename, const NameSet *rowNames=0, const NameSet *colNames=0)
reads basis information from filename and returns true on success; if rowNames and colNames are NULL,...
Presol< BP > _boostedSimplifierPaPILO
Definition soplex.h:1808
unsigned int randomSeed() const
returns the current random seed of the solver instance
SPxAutoPR< R > _pricerAuto
Definition soplex.h:1714
bool getExactCondition(R &condition)
computes the exact condition number for the current basis matrix using the power method; returns true...
Real _tolPrecisionRatio
ratios for computing the tolerances for precision boosting ratio denotes the proportion of precision ...
Definition soplex.h:1775
int numRowsReal() const
void _changeUpperReal(int i, const R &upper)
changes i 'th upper bound to upper and adjusts basis
void changeLowerRational(const VectorRational &lower)
changes vector of lower bounds to lower
void changeRowReal(int i, const LPRowBase< R > &lprow)
replaces row i with lprow
void _recomputeRangeTypesReal()
recomputes range types from scratch using real LP
int numIterationsBoosted() const
number of iterations in higher precision since last call to solve
SPxSteepExPR< R > _pricerSteep
Definition soplex.h:1719
bool getBasisInverseColRational(const int c, SSVectorRational &vec)
computes column c of basis inverse; performs rational factorization if not available; returns true on...
Rational _rationalOpttol
Definition soplex.h:1692
void _checkScaling(SPxLPBase< R > *origLP) const
check scaling of LP
void _solveRealForRationalBoostedStable(SolRational &sol, bool &primalFeasible, bool &dualFeasible, bool &infeasible, bool &unbounded, bool &stoppedTime, bool &stoppedIter, bool &error, bool &needNewBoostedIt)
solves current problem using multiprecision floating-point solver return false if a new boosted itera...
void removeRowReal(int i)
removes row i
DataArray< RangeType > _rowTypes
Definition soplex.h:1878
SPxDefaultRT< R > _ratiotesterTextbook
Definition soplex.h:1720
void _storeLastStableBasisBoosted(bool vanished)
SPxSolverBase< R >::VarStatus basisRowStatus(int row) const
returns basis status for a single row
void _restoreLPReal()
restores objective, bounds, and sides of real LP
SPxMainSM< BP > _boostedSimplifierMainSM
Definition soplex.h:1807
bool setBoolParam(const BoolParam param, const bool value, const bool init=true)
sets boolean parameter value; returns true on success
void changeLowerReal(const VectorBase< R > &lower)
changes vector of lower bounds to lower
void printSolutionStatistics(std::ostream &os)
prints solution statistics
void changeUpperReal(int i, const R &upper)
changes i 'th upper bound to upper
const Rational & maxObjRational(int i) const
returns objective value of column i after transformation to a maximization problem; since this is how...
void printShortStatistics(std::ostream &os)
prints short statistics
const Rational & lhsRational(int i) const
returns left-hand side of row i
int dmaxSizePrimalRational(const int base=2)
get size of largest denominator in primal solution
VectorRational _modLower
Definition soplex.h:1845
void changeUpperRational(int i, const Rational &upper)
changes i 'th upper bound to upper
bool getRedCost(VectorBase< R > &vector)
gets the vector of reduced cost values if available; returns true on success
SPxBoundFlippingRT< R > _ratiotesterBoundFlipping
Definition soplex.h:1723
bool getRedCostReal(R *vector, int dim)
void _syncLPRational(bool time=true)
synchronizes rational LP with real LP, i.e., copies real LP to rational LP, without looking at the sy...
bool _isBoostedStartingFromSlack(bool initialSolve=true)
return true if slack basis has to be loaded for boosted solver
bool _parseSettingsLine(char *line, const int lineNumber)
parses one line in a settings file and returns true on success; note that the string is modified
const char * getSimplifierName()
name of simplifier
const SVectorRational & colVectorRational(int i) const
returns vector of column i
void _syncRationalSolution()
synchronizes real solution with rational solution, i.e., copies real solution to rational solution
void _storeLastStableBasis(bool vanished)
void _changeLhsReal(int i, const R &lhs)
changes left-hand side of row i to lhs and adjusts basis
SPxSteepExPR< BP > _boostedPricerSteep
Definition soplex.h:1790
VectorRational _unboundedUpper
Definition soplex.h:1836
SPxSolverBase< R >::Status _status
Definition soplex.h:1886
void changeElementRational(int i, int j, const mpq_t *val)
changes matrix entry in row i and column j to val (GMP only method)
void _removeRowRangeReal(int start, int end, int perm[])
removes rows start to end including both; an array perm of size numRows() may be passed as buffer mem...
void changeBoundsRational(int i, const Rational &lower, const Rational &upper)
changes bounds of column i to lower and upper
RangeType _switchRangeType(const RangeType &rangeType) const
switches RANGETYPE_LOWER to RANGETYPE_UPPER and vice versa
void _ensureDSVectorRationalMemory(DSVectorRational &vec, const int newmax) const
extends sparse vector to hold newmax entries if and only if it holds no more free entries
bool _evaluateResult(SPxSolverBase< T > &solver, typename SPxSolverBase< T >::Status result, bool usingRefinedLP, SolRational &sol, VectorBase< T > &dualReal, bool &infeasible, bool &unbounded, bool &stoppedTime, bool &stoppedIter, bool &error)
evaluates result of solve. Return true if the algorithm must to stopped, false otherwise.
@ ALGORITHM_PRIMAL
primal simplex algorithm, i.e., entering for column and leaving for row representation
Definition soplex.h:1157
@ ALGORITHM_DUAL
dual simplex algorithm, i.e., leaving for column and entering for row representation
Definition soplex.h:1160
void _factorizeColumnRational(SolRational &sol, DataArray< typename SPxSolverBase< R >::VarStatus > &basisStatusRows, DataArray< typename SPxSolverBase< R >::VarStatus > &basisStatusCols, bool &stoppedTime, bool &stoppedIter, bool &error, bool &optimal)
factorizes rational basis matrix in column representation
void syncLPReal()
synchronizes real LP with rational LP, i.e., copies (rounded) rational LP into real LP,...
void _transformEquality()
introduces slack variables to transform inequality constraints into equations for both rational and r...
void clearBasis()
clears starting basis
SPxScaler< BP > * _boostedScaler
Definition soplex.h:1797
DataArray< int > _rationalLUSolverBind
Definition soplex.h:1832
Real _epsZeroPrecisionRatio
Definition soplex.h:1776
SPxGeometSC< R > _scalerGeo8
Definition soplex.h:1708
void _ratrecAndOrRatfac(int &minIRRoundsRemaining, int &lastStallIterations, int &numberOfIterations, bool &factorSolNewBasis, int &nextRatrec, const Rational &errorCorrectionFactor, Rational &errorCorrection, Rational &maxViolation, SolRational &sol, bool &primalFeasible, bool &dualFeasible, bool &stoppedTime, bool &stoppedIter, bool &error, bool &breakAfter, bool &continueAfter)
performs rational reconstruction and/or factorizationd
std::string statisticString() const
statistical information in form of a string
void _ensureRationalLP()
ensures that the rational LP is available; performs no sync
DataArray< typename SPxSolverBase< R >::VarStatus > _oldBasisStatusRows
Definition soplex.h:1898
VectorRational _modRhs
Definition soplex.h:1848
VectorBase< R > _manualLhs
Definition soplex.h:1819
void changeBoundsReal(const VectorBase< R > &lower, const VectorBase< R > &upper)
changes vectors of column bounds to lower and upper
void changeBoundsRational(int i, const mpq_t *lower, const mpq_t *upper)
changes bounds of column i to lower and upper (GMP only method)
void getNdualNorms(int &nnormsRow, int &nnormsCol) const
gets number of available dual norms
Rational _rationalNegone
Definition soplex.h:1938
void removeColRangeRational(int start, int end, int perm[]=0)
removes columns start to end including both; an array perm of size numColsRational() may be passed as...
SPxSolverBase< BP > _boostedSolver
Definition soplex.h:1747
void changeLhsRational(const VectorRational &lhs)
changes left-hand side vector for constraints to lhs
bool _isConsistent() const
checks consistency
void changeRowRational(int i, const LPRowRational &lprow)
replaces row i with lprow
void _addRowReal(const LPRowBase< R > &lprow)
adds a single row to the real LP and adjusts basis
void removeColRangeReal(int start, int end, int perm[]=0)
removes columns start to end including both; an array perm of size numColsReal() may be passed as buf...
void getUpperReal(VectorBase< R > &upper) const
gets upper bound vector
VectorBase< R > _manualLower
Definition soplex.h:1817
SoPlexBase< R > & operator=(const SoPlexBase< R > &rhs)
assignment operator
const VectorRational & maxObjRational() const
returns objective function vector after transformation to a maximization problem; since this is how i...
void removeRowsReal(int idx[], int n, int perm[]=0)
remove all rows with indices in array idx of size n; an array perm of size numRows() may be passed as...
bool hasPrimalRay() const
is a primal unbounded ray available?
bool getDual(VectorBase< R > &vector)
gets the dual solution vector if available; returns true on success
SPxSimplifier< BP > * _boostedSimplifier
Definition soplex.h:1798
void resetSettings(const bool quiet=false, const bool init=true)
resets default parameter settings
bool hasPrimal() const
deprecated: use hasSol() instead
Definition soplex.h:621
void removeRowsRational(int idx[], int n, int perm[]=0)
remove all rows with indices in array idx of size n; an array perm of size numRowsRational() may be p...
void changeObjReal(const VectorBase< R > &obj)
changes objective function vector to obj
Rational maxAbsNonzeroRational() const
returns biggest non-zero element in absolute value
@ POLISHING_FRACTIONALITY
minimize number of basic slack variables, i.e. more variables between bounds
Definition soplex.h:1375
@ POLISHING_OFF
no solution polishing
Definition soplex.h:1369
@ POLISHING_INTEGRALITY
maximize number of basic slack variables, i.e. more variables on bounds
Definition soplex.h:1372
void _correctPrimalSolution(SolRational &sol, Rational &primalScale, int &primalSize, const int &maxDimRational, VectorBase< T > &primalReal)
corrects primal solution and aligns with basis
Array< UnitVectorRational * > _unitMatrixRational
Definition soplex.h:1853
void _switchToStandardMode()
indicate if we are testing feasibility, unboundedness or neither
@ RATIOTESTER_TEXTBOOK
textbook ratio test without stabilization
Definition soplex.h:1278
@ RATIOTESTER_FAST
modified Harris ratio test
Definition soplex.h:1284
@ RATIOTESTER_HARRIS
standard Harris ratio test
Definition soplex.h:1281
@ RATIOTESTER_BOUNDFLIPPING
bound flipping ratio test for long steps in the dual simplex
Definition soplex.h:1287
VectorBase< R > _manualUpper
Definition soplex.h:1818
R maxObjReal(int i) const
returns objective value of column i after transformation to a maximization problem; since this is how...
void _unscaleSolutionReal(SPxLPBase< R > &LP, bool persistent=true)
unscales stored solution to remove internal or external scaling of LP
bool _reapplyPersistentScaling() const
check whether persistent scaling is supposed to be reapplied again after unscaling
void removeRowsReal(int perm[])
removes all rows with an index i such that perm[i] < 0; upon completion, perm[i] >= 0 indicates the n...
bool _inStandardMode()
check if we are testing feasibility, unboundedness or neither
int numNonzeros() const
returns number of nonzeros
void _changeRhsReal(const VectorBase< R > &rhs)
changes right-hand side vector to rhs and adjusts basis
SoPlexBase(const SoPlexBase< R > &rhs)
copy constructor
const VectorBase< R > & rhsRealInternal() const
returns right-hand side vector, ignoring scaling
void changeLowerRational(int i, const mpq_t *lower)
changes lower bound of column i to lower (GMP only method)
void _removeRowsReal(int perm[])
removes all rows with an index i such that perm[i] < 0; upon completion, perm[i] >= 0 indicates the n...
void _addRowReal(R lhs, const SVectorBase< R > &lprow, R rhs)
adds a single row to the real LP and adjusts basis
bool getBasisInverseRowRational(const int r, SSVectorRational &vec)
computes row r of basis inverse; performs rational factorization if not available; returns true on su...
SPxLeastSqSC< R > _scalerLeastsq
Definition soplex.h:1710
void _solveRealLPAndRecordStatistics(volatile bool *interrupt=NULL)
call floating-point solver and update statistics on iterations etc.
bool getPrimalRayRational(mpq_t *vector, const int size)
gets the primal ray if LP is unbounded; returns true on success (GMP only method)
bool getPrimalRayRational(VectorRational &vector)
void _storeBasisAsOldBasisBoosted(DataArray< typename SPxSolverBase< BP >::VarStatus > &rows, DataArray< typename SPxSolverBase< BP >::VarStatus > &cols)
SPxGeometSC< BP > _boostedScalerGeo1
Definition soplex.h:1802
void printVersion() const
prints version and compilation options
Statistics * _statistics
statistics since last call to solveReal() or solveRational()
Definition soplex.h:1677
SPxSolverBase< R > _solver
Definition soplex.h:1701
bool _boostPrecision()
increase the multiprecision, return false if maximum precision is reached, true otherwise
SPxDevexPR< BP > _boostedPricerDevex
Definition soplex.h:1788
void syncLPRational()
synchronizes rational LP with real LP, i.e., copies real LP to rational LP, if sync mode is manual
void clearLPReal()
clears the LP
@ HYPER_PRICING_OFF
never
Definition soplex.h:1356
@ HYPER_PRICING_ON
always
Definition soplex.h:1362
@ HYPER_PRICING_AUTO
decide according to problem size
Definition soplex.h:1359
void getColVectorReal(int i, DSVectorBase< R > &col) const
gets vector of col i
bool hasDualFarkas() const
is Farkas proof of infeasibility available?
SPxLPRational * _rationalLP
Definition soplex.h:1830
void _changeRangeReal(int i, const R &lhs, const R &rhs)
changes left- and right-hand side of row i and adjusts basis
VectorRational _feasUpper
Definition soplex.h:1844
void getColsRational(int start, int end, LPColSetRational &lpcolset) const
gets columns start, ..., end
@ READMODE_REAL
standard floating-point parsing
Definition soplex.h:1307
@ READMODE_RATIONAL
rational parsing
Definition soplex.h:1310
@ FACTOR_UPDATE_TYPE_ETA
product form update
Definition soplex.h:1167
@ FACTOR_UPDATE_TYPE_FT
Forrest-Tomlin type update.
Definition soplex.h:1170
bool setSettings(const Settings &newSettings, const bool init=true)
sets parameter settings; returns true on success
bool getRedCostRational(mpq_t *vector, const int size)
gets the vector of reduced cost values if available; returns true on success (GMP only method)
@ PRICER_DEVEX
devex pricer
Definition soplex.h:1265
@ PRICER_STEEP
steepest edge pricer with exact initialization of norms
Definition soplex.h:1271
@ PRICER_QUICKSTEEP
steepest edge pricer with initialization to unit norms
Definition soplex.h:1268
@ PRICER_PARMULT
partial multiple pricer based on Dantzig pricing
Definition soplex.h:1262
@ PRICER_AUTO
automatic pricer
Definition soplex.h:1256
@ PRICER_DANTZIG
Dantzig pricer.
Definition soplex.h:1259
void _addColsReal(const LPColSetReal &lpcolset)
adds multiple columns to the real LP and adjusts basis
Real _epsUpdatePrecisionRatio
Definition soplex.h:1778
Real _epsFactorPrecisionRatio
Definition soplex.h:1777
void _changeRhsReal(int i, const R &rhs)
changes right-hand side of row i to rhs and adjusts basis
SPxSimplifier< R > * _simplifier
Definition soplex.h:1726
void getRowVectorReal(int i, DSVectorBase< R > &row) const
gets vector of row i
void _storeBasisAsOldBasis(DataArray< typename SPxSolverBase< R >::VarStatus > &rows, DataArray< typename SPxSolverBase< R >::VarStatus > &cols)
void changeLhsReal(int i, const R &lhs)
changes left-hand side of row i to lhs
DataArray< typename SPxSolverBase< R >::VarStatus > _oldUnbdBasisStatusCols
Definition soplex.h:1907
void removeRowsRational(int perm[])
removes all rows with an index i such that perm[i] < 0; upon completion, perm[i] >= 0 indicates the n...
bool getBasisInverseRowReal(int r, R *coef, int *inds=NULL, int *ninds=NULL, bool unscale=true)
computes row r of basis inverse; returns true on success
const Settings & settings() const
returns current parameter settings
@ SOLVEMODE_RATIONAL
force iterative refinement
Definition soplex.h:1323
@ SOLVEMODE_REAL
apply standard floating-point algorithm
Definition soplex.h:1317
@ SOLVEMODE_AUTO
decide depending on tolerances whether to apply iterative refinement
Definition soplex.h:1320
bool getBasisInverseColReal(int c, R *coef, int *inds=NULL, int *ninds=NULL, bool unscale=true)
computes column c of basis inverse; returns true on success
LPRowBase< R >::Type rowTypeReal(int i) const
returns inequality type of row i
SPxFastRT< R > _ratiotesterFast
Definition soplex.h:1722
SPxDefaultRT< BP > _boostedRatiotesterTextbook
Definition soplex.h:1792
void _optimizeRational(volatile bool *interrupt=NULL)
temporary fix for Rational
SPxFastRT< BP > _boostedRatiotesterFast
Definition soplex.h:1794
void _resetBoostedPrecision()
reset the boosted precision to the default value
Rational _rationalFeastol
Definition soplex.h:1691
const VectorRational & lhsRational() const
returns left-hand side vector
void changeObjRational(const VectorRational &obj)
changes objective function vector to obj
void getLhsReal(VectorBase< R > &lhs) const
gets left-hand side vector
SPxSolverBase< R >::Status status() const
returns the current solver status
bool getDualFarkasRational(VectorRational &vector)
R maxAbsNonzeroReal() const
returns biggest non-zero element in absolute value
SPxBasisBase< R >::SPxStatus basisStatus() const
returns the current basis status
bool isPrimalFeasible() const
is stored primal solution feasible?
void getLowerReal(VectorBase< R > &lower) const
gets lower bound vector
void _performFeasIRStable(SolRational &sol, bool &withDualFarkas, bool &stoppedTime, bool &stoppedIter, bool &error)
performs iterative refinement on the auxiliary problem for testing feasibility
SPxStarter< R > * _starter
Definition soplex.h:1728
void _restoreBasis()
restore basis
SPxSteepPR< BP > _boostedPricerQuickSteep
Definition soplex.h:1789
RangeType _rangeTypeReal(const R &lower, const R &upper) const
determines RangeType from real bounds
bool getPrimalReal(R *p_vector, int size)
bool getDualRational(VectorRational &vector)
bool hasBasis() const
is an advanced starting basis available?
SPxScaler< R > * _scaler
Definition soplex.h:1727
void _untransformUnbounded(SolRational &sol, bool unbounded)
undoes transformation to unboundedness problem
bool _boostingLimitReached
Definition soplex.h:1752
void _verifySolutionReal()
verify computed solution and resolve if necessary
void removeColsReal(int perm[])
removes all columns with an index i such that perm[i] < 0; upon completion, perm[i] >= 0 indicates th...
DataArray< typename SPxSolverBase< R >::VarStatus > _oldFeasBasisStatusCols
Definition soplex.h:1903
Real precisionBoostTime() const
time spen in higher precision since last call to solve
virtual ~SoPlexBase()
destructor
SPxSolverBase< R >::Status _solveRealStable(bool acceptUnbounded, bool acceptInfeasible, VectorBase< R > &primal, VectorBase< R > &dual, DataArray< typename SPxSolverBase< R >::VarStatus > &basisStatusRows, DataArray< typename SPxSolverBase< R >::VarStatus > &basisStatusCols, const bool forceNoSimplifier=false)
solves real LP with recovery mechanism
void changeLowerReal(int i, const R &lower)
changes lower bound of column i to lower
void _evaluateSolutionReal(typename SPxSimplifier< R >::Result simplificationStatus)
checks result of the solving process and solves again without preprocessing if necessary
R upperReal(int i) const
returns upper bound of column i
bool setRealParam(const RealParam param, const Real value, const bool init=true)
sets real parameter value; returns true on success
const VectorRational & lowerRational() const
returns lower bound vector
void _removeColRangeReal(int start, int end, int perm[])
removes columns start to end including both; an array perm of size numColsReal() may be passed as buf...
void _changeElementReal(int i, int j, const R &val)
changes matrix entry in row i and column j to val and adjusts basis
void addRowReal(const LPRowBase< R > &lprow)
adds a single row
void _removeColsReal(int perm[])
removes all columns with an index i such that perm[i] < 0; upon completion, perm[i] >= 0 indicates th...
SPxSolverBase< R >::VarStatus basisColStatus(int col) const
returns basis status for a single column
Rational minAbsNonzeroRational() const
returns smallest non-zero element in absolute value
bool setIntParam(const IntParam param, const int value, const bool init=true)
sets integer parameter value; returns true on success
bool getDualReal(R *p_vector, int dim)
void getRowsRational(int start, int end, LPRowSetRational &lprowset) const
gets rows start, ..., end.
SPxMainSM< R > _simplifierMainSM
Definition soplex.h:1703
bool getDualViolationRational(Rational &maxviol, Rational &sumviol)
@ VERBOSITY_HIGH
high verbosity level
Definition soplex.h:1189
@ VERBOSITY_WARNING
only error and warning output
Definition soplex.h:1180
@ VERBOSITY_DEBUG
only error, warning, and debug output
Definition soplex.h:1183
@ VERBOSITY_NORMAL
standard verbosity level
Definition soplex.h:1186
@ VERBOSITY_ERROR
only error output
Definition soplex.h:1177
@ VERBOSITY_FULL
full verbosity level
Definition soplex.h:1192
void _addRowsReal(const LPRowSetBase< R > &lprowset)
adds multiple rows to the real LP and adjusts basis
int numPrecisionBoosts() const
number of precision boosts since last call to solve
SPxSolverBase< R >::Status solve(volatile bool *interrupt=NULL)
Definition soplex.h:606
DataArray< typename SPxSolverBase< R >::VarStatus > _oldUnbdBasisStatusRows
Definition soplex.h:1906
void addColsReal(const LPColSetBase< R > &lpcolset)
adds multiple columns
void _optimize(volatile bool *interrupt=NULL)
solves the templated LP
void changeRhsReal(const VectorBase< R > &rhs)
changes right-hand side vector to rhs
const VectorRational & rhsRational() const
returns right-hand side vector
void changeRangeReal(const VectorBase< R > &lhs, const VectorBase< R > &rhs)
changes left- and right-hand side vectors
void addRowRational(const mpq_t *lhs, const mpq_t *rowValues, const int *rowIndices, const int rowSize, const mpq_t *rhs)
adds a single row (GMP only method)
bool computeBasisInverseRational()
compute rational basis inverse; returns true on success
void removeRowRangeReal(int start, int end, int perm[]=0)
removes rows start to end including both; an array perm of size numRows() may be passed as buffer mem...
@ REPRESENTATION_AUTO
automatic choice according to number of rows and columns
Definition soplex.h:1144
@ REPRESENTATION_COLUMN
column representation Ax - s = 0, lower <= x <= upper, lhs <= s <= rhs
Definition soplex.h:1147
@ REPRESENTATION_ROW
row representation (lower,lhs) <= (x,Ax) <= (upper,rhs)
Definition soplex.h:1150
bool loadSettingsFile(const char *filename)
reads settings file; returns true on success
void _storeSolutionRealFromPresol()
stores solution from the simplifier because problem vanished in presolving step
const char * getScalerName()
name of scaling method
SPxGeometSC< R > _scalerGeoequi
Definition soplex.h:1709
void addColRational(const mpq_t *obj, const mpq_t *lower, const mpq_t *colValues, const int *colIndices, const int colSize, const mpq_t *upper)
adds a single column (GMP only method)
bool multBasis(R *vec, bool unscale=true)
multiply with basis matrix; B * vec (inplace)
VectorRational _modLhs
Definition soplex.h:1847
bool _reconstructSolutionRational(SolRational &sol, DataArray< typename SPxSolverBase< R >::VarStatus > &basisStatusRows, DataArray< typename SPxSolverBase< R >::VarStatus > &basisStatusCols, const Rational &denomBoundSquared)
attempts rational reconstruction of primal-dual solution
void _changeLowerReal(int i, const R &lower)
changes lower bound of column i to lower and adjusts basis
void changeRangeRational(const VectorRational &lhs, const VectorRational &rhs)
changes left- and right-hand side vectors
void _addColReal(R obj, R lower, const SVectorBase< R > &lpcol, R upper)
adds a single column to the real LP and adjusts basis
void changeLhsRational(int i, const Rational &lhs)
changes left-hand side of row i to lhs
void _performOptIRWrapper(SolRational &sol, bool acceptUnbounded, bool acceptInfeasible, int minIRRoundsRemaining, bool &primalFeasible, bool &dualFeasible, bool &infeasible, bool &unbounded, bool &stoppedTime, bool &stoppedIter, bool &error)
perform iterative refinement using the right precision
Rational _rationalMaxscaleincr
Definition soplex.h:1693
DataArray< typename SPxSolverBase< R >::VarStatus > _oldBasisStatusCols
Definition soplex.h:1899
void setIntegralityInformation(int ncols, int *intInfo)
pass integrality information about the variables to the solver
bool writeFileReal(const char *filename, const NameSet *rowNames=0, const NameSet *colNames=0, const DIdxSet *intvars=0, const bool unscale=true) const
void _computeReducedCostViolation(SolRational &sol, Rational &redCostViolation, const bool &maximizing)
computes violation of reduced costs during the refinement loop
R lhsReal(int i) const
returns left-hand side of row i
void addColsRational(const mpq_t *obj, const mpq_t *lower, const mpq_t *colValues, const int *colIndices, const int *colStarts, const int *colLengths, const int numCols, const int numValues, const mpq_t *upper)
adds a set of columns (GMP only method)
bool getPrimalRational(mpq_t *vector, const int size)
gets the primal solution vector if available; returns true on success (GMP only method)
void _computeBoundsViolation(SolRational &sol, Rational &boundsViolation)
computes violation of bounds during the refinement loop
void _disableSimplifierAndScaler()
disables simplifier and scaler
R minAbsNonzeroReal() const
returns smallest non-zero element in absolute value
void getObjRational(VectorRational &obj) const
gets objective function vector
SPxGeometSC< BP > _boostedScalerGeoequi
Definition soplex.h:1804
bool getPrimalRay(VectorBase< R > &vector)
gets the primal ray if available; returns true on success
SPxHarrisRT< R > _ratiotesterHarris
Definition soplex.h:1721
const Rational & rhsRational(int i) const
returns right-hand side of row i
const UnitVectorRational * _unitVectorRational(const int i)
returns pointer to a constant unit vector available until destruction of the SoPlexBase class
void _changeRowReal(int i, const LPRowBase< R > &lprow)
replaces row i with lprow and adjusts basis
bool getRedCostRational(VectorRational &vector)
void removeRowRangeRational(int start, int end, int perm[]=0)
removes rows start to end including both; an array perm of size numRowsRational() may be passed as bu...
void _setupBoostedSolver()
setup boosted solver before launching iteration
R rhsReal(int i) const
returns right-hand side of row i
bool _isRefinementOver(bool &primalFeasible, bool &dualFeasible, Rational &boundsViolation, Rational &sideViolation, Rational &redCostViolation, Rational &dualViolation, int minIRRoundsRemaining, bool &stoppedTime, bool &stoppedIter, int numFailedRefinements)
checks termination criteria for refinement loop
const VectorBase< R > & upperRealInternal() const
returns upper bound vector
bool getRedCostViolationRational(Rational &maxviol, Rational &sumviol)
bool hasSol() const
is a solution available (not neccessarily feasible)?
SPxEquiliSC< BP > _boostedScalerUniequi
Definition soplex.h:1800
LPColSetRational _slackCols
Definition soplex.h:1834
void changeRhsReal(int i, const R &rhs)
changes right-hand side of row i to rhs
void _idxToPerm(int *idx, int idxSize, int *perm, int permSize) const
creates a permutation for removing rows/columns from an array of indices
void changeRangeRational(int i, const Rational &lhs, const Rational &rhs)
changes left- and right-hand side of row i
bool _readFileRational(const char *filename, NameSet *rowNames=0, NameSet *colNames=0, DIdxSet *intVars=0)
reads rational LP in LP or MPS format from file and returns true on success; gets row names,...
void _lift()
reduces matrix coefficient in absolute value by the lifting procedure of Thiele et al....
void removeColsRational(int perm[])
removes all columns with an index i such that perm[i] < 0; upon completion, perm[i] >= 0 indicates th...
const VectorRational & upperRational() const
returns upper bound vector
BoolParam
boolean parameters
Definition soplex.h:952
@ TESTDUALINF
should dual infeasibility be tested in order to try to return a dual solution even if primal infeasib...
Definition soplex.h:960
@ FORCEBASIC
try to enforce that the optimal solution is a basic solution
Definition soplex.h:990
@ ENSURERAY
re-optimize the original problem to get a proof (ray) of infeasibility/unboundedness?
Definition soplex.h:987
@ PRECISION_BOOSTING
enable precision boosting ?
Definition soplex.h:1023
@ SIMPLIFIER_PARALLELCOLDETECTION
Definition soplex.h:1002
@ ACCEPTCYCLING
should cycling solutions be accepted during iterative refinement?
Definition soplex.h:966
@ RATREC
apply rational reconstruction after each iterative refinement?
Definition soplex.h:969
@ RATFAC
should a rational factorization be performed after iterative refinement?
Definition soplex.h:963
@ ADAPT_TOLS_TO_MULTIPRECISION
adapt tolerances to the multiprecision used
Definition soplex.h:1020
@ LIFTING
should lifting be used to reduce range of nonzero matrix coefficients?
Definition soplex.h:954
@ SIMPLIFIER_CONSTRAINTPROPAGATION
Definition soplex.h:996
@ EQTRANS
should LP be transformed to equality form before a rational solve?
Definition soplex.h:957
@ FULLPERTURBATION
perturb the entire problem or only the relevant bounds of s single pivot?
Definition soplex.h:984
@ BOOSTED_WARM_START
boosted solver start from last basis
Definition soplex.h:1026
@ STORE_BASIS_BEFORE_SIMPLEX_PIVOT
store advanced and stable basis met before each simplex iteration, to better warm start
Definition soplex.h:1032
@ SIMPLIFIER_SINGLETONSTUFFING
Definition soplex.h:1005
@ POWERSCALING
round scaling factors for iterative refinement to powers of two?
Definition soplex.h:972
@ BOOLPARAM_COUNT
number of boolean parameters
Definition soplex.h:1035
@ SIMPLIFIER_PARALLELROWDETECTION
Definition soplex.h:999
@ PERSISTENTSCALING
use persistent scaling?
Definition soplex.h:981
@ ROWBOUNDFLIPS
use bound flipping also for row representation?
Definition soplex.h:978
@ RATFACJUMP
continue iterative refinement with exact basic solution if not optimal?
Definition soplex.h:975
@ RECOVERY_MECHANISM
try different settings when solve fails
Definition soplex.h:1029
RangeType
type of bounds and sides
Definition soplex.h:1860
@ RANGETYPE_UPPER
upper bound is finite, lower bound is infinite
Definition soplex.h:1868
@ RANGETYPE_FIXED
lower bound equals upper bound
Definition soplex.h:1874
@ RANGETYPE_BOXED
lower and upper bound finite, but different
Definition soplex.h:1871
@ RANGETYPE_LOWER
lower bound is finite, upper bound is infinite
Definition soplex.h:1865
@ RANGETYPE_FREE
both bounds are infinite
Definition soplex.h:1862
void changeLowerRational(int i, const Rational &lower)
changes lower bound of column i to lower
SPxSolverBase< R >::Status optimize(volatile bool *interrupt=NULL)
optimize the given LP
void addRowRational(const LPRowRational &lprow)
adds a single row
Rational _rationalPosInfty
Definition soplex.h:1689
void _checkBasisScaling()
check correctness of (un)scaled basis matrix operations
RangeType _rangeTypeRational(const Rational &lower, const Rational &upper) const
determines RangeType from rational bounds
SPxEquiliSC< R > _scalerUniequi
Definition soplex.h:1705
void getRhsReal(VectorBase< R > &rhs) const
gets right-hand side vector
DataArray< typename SPxSolverBase< BP >::VarStatus > _tmpBasisStatusCols
Definition soplex.h:1919
void writeStateRational(const char *filename, const NameSet *rowNames=0, const NameSet *colNames=0, const bool cpxFormat=false) const
writes internal LP, basis information, and parameter settings; if rowNames and colNames are NULL,...
bool getRowViolationRational(Rational &maxviol, Rational &sumviol)
Class for storing a primal-dual solution with basis information.
Definition solbase.h:53
TYPE
types of timers
Definition timer.h:109
Dense vector.
Definition vectorbase.h:86
Everything should be within this namespace.
double Real
Definition spxdefines.h:269
Implementation of Sparse Linear Solver.
Implementation of Sparse Linear Solver with Rational precision.
Types of solution classes.
Class for storing a primal-dual solution with basis information.
Auto pricer.
Bound flipping ratio test (long step dual) for SoPlex.
Dantzig pricer.
Textbook ratio test for SoPlex.
Debugging, floating point type and parameter definitions.
Devex pricer.
LP equilibrium scaling.
Fast shifting ratio test.
LP geometric mean scaling.
returns the current git hash of SoPlex
Harris pricing with shifting.
Hybrid pricer.
LP least squares scaling.
Saving LPs in a form suitable for SoPlex.
General methods in LP preprocessing.
Partial multiple pricing.
Abstract pricer base class.
Abstract ratio test base class.
LP scaling base class.
LP simplification base class.
main LP solver class
SoPlex start basis generation base class.
Steepest edge pricer with exact initialization of weights.
Steepest edge pricer.
Simple heuristic SPxStarter.
Solution vector based start basis.
Weighted start basis.
std::string name[SoPlexBase< R >::BOOLPARAM_COUNT]
array of names for boolean parameters
Definition soplex.h:1484
std::string description[SoPlexBase< R >::BOOLPARAM_COUNT]
array of descriptions for boolean parameters
Definition soplex.h:1486
bool defaultValue[SoPlexBase< R >::BOOLPARAM_COUNT]
array of default values for boolean parameters
Definition soplex.h:1488
std::string name[SoPlexBase< R >::INTPARAM_COUNT]
array of names for integer parameters
Definition soplex.h:1496
int lower[SoPlexBase< R >::INTPARAM_COUNT]
array of lower bounds for int parameter values
Definition soplex.h:1502
int upper[SoPlexBase< R >::INTPARAM_COUNT]
array of upper bounds for int parameter values
Definition soplex.h:1504
int defaultValue[SoPlexBase< R >::INTPARAM_COUNT]
array of default values for integer parameters
Definition soplex.h:1500
std::string description[SoPlexBase< R >::INTPARAM_COUNT]
array of descriptions for integer parameters
Definition soplex.h:1498
Real upper[SoPlexBase< R >::REALPARAM_COUNT]
array of upper bounds for real parameter values
Definition soplex.h:1520
Real defaultValue[SoPlexBase< R >::REALPARAM_COUNT]
array of default values for real parameters
Definition soplex.h:1516
Real lower[SoPlexBase< R >::REALPARAM_COUNT]
array of lower bounds for real parameter values
Definition soplex.h:1518
std::string description[SoPlexBase< R >::REALPARAM_COUNT]
array of descriptions for real parameters
Definition soplex.h:1514
std::string name[SoPlexBase< R >::REALPARAM_COUNT]
array of names for real parameters
Definition soplex.h:1512