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 /// number of boolean parameters
1032 BOOLPARAM_COUNT = 26
1034
1035 /// integer parameters
1036 typedef enum
1037 {
1038 /// objective sense
1040
1041 /// type of computational form, i.e., column or row representation
1043
1044 /// type of algorithm, i.e., primal or dual
1046
1047 /// type of LU update
1049
1050 /// maximum number of updates without fresh factorization
1052
1053 /// iteration limit (-1 if unlimited)
1055
1056 /// refinement limit (-1 if unlimited)
1058
1059 /// stalling refinement limit (-1 if unlimited)
1061
1062 /// display frequency
1064
1065 /// verbosity level
1067
1068 /// type of simplifier
1070
1071 /// type of scaler
1073
1074 /// type of starter used to create crash basis
1076
1077 /// type of pricer
1079
1080 /// type of ratio test
1082
1083 /// mode for synchronizing real and rational LP
1085
1086 /// mode for reading LP files
1088
1089 /// mode for iterative refinement strategy
1091
1092 /// mode for a posteriori feasibility checks
1094
1095 /// type of timer
1096 TIMER = 19,
1097
1098 /// mode for hyper sparse pricing
1100
1101 /// minimum number of stalling refinements since last pivot to trigger rational factorization
1103
1104 /// maximum number of conjugate gradient iterations in least square scaling
1106
1107 /// mode for solution polishing
1109
1110 /// print condition number during the solve
1112
1113 /// type of timer for statistics
1115
1116 // maximum number of digits for the multiprecision type
1118
1119 ///@todo precision-boosting find better parameter name
1120 /// after how many simplex pivots do we store the advanced and stable basis, 1 = every iterations
1122
1123 /// number of integer parameters
1124 INTPARAM_COUNT = 28
1126
1127 /// values for parameter OBJSENSE
1128 enum
1129 {
1130 /// minimization
1132
1133 /// maximization
1136
1137 /// values for parameter REPRESENTATION
1138 enum
1139 {
1140 /// automatic choice according to number of rows and columns
1142
1143 /// column representation Ax - s = 0, lower <= x <= upper, lhs <= s <= rhs
1145
1146 /// row representation (lower,lhs) <= (x,Ax) <= (upper,rhs)
1149
1150 /// values for parameter ALGORITHM
1151 enum
1152 {
1153 /// primal simplex algorithm, i.e., entering for column and leaving for row representation
1155
1156 /// dual simplex algorithm, i.e., leaving for column and entering for row representation
1157 ALGORITHM_DUAL = 1
1159
1160 /// values for parameter FACTOR_UPDATE_TYPE
1161 enum
1162 {
1163 /// product form update
1165
1166 /// Forrest-Tomlin type update
1169
1170 /// values for parameter VERBOSITY
1171 enum
1172 {
1173 /// only error output
1175
1176 /// only error and warning output
1178
1179 /// only error, warning, and debug output
1181
1182 /// standard verbosity level
1184
1185 /// high verbosity level
1187
1188 /// full verbosity level
1189 VERBOSITY_FULL = 5
1191
1192 /// values for parameter SIMPLIFIER
1193 enum
1194 {
1195 /// disabling presolving
1197
1198 /// using internal presolving methods
1200
1201 /// using the presolve lib papilo
1203
1204 /// SoPlex chooses automatically (currently always "internal")
1205 SIMPLIFIER_AUTO = 1
1207
1208 /// values for parameter SCALER
1209 enum
1210 {
1211 /// no scaler
1213
1214 /// equilibrium scaling on rows or columns
1216
1217 /// equilibrium scaling on rows and columns
1219
1220 /// geometric mean scaling on rows and columns, max 1 round
1222
1223 /// geometric mean scaling on rows and columns, max 8 rounds
1225
1226 /// least square scaling
1228
1229 /// geometric mean scaling (max 8 rounds) followed by equilibrium scaling (rows and columns)
1230 SCALER_GEOEQUI = 6
1232
1233 /// values for parameter STARTER
1234 enum
1235 {
1236 /// slack basis
1238
1239 /// greedy crash basis weighted by objective, bounds, and sides
1241
1242 /// crash basis from a greedy solution
1244
1245 /// generic solution-based crash basis
1246 STARTER_VECTOR = 3
1248
1249 /// values for parameter PRICER
1250 enum
1251 {
1252 /// automatic pricer
1254
1255 /// Dantzig pricer
1257
1258 /// partial multiple pricer based on Dantzig pricing
1260
1261 /// devex pricer
1263
1264 /// steepest edge pricer with initialization to unit norms
1266
1267 /// steepest edge pricer with exact initialization of norms
1268 PRICER_STEEP = 5
1270
1271 /// values for parameter RATIOTESTER
1272 enum
1273 {
1274 /// textbook ratio test without stabilization
1276
1277 /// standard Harris ratio test
1279
1280 /// modified Harris ratio test
1282
1283 /// bound flipping ratio test for long steps in the dual simplex
1286
1287 /// values for parameter SYNCMODE
1288 enum
1289 {
1290 /// store only real LP
1292
1293 /// automatic sync of real and rational LP
1295
1296 /// user sync of real and rational LP
1297 SYNCMODE_MANUAL = 2
1299
1300 /// values for parameter READMODE
1301 enum
1302 {
1303 /// standard floating-point parsing
1305
1306 /// rational parsing
1309
1310 /// values for parameter SOLVEMODE
1311 enum
1312 {
1313 /// apply standard floating-point algorithm
1315
1316 /// decide depending on tolerances whether to apply iterative refinement
1318
1319 /// force iterative refinement
1322
1323 /// values for parameter CHECKMODE
1324 enum
1325 {
1326 /// floating-point check
1328
1329 /// decide according to READMODE
1331
1332 /// rational check
1335
1336 /// values for parameter TIMER
1337 enum
1338 {
1339 /// disable timing
1341
1342 /// cpu or user time
1344
1345 /// wallclock time
1346 TIMER_WALLCLOCK = 2
1348
1349 /// values for parameter HYPER_PRICING
1350 enum
1351 {
1352 /// never
1354
1355 /// decide according to problem size
1357
1358 /// always
1361
1362 /// values for parameter SOLUTION_POLISHING
1363 enum
1364 {
1365 /// no solution polishing
1367
1368 /// maximize number of basic slack variables, i.e. more variables on bounds
1370
1371 /// minimize number of basic slack variables, i.e. more variables between bounds
1374
1375 /// real parameters
1376 typedef enum
1377 {
1378 /// primal feasibility tolerance
1380
1381 /// dual feasibility tolerance
1383
1384 /// general zero tolerance
1386
1387 /// zero tolerance used in factorization
1389
1390 /// zero tolerance used in update of the factorization
1392
1393 /// pivot zero tolerance used in factorization
1395
1396 /// infinity threshold
1398
1399 /// time limit in seconds (INFTY if unlimited)
1401
1402 /// lower limit on objective value
1404
1405 /// upper limit on objective value
1407
1408 /// working tolerance for feasibility in floating-point solver during iterative refinement
1410
1411 /// working tolerance for optimality in floating-point solver during iterative refinement
1413
1414 /// maximum increase of scaling factors between refinements
1416
1417 /// lower threshold in lifting (nonzero matrix coefficients with smaller absolute value will be reformulated)
1419
1420 /// upper threshold in lifting (nonzero matrix coefficients with larger absolute value will be reformulated)
1422
1423 /// sparse pricing threshold (\#violations < dimension * SPARSITY_THRESHOLD activates sparse pricing)
1425
1426 /// threshold on number of rows vs. number of columns for switching from column to row representations in auto mode
1428
1429 /// geometric frequency at which to apply rational reconstruction
1431
1432 /// minimal reduction (sum of removed rows/cols) to continue simplification
1434
1435 /// refactor threshold for nonzeros in last factorized basis matrix compared to updated basis matrix
1437
1438 /// refactor threshold for fill-in in current factor update compared to fill-in in last factorization
1440
1441 /// refactor threshold for memory growth in factorization since last refactorization
1443
1444 /// accuracy of conjugate gradient method in least squares scaling (higher value leads to more iterations)
1446
1447 /// objective offset
1449
1450 /// minimal Markowitz threshold to control sparsity/stability in LU factorization
1452
1453 /// minimal modification threshold to apply presolve reductions
1455
1456 /// factor by which the precision of the floating-point solver is multiplied
1458
1459 /// number of real parameters
1460 REALPARAM_COUNT = 27
1462
1463#ifdef SOPLEX_WITH_RATIONALPARAM
1464 /// rational parameters
1465 typedef enum
1466 {
1467 /// number of rational parameters
1468 RATIONALPARAM_COUNT = 0
1469 } RationalParam;
1470#endif
1471
1472 /// class of parameter settings
1474 {
1475 public:
1476 static struct BoolParam
1477 {
1478 /// constructor
1480 /// array of names for boolean parameters
1482 /// array of descriptions for boolean parameters
1484 /// array of default values for boolean parameters
1487
1488 static struct IntParam
1489 {
1490 /// constructor
1492 /// array of names for integer parameters
1494 /// array of descriptions for integer parameters
1496 /// array of default values for integer parameters
1498 /// array of lower bounds for int parameter values
1500 /// array of upper bounds for int parameter values
1503
1504 static struct RealParam
1505 {
1506 /// constructor
1508 /// array of names for real parameters
1510 /// array of descriptions for real parameters
1512 /// array of default values for real parameters
1514 /// array of lower bounds for real parameter values
1516 /// array of upper bounds for real parameter values
1519
1520#ifdef SOPLEX_WITH_RATIONALPARAM
1521 static struct RationalParam
1522 {
1523 /// constructor
1524 RationalParam();
1525 /// array of names for rational parameters
1526 std::string name[SoPlexBase<R>::RATIONALPARAM_COUNT];
1527 /// array of descriptions for rational parameters
1528 std::string description[SoPlexBase<R>::RATIONALPARAM_COUNT];
1529 /// array of default values for rational parameters
1531 /// array of lower bounds for rational parameter values
1533 /// array of upper bounds for rational parameter values
1535 } rationalParam;
1536#endif
1537
1538 /// array of current boolean parameter values
1540
1541 /// array of current integer parameter values
1543
1544 /// array of current real parameter values
1546
1547#ifdef SOPLEX_WITH_RATIONALPARAM
1548 /// array of current rational parameter values
1549 Rational _rationalParamValues[SoPlexBase<R>::RATIONALPARAM_COUNT];
1550#endif
1551
1552 /// default constructor initializing default settings
1554
1555 /// copy constructor
1557
1558 /// assignment operator
1560 };
1561
1563
1564 /// returns boolean parameter value
1565 bool boolParam(const BoolParam param) const;
1566
1567 /// returns integer parameter value
1568 int intParam(const IntParam param) const;
1569
1570 /// returns real parameter value
1571 Real realParam(const RealParam param) const;
1572
1573#ifdef SOPLEX_WITH_RATIONALPARAM
1574 /// returns rational parameter value
1575 Rational rationalParam(const RationalParam param) const;
1576#endif
1577
1578 /// returns current parameter settings
1579 const Settings& settings() const;
1580
1581 /// returns current tolerances
1582 const std::shared_ptr<Tolerances> tolerances() const;
1583
1584 /// sets boolean parameter value; returns true on success
1585 bool setBoolParam(const BoolParam param, const bool value, const bool init = true);
1586
1587 /// sets integer parameter value; returns true on success
1588 bool setIntParam(const IntParam param, const int value, const bool init = true);
1589
1590 /// sets real parameter value; returns true on success
1591 bool setRealParam(const RealParam param, const Real value, const bool init = true);
1592
1593#ifdef SOPLEX_WITH_RATIONALPARAM
1594 /// sets rational parameter value; returns true on success
1595 bool setRationalParam(const RationalParam param, const Rational value, const bool init = true);
1596#endif
1597
1598 /// sets parameter settings; returns true on success
1599 bool setSettings(const Settings& newSettings, const bool init = true);
1600
1601 /// resets default parameter settings
1602 void resetSettings(const bool quiet = false, const bool init = true);
1603
1604 /// print non-default parameter values
1606
1607 /// writes settings file; returns true on success
1608 bool saveSettingsFile(const char* filename, const bool onlyChanged = false,
1609 int solvemode = 1) const;
1610
1611 /// reads settings file; returns true on success
1612 bool loadSettingsFile(const char* filename);
1613
1614 /// parses one setting string and returns true on success; note that string is modified
1615 bool parseSettingsString(char* str);
1616
1617 ///@}
1618
1619
1620 ///@name Statistics
1621 ///@{
1622
1623 /// set statistic timers to a certain type
1624 void setTimings(const Timer::TYPE ttype);
1625
1626 /// prints solution statistics
1627 void printSolutionStatistics(std::ostream& os);
1628
1629 /// prints statistics on solving process
1630 void printSolvingStatistics(std::ostream& os);
1631
1632 /// prints short statistics
1633 void printShortStatistics(std::ostream& os);
1634
1635 /// prints complete statistics
1636 void printStatistics(std::ostream& os);
1637
1638 /// prints status
1639
1640 void printStatus(std::ostream& os, typename SPxSolverBase<R>::Status status);
1641
1642 ///@}
1643
1644
1645 ///@name Miscellaneous
1646 ///@{
1647
1648 /// prints version and compilation options
1649 void printVersion() const;
1650
1651 /// checks if real LP and rational LP are in sync; dimensions will always be compared,
1652 /// vector and matrix values only if the respective parameter is set to true.
1653 /// If quiet is set to true the function will only display which vectors are different.
1654 bool areLPsInSync(const bool checkVecVals = true, const bool checkMatVals = false,
1655 const bool quiet = false) const;
1656
1657 /// set the random seeds of the solver instance
1658 void setRandomSeed(unsigned int seed);
1659
1660 /// returns the current random seed of the solver instance
1661 unsigned int randomSeed() const;
1662
1663 ///@}
1664
1665private:
1666
1667 ///@name Statistics on solving process
1668 ///@{
1669
1670 /// class of statistics
1671 class Statistics;
1672
1673 /// statistics since last call to solveReal() or solveRational()
1675
1676 ///@}
1677
1678
1679 ///@name Parameter settings
1680 ///@{
1681
1683
1684 std::shared_ptr<Tolerances> _tolerances;
1685
1691
1692 ///@}
1693
1694
1695 ///@name Data for the real LP
1696 ///@{
1697
1721
1726
1727#ifdef SOPLEX_WITH_BOOST
1728#ifdef SOPLEX_WITH_MPFR
1729 //----------------------------- BOOSTED SOLVER -----------------------------
1730 // multiprecision type used for the boosted solver
1731 using BP = number<mpfr_float_backend<0>, et_off>;
1732#else
1733#ifdef SOPLEX_WITH_GMP
1734 using BP = number<gmp_float<50>, et_off>;
1735#else
1736 using BP = number<cpp_dec_float<50>, et_off>;
1737#endif
1738#endif
1739#else
1740 using BP = double;
1741#endif
1742
1743 // boosted solver object
1745
1746 // ------------- Main attributes for precision boosting
1747
1748 int _initialPrecision = 50; // initial number of digits for multiprecision
1749 bool _boostingLimitReached; // true if BP::default_precision() > max authorized number of digits
1750 bool _switchedToBoosted; // true if _boostedSolver is used instead of _solver to cope with the numerical failure of _solver
1751 // this attribute remembers wether we are testing feasibility (1), unboundedness (2) or neither (0)
1752 // it is used when storing/loading the right basis in precision boosting.
1753 // example: if _certificateMode == 1, it is the basis for the feasibility LP that should be stored/loaded.
1755
1756 // ------------- Buffers for statistics of precision boosting
1757
1758 // ideally these four attributes would be local variables, however the precision boosting loop
1759 // wraps the solve in a way that it is complicated to declare these variables locally.
1760 int _lastStallPrecBoosts; // number of previous stalling precision boosts
1761 bool _factorSolNewBasisPrecBoost; // false if the current basis has already been factorized (no new iterations have been done)
1762 int _nextRatrecPrecBoost; // the iteration during or after which rational reconstruction can be performed
1763 // buffer storing the number of iterations before a given precision boost
1764 // used to detect stalling (_prevIterations < _statistics->iterations)
1766
1767 // ------------- Tolerances Ratios
1768
1769 /// ratios for computing the tolerances for precision boosting
1770 /// ratio denotes the proportion of precision used by the tolerance
1771 /// e.g. ratio = 0.65, precision = 100 digits, new tol = 10^(0.65*100)
1777
1778 // ------------- [Boosted] SLUFactor, Pricers, RatioTesters, Scalers, Simplifiers
1779
1781
1788
1793
1796
1803
1806
1807 //--------------------------------------------------------------------------
1808
1809 bool _isRealLPLoaded; // true indicates that the original LP is loaded in the _solver variable, hence all actions
1810 // are performed on the original LP.
1813
1820
1821 ///@}
1822
1823
1824 ///@name Data for the rational LP
1825 ///@{
1826
1830
1854
1855 /// type of bounds and sides
1856 typedef enum
1857 {
1858 /// both bounds are infinite
1860
1861 /// lower bound is finite, upper bound is infinite
1863
1864 /// upper bound is finite, lower bound is infinite
1866
1867 /// lower and upper bound finite, but different
1869
1870 /// lower bound equals upper bound
1871 RANGETYPE_FIXED = 4
1873
1876
1877 ///@}
1878
1879
1880 ///@name Solution data
1881 ///@{
1882
1885
1888
1889 // indicates wether an old basis is currently stored for warm start
1891 bool _hasOldFeasBasis; // basis for testing feasibility
1892 bool _hasOldUnbdBasis; // basis for testing unboundedness
1893
1894 // these vectors store the last basis met in precision boosting when not testing feasibility or unboundedness.
1897
1898 // these vectors store the last basis met when testing feasibility in precision boosting.
1901
1902 // these vectors store the last basis met when testing unboundedness in precision boosting.
1905
1906 // these vectors don't replace _basisStatusRows and _basisStatusCols
1907 // they aim to overcome the issue of having the enum VarStatus inside SPxSolverBase.
1908 // When calling setBasis or getBasis (from SPxSolverBase class), a specific conversion is needed.
1909 // Function: SPxSolverBase<BP>::setBasis(...)
1910 // Usage: copy _basisStatusRows(Cols) to _tmpBasisStatusRows(Cols) before calling
1911 // mysolver.setBasis(_tmpBasisStatusRows, _tmpBasisStatusCols)
1912 // Function: SPxSolverBase<BP>::getBasis(...)
1913 // Usage: copy _tmpBasisStatusRows(Cols) to _basisStatusRows(Cols) after calling
1914 // mysolver.getBasis(_tmpBasisStatusRows, _tmpBasisStatusCols, _basisStatusRows.size(), _basisStatusCols.size())
1917
1921
1925
1926 ///@}
1927
1928 ///@name Miscellaneous
1929 ///@{
1930
1933
1937
1938 ///@}
1939
1940 ///@name Constant helper methods
1941 ///@{
1942
1943 /// extends sparse vector to hold newmax entries if and only if it holds no more free entries
1944 void _ensureDSVectorRationalMemory(DSVectorRational& vec, const int newmax) const;
1945
1946 /// creates a permutation for removing rows/columns from an array of indices
1947 void _idxToPerm(int* idx, int idxSize, int* perm, int permSize) const;
1948
1949 /// creates a permutation for removing rows/columns from a range of indices
1950 void _rangeToPerm(int start, int end, int* perm, int permSize) const;
1951
1952 /// checks consistency for the boosted solver
1954
1955 /// checks consistency
1956 bool _isConsistent() const;
1957
1958 /// should solving process be stopped?
1959 bool _isSolveStopped(bool& stoppedTime, bool& stoppedIter) const;
1960
1961 /// determines RangeType from real bounds
1962 RangeType _rangeTypeReal(const R& lower, const R& upper) const;
1963
1964 /// determines RangeType from rational bounds
1965 RangeType _rangeTypeRational(const Rational& lower, const Rational& upper) const;
1966
1967 /// switches RANGETYPE_LOWER to RANGETYPE_UPPER and vice versa
1968 RangeType _switchRangeType(const RangeType& rangeType) const;
1969
1970 /// checks whether RangeType corresponds to finite lower bound
1971 bool _lowerFinite(const RangeType& rangeType) const;
1972
1973 /// checks whether RangeType corresponds to finite upper bound
1974 bool _upperFinite(const RangeType& rangeType) const;
1975
1976 ///@}
1977
1978
1979 ///@name Non-constant helper methods
1980 ///@{
1981
1982 /// adds a single row to the real LP and adjusts basis
1983 void _addRowReal(const LPRowBase<R>& lprow);
1984
1985 /// adds a single row to the real LP and adjusts basis
1986 void _addRowReal(R lhs, const SVectorBase<R>& lprow, R rhs);
1987
1988 /// adds multiple rows to the real LP and adjusts basis
1989 void _addRowsReal(const LPRowSetBase<R>& lprowset);
1990
1991 /// adds a single column to the real LP and adjusts basis
1992 void _addColReal(const LPColReal& lpcol);
1993
1994 /// adds a single column to the real LP and adjusts basis
1995 void _addColReal(R obj, R lower, const SVectorBase<R>& lpcol, R upper);
1996
1997 /// adds multiple columns to the real LP and adjusts basis
1998 void _addColsReal(const LPColSetReal& lpcolset);
1999
2000 /// replaces row \p i with \p lprow and adjusts basis
2001 void _changeRowReal(int i, const LPRowBase<R>& lprow);
2002
2003 /// changes left-hand side vector for constraints to \p lhs and adjusts basis
2005
2006 /// changes left-hand side of row \p i to \p lhs and adjusts basis
2007 void _changeLhsReal(int i, const R& lhs);
2008
2009 /// changes right-hand side vector to \p rhs and adjusts basis
2011
2012 /// changes right-hand side of row \p i to \p rhs and adjusts basis
2013 void _changeRhsReal(int i, const R& rhs);
2014
2015 /// changes left- and right-hand side vectors and adjusts basis
2016 void _changeRangeReal(const VectorBase<R>& lhs, const VectorBase<R>& rhs);
2017
2018 /// changes left- and right-hand side of row \p i and adjusts basis
2019 void _changeRangeReal(int i, const R& lhs, const R& rhs);
2020
2021 /// replaces column \p i with \p lpcol and adjusts basis
2022 void _changeColReal(int i, const LPColReal& lpcol);
2023
2024 /// changes vector of lower bounds to \p lower and adjusts basis
2026
2027 /// changes lower bound of column i to \p lower and adjusts basis
2028 void _changeLowerReal(int i, const R& lower);
2029
2030 /// changes vector of upper bounds to \p upper and adjusts basis
2032
2033 /// changes \p i 'th upper bound to \p upper and adjusts basis
2034 void _changeUpperReal(int i, const R& upper);
2035
2036 /// changes vectors of column bounds to \p lower and \p upper and adjusts basis
2037 void _changeBoundsReal(const VectorBase<R>& lower, const VectorBase<R>& upper);
2038
2039 /// changes bounds of column \p i to \p lower and \p upper and adjusts basis
2040 void _changeBoundsReal(int i, const R& lower, const R& upper);
2041
2042 /// changes matrix entry in row \p i and column \p j to \p val and adjusts basis
2043 void _changeElementReal(int i, int j, const R& val);
2044
2045 /// removes row \p i and adjusts basis
2046 void _removeRowReal(int i);
2047
2048 /// removes all rows with an index \p i such that \p perm[i] < 0; upon completion, \p perm[i] >= 0 indicates the
2049 /// new index where row \p i has been moved to; note that \p perm must point to an array of size at least
2050 /// #numRows()
2051 void _removeRowsReal(int perm[]);
2052
2053 /// remove all rows with indices in array \p idx of size \p n; an array \p perm of size #numRows() may be passed
2054 /// as buffer memory
2055 void _removeRowsReal(int idx[], int n, int perm[]);
2056
2057 /// removes rows \p start to \p end including both; an array \p perm of size #numRows() may be passed as buffer
2058 /// memory
2059 void _removeRowRangeReal(int start, int end, int perm[]);
2060
2061 /// removes column i
2062 void _removeColReal(int i);
2063
2064 /// removes all columns with an index \p i such that \p perm[i] < 0; upon completion, \p perm[i] >= 0 indicates the
2065 /// new index where column \p i has been moved to; note that \p perm must point to an array of size at least
2066 /// #numColsReal()
2067 void _removeColsReal(int perm[]);
2068
2069 /// remove all columns with indices in array \p idx of size \p n; an array \p perm of size #numColsReal() may be
2070 /// passed as buffer memory
2071 void _removeColsReal(int idx[], int n, int perm[]);
2072
2073 /// removes columns \p start to \p end including both; an array \p perm of size #numColsReal() may be passed as
2074 /// buffer memory
2075 void _removeColRangeReal(int start, int end, int perm[]);
2076
2077 /// invalidates solution
2079
2080 /// enables simplifier and scaler according to current parameters
2082
2083 /// disables simplifier and scaler
2085
2086 /// ensures that the rational LP is available; performs no sync
2088
2089 /// ensures that the real LP and the basis are loaded in the solver; performs no sync
2091
2092 /// call floating-point solver and update statistics on iterations etc.
2093 void _solveBoostedRealLPAndRecordStatistics(volatile bool* interrupt = NULL);
2094
2095 /// call floating-point solver and update statistics on iterations etc.
2096 void _solveRealLPAndRecordStatistics(volatile bool* interrupt = NULL);
2097
2098 /// reads real LP in LP or MPS format from file and returns true on success; gets row names, column names, and
2099 /// integer variables if desired
2100 bool _readFileReal(const char* filename, NameSet* rowNames = 0, NameSet* colNames = 0,
2101 DIdxSet* intVars = 0);
2102
2103 /// reads rational LP in LP or MPS format from file and returns true on success; gets row names, column names, and
2104 /// integer variables if desired
2105 bool _readFileRational(const char* filename, NameSet* rowNames = 0, NameSet* colNames = 0,
2106 DIdxSet* intVars = 0);
2107
2108 /// completes range type arrays after adding columns and/or rows
2110
2111 /// recomputes range types from scratch using real LP
2113
2114 /// recomputes range types from scratch using rational LP
2116
2117 /// synchronizes real LP with rational LP, i.e., copies (rounded) rational LP into real LP, without looking at the sync mode
2118 void _syncLPReal(bool time = true);
2119
2120 /// synchronizes rational LP with real LP, i.e., copies real LP to rational LP, without looking at the sync mode
2121 void _syncLPRational(bool time = true);
2122
2123 /// synchronizes rational solution with real solution, i.e., copies (rounded) rational solution to real solution
2125
2126 /// synchronizes real solution with rational solution, i.e., copies real solution to rational solution
2128
2129 /// returns pointer to a constant unit vector available until destruction of the SoPlexBase class
2131
2132 /// parses one line in a settings file and returns true on success; note that the string is modified
2133 bool _parseSettingsLine(char* line, const int lineNumber);
2134
2135 ///@}
2136
2137
2138 //**@name Private solving methods implemented in solverational.hpp */
2139 ///@{
2140
2141 /// 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
2142 template <typename T>
2144 SolRational& sol,
2145 VectorBase<T>& primalReal,
2146 VectorBase<T>& dualReal,
2147 int& dualSize);
2148
2149 /// computes violation of bounds during the refinement loop
2150 void _computeBoundsViolation(SolRational& sol, Rational& boundsViolation);
2151
2152 /// computes violation of sides during the refinement loop
2153 void _computeSidesViolation(SolRational& sol, Rational& sideViolation);
2154
2155 /// computes violation of reduced costs during the refinement loop
2157 SolRational& sol,
2158 Rational& redCostViolation,
2159 const bool& maximizing);
2160
2161 /// computes dual violation during the refinement loop
2163 SolRational& sol,
2164 Rational& dualViolation,
2165 const bool& maximizing);
2166
2167 /// checks termination criteria for refinement loop
2169 bool& primalFeasible,
2170 bool& dualFeasible,
2171 Rational& boundsViolation,
2172 Rational& sideViolation,
2173 Rational& redCostViolation,
2174 Rational& dualViolation,
2175 int minIRRoundsRemaining,
2176 bool& stoppedTime,
2177 bool& stoppedIter,
2178 int numFailedRefinements);
2179
2180 /// checks refinement loop progress
2182 Rational& boundsViolation,
2183 Rational& sideViolation,
2184 Rational& redCostViolation,
2185 Rational& dualViolation,
2186 Rational& maxViolation,
2187 Rational& bestViolation,
2188 const Rational& violationImprovementFactor,
2189 int& numFailedRefinements);
2190
2191 /// performs rational reconstruction and/or factorizationd
2193 int& minIRRoundsRemaining,
2194 int& lastStallIterations,
2195 int& numberOfIterations,
2196 bool& factorSolNewBasis,
2197 int& nextRatrec,
2198 const Rational& errorCorrectionFactor,
2199 Rational& errorCorrection,
2200 Rational& maxViolation,
2201 SolRational& sol,
2202 bool& primalFeasible,
2203 bool& dualFeasible,
2204 bool& stoppedTime,
2205 bool& stoppedIter,
2206 bool& error,
2207 bool& breakAfter,
2208 bool& continueAfter);
2209
2210 /// forces value of given nonbasic variable to bound
2212 SolRational& sol,
2213 int& c,
2214 const int& maxDimRational,
2215 bool toLower);
2216
2217 /// computes primal scaling factor; limit increase in scaling by tolerance used in floating point solve
2219 Rational& maxScale,
2220 Rational& primalScale,
2221 Rational& boundsViolation,
2222 Rational& sideViolation,
2223 Rational& redCostViolation);
2224
2225 /// computes dual scaling factor; limit increase in scaling by tolerance used in floating point solve
2227 Rational& maxScale,
2228 Rational& primalScale,
2229 Rational& dualScale,
2230 Rational& redCostViolation,
2231 Rational& dualViolation);
2232
2233 /// applies scaled bounds
2234 template <typename T>
2235 void _applyScaledBounds(SPxSolverBase<T>& solver, Rational& primalScale);
2236
2237 /// applies scaled sides
2238 template <typename T>
2239 void _applyScaledSides(SPxSolverBase<T>& solver, Rational& primalScale);
2240
2241 /// applies scaled objective function
2242 template <typename T>
2243 void _applyScaledObj(SPxSolverBase<T>& solver, Rational& dualScale, SolRational& sol);
2244
2245 /// evaluates result of solve. Return true if the algorithm must to stopped, false otherwise.
2246 template <typename T>
2248 SPxSolverBase<T>& solver,
2249 typename SPxSolverBase<T>::Status result,
2250 bool usingRefinedLP,
2251 SolRational& sol,
2252 VectorBase<T>& dualReal,
2253 bool& infeasible,
2254 bool& unbounded,
2255 bool& stoppedTime,
2256 bool& stoppedIter,
2257 bool& error);
2258
2259 /// corrects primal solution and aligns with basis
2260 template <typename T>
2262 SolRational& sol,
2263 Rational& primalScale,
2264 int& primalSize,
2265 const int& maxDimRational,
2266 VectorBase<T>& primalReal);
2267
2268 /// updates or recomputes slacks depending on which looks faster
2269 void _updateSlacks(SolRational& sol, int& primalSize);
2270
2271 /// corrects dual solution and aligns with basis
2272 template <typename T>
2274 SPxSolverBase<T>& solver,
2275 SolRational& sol,
2276 const bool& maximizing,
2277 VectorBase<T>& dualReal,
2278 Rational& dualScale,
2279 int& dualSize,
2280 const int& maxDimRational);
2281
2282 /// updates or recomputes reduced cost values depending on which looks faster; adding one to the length of the
2283 /// dual vector accounts for the objective function vector
2284 void _updateReducedCosts(SolRational& sol, int& dualSize, const int& numCorrectedPrimals);
2285
2286 ///@todo precision-boosting move some place else
2287 /// converts the given DataArray of VarStatus to boostedPrecision
2289 DataArray< typename SPxSolverBase<R>::VarStatus >& base,
2290 DataArray< typename SPxSolverBase<BP>::VarStatus >& copy);
2291
2292 ///@todo precision-boosting move some place else
2293 /// converts the given DataArray of VarStatus to R precision
2295 DataArray< typename SPxSolverBase<BP>::VarStatus >& base,
2296 DataArray< typename SPxSolverBase<R>::VarStatus >& copy);
2297
2298 /// disable initial precision solver and switch to boosted solver
2300
2301 /// setup boosted solver before launching iteration
2303
2304 /// increase the multiprecision, return false if maximum precision is reached, true otherwise
2306
2307 /// reset the boosted precision to the default value
2309
2310 /// setup recovery mecanism using multiprecision, return false if maximum precision reached, true otherwise
2312
2313 /// return true if slack basis has to be loaded for boosted solver
2314 bool _isBoostedStartingFromSlack(bool initialSolve = true);
2315
2316 /// indicate if we are testing feasibility, unboundedness or neither
2320
2321 /// check if we are testing feasibility, unboundedness or neither
2325
2326 // stores given basis in old basis attributes: _oldBasisStatusRows, _oldFeasBasisStatusRows, _oldUnbdBasisStatusRows (and ...Cols)
2328 DataArray< typename SPxSolverBase<R>::VarStatus >& cols);
2329
2330 // stores given basis in old basis attributes: _oldBasisStatusRows, _oldFeasBasisStatusRows, _oldUnbdBasisStatusRows (and ...Cols)
2332 DataArray< typename SPxSolverBase<BP>::VarStatus >& cols);
2333
2334 // get the last advanced and stable basis stored by the initial solver and store it as old basis, unsimplify basis if simplifier activated
2335 void _storeLastStableBasis(bool vanished);
2336
2337 // get the last advanced and stable basis stored by the boosted solver and store it as old basis, unsimplify basis if simplifier activated
2338 void _storeLastStableBasisBoosted(bool vanished);
2339
2340 // load old basis in solver. The old basis loaded depends on the certificate mode (feasibility, unboundedness, or neither)
2341 bool _loadBasisFromOldBasis(bool boosted);
2342
2343 // update statistics for precision boosting
2345
2346 /// solves current problem using multiprecision floating-point solver
2347 /// return false if a new boosted iteration is necessary, true otherwise
2349 SolRational& sol,
2350 bool& primalFeasible,
2351 bool& dualFeasible,
2352 bool& infeasible,
2353 bool& unbounded,
2354 bool& stoppedTime,
2355 bool& stoppedIter,
2356 bool& error,
2357 bool& needNewBoostedIt);
2358
2359 /// solves current problem with iterative refinement and recovery mechanism using boosted solver
2361 SolRational& sol,
2362 bool acceptUnbounded,
2363 bool acceptInfeasible,
2364 int minIRRoundsRemaining,
2365 bool& primalFeasible,
2366 bool& dualFeasible,
2367 bool& infeasible,
2368 bool& unbounded,
2369 bool& stoppedTime,
2370 bool& stoppedIter,
2371 bool& error,
2372 bool& needNewBoostedIt);
2373
2374 /// perform iterative refinement using the right precision
2376 SolRational& sol,
2377 bool acceptUnbounded,
2378 bool acceptInfeasible,
2379 int minIRRoundsRemaining,
2380 bool& primalFeasible,
2381 bool& dualFeasible,
2382 bool& infeasible,
2383 bool& unbounded,
2384 bool& stoppedTime,
2385 bool& stoppedIter,
2386 bool& error
2387 );
2388
2389 /// solves current problem using double floating-point solver
2391 SolRational& sol,
2392 bool& primalFeasible,
2393 bool& dualFeasible,
2394 bool& infeasible,
2395 bool& unbounded,
2396 bool& stoppedTime,
2397 bool& stoppedIter,
2398 bool& error);
2399
2400 /// solves current problem with iterative refinement and recovery mechanism
2402 bool acceptUnbounded,
2403 bool acceptInfeasible,
2404 int minIRRoundsRemaining,
2405 bool& primalFeasible,
2406 bool& dualFeasible,
2407 bool& infeasible,
2408 bool& unbounded,
2409 bool& stoppedTime,
2410 bool& stoppedIter,
2411 bool& error);
2412
2413 /// performs iterative refinement on the auxiliary problem for testing unboundedness
2414 void _performUnboundedIRStable(SolRational& sol, bool& hasUnboundedRay, bool& stoppedTime,
2415 bool& stoppedIter, bool& error);
2416
2417 /// performs iterative refinement on the auxiliary problem for testing feasibility
2418 void _performFeasIRStable(SolRational& sol, bool& withDualFarkas, bool& stoppedTime,
2419 bool& stoppedIter, bool& error);
2420
2421 /// reduces matrix coefficient in absolute value by the lifting procedure of Thiele et al. 2013
2422 void _lift();
2423
2424 /// undoes lifting
2426
2427 /// store basis
2429
2430 /// restore basis
2432
2433 /// stores objective, bounds, and sides of real LP
2435
2436 /// restores objective, bounds, and sides of real LP
2438
2439 /// introduces slack variables to transform inequality constraints into equations for both rational and real LP,
2440 /// which should be in sync
2442
2443 /// undoes transformation to equality form
2445
2446 /// transforms LP to unboundedness problem by moving the objective function to the constraints, changing right-hand
2447 /// side and bounds to zero, and adding an auxiliary variable for the decrease in the objective function
2449
2450 /// undoes transformation to unboundedness problem
2451 void _untransformUnbounded(SolRational& sol, bool unbounded);
2452
2453 /// transforms LP to feasibility problem by removing the objective function, shifting variables, and homogenizing the
2454 /// right-hand side
2456
2457 /// undoes transformation to feasibility problem
2458 void _untransformFeasibility(SolRational& sol, bool infeasible);
2459
2460 /** computes radius of infeasibility box implied by an approximate Farkas' proof
2461
2462 Given constraints of the form \f$ lhs <= Ax <= rhs \f$, a farkas proof y should satisfy \f$ y^T A = 0 \f$ and
2463 \f$ y_+^T lhs - y_-^T rhs > 0 \f$, where \f$ y_+, y_- \f$ denote the positive and negative parts of \f$ y \f$.
2464 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
2465 as the following holds for all potentially feasible \f$ x \f$:
2466
2467 \f[
2468 y^T Ax < (y_+^T lhs - y_-^T rhs) (*)
2469 \f]
2470
2471 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
2472 bounds on \f$ x \f$ imply that all feasible \f$ x \f$ satisfy (*), and if not then compute bounds on \f$ x \f$ to
2473 guarantee (*). The simplest way to do this is to compute
2474
2475 \f[
2476 B = (y_+^T lhs - y_-^T rhs) / \sum_i(|(y^T A)_i|)
2477 \f]
2478
2479 noting that if every component of \f$ x \f$ has \f$ |x_i| < B \f$, then (*) holds.
2480
2481 \f$ B \f$ can be increased by iteratively including variable bounds smaller than \f$ B \f$. The speed of this
2482 method can be further improved by using interval arithmetic for all computations. For related information see
2483 Sec. 4 of Neumaier and Shcherbina, Mathematical Programming A, 2004.
2484
2485 Set transformed to true if this method is called after _transformFeasibility().
2486 */
2487 void _computeInfeasBox(SolRational& sol, bool transformed);
2488
2489 /// solves real LP during iterative refinement
2491 VectorBase<R>& dual,
2492 DataArray< typename SPxSolverBase<R>::VarStatus >& basisStatusRows,
2493 DataArray< typename SPxSolverBase<R>::VarStatus >& basisStatusCols);
2494
2495 /// solves real LP with recovery mechanism
2496 typename SPxSolverBase<R>::Status _solveRealStable(bool acceptUnbounded, bool acceptInfeasible,
2497 VectorBase<R>& primal, VectorBase<R>& dual,
2498 DataArray< typename SPxSolverBase<R>::VarStatus >& basisStatusRows,
2499 DataArray< typename SPxSolverBase<R>::VarStatus >& basisStatusCols,
2500 const bool forceNoSimplifier = false);
2501
2502 /// solves real LP during iterative refinement
2504 VectorBase<BP>& primal, VectorBase<BP>& dual,
2505 DataArray< typename SPxSolverBase<R>::VarStatus >& basisStatusRows,
2506 DataArray< typename SPxSolverBase<R>::VarStatus >& basisStatusCols,
2507 typename SPxSolverBase<BP>::Status& boostedResult, bool initialSolve);
2508
2509 /// computes rational inverse of basis matrix as defined by _rationalLUSolverBind
2511
2512 /// factorizes rational basis matrix in column representation
2514 DataArray< typename SPxSolverBase<R>::VarStatus >& basisStatusRows,
2515 DataArray< typename SPxSolverBase<R>::VarStatus >& basisStatusCols, bool& stoppedTime,
2516 bool& stoppedIter, bool& error, bool& optimal);
2517
2518 /// attempts rational reconstruction of primal-dual solution
2520 DataArray< typename SPxSolverBase<R>::VarStatus >& basisStatusRows,
2521 DataArray< typename SPxSolverBase<R>::VarStatus >& basisStatusCols,
2522 const Rational& denomBoundSquared);
2523 ///@}
2524
2525 ///@name Private solving methods implemented in solvereal.cpp
2526 ///@{
2527
2528 /// solves the templated LP
2529 void _optimize(volatile bool* interrupt = NULL);
2530
2531 /// temporary fix for Rational
2532 void _optimizeRational(volatile bool* interrupt = NULL);
2533
2534 /// checks result of the solving process and solves again without preprocessing if necessary
2535 void _evaluateSolutionReal(typename SPxSimplifier<R>::Result simplificationStatus);
2536
2537 /// solves real LP with/without preprocessing
2538 void _preprocessAndSolveReal(bool applyPreprocessing, volatile bool* interrupt = NULL);
2539
2540 /// loads original problem into solver and solves again after it has been solved to optimality with preprocessing
2541 void _resolveWithoutPreprocessing(typename SPxSimplifier<R>::Result simplificationStatus);
2542
2543 /// verify computed solution and resolve if necessary
2545
2546 /// verify computed obj stop and resolve if necessary
2548
2549 /// stores solution of the real LP; before calling this, the real LP must be loaded in the solver and solved (again)
2550 void _storeSolutionReal(bool verify = true);
2551
2552 /// stores solution from the simplifier because problem vanished in presolving step
2554
2555 /// unscales stored solution to remove internal or external scaling of LP
2556 void _unscaleSolutionReal(SPxLPBase<R>& LP, bool persistent = true);
2557
2558 /// load original LP and possibly setup a slack basis
2559 void _loadRealLP(bool initBasis);
2560
2561 /// check scaling of LP
2562 void _checkScaling(SPxLPBase<R>* origLP) const;
2563
2564 /// check correctness of (un)scaled basis matrix operations
2566
2567 /// check whether persistent scaling is supposed to be reapplied again after unscaling
2569
2570 /// checks the dual feasibility of the current basis
2572 ///@}
2573};
2574
2575/* Backwards compatibility */
2577// A header file containing all the general templated functions
2578
2579} // namespace soplex
2580
2581// General templated function
2582#include "soplex.hpp"
2583#include "soplex/solverational.hpp"
2584#include "soplex/testsoplex.hpp"
2585#include "soplex/solvereal.hpp"
2586
2587#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:1474
int _intParamValues[SoPlexBase< R >::INTPARAM_COUNT]
array of current integer parameter values
Definition soplex.h:1542
static struct soplex::SoPlexBase::Settings::BoolParam boolParam
bool _boolParamValues[SoPlexBase< R >::BOOLPARAM_COUNT]
array of current boolean parameter values
Definition soplex.h:1539
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:1545
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:1802
@ STARTER_VECTOR
generic solution-based crash basis
Definition soplex.h:1246
@ STARTER_WEIGHT
greedy crash basis weighted by objective, bounds, and sides
Definition soplex.h:1240
@ STARTER_SUM
crash basis from a greedy solution
Definition soplex.h:1243
@ STARTER_OFF
slack basis
Definition soplex.h:1237
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:1327
@ CHECKMODE_RATIONAL
rational check
Definition soplex.h:1333
@ CHECKMODE_AUTO
decide according to READMODE
Definition soplex.h:1330
VectorRational _modObj
Definition soplex.h:1846
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:1134
@ OBJSENSE_MINIMIZE
minimization
Definition soplex.h:1131
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:1843
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:1817
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:1708
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:1834
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:1915
SPxDantzigPR< BP > _boostedPricerDantzig
Definition soplex.h:1783
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:1703
RealParam
real parameters
Definition soplex.h:1377
@ OPTTOL
dual feasibility tolerance
Definition soplex.h:1382
@ FPOPTTOL
working tolerance for optimality in floating-point solver during iterative refinement
Definition soplex.h:1412
@ PRECISION_BOOSTING_FACTOR
factor by which the precision of the floating-point solver is multiplied
Definition soplex.h:1457
@ SPARSITY_THRESHOLD
sparse pricing threshold (#violations < dimension * SPARSITY_THRESHOLD activates sparse pricing)
Definition soplex.h:1424
@ LIFTMAXVAL
upper threshold in lifting (nonzero matrix coefficients with larger absolute value will be reformulat...
Definition soplex.h:1421
@ EPSILON_ZERO
general zero tolerance
Definition soplex.h:1385
@ EPSILON_FACTORIZATION
zero tolerance used in factorization
Definition soplex.h:1388
@ OBJLIMIT_UPPER
upper limit on objective value
Definition soplex.h:1406
@ FPFEASTOL
working tolerance for feasibility in floating-point solver during iterative refinement
Definition soplex.h:1409
@ RATREC_FREQ
geometric frequency at which to apply rational reconstruction
Definition soplex.h:1430
@ MAXSCALEINCR
maximum increase of scaling factors between refinements
Definition soplex.h:1415
@ TIMELIMIT
time limit in seconds (INFTY if unlimited)
Definition soplex.h:1400
@ LIFTMINVAL
lower threshold in lifting (nonzero matrix coefficients with smaller absolute value will be reformula...
Definition soplex.h:1418
@ REPRESENTATION_SWITCH
threshold on number of rows vs. number of columns for switching from column to row representations in...
Definition soplex.h:1427
@ REFAC_UPDATE_FILL
refactor threshold for fill-in in current factor update compared to fill-in in last factorization
Definition soplex.h:1439
@ REALPARAM_COUNT
number of real parameters
Definition soplex.h:1460
@ MINRED
minimal reduction (sum of removed rows/cols) to continue simplification
Definition soplex.h:1433
@ OBJ_OFFSET
objective offset
Definition soplex.h:1448
@ OBJLIMIT_LOWER
lower limit on objective value
Definition soplex.h:1403
@ FEASTOL
primal feasibility tolerance
Definition soplex.h:1379
@ EPSILON_PIVOT
pivot zero tolerance used in factorization
Definition soplex.h:1394
@ MIN_MARKOWITZ
minimal Markowitz threshold to control sparsity/stability in LU factorization
Definition soplex.h:1451
@ REFAC_MEM_FACTOR
refactor threshold for memory growth in factorization since last refactorization
Definition soplex.h:1442
@ SIMPLIFIER_MODIFYROWFAC
minimal modification threshold to apply presolve reductions
Definition soplex.h:1454
@ EPSILON_UPDATE
zero tolerance used in update of the factorization
Definition soplex.h:1391
@ REFAC_BASIS_NNZ
refactor threshold for nonzeros in last factorized basis matrix compared to updated basis matrix
Definition soplex.h:1436
@ LEASTSQ_ACRCY
accuracy of conjugate gradient method in least squares scaling (higher value leads to more iterations...
Definition soplex.h:1445
@ INFTY
infinity threshold
Definition soplex.h:1397
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:1886
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:1346
@ TIMER_CPU
cpu or user time
Definition soplex.h:1343
@ TIMER_OFF
disable timing
Definition soplex.h:1340
VectorRational _feasObj
Definition soplex.h:1837
void _solveBoostedRealLPAndRecordStatistics(volatile bool *interrupt=NULL)
call floating-point solver and update statistics on iterations etc.
bool _switchedToBoosted
Definition soplex.h:1750
void changeRhsRational(const VectorRational &rhs)
changes right-hand side vector to rhs
IntParam
integer parameters
Definition soplex.h:1037
@ HYPER_PRICING
mode for hyper sparse pricing
Definition soplex.h:1099
@ DISPLAYFREQ
display frequency
Definition soplex.h:1063
@ TIMER
type of timer
Definition soplex.h:1096
@ CHECKMODE
mode for a posteriori feasibility checks
Definition soplex.h:1093
@ STATTIMER
type of timer for statistics
Definition soplex.h:1114
@ FACTOR_UPDATE_TYPE
type of LU update
Definition soplex.h:1048
@ READMODE
mode for reading LP files
Definition soplex.h:1087
@ STALLREFLIMIT
stalling refinement limit (-1 if unlimited)
Definition soplex.h:1060
@ STARTER
type of starter used to create crash basis
Definition soplex.h:1075
@ REFLIMIT
refinement limit (-1 if unlimited)
Definition soplex.h:1057
@ SYNCMODE
mode for synchronizing real and rational LP
Definition soplex.h:1084
@ PRICER
type of pricer
Definition soplex.h:1078
@ LEASTSQ_MAXROUNDS
maximum number of conjugate gradient iterations in least square scaling
Definition soplex.h:1105
@ ALGORITHM
type of algorithm, i.e., primal or dual
Definition soplex.h:1045
@ INTPARAM_COUNT
number of integer parameters
Definition soplex.h:1124
@ OBJSENSE
objective sense
Definition soplex.h:1039
@ SIMPLIFIER
type of simplifier
Definition soplex.h:1069
@ PRINTBASISMETRIC
print condition number during the solve
Definition soplex.h:1111
@ REPRESENTATION
type of computational form, i.e., column or row representation
Definition soplex.h:1042
@ SOLVEMODE
mode for iterative refinement strategy
Definition soplex.h:1090
@ RATFAC_MINSTALLS
minimum number of stalling refinements since last pivot to trigger rational factorization
Definition soplex.h:1102
@ SOLUTION_POLISHING
mode for solution polishing
Definition soplex.h:1108
@ FACTOR_UPDATE_MAX
maximum number of updates without fresh factorization
Definition soplex.h:1051
@ SCALER
type of scaler
Definition soplex.h:1072
@ ITERLIMIT
iteration limit (-1 if unlimited)
Definition soplex.h:1054
@ RATIOTESTER
type of ratio test
Definition soplex.h:1081
@ VERBOSITY
verbosity level
Definition soplex.h:1066
DSVectorRational _tauColVector
Definition soplex.h:1836
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:1919
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:1848
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:1920
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:1832
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:1761
SPxGeometSC< R > _scalerGeo1
Definition soplex.h:1704
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:1819
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:1790
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:1722
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:1297
@ SYNCMODE_ONLYREAL
store only real LP
Definition soplex.h:1291
@ SYNCMODE_AUTO
automatic sync of real and rational LP
Definition soplex.h:1294
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:1713
const char * getPricerName()
name of currently loaded pricer
void addColsRational(const LPColSetRational &lpcolset)
adds multiple columns
VectorRational _feasLhs
Definition soplex.h:1838
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:1839
VectorRational _feasLower
Definition soplex.h:1840
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:1782
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:1687
Rational _rationalZero
Definition soplex.h:1936
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:1874
bool isDualFeasible() const
is stored dual solution feasible?
DataArray< typename SPxSolverBase< R >::VarStatus > _basisStatusCols
Definition soplex.h:1887
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:1712
Presol< R > _simplifierPaPILO
Definition soplex.h:1701
SPxGeometSC< BP > _boostedScalerGeo8
Definition soplex.h:1800
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:1934
SPxParMultPR< BP > _boostedPricerParMult
Definition soplex.h:1784
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:1715
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:1847
DataArray< typename SPxSolverBase< R >::VarStatus > _storedBasisStatusCols
Definition soplex.h:1849
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:1709
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:1699
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:1714
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:1818
SLUFactorRational _rationalLUSolver
Definition soplex.h:1828
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:1199
@ SIMPLIFIER_PAPILO
using the presolve lib papilo
Definition soplex.h:1202
@ SIMPLIFIER_AUTO
SoPlex chooses automatically (currently always "internal")
Definition soplex.h:1205
@ SIMPLIFIER_OFF
disabling presolving
Definition soplex.h:1196
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:1776
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:1798
void changeRhsRational(int i, const Rational &rhs)
changes right-hand side of row i to rhs
SPxVectorST< R > _starterVector
Definition soplex.h:1710
void _convertDataArrayVarStatusToBoosted(DataArray< typename SPxSolverBase< R >::VarStatus > &base, DataArray< typename SPxSolverBase< BP >::VarStatus > &copy)
SPxBoundFlippingRT< BP > _boostedRatiotesterBoundFlipping
Definition soplex.h:1792
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:1684
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:1835
@ SCALER_GEOEQUI
geometric mean scaling (max 8 rounds) followed by equilibrium scaling (rows and columns)
Definition soplex.h:1230
@ SCALER_UNIEQUI
equilibrium scaling on rows or columns
Definition soplex.h:1215
@ SCALER_BIEQUI
equilibrium scaling on rows and columns
Definition soplex.h:1218
@ SCALER_LEASTSQ
least square scaling
Definition soplex.h:1227
@ SCALER_GEO1
geometric mean scaling on rows and columns, max 1 round
Definition soplex.h:1221
@ SCALER_OFF
no scaler
Definition soplex.h:1212
@ SCALER_GEO8
geometric mean scaling on rows and columns, max 8 rounds
Definition soplex.h:1224
SolBase< R > _solReal
Definition soplex.h:1918
SLUFactor< BP > _boostedSlufactor
Definition soplex.h:1780
DataArray< typename SPxSolverBase< R >::VarStatus > _oldFeasBasisStatusRows
Definition soplex.h:1899
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:1682
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:1805
unsigned int randomSeed() const
returns the current random seed of the solver instance
SPxAutoPR< R > _pricerAuto
Definition soplex.h:1711
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:1772
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:1716
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:1689
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:1875
SPxDefaultRT< R > _ratiotesterTextbook
Definition soplex.h:1717
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:1804
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:1842
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:1720
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:1787
VectorRational _unboundedUpper
Definition soplex.h:1833
SPxSolverBase< R >::Status _status
Definition soplex.h:1883
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:1154
@ ALGORITHM_DUAL
dual simplex algorithm, i.e., leaving for column and entering for row representation
Definition soplex.h:1157
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:1794
DataArray< int > _rationalLUSolverBind
Definition soplex.h:1829
Real _epsZeroPrecisionRatio
Definition soplex.h:1773
SPxGeometSC< R > _scalerGeo8
Definition soplex.h:1705
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:1895
VectorRational _modRhs
Definition soplex.h:1845
VectorBase< R > _manualLhs
Definition soplex.h:1816
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:1935
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:1744
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:1814
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:1795
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:1372
@ POLISHING_OFF
no solution polishing
Definition soplex.h:1366
@ POLISHING_INTEGRALITY
maximize number of basic slack variables, i.e. more variables on bounds
Definition soplex.h:1369
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:1850
void _switchToStandardMode()
indicate if we are testing feasibility, unboundedness or neither
@ RATIOTESTER_TEXTBOOK
textbook ratio test without stabilization
Definition soplex.h:1275
@ RATIOTESTER_FAST
modified Harris ratio test
Definition soplex.h:1281
@ RATIOTESTER_HARRIS
standard Harris ratio test
Definition soplex.h:1278
@ RATIOTESTER_BOUNDFLIPPING
bound flipping ratio test for long steps in the dual simplex
Definition soplex.h:1284
VectorBase< R > _manualUpper
Definition soplex.h:1815
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:1707
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:1799
void printVersion() const
prints version and compilation options
Statistics * _statistics
statistics since last call to solveReal() or solveRational()
Definition soplex.h:1674
SPxSolverBase< R > _solver
Definition soplex.h:1698
bool _boostPrecision()
increase the multiprecision, return false if maximum precision is reached, true otherwise
SPxDevexPR< BP > _boostedPricerDevex
Definition soplex.h:1785
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:1353
@ HYPER_PRICING_ON
always
Definition soplex.h:1359
@ HYPER_PRICING_AUTO
decide according to problem size
Definition soplex.h:1356
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:1827
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:1841
void getColsRational(int start, int end, LPColSetRational &lpcolset) const
gets columns start, ..., end
@ READMODE_REAL
standard floating-point parsing
Definition soplex.h:1304
@ READMODE_RATIONAL
rational parsing
Definition soplex.h:1307
@ FACTOR_UPDATE_TYPE_ETA
product form update
Definition soplex.h:1164
@ FACTOR_UPDATE_TYPE_FT
Forrest-Tomlin type update.
Definition soplex.h:1167
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:1262
@ PRICER_STEEP
steepest edge pricer with exact initialization of norms
Definition soplex.h:1268
@ PRICER_QUICKSTEEP
steepest edge pricer with initialization to unit norms
Definition soplex.h:1265
@ PRICER_PARMULT
partial multiple pricer based on Dantzig pricing
Definition soplex.h:1259
@ PRICER_AUTO
automatic pricer
Definition soplex.h:1253
@ PRICER_DANTZIG
Dantzig pricer.
Definition soplex.h:1256
void _addColsReal(const LPColSetReal &lpcolset)
adds multiple columns to the real LP and adjusts basis
Real _epsUpdatePrecisionRatio
Definition soplex.h:1775
Real _epsFactorPrecisionRatio
Definition soplex.h:1774
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:1723
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:1904
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:1320
@ SOLVEMODE_REAL
apply standard floating-point algorithm
Definition soplex.h:1314
@ SOLVEMODE_AUTO
decide depending on tolerances whether to apply iterative refinement
Definition soplex.h:1317
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:1719
SPxDefaultRT< BP > _boostedRatiotesterTextbook
Definition soplex.h:1789
void _optimizeRational(volatile bool *interrupt=NULL)
temporary fix for Rational
SPxFastRT< BP > _boostedRatiotesterFast
Definition soplex.h:1791
void _resetBoostedPrecision()
reset the boosted precision to the default value
Rational _rationalFeastol
Definition soplex.h:1688
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:1725
void _restoreBasis()
restore basis
SPxSteepPR< BP > _boostedPricerQuickSteep
Definition soplex.h:1786
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:1724
void _untransformUnbounded(SolRational &sol, bool unbounded)
undoes transformation to unboundedness problem
bool _boostingLimitReached
Definition soplex.h:1749
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:1900
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:1700
bool getDualViolationRational(Rational &maxviol, Rational &sumviol)
@ VERBOSITY_HIGH
high verbosity level
Definition soplex.h:1186
@ VERBOSITY_WARNING
only error and warning output
Definition soplex.h:1177
@ VERBOSITY_DEBUG
only error, warning, and debug output
Definition soplex.h:1180
@ VERBOSITY_NORMAL
standard verbosity level
Definition soplex.h:1183
@ VERBOSITY_ERROR
only error output
Definition soplex.h:1174
@ VERBOSITY_FULL
full verbosity level
Definition soplex.h:1189
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:1903
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:1141
@ REPRESENTATION_COLUMN
column representation Ax - s = 0, lower <= x <= upper, lhs <= s <= rhs
Definition soplex.h:1144
@ REPRESENTATION_ROW
row representation (lower,lhs) <= (x,Ax) <= (upper,rhs)
Definition soplex.h:1147
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:1706
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:1844
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:1690
DataArray< typename SPxSolverBase< R >::VarStatus > _oldBasisStatusCols
Definition soplex.h:1896
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:1801
bool getPrimalRay(VectorBase< R > &vector)
gets the primal ray if available; returns true on success
SPxHarrisRT< R > _ratiotesterHarris
Definition soplex.h:1718
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:1797
LPColSetRational _slackCols
Definition soplex.h:1831
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
@ 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:1032
@ 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:1857
@ RANGETYPE_UPPER
upper bound is finite, lower bound is infinite
Definition soplex.h:1865
@ RANGETYPE_FIXED
lower bound equals upper bound
Definition soplex.h:1871
@ RANGETYPE_BOXED
lower and upper bound finite, but different
Definition soplex.h:1868
@ RANGETYPE_LOWER
lower bound is finite, upper bound is infinite
Definition soplex.h:1862
@ RANGETYPE_FREE
both bounds are infinite
Definition soplex.h:1859
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:1686
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:1702
void getRhsReal(VectorBase< R > &rhs) const
gets right-hand side vector
DataArray< typename SPxSolverBase< BP >::VarStatus > _tmpBasisStatusCols
Definition soplex.h:1916
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:1481
std::string description[SoPlexBase< R >::BOOLPARAM_COUNT]
array of descriptions for boolean parameters
Definition soplex.h:1483
bool defaultValue[SoPlexBase< R >::BOOLPARAM_COUNT]
array of default values for boolean parameters
Definition soplex.h:1485
std::string name[SoPlexBase< R >::INTPARAM_COUNT]
array of names for integer parameters
Definition soplex.h:1493
int lower[SoPlexBase< R >::INTPARAM_COUNT]
array of lower bounds for int parameter values
Definition soplex.h:1499
int upper[SoPlexBase< R >::INTPARAM_COUNT]
array of upper bounds for int parameter values
Definition soplex.h:1501
int defaultValue[SoPlexBase< R >::INTPARAM_COUNT]
array of default values for integer parameters
Definition soplex.h:1497
std::string description[SoPlexBase< R >::INTPARAM_COUNT]
array of descriptions for integer parameters
Definition soplex.h:1495
Real upper[SoPlexBase< R >::REALPARAM_COUNT]
array of upper bounds for real parameter values
Definition soplex.h:1517
Real defaultValue[SoPlexBase< R >::REALPARAM_COUNT]
array of default values for real parameters
Definition soplex.h:1513
Real lower[SoPlexBase< R >::REALPARAM_COUNT]
array of lower bounds for real parameter values
Definition soplex.h:1515
std::string description[SoPlexBase< R >::REALPARAM_COUNT]
array of descriptions for real parameters
Definition soplex.h:1511
std::string name[SoPlexBase< R >::REALPARAM_COUNT]
array of names for real parameters
Definition soplex.h:1509