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 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 /// time spent in last call to solve
861
862 /// statistical information in form of a string
863 std::string statisticString() const;
864
865 /// name of starter
866 const char* getStarterName();
867
868 /// name of simplifier
869 const char* getSimplifierName();
870
871 /// name of scaling method
872 const char* getScalerName();
873
874 /// name of currently loaded pricer
875 const char* getPricerName();
876
877 /// name of currently loaded ratiotester
878 const char* getRatiotesterName();
879
880 ///@}
881
882
883 ///@name File I/O
884 ///@{
885
886 /// reads LP file in LP or MPS format according to READMODE parameter; gets row names, column names, and
887 /// integer variables if desired; returns true on success
888 bool readFile(const char* filename, NameSet* rowNames = 0, NameSet* colNames = 0,
889 DIdxSet* intVars = 0);
890
891 /// Templated write function
892 /// Real
893 /// writes real LP to file; LP or MPS format is chosen from the extension in \p filename; if \p rowNames and \p
894 /// colNames are \c NULL, default names are used; if \p intVars is not \c NULL, the variables contained in it are
895 /// marked as integer; returns true on success
896 /// Rational
897 /// writes rational LP to file; LP or MPS format is chosen from the extension in \p filename; if \p rowNames and \p
898 /// colNames are \c NULL, default names are used; if \p intVars is not \c NULL, the variables contained in it are
899 /// marked as integer; returns true on success
900 bool writeFile(const char* filename, const NameSet* rowNames = 0, const NameSet* colNames = 0,
901 const DIdxSet* intvars = 0, const bool unscale = true) const;
902
903 bool writeFileRational(const char* filename, const NameSet* rowNames = 0,
904 const NameSet* colNames = 0, const DIdxSet* intvars = 0) const;
905
906 /* For SCIP compatibility */
907 bool writeFileReal(const char* filename, const NameSet* rowNames = 0, const NameSet* colNames = 0,
908 const DIdxSet* intvars = 0, const bool unscale = true) const;
909
910 /// writes the dual of the real LP to file; LP or MPS format is chosen from the extension in \p filename;
911 /// if \p rowNames and \p colNames are \c NULL, default names are used; if \p intVars is not \c NULL,
912 /// the variables contained in it are marked as integer; returns true on success
913 bool writeDualFileReal(const char* filename, const NameSet* rowNames = 0,
914 const NameSet* colNames = 0, const DIdxSet* intvars = 0) const;
915
916 /// reads basis information from \p filename and returns true on success; if \p rowNames and \p colNames are \c NULL,
917 /// default names are assumed; returns true on success
918 bool readBasisFile(const char* filename, const NameSet* rowNames = 0, const NameSet* colNames = 0);
919
920 /// writes basis information to \p filename; if \p rowNames and \p colNames are \c NULL, default names are used;
921 /// returns true on success
922 bool writeBasisFile(const char* filename, const NameSet* rowNames = 0, const NameSet* colNames = 0,
923 const bool cpxFormat = false) const;
924
925 /// writes internal LP, basis information, and parameter settings; if \p rowNames and \p colNames are \c NULL,
926 /// default names are used
927 void writeStateReal(const char* filename, const NameSet* rowNames = 0, const NameSet* colNames = 0,
928 const bool cpxFormat = false) const;
929
930 /// writes internal LP, basis information, and parameter settings; if \p rowNames and \p colNames are \c NULL,
931 /// default names are used
932 void writeStateRational(const char* filename, const NameSet* rowNames = 0,
933 const NameSet* colNames = 0, const bool cpxFormat = false) const;
934
935 ///@}
936
937
938 ///@name Parameters
939 ///@{
940
941 /// boolean parameters
942 typedef enum
943 {
944 /// should lifting be used to reduce range of nonzero matrix coefficients?
946
947 /// should LP be transformed to equality form before a rational solve?
949
950 /// should dual infeasibility be tested in order to try to return a dual solution even if primal infeasible?
952
953 /// should a rational factorization be performed after iterative refinement?
955
956 /// should the decomposition based dual simplex be used to solve the LP? Setting this to true forces the solve mode to
957 /// SOLVEMODE_REAL and the basis representation to REPRESENTATION_ROW
959
960 /// should the degeneracy be computed for each basis?
962
963 /// should the dual of the complementary problem be used in the decomposition simplex?
965
966 /// should row and bound violations be computed explicitly in the update of reduced problem in the decomposition simplex
968
969 /// should cycling solutions be accepted during iterative refinement?
971
972 /// apply rational reconstruction after each iterative refinement?
974
975 /// round scaling factors for iterative refinement to powers of two?
977
978 /// continue iterative refinement with exact basic solution if not optimal?
980
981 /// use bound flipping also for row representation?
983
984 /// use persistent scaling?
986
987 /// perturb the entire problem or only the relevant bounds of s single pivot?
989
990 /// re-optimize the original problem to get a proof (ray) of infeasibility/unboundedness?
992
993 /// try to enforce that the optimal solution is a basic solutiong
995
996 /// number of boolean parameters
997 BOOLPARAM_COUNT = 17
999
1000 /// integer parameters
1001 typedef enum
1002 {
1003 /// objective sense
1005
1006 /// type of computational form, i.e., column or row representation
1008
1009 /// type of algorithm, i.e., primal or dual
1011
1012 /// type of LU update
1014
1015 /// maximum number of updates without fresh factorization
1017
1018 /// iteration limit (-1 if unlimited)
1020
1021 /// refinement limit (-1 if unlimited)
1023
1024 /// stalling refinement limit (-1 if unlimited)
1026
1027 /// display frequency
1029
1030 /// verbosity level
1032
1033 /// type of simplifier
1035
1036 /// type of scaler
1038
1039 /// type of starter used to create crash basis
1041
1042 /// type of pricer
1044
1045 /// type of ratio test
1047
1048 /// mode for synchronizing real and rational LP
1050
1051 /// mode for reading LP files
1053
1054 /// mode for iterative refinement strategy
1056
1057 /// mode for a posteriori feasibility checks
1059
1060 /// type of timer
1061 TIMER = 19,
1062
1063 /// mode for hyper sparse pricing
1065
1066 /// minimum number of stalling refinements since last pivot to trigger rational factorization
1068
1069 /// maximum number of conjugate gradient iterations in least square scaling
1071
1072 /// mode for solution polishing
1074
1075 /// the number of iterations before the decomposition simplex initialisation is terminated.
1077
1078 /// the maximum number of rows that are added in each iteration of the decomposition based simplex
1080
1081 /// the iteration frequency at which the decomposition solve output is displayed.
1083
1084 /// the verbosity of the decomposition based simplex
1086
1087 /// print condition number during the solve
1089
1090 /// type of timer for statistics
1092
1093 /// number of integer parameters
1094 INTPARAM_COUNT = 30
1096
1097 /// values for parameter OBJSENSE
1098 enum
1099 {
1100 /// minimization
1102
1103 /// maximization
1106
1107 /// values for parameter REPRESENTATION
1108 enum
1109 {
1110 /// automatic choice according to number of rows and columns
1112
1113 /// column representation Ax - s = 0, lower <= x <= upper, lhs <= s <= rhs
1115
1116 /// row representation (lower,lhs) <= (x,Ax) <= (upper,rhs)
1119
1120 /// values for parameter ALGORITHM
1121 enum
1122 {
1123 /// primal simplex algorithm, i.e., entering for column and leaving for row representation
1125
1126 /// dual simplex algorithm, i.e., leaving for column and entering for row representation
1127 ALGORITHM_DUAL = 1
1129
1130 /// values for parameter FACTOR_UPDATE_TYPE
1131 enum
1132 {
1133 /// product form update
1135
1136 /// Forrest-Tomlin type update
1139
1140 /// values for parameter VERBOSITY
1141 enum
1142 {
1143 /// only error output
1145
1146 /// only error and warning output
1148
1149 /// only error, warning, and debug output
1151
1152 /// standard verbosity level
1154
1155 /// high verbosity level
1157
1158 /// full verbosity level
1159 VERBOSITY_FULL = 5
1161
1162 /// values for parameter SIMPLIFIER
1163 enum
1164 {
1165 /// disabling presolving
1167
1168 /// using internal presolving methods
1170
1171 /// using the presolve lib papilo
1173
1174 /// SoPlex chooses automatically (currently always "internal")
1175 SIMPLIFIER_AUTO = 1
1177
1178 /// values for parameter SCALER
1179 enum
1180 {
1181 /// no scaler
1183
1184 /// equilibrium scaling on rows or columns
1186
1187 /// equilibrium scaling on rows and columns
1189
1190 /// geometric mean scaling on rows and columns, max 1 round
1192
1193 /// geometric mean scaling on rows and columns, max 8 rounds
1195
1196 /// least square scaling
1198
1199 /// geometric mean scaling (max 8 rounds) followed by equilibrium scaling (rows and columns)
1200 SCALER_GEOEQUI = 6
1202
1203 /// values for parameter STARTER
1204 enum
1205 {
1206 /// slack basis
1208
1209 /// greedy crash basis weighted by objective, bounds, and sides
1211
1212 /// crash basis from a greedy solution
1214
1215 /// generic solution-based crash basis
1216 STARTER_VECTOR = 3
1218
1219 /// values for parameter PRICER
1220 enum
1221 {
1222 /// automatic pricer
1224
1225 /// Dantzig pricer
1227
1228 /// partial multiple pricer based on Dantzig pricing
1230
1231 /// devex pricer
1233
1234 /// steepest edge pricer with initialization to unit norms
1236
1237 /// steepest edge pricer with exact initialization of norms
1238 PRICER_STEEP = 5
1240
1241 /// values for parameter RATIOTESTER
1242 enum
1243 {
1244 /// textbook ratio test without stabilization
1246
1247 /// standard Harris ratio test
1249
1250 /// modified Harris ratio test
1252
1253 /// bound flipping ratio test for long steps in the dual simplex
1256
1257 /// values for parameter SYNCMODE
1258 enum
1259 {
1260 /// store only real LP
1262
1263 /// automatic sync of real and rational LP
1265
1266 /// user sync of real and rational LP
1267 SYNCMODE_MANUAL = 2
1269
1270 /// values for parameter READMODE
1271 enum
1272 {
1273 /// standard floating-point parsing
1275
1276 /// rational parsing
1279
1280 /// values for parameter SOLVEMODE
1281 enum
1282 {
1283 /// apply standard floating-point algorithm
1285
1286 /// decide depending on tolerances whether to apply iterative refinement
1288
1289 /// force iterative refinement
1292
1293 /// values for parameter CHECKMODE
1294 enum
1295 {
1296 /// floating-point check
1298
1299 /// decide according to READMODE
1301
1302 /// rational check
1305
1306 /// values for parameter TIMER
1307 enum
1308 {
1309 /// disable timing
1311
1312 /// cpu or user time
1314
1315 /// wallclock time
1316 TIMER_WALLCLOCK = 2
1318
1319 /// values for parameter HYPER_PRICING
1320 enum
1321 {
1322 /// never
1324
1325 /// decide according to problem size
1327
1328 /// always
1331
1332 /// values for parameter SOLUTION_POLISHING
1333 enum
1334 {
1335 /// no solution polishing
1337
1338 /// maximize number of basic slack variables, i.e. more variables on bounds
1340
1341 /// minimize number of basic slack variables, i.e. more variables between bounds
1344
1345 /// real parameters
1346 typedef enum
1347 {
1348 /// primal feasibility tolerance
1350
1351 /// dual feasibility tolerance
1353
1354 /// general zero tolerance
1356
1357 /// zero tolerance used in factorization
1359
1360 /// zero tolerance used in update of the factorization
1362
1363 /// pivot zero tolerance used in factorization
1365
1366 /// infinity threshold
1368
1369 /// time limit in seconds (INFTY if unlimited)
1371
1372 /// lower limit on objective value
1374
1375 /// upper limit on objective value
1377
1378 /// working tolerance for feasibility in floating-point solver during iterative refinement
1380
1381 /// working tolerance for optimality in floating-point solver during iterative refinement
1383
1384 /// maximum increase of scaling factors between refinements
1386
1387 /// lower threshold in lifting (nonzero matrix coefficients with smaller absolute value will be reformulated)
1389
1390 /// upper threshold in lifting (nonzero matrix coefficients with larger absolute value will be reformulated)
1392
1393 /// sparse pricing threshold (\#violations < dimension * SPARSITY_THRESHOLD activates sparse pricing)
1395
1396 /// threshold on number of rows vs. number of columns for switching from column to row representations in auto mode
1398
1399 /// geometric frequency at which to apply rational reconstruction
1401
1402 /// minimal reduction (sum of removed rows/cols) to continue simplification
1404
1405 /// refactor threshold for nonzeros in last factorized basis matrix compared to updated basis matrix
1407
1408 /// refactor threshold for fill-in in current factor update compared to fill-in in last factorization
1410
1411 /// refactor threshold for memory growth in factorization since last refactorization
1413
1414 /// accuracy of conjugate gradient method in least squares scaling (higher value leads to more iterations)
1416
1417 /// objective offset
1419
1420 /// minimal Markowitz threshold to control sparsity/stability in LU factorization
1422
1423 /// minimal modification threshold to apply presolve reductions
1425
1426 /// number of real parameters
1427 REALPARAM_COUNT = 26
1429
1430#ifdef SOPLEX_WITH_RATIONALPARAM
1431 /// rational parameters
1432 typedef enum
1433 {
1434 /// number of rational parameters
1435 RATIONALPARAM_COUNT = 0
1436 } RationalParam;
1437#endif
1438
1439 /// class of parameter settings
1441 {
1442 public:
1443 static struct BoolParam
1444 {
1445 /// constructor
1447 /// array of names for boolean parameters
1449 /// array of descriptions for boolean parameters
1451 /// array of default values for boolean parameters
1454
1455 static struct IntParam
1456 {
1457 /// constructor
1459 /// array of names for integer parameters
1461 /// array of descriptions for integer parameters
1463 /// array of default values for integer parameters
1465 /// array of lower bounds for int parameter values
1467 /// array of upper bounds for int parameter values
1470
1471 static struct RealParam
1472 {
1473 /// constructor
1475 /// array of names for real parameters
1477 /// array of descriptions for real parameters
1479 /// array of default values for real parameters
1481 /// array of lower bounds for real parameter values
1483 /// array of upper bounds for real parameter values
1486
1487#ifdef SOPLEX_WITH_RATIONALPARAM
1488 static struct RationalParam
1489 {
1490 /// constructor
1491 RationalParam();
1492 /// array of names for rational parameters
1493 std::string name[SoPlexBase<R>::RATIONALPARAM_COUNT];
1494 /// array of descriptions for rational parameters
1495 std::string description[SoPlexBase<R>::RATIONALPARAM_COUNT];
1496 /// array of default values for rational parameters
1498 /// array of lower bounds for rational parameter values
1500 /// array of upper bounds for rational parameter values
1502 } rationalParam;
1503#endif
1504
1505 /// array of current boolean parameter values
1507
1508 /// array of current integer parameter values
1510
1511 /// array of current real parameter values
1513
1514#ifdef SOPLEX_WITH_RATIONALPARAM
1515 /// array of current rational parameter values
1516 Rational _rationalParamValues[SoPlexBase<R>::RATIONALPARAM_COUNT];
1517#endif
1518
1519 /// default constructor initializing default settings
1521
1522 /// copy constructor
1524
1525 /// assignment operator
1527 };
1528
1530
1531 /// returns boolean parameter value
1532 bool boolParam(const BoolParam param) const;
1533
1534 /// returns integer parameter value
1535 int intParam(const IntParam param) const;
1536
1537 /// returns real parameter value
1538 Real realParam(const RealParam param) const;
1539
1540#ifdef SOPLEX_WITH_RATIONALPARAM
1541 /// returns rational parameter value
1542 Rational rationalParam(const RationalParam param) const;
1543#endif
1544
1545 /// returns current parameter settings
1546 const Settings& settings() const;
1547
1548 /// sets boolean parameter value; returns true on success
1549 bool setBoolParam(const BoolParam param, const bool value, const bool init = true);
1550
1551 /// sets integer parameter value; returns true on success
1552 bool setIntParam(const IntParam param, const int value, const bool init = true);
1553
1554 /// sets real parameter value; returns true on success
1555 bool setRealParam(const RealParam param, const Real value, const bool init = true);
1556
1557#ifdef SOPLEX_WITH_RATIONALPARAM
1558 /// sets rational parameter value; returns true on success
1559 bool setRationalParam(const RationalParam param, const Rational value, const bool init = true);
1560#endif
1561
1562 /// sets parameter settings; returns true on success
1563 bool setSettings(const Settings& newSettings, const bool init = true);
1564
1565 /// resets default parameter settings
1566 void resetSettings(const bool quiet = false, const bool init = true);
1567
1568 /// print non-default parameter values
1570
1571 /// writes settings file; returns true on success
1572 bool saveSettingsFile(const char* filename, const bool onlyChanged = false,
1573 int solvemode = 1) const;
1574
1575 /// reads settings file; returns true on success
1576 bool loadSettingsFile(const char* filename);
1577
1578 /// parses one setting string and returns true on success; note that string is modified
1579 bool parseSettingsString(char* str);
1580
1581 ///@}
1582
1583
1584 ///@name Statistics
1585 ///@{
1586
1587 /// set statistic timers to a certain type
1588 void setTimings(const Timer::TYPE ttype);
1589
1590 /// prints solution statistics
1591 void printSolutionStatistics(std::ostream& os);
1592
1593 /// prints statistics on solving process
1594 void printSolvingStatistics(std::ostream& os);
1595
1596 /// prints short statistics
1597 void printShortStatistics(std::ostream& os);
1598
1599 /// prints complete statistics
1600 void printStatistics(std::ostream& os);
1601
1602 /// prints status
1603
1604 void printStatus(std::ostream& os, typename SPxSolverBase<R>::Status status);
1605
1606 ///@}
1607
1608
1609 ///@name Miscellaneous
1610 ///@{
1611
1612 /// prints version and compilation options
1613 void printVersion() const;
1614
1615 /// checks if real LP and rational LP are in sync; dimensions will always be compared,
1616 /// vector and matrix values only if the respective parameter is set to true.
1617 /// If quiet is set to true the function will only display which vectors are different.
1618 bool areLPsInSync(const bool checkVecVals = true, const bool checkMatVals = false,
1619 const bool quiet = false) const;
1620
1621 /// set the random seeds of the solver instance
1622 void setRandomSeed(unsigned int seed);
1623
1624 /// returns the current random seed of the solver instance
1625 unsigned int randomSeed() const;
1626
1627 ///@}
1628
1629private:
1630
1631 ///@name Statistics on solving process
1632 ///@{
1633
1634 /// class of statistics
1635 class Statistics;
1636
1637 /// statistics since last call to solveReal() or solveRational()
1639
1640 ///@}
1641
1642
1643 ///@name Parameter settings
1644 ///@{
1645
1647
1653
1654 ///@}
1655
1656
1657 ///@name Data for the real LP
1658 ///@{
1659
1683
1685 _realLP; // the real LP is also used as the original LP for the decomposition dual simplex
1686 SPxLPBase<R>* _decompLP; // used to store the original LP for the decomposition dual simplex
1690
1691 bool _isRealLPLoaded; // true indicates that the original LP is loaded in the _solver variable, hence all actions
1692 // are performed on the original LP.
1695
1702
1703 ///@}
1704
1705
1706 ///@name Data for the rational LP
1707 ///@{
1708
1712
1736
1737 /// type of bounds and sides
1738 typedef enum
1739 {
1740 /// both bounds are infinite
1742
1743 /// lower bound is finite, upper bound is infinite
1745
1746 /// upper bound is finite, lower bound is infinite
1748
1749 /// lower and upper bound finite, but different
1751
1752 /// lower bound equals upper bound
1753 RANGETYPE_FIXED = 4
1755
1758
1759 ///@}
1760
1761
1762 ///@name Data for the Decomposition Based Dual Simplex
1763 ///@{
1764
1765 /** row violation structure
1766 */
1768 {
1769 R violation; /**< the violation of the row */
1770 int idx; /**< index of corresponding row */
1771 };
1772
1773 /** Compare class for row violations
1774 */
1776 {
1777 public:
1778 /** constructor
1779 */
1781 : entry(0)
1782 {
1783 }
1784
1786
1788 RowViolation i,
1789 RowViolation j
1790 ) const
1791 {
1792 return i.violation - j.violation;
1793 }
1794 };
1795
1796
1797 typedef enum
1798 {
1799 // is the original problem currently being solved.
1801
1802 // is the reduced problem currently being solved.
1804
1805 // is the complementary problem currently being solved.
1806 DECOMP_COMP = 2
1808
1809 // the expected sign of the dual variables.
1811 {
1814 IS_FREE = 2
1816
1818 _compSolver; // adding a solver to contain the complementary problem. It is too confusing to switch
1819 // the LP for the reduced and complementary problem in the one solver variable. The reduced
1820 // problem will be stored in _solver and the complementary problem will be stored in
1821 // _compSolver.
1823
1825 _decompTransBasis; // the basis required for the transformation to form the reduced problem
1826
1827 VectorBase<R> _transformedObj; // the objective coefficients of the transformed problem
1828 VectorBase<R> _decompFeasVector; // feasibility vector calculated using unshifted bounds.
1830 _transformedRows; // a set of the original rows that have been transformed using the original basis.
1831 SPxColId _compSlackColId; // column id of the primal complementary problem slack column.
1832 SPxRowId _compSlackDualRowId; // row id in the dual of complementary problem related to the slack column.
1833 bool* _decompReducedProbRows; // flag to indicate the inclusion of a row in the reduced problem.
1834 bool* _decompReducedProbCols; // flag to indicate the inclusion of a col in the reduced problem.
1837 int* _decompCompProbColIDsIdx; // the index to _decompPrimalColIDs for a given original col.
1838 DataArray < SPxRowId >
1839 _decompReducedProbRowIDs; // the row IDs for the related rows in the reduced problem
1841 _decompReducedProbColRowIDs;// the row IDs for the related cols in the reduced problem
1843 _decompReducedProbColIDs; // the col IDs for the related cols in the reduced problem
1844 DataArray < SPxRowId > _decompPrimalRowIDs; // the primal row IDs from the original problem
1845 DataArray < SPxColId > _decompPrimalColIDs; // the primal col IDs from the original problem
1847 _decompElimPrimalRowIDs; // the primal row IDs eliminated in the complementary problem
1849 _decompDualRowIDs; // the dual row IDs from the complementary problem
1851 _decompDualColIDs; // the dual col IDs from the complementary problem
1852 DataArray < SPxColId > _decompFixedVarDualIDs; // the column ids related to the fixed variables.
1854 _decompVarBoundDualIDs; // the column ids related to the variable bound constraints.
1855
1857 _decompCompPrimalFixedVarIDs; // the column ids related to the fixed variables in the complementary primal.
1859 _decompCompPrimalVarBoundIDs; // the column ids related to the variable bound constraints in the complementary primal.
1860
1862 _decompCompPrimalRowIDs; // the primal row IDs from the complementary problem
1864 _decompCompPrimalColIDs; // the primal col IDs from the complementary problem
1865
1866 int _nDecompViolBounds; // the number of violated bound constraints
1867 int _nDecompViolRows; // the number of violated rows
1868 int* _decompViolatedBounds; // the violated bounds given by the solution to the IDS reduced problem
1869 int* _decompViolatedRows; // the violated rows given by the solution to the IDS reduced problem
1870
1871
1872 int* _fixedOrigVars; // the original variables that are at their bounds in the reduced problem.
1873 // 1: fixed to upper, -1: fixed to lower, 0: unfixed.
1874 int _nPrimalRows; // the number of original problem rows included in the complementary problem
1875 int _nPrimalCols; // the number of original problem columns included in the complementary problem
1876 int _nElimPrimalRows; // the number of primal rows from the original problem eliminated from the complementary prob
1877 int _nDualRows; // the number of dual rows in the complementary problem. NOTE: _nPrimalRows = _nDualCols
1878 int _nDualCols; // the number of dual columns in the complementary problem. NOTE: _nPrimalRows = _nDualCols
1879 int _nCompPrimalRows; // the number of rows in the complementary primal problem. NOTE: _nPrimalRows = _nCompPrimalRows
1880 int _nCompPrimalCols; // the number of dual columns in the complementary problem. NOTE: _nPrimalCols = _nCompPrimalCols
1881
1882 int _decompDisplayLine; // the count for the display line
1883
1884 NameSet* _rowNames; // the row names from the input file
1885 NameSet* _colNames; // the col names from the input file
1886
1887 // Statistic information
1888 int numIncludedRows; // the number of rows currently included in the reduced problem.
1889 int numDecompIter; // the number of iterations of the decomposition dual simplex algorithm.
1890 int numRedProbIter; // the number of simplex iterations performed in the reduced problem.
1891 int numCompProbIter; // the number of iterations of the complementary problem.
1892
1893 // problem statistics
1899
1904
1910
1912
1913 ///@}
1914
1915
1916 ///@name Solution data
1917 ///@{
1918
1921
1924
1928
1932
1933 ///@}
1934
1935 ///@name Miscellaneous
1936 ///@{
1937
1940
1944
1945 ///@}
1946
1947 ///@name Constant helper methods
1948 ///@{
1949
1950 /// extends sparse vector to hold newmax entries if and only if it holds no more free entries
1952
1953 /// creates a permutation for removing rows/columns from an array of indices
1954 void _idxToPerm(int* idx, int idxSize, int* perm, int permSize) const;
1955
1956 /// creates a permutation for removing rows/columns from a range of indices
1957 void _rangeToPerm(int start, int end, int* perm, int permSize) const;
1958
1959 /// checks consistency
1960 bool _isConsistent() const;
1961
1962 /// should solving process be stopped?
1963 bool _isSolveStopped(bool& stoppedTime, bool& stoppedIter) const;
1964
1965 /// determines RangeType from real bounds
1966 RangeType _rangeTypeReal(const R& lower, const R& upper) const;
1967
1968 /// determines RangeType from rational bounds
1969 RangeType _rangeTypeRational(const Rational& lower, const Rational& upper) const;
1970
1971 /// switches RANGETYPE_LOWER to RANGETYPE_UPPER and vice versa
1973
1974 /// checks whether RangeType corresponds to finite lower bound
1976
1977 /// checks whether RangeType corresponds to finite upper bound
1979
1980 ///@}
1981
1982
1983 ///@name Non-constant helper methods
1984 ///@{
1985
1986 /// adds a single row to the real LP and adjusts basis
1988
1989 /// adds a single row to the real LP and adjusts basis
1990 void _addRowReal(R lhs, const SVectorBase<R>& lprow, R rhs);
1991
1992 /// adds multiple rows to the real LP and adjusts basis
1993 void _addRowsReal(const LPRowSetBase<R>& lprowset);
1994
1995 /// adds a single column to the real LP and adjusts basis
1997
1998 /// adds a single column to the real LP and adjusts basis
1999 void _addColReal(R obj, R lower, const SVectorBase<R>& lpcol, R upper);
2000
2001 /// adds multiple columns to the real LP and adjusts basis
2002 void _addColsReal(const LPColSetReal& lpcolset);
2003
2004 /// replaces row \p i with \p lprow and adjusts basis
2006
2007 /// changes left-hand side vector for constraints to \p lhs and adjusts basis
2009
2010 /// changes left-hand side of row \p i to \p lhs and adjusts basis
2011 void _changeLhsReal(int i, const R& lhs);
2012
2013 /// changes right-hand side vector to \p rhs and adjusts basis
2015
2016 /// changes right-hand side of row \p i to \p rhs and adjusts basis
2017 void _changeRhsReal(int i, const R& rhs);
2018
2019 /// changes left- and right-hand side vectors and adjusts basis
2020 void _changeRangeReal(const VectorBase<R>& lhs, const VectorBase<R>& rhs);
2021
2022 /// changes left- and right-hand side of row \p i and adjusts basis
2023 void _changeRangeReal(int i, const R& lhs, const R& rhs);
2024
2025 /// replaces column \p i with \p lpcol and adjusts basis
2026 void _changeColReal(int i, const LPColReal& lpcol);
2027
2028 /// changes vector of lower bounds to \p lower and adjusts basis
2030
2031 /// changes lower bound of column i to \p lower and adjusts basis
2032 void _changeLowerReal(int i, const R& lower);
2033
2034 /// changes vector of upper bounds to \p upper and adjusts basis
2036
2037 /// changes \p i 'th upper bound to \p upper and adjusts basis
2038 void _changeUpperReal(int i, const R& upper);
2039
2040 /// changes vectors of column bounds to \p lower and \p upper and adjusts basis
2041 void _changeBoundsReal(const VectorBase<R>& lower, const VectorBase<R>& upper);
2042
2043 /// changes bounds of column \p i to \p lower and \p upper and adjusts basis
2044 void _changeBoundsReal(int i, const R& lower, const R& upper);
2045
2046 /// changes matrix entry in row \p i and column \p j to \p val and adjusts basis
2047 void _changeElementReal(int i, int j, const R& val);
2048
2049 /// removes row \p i and adjusts basis
2051
2052 /// removes all rows with an index \p i such that \p perm[i] < 0; upon completion, \p perm[i] >= 0 indicates the
2053 /// new index where row \p i has been moved to; note that \p perm must point to an array of size at least
2054 /// #numRows()
2055 void _removeRowsReal(int perm[]);
2056
2057 /// remove all rows with indices in array \p idx of size \p n; an array \p perm of size #numRows() may be passed
2058 /// as buffer memory
2059 void _removeRowsReal(int idx[], int n, int perm[]);
2060
2061 /// removes rows \p start to \p end including both; an array \p perm of size #numRows() may be passed as buffer
2062 /// memory
2063 void _removeRowRangeReal(int start, int end, int perm[]);
2064
2065 /// removes column i
2067
2068 /// removes all columns with an index \p i such that \p perm[i] < 0; upon completion, \p perm[i] >= 0 indicates the
2069 /// new index where column \p i has been moved to; note that \p perm must point to an array of size at least
2070 /// #numColsReal()
2071 void _removeColsReal(int perm[]);
2072
2073 /// remove all columns with indices in array \p idx of size \p n; an array \p perm of size #numColsReal() may be
2074 /// passed as buffer memory
2075 void _removeColsReal(int idx[], int n, int perm[]);
2076
2077 /// removes columns \p start to \p end including both; an array \p perm of size #numColsReal() may be passed as
2078 /// buffer memory
2079 void _removeColRangeReal(int start, int end, int perm[]);
2080
2081 /// invalidates solution
2083
2084 /// enables simplifier and scaler according to current parameters
2086
2087 /// disables simplifier and scaler
2089
2090 /// ensures that the rational LP is available; performs no sync
2092
2093 /// ensures that the real LP and the basis are loaded in the solver; performs no sync
2095
2096 /// call floating-point solver and update statistics on iterations etc.
2098
2099 /// reads real LP in LP or MPS format from file and returns true on success; gets row names, column names, and
2100 /// integer variables if desired
2102 DIdxSet* intVars = 0);
2103
2104 /// reads rational LP in LP or MPS format from file and returns true on success; gets row names, column names, and
2105 /// integer variables if desired
2107 DIdxSet* intVars = 0);
2108
2109 /// completes range type arrays after adding columns and/or rows
2111
2112 /// recomputes range types from scratch using real LP
2114
2115 /// recomputes range types from scratch using rational LP
2117
2118 /// synchronizes real LP with rational LP, i.e., copies (rounded) rational LP into real LP, without looking at the sync mode
2119 void _syncLPReal(bool time = true);
2120
2121 /// synchronizes rational LP with real LP, i.e., copies real LP to rational LP, without looking at the sync mode
2122 void _syncLPRational(bool time = true);
2123
2124 /// synchronizes rational solution with real solution, i.e., copies (rounded) rational solution to real solution
2126
2127 /// synchronizes real solution with rational solution, i.e., copies real solution to rational solution
2129
2130 /// returns pointer to a constant unit vector available until destruction of the SoPlexBase class
2132
2133 /// parses one line in a settings file and returns true on success; note that the string is modified
2134 bool _parseSettingsLine(char* line, const int lineNumber);
2135
2136 ///@}
2137
2138
2139 //**@name Private solving methods implemented in solverational.hpp */
2140 ///@{
2141
2142 /// solves current problem with iterative refinement and recovery mechanism
2144 bool acceptUnbounded,
2145 bool acceptInfeasible,
2146 int minRounds,
2147 bool& primalFeasible,
2148 bool& dualFeasible,
2149 bool& infeasible,
2150 bool& unbounded,
2151 bool& stoppedTime,
2152 bool& stoppedIter,
2153 bool& error);
2154
2155 /// performs iterative refinement on the auxiliary problem for testing unboundedness
2157 bool& stoppedIter, bool& error);
2158
2159 /// performs iterative refinement on the auxiliary problem for testing feasibility
2161 bool& stoppedIter, bool& error);
2162
2163 /// reduces matrix coefficient in absolute value by the lifting procedure of Thiele et al. 2013
2164 void _lift();
2165
2166 /// undoes lifting
2168
2169 /// store basis
2171
2172 /// restore basis
2174
2175 /// stores objective, bounds, and sides of real LP
2177
2178 /// restores objective, bounds, and sides of real LP
2180
2181 /// introduces slack variables to transform inequality constraints into equations for both rational and real LP,
2182 /// which should be in sync
2184
2185 /// undoes transformation to equality form
2187
2188 /// transforms LP to unboundedness problem by moving the objective function to the constraints, changing right-hand
2189 /// side and bounds to zero, and adding an auxiliary variable for the decrease in the objective function
2191
2192 /// undoes transformation to unboundedness problem
2194
2195 /// transforms LP to feasibility problem by removing the objective function, shifting variables, and homogenizing the
2196 /// right-hand side
2198
2199 /// undoes transformation to feasibility problem
2201
2202 /** computes radius of infeasibility box implied by an approximate Farkas' proof
2203
2204 Given constraints of the form \f$ lhs <= Ax <= rhs \f$, a farkas proof y should satisfy \f$ y^T A = 0 \f$ and
2205 \f$ y_+^T lhs - y_-^T rhs > 0 \f$, where \f$ y_+, y_- \f$ denote the positive and negative parts of \f$ y \f$.
2206 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
2207 as the following holds for all potentially feasible \f$ x \f$:
2208
2209 \f[
2210 y^T Ax < (y_+^T lhs - y_-^T rhs) (*)
2211 \f]
2212
2213 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
2214 bounds on \f$ x \f$ imply that all feasible \f$ x \f$ satisfy (*), and if not then compute bounds on \f$ x \f$ to
2215 guarantee (*). The simplest way to do this is to compute
2216
2217 \f[
2218 B = (y_+^T lhs - y_-^T rhs) / \sum_i(|(y^T A)_i|)
2219 \f]
2220
2221 noting that if every component of \f$ x \f$ has \f$ |x_i| < B \f$, then (*) holds.
2222
2223 \f$ B \f$ can be increased by iteratively including variable bounds smaller than \f$ B \f$. The speed of this
2224 method can be further improved by using interval arithmetic for all computations. For related information see
2225 Sec. 4 of Neumaier and Shcherbina, Mathematical Programming A, 2004.
2226
2227 Set transformed to true if this method is called after _transformFeasibility().
2228 */
2230
2231 /// solves real LP during iterative refinement
2233 VectorBase<R>& dual,
2236
2237 /// solves real LP with recovery mechanism
2239 VectorBase<R>& primal, VectorBase<R>& dual,
2242 const bool forceNoSimplifier = false);
2243
2244 /// computes rational inverse of basis matrix as defined by _rationalLUSolverBind
2246
2247 /// factorizes rational basis matrix in column representation
2251 bool& stoppedIter, bool& error, bool& optimal);
2252
2253 /// attempts rational reconstruction of primal-dual solution
2258 ///@}
2259
2260 ///@name Private solving methods implemented in solvereal.cpp
2261 ///@{
2262
2263 /// solves the templated LP
2264 void _optimize(volatile bool* interrupt = NULL);
2265
2266 /// temporary fix for Rational
2267 void _optimizeRational(volatile bool* interrupt = NULL);
2268
2269 /// checks result of the solving process and solves again without preprocessing if necessary
2271
2272 /// solves real LP with/without preprocessing
2274
2275 /// loads original problem into solver and solves again after it has been solved to optimality with preprocessing
2277
2278 /// verify computed solution and resolve if necessary
2280
2281 /// stores solution of the real LP; before calling this, the real LP must be loaded in the solver and solved (again)
2282 void _storeSolutionReal(bool verify = true);
2283
2284 /// stores solution from the simplifier because problem vanished in presolving step
2286
2287 /// unscales stored solution to remove internal or external scaling of LP
2289
2290 /// load original LP and possibly setup a slack basis
2292
2293 /// check scaling of LP
2295
2296 /// check correctness of (un)scaled basis matrix operations
2298
2299 /// check whether persistent scaling is supposed to be reapplied again after unscaling
2301
2302 /// solves LP using the decomposition based dual simplex
2304
2305 /// creating copies of the original problem that will be manipulated to form the reduced and complementary problems
2307
2308 /// forms the reduced problem
2310
2311 /// solves the reduced problem
2313
2314 /// forms the complementary problem
2316
2317 /// simplifies the problem and solves
2319 bool applyPreprocessing);
2320
2321 /// loads original problem into solver and solves again after it has been solved to optimality with preprocessing
2323 typename SPxSimplifier<R>::Result result);
2324
2325 /// identifies the columns of the row-form basis that correspond to rows with zero dual multipliers.
2327 int* nnonposind, bool& stop);
2328
2329 /// retrieves the compatible columns from the constraint matrix
2331 int* rowsforremoval, int* colsforremoval,
2332 int nnonposind, int* ncompatind, bool formRedProb, bool& stop);
2333
2334 /// computes the reduced problem objective coefficients
2336
2337 /// computes the compatible bound constraints and adds them to the reduced problem
2339 int* ncompatboundcons,
2340 int nnonposind, bool& stop);
2341
2342 /// computes the rows to remove from the complementary problem
2344 int* nrowsforremoval,
2345 int nnonposind);
2346
2347 /// removing rows from the complementary problem.
2349
2350 /// evaluates the solution of the reduced problem for the DBDS
2352 typename SPxSimplifier<R>::Result result);
2353
2354 /// update the reduced problem with additional columns and rows
2358
2359 /// update the reduced problem with additional columns and rows based upon the violated original bounds and rows
2361
2362 /// builds the update rows with those violated in the complmentary problem
2364
2365 /// update the dual complementary problem with additional columns and rows
2367
2368 /// update the primal complementary problem with additional columns and rows
2370
2371 /// checking the optimality of the original problem.
2373
2374 /// updating the slack column coefficients to adjust for equality constraints
2376
2377 /// updating the slack column coefficients to adjust for equality constraints
2379
2380 /// removing the dual columns related to the fixed variables
2382
2383 /// removing the dual columns related to the fixed variables
2385
2386 /// updating the dual columns related to the fixed primal variables.
2388
2389 /// removing the dual columns related to the fixed variables
2391
2392 /// updating the dual columns related to the fixed primal variables.
2394
2395 /// updating the complementary dual problem with the original objective function
2397
2398 /// updating the complementary primal problem with the original objective function
2400
2401 /// determining which bound the primal variables will be fixed to.
2403
2404 /// checks the dual feasibility of the current basis
2406
2407 /// returns the expected sign of the dual variables for the reduced problem
2409
2410 /// returns the expected sign of the dual variables for the original problem
2412
2413 /// prints a display line of the flying table for the DBDS
2415 bool forceHead);
2416
2417 /// stores the problem statistics of the original problem
2419
2420 /// stores the problem statistics of the original problem
2422
2423 /// gets the coefficient of the slack variable in the primal complementary problem
2425
2426 /// gets violation of bounds; returns true on success
2428
2429 /// gets violation of constraints; returns true on success
2431
2432 /// function call to terminate the decomposition simplex
2433 bool decompTerminate(R timeLimit);
2434
2435 /// function to build a basis for the original problem as given by the solution to the reduced problem
2437 bool cpxFormat);
2438
2439 /// function to retrieve the original problem row basis status from the reduced and complementary problems
2442 int& nNonBasicRows);
2443
2444 /// function to retrieve the column status for the original problem basis from the reduced and complementary problems
2446
2447 ///@}
2448};
2449
2450/* Backwards compatibility */
2452// A header file containing all the general templated functions
2453
2454} // namespace soplex
2455
2456// General templated function
2457#include "soplex/solvedbds.hpp"
2458#include "soplex.hpp"
2459#include "soplex/solverational.hpp"
2460#include "soplex/testsoplex.hpp"
2461#include "soplex/solvereal.hpp"
2462
2463#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
Simplex basis.
Definition spxbasis.h:94
SPxStatus
basis status.
Definition spxbasis.h:102
Bound flipping ratio test ("long step dual") for SoPlex.
Ids for LP columns.
Definition spxid.h:46
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:52
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:73
Verbosity
Verbosity level.
Definition spxout.h:82
Partial multiple pricing.
Ids for LP rows.
Definition spxid.h:65
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:1441
int _intParamValues[SoPlexBase< R >::INTPARAM_COUNT]
array of current integer parameter values
Definition soplex.h:1509
static struct soplex::SoPlexBase::Settings::BoolParam boolParam
bool _boolParamValues[SoPlexBase< R >::BOOLPARAM_COUNT]
array of current boolean parameter values
Definition soplex.h:1506
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:1512
static struct soplex::SoPlexBase::Settings::RealParam realParam
Settings()
default constructor initializing default settings
int numRows() const
returns number of rows
bool getBasisInverseTimesVecRational(const SVectorRational &rhs, SSVectorRational &sol)
computes solution of basis matrix B * sol = rhs; performs rational factorization if not available; re...
void _performOptIRStable(SolRational &sol, bool acceptUnbounded, bool acceptInfeasible, int minRounds, bool &primalFeasible, bool &dualFeasible, bool &infeasible, bool &unbounded, bool &stoppedTime, bool &stoppedIter, bool &error)
solves current problem with iterative refinement and recovery mechanism
bool _isSolveStopped(bool &stoppedTime, bool &stoppedIter) const
should solving process be stopped?
@ STARTER_VECTOR
generic solution-based crash basis
Definition soplex.h:1216
@ STARTER_WEIGHT
greedy crash basis weighted by objective, bounds, and sides
Definition soplex.h:1210
@ STARTER_SUM
crash basis from a greedy solution
Definition soplex.h:1213
@ STARTER_OFF
slack basis
Definition soplex.h:1207
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:1297
@ CHECKMODE_RATIONAL
rational check
Definition soplex.h:1303
@ CHECKMODE_AUTO
decide according to READMODE
Definition soplex.h:1300
VectorRational _modObj
Definition soplex.h:1728
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 _setComplementaryPrimalOriginalObjective()
updating the complementary primal problem with the original objective function
void _untransformFeasibility(SolRational &sol, bool infeasible)
undoes transformation to feasibility problem
@ OBJSENSE_MAXIMIZE
maximization
Definition soplex.h:1104
@ OBJSENSE_MINIMIZE
minimization
Definition soplex.h:1101
bool getRowViolation(R &maxviol, R &sumviol)
gets violation of constraints; returns true on success
DataArray< SPxRowId > _decompElimPrimalRowIDs
Definition soplex.h:1847
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 * _decompReducedProbRows
Definition soplex.h:1833
VectorRational _modUpper
Definition soplex.h:1725
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
int * _decompCompProbColIDsIdx
Definition soplex.h:1837
void _storeLPReal()
stores objective, bounds, and sides of real LP
Real solveTime() const
time spent in last call to solve
void _identifyComplementaryPrimalFixedPrimalVars(int *currFixedVars)
removing the dual columns related to the fixed variables
void _preprocessAndSolveReal(bool applyPreprocessing, volatile bool *interrupt=NULL)
solves real LP with/without preprocessing
VectorBase< R > _manualRhs
Definition soplex.h:1699
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:1670
const VectorBase< R > & lhsRealInternal() const
returns left-hand side vector, ignoring scaling
R coefReal(int row, int col) const
returns (unscaled) coefficient
VectorRational _unboundedLhs
Definition soplex.h:1716
SPxBasisBase< R > _decompTransBasis
Definition soplex.h:1825
bool getSlacksReal(VectorBase< R > &vector)
gets the vector of slack values if available; returns true on success
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:1665
RealParam
real parameters
Definition soplex.h:1347
@ OPTTOL
dual feasibility tolerance
Definition soplex.h:1352
@ FPOPTTOL
working tolerance for optimality in floating-point solver during iterative refinement
Definition soplex.h:1382
@ SPARSITY_THRESHOLD
sparse pricing threshold (#violations < dimension * SPARSITY_THRESHOLD activates sparse pricing)
Definition soplex.h:1394
@ LIFTMAXVAL
upper threshold in lifting (nonzero matrix coefficients with larger absolute value will be reformulat...
Definition soplex.h:1391
@ EPSILON_ZERO
general zero tolerance
Definition soplex.h:1355
@ EPSILON_FACTORIZATION
zero tolerance used in factorization
Definition soplex.h:1358
@ OBJLIMIT_UPPER
upper limit on objective value
Definition soplex.h:1376
@ FPFEASTOL
working tolerance for feasibility in floating-point solver during iterative refinement
Definition soplex.h:1379
@ RATREC_FREQ
geometric frequency at which to apply rational reconstruction
Definition soplex.h:1400
@ MAXSCALEINCR
maximum increase of scaling factors between refinements
Definition soplex.h:1385
@ TIMELIMIT
time limit in seconds (INFTY if unlimited)
Definition soplex.h:1370
@ LIFTMINVAL
lower threshold in lifting (nonzero matrix coefficients with smaller absolute value will be reformula...
Definition soplex.h:1388
@ REPRESENTATION_SWITCH
threshold on number of rows vs. number of columns for switching from column to row representations in...
Definition soplex.h:1397
@ REFAC_UPDATE_FILL
refactor threshold for fill-in in current factor update compared to fill-in in last factorization
Definition soplex.h:1409
@ REALPARAM_COUNT
number of real parameters
Definition soplex.h:1427
@ MINRED
minimal reduction (sum of removed rows/cols) to continue simplification
Definition soplex.h:1403
@ OBJ_OFFSET
objective offset
Definition soplex.h:1418
@ OBJLIMIT_LOWER
lower limit on objective value
Definition soplex.h:1373
@ FEASTOL
primal feasibility tolerance
Definition soplex.h:1349
@ EPSILON_PIVOT
pivot zero tolerance used in factorization
Definition soplex.h:1364
@ MIN_MARKOWITZ
minimal Markowitz threshold to control sparsity/stability in LU factorization
Definition soplex.h:1421
@ REFAC_MEM_FACTOR
refactor threshold for memory growth in factorization since last refactorization
Definition soplex.h:1412
@ SIMPLIFIER_MODIFYROWFAC
minimal modification threshold to apply presolve reductions
Definition soplex.h:1424
@ EPSILON_UPDATE
zero tolerance used in update of the factorization
Definition soplex.h:1361
@ REFAC_BASIS_NNZ
refactor threshold for nonzeros in last factorized basis matrix compared to updated basis matrix
Definition soplex.h:1406
@ LEASTSQ_ACRCY
accuracy of conjugate gradient method in least squares scaling (higher value leads to more iterations...
Definition soplex.h:1415
@ INFTY
infinity threshold
Definition soplex.h:1367
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 _updateComplementaryDualSlackColCoeff()
updating the slack column coefficients to adjust for equality constraints
bool getSlacksReal(R *p_vector, int dim)
DataArray< typename SPxSolverBase< R >::VarStatus > _basisStatusRows
Definition soplex.h:1922
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:1316
@ TIMER_CPU
cpu or user time
Definition soplex.h:1313
@ TIMER_OFF
disable timing
Definition soplex.h:1310
VectorRational _feasObj
Definition soplex.h:1719
void changeRhsRational(const VectorRational &rhs)
changes right-hand side vector to rhs
IntParam
integer parameters
Definition soplex.h:1002
@ HYPER_PRICING
mode for hyper sparse pricing
Definition soplex.h:1064
@ DECOMP_MAXADDEDROWS
the maximum number of rows that are added in each iteration of the decomposition based simplex
Definition soplex.h:1079
@ DISPLAYFREQ
display frequency
Definition soplex.h:1028
@ TIMER
type of timer
Definition soplex.h:1061
@ CHECKMODE
mode for a posteriori feasibility checks
Definition soplex.h:1058
@ STATTIMER
type of timer for statistics
Definition soplex.h:1091
@ FACTOR_UPDATE_TYPE
type of LU update
Definition soplex.h:1013
@ READMODE
mode for reading LP files
Definition soplex.h:1052
@ STALLREFLIMIT
stalling refinement limit (-1 if unlimited)
Definition soplex.h:1025
@ STARTER
type of starter used to create crash basis
Definition soplex.h:1040
@ REFLIMIT
refinement limit (-1 if unlimited)
Definition soplex.h:1022
@ SYNCMODE
mode for synchronizing real and rational LP
Definition soplex.h:1049
@ PRICER
type of pricer
Definition soplex.h:1043
@ LEASTSQ_MAXROUNDS
maximum number of conjugate gradient iterations in least square scaling
Definition soplex.h:1070
@ ALGORITHM
type of algorithm, i.e., primal or dual
Definition soplex.h:1010
@ DECOMP_VERBOSITY
the verbosity of the decomposition based simplex
Definition soplex.h:1085
@ DECOMP_ITERLIMIT
the number of iterations before the decomposition simplex initialisation is terminated.
Definition soplex.h:1076
@ DECOMP_DISPLAYFREQ
the iteration frequency at which the decomposition solve output is displayed.
Definition soplex.h:1082
@ INTPARAM_COUNT
number of integer parameters
Definition soplex.h:1094
@ OBJSENSE
objective sense
Definition soplex.h:1004
@ SIMPLIFIER
type of simplifier
Definition soplex.h:1034
@ PRINTBASISMETRIC
print condition number during the solve
Definition soplex.h:1088
@ REPRESENTATION
type of computational form, i.e., column or row representation
Definition soplex.h:1007
@ SOLVEMODE
mode for iterative refinement strategy
Definition soplex.h:1055
@ RATFAC_MINSTALLS
minimum number of stalling refinements since last pivot to trigger rational factorization
Definition soplex.h:1067
@ SOLUTION_POLISHING
mode for solution polishing
Definition soplex.h:1073
@ FACTOR_UPDATE_MAX
maximum number of updates without fresh factorization
Definition soplex.h:1016
@ SCALER
type of scaler
Definition soplex.h:1037
@ ITERLIMIT
iteration limit (-1 if unlimited)
Definition soplex.h:1019
@ RATIOTESTER
type of ratio test
Definition soplex.h:1046
@ VERBOSITY
verbosity level
Definition soplex.h:1031
DSVectorRational _tauColVector
Definition soplex.h:1718
void _removeColReal(int i)
removes column i
void changeUpperRational(const VectorRational &upper)
changes vector of upper bounds to upper
SolRational _solRational
Definition soplex.h:1926
void _addColReal(const LPColReal &lpcol)
adds a single column to the real LP and adjusts basis
NameSet * _rowNames
Definition soplex.h:1884
DataArray< typename SPxSolverBase< R >::VarStatus > _storedBasisStatusRows
Definition soplex.h:1730
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
void _solveDecompReducedProblem()
solves the reduced problem
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
int * _decompViolatedBounds
Definition soplex.h:1868
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:1927
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:1714
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...
SPxRowId _compSlackDualRowId
Definition soplex.h:1832
int numRowsRational() const
void _updateDecompComplementaryDualProblem(bool origObj)
update the dual complementary problem with additional columns and rows
bool checkBasisDualFeasibility(VectorBase< R > feasVec)
checks the dual feasibility of the current basis
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
void _updateDecompReducedProblemViol(bool allrows)
update the reduced problem with additional columns and rows based upon the violated original bounds a...
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-...
SPxColId _compSlackColId
Definition soplex.h:1831
bool getBasisInverseTimesVecReal(R *rhs, R *sol, bool unscale=true)
computes dense solution of basis matrix B * sol = rhs; returns true on success
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
void _setComplementaryDualOriginalObjective()
updating the complementary dual problem with the original objective function
SPxGeometSC< R > _scalerGeo1
Definition soplex.h:1666
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)
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:1701
void changeColReal(int i, const LPColReal &lpcol)
replaces column i with lpcol
DataArray< SPxRowId > _decompCompPrimalRowIDs
Definition soplex.h:1862
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
DataArray< SPxColId > _decompVarBoundDualIDs
Definition soplex.h:1854
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...
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:1685
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:1267
@ SYNCMODE_ONLYREAL
store only real LP
Definition soplex.h:1261
@ SYNCMODE_AUTO
automatic sync of real and rational LP
Definition soplex.h:1264
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:1675
const char * getPricerName()
name of currently loaded pricer
void addColsRational(const LPColSetRational &lpcolset)
adds multiple columns
DataArray< SPxRowId > _decompPrimalRowIDs
Definition soplex.h:1844
VectorRational _feasLhs
Definition soplex.h:1720
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
DataArray< SPxColId > _decompCompPrimalVarBoundIDs
Definition soplex.h:1859
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
VectorRational _feasRhs
Definition soplex.h:1721
VectorRational _feasLower
Definition soplex.h:1722
void _removeComplementaryDualFixedPrimalVars(int *currFixedVars)
removing the dual columns related to the fixed variables
SPxSolverBase< R > _compSolver
Definition soplex.h:1818
int numColsReal() const
void _findViolatedRows(R compObjValue, Array< RowViolation > &violatedrows, int &nviolatedrows)
builds the update rows with those violated in the complmentary problem
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
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)
NameSet * _colNames
Definition soplex.h:1885
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:1649
Rational _rationalZero
Definition soplex.h:1943
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:1756
bool isDualFeasible() const
is stored dual solution feasible?
DataArray< typename SPxSolverBase< R >::VarStatus > _basisStatusCols
Definition soplex.h:1923
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:1674
Presol< R > _simplifierPaPILO
Definition soplex.h:1663
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
void _getZeroDualMultiplierIndices(VectorBase< R > feasVector, int *nonposind, int *colsforremoval, int *nnonposind, bool &stop)
identifies the columns of the row-form basis that correspond to rows with zero dual multipliers.
Rational _rationalPosone
Definition soplex.h:1941
bool getPrimalRational(VectorRational &vector)
int totalSizeDualRational(const int base=2)
get size of dual solution
void getOriginalProblemStatistics()
stores the problem statistics of the original problem
int dlcmSizeDualRational(const int base=2)
get size of least common multiple of denominators in dual solution
SPxSteepPR< R > _pricerQuickSteep
Definition soplex.h:1677
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:1729
DataArray< typename SPxSolverBase< R >::VarStatus > _storedBasisStatusCols
Definition soplex.h:1731
void _updateDecompComplementaryPrimalProblem(bool origObj)
update the primal complementary problem with additional columns and rows
void _evaluateSolutionDecomp(SPxSolverBase< R > &solver, SLUFactor< R > &sluFactor, typename SPxSimplifier< R >::Result result)
evaluates the solution of the reduced problem for the DBDS
SPxSumST< R > _starterSum
Definition soplex.h:1671
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:1661
int numCols() const
Templated function that returns number of columns.
bool _lowerFinite(const RangeType &rangeType) const
checks whether RangeType corresponds to finite lower bound
SPxDevexPR< R > _pricerDevex
Definition soplex.h:1676
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:1700
SLUFactorRational _rationalLUSolver
Definition soplex.h:1710
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 _computeReducedProbObjCoeff(bool &stop)
computes the reduced problem objective coefficients
bool * _decompReducedProbCols
Definition soplex.h:1834
void _checkOriginalProblemOptimality(VectorBase< R > primalVector, bool printViol)
checking the optimality of the original problem.
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:1169
@ SIMPLIFIER_PAPILO
using the presolve lib papilo
Definition soplex.h:1172
@ SIMPLIFIER_AUTO
SoPlex chooses automatically (currently always "internal")
Definition soplex.h:1175
@ SIMPLIFIER_OFF
disabling presolving
Definition soplex.h:1166
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...
const char * getRatiotesterName()
name of currently loaded ratiotester
Rational objValueRational()
returns the objective value if a primal solution is available
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
void changeRhsRational(int i, const Rational &rhs)
changes right-hand side of row i to rhs
SPxVectorST< R > _starterVector
Definition soplex.h:1672
void _getRowsForRemovalComplementaryProblem(int *nonposind, int *bind, int *rowsforremoval, int *nrowsforremoval, int nnonposind)
computes the rows to remove from the complementary problem
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
void _changeLowerReal(const VectorBase< R > &lower)
changes vector of lower bounds to lower and adjusts basis
void _solveDecompositionDualSimplex()
solves LP using the decomposition based dual simplex
void _changeUpperReal(const VectorBase< R > &upper)
changes vector of upper bounds to upper and adjusts basis
void _formDecompComplementaryProblem()
forms the complementary problem
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
R objReal(int i) const
returns objective value of column i
void _updateComplementaryPrimalSlackColCoeff()
updating the slack column coefficients to adjust for equality constraints
VectorRational _unboundedRhs
Definition soplex.h:1717
@ SCALER_GEOEQUI
geometric mean scaling (max 8 rounds) followed by equilibrium scaling (rows and columns)
Definition soplex.h:1200
@ SCALER_UNIEQUI
equilibrium scaling on rows or columns
Definition soplex.h:1185
@ SCALER_BIEQUI
equilibrium scaling on rows and columns
Definition soplex.h:1188
@ SCALER_LEASTSQ
least square scaling
Definition soplex.h:1197
@ SCALER_GEO1
geometric mean scaling on rows and columns, max 1 round
Definition soplex.h:1191
@ SCALER_OFF
no scaler
Definition soplex.h:1182
@ SCALER_GEO8
geometric mean scaling on rows and columns, max 8 rounds
Definition soplex.h:1194
SolBase< R > _solReal
Definition soplex.h:1925
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:1646
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,...
unsigned int randomSeed() const
returns the current random seed of the solver instance
SPxAutoPR< R > _pricerAuto
Definition soplex.h:1673
void getOriginalProblemBasisColStatus(int &nNonBasicCols)
function to retrieve the column status for the original problem basis from the reduced and complement...
bool getExactCondition(R &condition)
computes the exact condition number for the current basis matrix using the power method; returns true...
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
VectorBase< R > _transformedObj
Definition soplex.h:1827
void changeRowReal(int i, const LPRowBase< R > &lprow)
replaces row i with lprow
void _recomputeRangeTypesReal()
recomputes range types from scratch using real LP
SPxSteepExPR< R > _pricerSteep
Definition soplex.h:1678
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:1651
void _checkScaling(SPxLPBase< R > *origLP) const
check scaling of LP
void removeRowReal(int i)
removes row i
DataArray< RangeType > _rowTypes
Definition soplex.h:1757
SPxDefaultRT< R > _ratiotesterTextbook
Definition soplex.h:1679
void _writeOriginalProblemBasis(const char *filename, NameSet *rowNames, NameSet *colNames, bool cpxFormat)
function to build a basis for the original problem as given by the solution to the reduced problem
DataArray< SPxColId > _decompDualColIDs
Definition soplex.h:1851
SPxSolverBase< R >::VarStatus basisRowStatus(int row) const
returns basis status for a single row
void _restoreLPReal()
restores objective, bounds, and sides of real LP
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:1724
void changeUpperRational(int i, const Rational &upper)
changes i 'th upper bound to upper
void _updateComplementaryPrimalFixedPrimalVars(int *currFixedVars)
updating the dual columns related to the fixed primal variables.
bool getRedCost(VectorBase< R > &vector)
gets the vector of reduced cost values if available; returns true on success
SPxBoundFlippingRT< R > _ratiotesterBoundFlipping
Definition soplex.h:1682
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 _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
bool getDecompBoundViolation(R &maxviol, R &sumviol)
gets violation of bounds; returns true on success
void _syncRationalSolution()
synchronizes real solution with rational solution, i.e., copies real solution to rational solution
void _changeLhsReal(int i, const R &lhs)
changes left-hand side of row i to lhs and adjusts basis
VectorRational _unboundedUpper
Definition soplex.h:1715
SPxSolverBase< R >::Status _status
Definition soplex.h:1919
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
DataArray< SPxColId > _decompReducedProbColIDs
Definition soplex.h:1843
@ ALGORITHM_PRIMAL
primal simplex algorithm, i.e., entering for column and leaving for row representation
Definition soplex.h:1124
@ ALGORITHM_DUAL
dual simplex algorithm, i.e., leaving for column and entering for row representation
Definition soplex.h:1127
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,...
bool getDecompRowViolation(R &maxviol, R &sumviol)
gets violation of constraints; returns true on success
void _transformEquality()
introduces slack variables to transform inequality constraints into equations for both rational and r...
void clearBasis()
clears starting basis
DataArray< int > _rationalLUSolverBind
Definition soplex.h:1711
SPxGeometSC< R > _scalerGeo8
Definition soplex.h:1667
VectorBase< R > _decompFeasVector
Definition soplex.h:1828
bool decompTerminate(R timeLimit)
function call to terminate the decomposition simplex
DualSign getExpectedDualVariableSign(int rowNumber)
returns the expected sign of the dual variables for the reduced problem
std::string statisticString() const
statistical information in form of a string
void _ensureRationalLP()
ensures that the rational LP is available; performs no sync
DataArray< SPxColId > _decompCompPrimalColIDs
Definition soplex.h:1864
VectorRational _modRhs
Definition soplex.h:1727
VectorBase< R > _manualLhs
Definition soplex.h:1698
void _getCompatibleBoundCons(LPRowSetBase< R > &boundcons, int *compatboundcons, int *nonposind, int *ncompatboundcons, int nnonposind, bool &stop)
computes the compatible bound constraints and adds them to the reduced problem
void changeBoundsReal(const VectorBase< R > &lower, const VectorBase< R > &upper)
changes vectors of column bounds to lower and upper
int getOrigVarFixedDirection(int colNum)
determining which bound the primal variables will be fixed to.
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 _identifyComplementaryDualFixedPrimalVars(int *currFixedVars)
removing the dual columns related to the fixed variables
void getNdualNorms(int &nnormsRow, int &nnormsCol) const
gets number of available dual norms
Rational _rationalNegone
Definition soplex.h:1942
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...
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
void _createDecompReducedAndComplementaryProblems()
creating copies of the original problem that will be manipulated to form the reduced and complementar...
VectorBase< R > _manualLower
Definition soplex.h:1696
DataArray< SPxColId > _decompCompPrimalFixedVarIDs
Definition soplex.h:1857
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
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
DataArray< SPxColId > _decompFixedVarDualIDs
Definition soplex.h:1852
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:1342
@ POLISHING_OFF
no solution polishing
Definition soplex.h:1336
@ POLISHING_INTEGRALITY
maximize number of basic slack variables, i.e. more variables on bounds
Definition soplex.h:1339
Array< UnitVectorRational * > _unitMatrixRational
Definition soplex.h:1732
DataArray< SPxRowId > _decompReducedProbRowIDs
Definition soplex.h:1839
@ RATIOTESTER_TEXTBOOK
textbook ratio test without stabilization
Definition soplex.h:1245
@ RATIOTESTER_FAST
modified Harris ratio test
Definition soplex.h:1251
@ RATIOTESTER_HARRIS
standard Harris ratio test
Definition soplex.h:1248
@ RATIOTESTER_BOUNDFLIPPING
bound flipping ratio test for long steps in the dual simplex
Definition soplex.h:1254
VectorBase< R > _manualUpper
Definition soplex.h:1697
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...
int numNonzeros() const
returns number of nonzeros
SPxLPBase< R > * _decompLP
Definition soplex.h:1686
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...
R getCompSlackVarCoeff(int primalRowNum)
gets the coefficient of the slack variable in the primal complementary problem
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:1669
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 printVersion() const
prints version and compilation options
decompStatus _currentProb
Definition soplex.h:1911
Statistics * _statistics
statistics since last call to solveReal() or solveRational()
Definition soplex.h:1638
SPxSolverBase< R > _solver
Definition soplex.h:1660
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:1323
@ HYPER_PRICING_ON
always
Definition soplex.h:1329
@ HYPER_PRICING_AUTO
decide according to problem size
Definition soplex.h:1326
void getColVectorReal(int i, DSVectorBase< R > &col) const
gets vector of col i
int * _decompViolatedRows
Definition soplex.h:1869
bool hasDualFarkas() const
is Farkas proof of infeasibility available?
SPxLPRational * _rationalLP
Definition soplex.h:1709
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:1723
void getColsRational(int start, int end, LPColSetRational &lpcolset) const
gets columns start, ..., end
@ READMODE_REAL
standard floating-point parsing
Definition soplex.h:1274
@ READMODE_RATIONAL
rational parsing
Definition soplex.h:1277
@ FACTOR_UPDATE_TYPE_ETA
product form update
Definition soplex.h:1134
@ FACTOR_UPDATE_TYPE_FT
Forrest-Tomlin type update.
Definition soplex.h:1137
bool setSettings(const Settings &newSettings, const bool init=true)
sets parameter settings; returns true on success
void _decompResolveWithoutPreprocessing(SPxSolverBase< R > &solver, SLUFactor< R > &sluFactor, typename SPxSimplifier< R >::Result result)
loads original problem into solver and solves again after it has been solved to optimality with prepr...
void _decompSimplifyAndSolve(SPxSolverBase< R > &solver, SLUFactor< R > &sluFactor, bool fromScratch, bool applyPreprocessing)
simplifies the problem and solves
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:1232
@ PRICER_STEEP
steepest edge pricer with exact initialization of norms
Definition soplex.h:1238
@ PRICER_QUICKSTEEP
steepest edge pricer with initialization to unit norms
Definition soplex.h:1235
@ PRICER_PARMULT
partial multiple pricer based on Dantzig pricing
Definition soplex.h:1229
@ PRICER_AUTO
automatic pricer
Definition soplex.h:1223
@ PRICER_DANTZIG
Dantzig pricer.
Definition soplex.h:1226
void _addColsReal(const LPColSetReal &lpcolset)
adds multiple columns to the real LP and adjusts basis
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:1687
void printOriginalProblemStatistics(std::ostream &os)
stores the problem statistics of the original problem
void getRowVectorReal(int i, DSVectorBase< R > &row) const
gets vector of row i
SLUFactor< R > _compSlufactor
Definition soplex.h:1822
void changeLhsReal(int i, const R &lhs)
changes left-hand side of row i to lhs
LPRowSetBase< R > _transformedRows
Definition soplex.h:1830
void removeRowsRational(int perm[])
removes all rows with an index i such that perm[i] < 0; upon completion, perm[i] >= 0 indicates the n...
void getOriginalProblemBasisRowStatus(DataArray< int > &degenerateRowNums, DataArray< typename SPxSolverBase< R >::VarStatus > &degenerateRowStatus, int &nDegenerateRows, int &nNonBasicRows)
function to retrieve the original problem row basis status from the reduced and complementary problem...
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:1290
@ SOLVEMODE_REAL
apply standard floating-point algorithm
Definition soplex.h:1284
@ SOLVEMODE_AUTO
decide depending on tolerances whether to apply iterative refinement
Definition soplex.h:1287
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
int * _decompColStatus
Definition soplex.h:1836
SPxFastRT< R > _ratiotesterFast
Definition soplex.h:1681
void _optimizeRational(volatile bool *interrupt=NULL)
temporary fix for Rational
Rational _rationalFeastol
Definition soplex.h:1650
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:1689
void _restoreBasis()
restore basis
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:1688
void _untransformUnbounded(SolRational &sol, bool unbounded)
undoes transformation to unboundedness problem
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< SPxRowId > _decompDualRowIDs
Definition soplex.h:1849
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
void _deleteAndUpdateRowsComplementaryProblem(SPxRowId rangedRowIds[], int &naddedrows)
removing rows from the complementary problem.
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:1662
bool getDualViolationRational(Rational &maxviol, Rational &sumviol)
@ VERBOSITY_HIGH
high verbosity level
Definition soplex.h:1156
@ VERBOSITY_WARNING
only error and warning output
Definition soplex.h:1147
@ VERBOSITY_DEBUG
only error, warning, and debug output
Definition soplex.h:1150
@ VERBOSITY_NORMAL
standard verbosity level
Definition soplex.h:1153
@ VERBOSITY_ERROR
only error output
Definition soplex.h:1144
@ VERBOSITY_FULL
full verbosity level
Definition soplex.h:1159
void _addRowsReal(const LPRowSetBase< R > &lprowset)
adds multiple rows to the real LP and adjusts basis
SPxSolverBase< R >::Status solve(volatile bool *interrupt=NULL)
Definition soplex.h:606
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)
void _updateDecompReducedProblem(R objVal, VectorBase< R > dualVector, VectorBase< R > redcostVector, VectorBase< R > compPrimalVector, VectorBase< R > compDualVector)
update the reduced problem with additional columns and rows
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:1111
@ REPRESENTATION_COLUMN
column representation Ax - s = 0, lower <= x <= upper, lhs <= s <= rhs
Definition soplex.h:1114
@ REPRESENTATION_ROW
row representation (lower,lhs) <= (x,Ax) <= (upper,rhs)
Definition soplex.h:1117
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:1668
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:1726
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
int * _decompRowStatus
Definition soplex.h:1835
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
Rational _rationalMaxscaleincr
Definition soplex.h:1652
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
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)
DataArray< SPxRowId > _decompReducedProbColRowIDs
Definition soplex.h:1841
bool getPrimalRational(mpq_t *vector, const int size)
gets the primal solution vector if available; returns true on success (GMP only method)
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
bool getPrimalRay(VectorBase< R > &vector)
gets the primal ray if available; returns true on success
SPxHarrisRT< R > _ratiotesterHarris
Definition soplex.h:1680
DualSign getOrigProbDualVariableSign(int rowNumber)
returns the expected sign of the dual variables for the original problem
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...
R rhsReal(int i) const
returns right-hand side of row i
DataArray< SPxColId > _decompPrimalColIDs
Definition soplex.h:1845
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)?
LPColSetRational _slackCols
Definition soplex.h:1713
void _getCompatibleColumns(VectorBase< R > feasVector, int *nonposind, int *compatind, int *rowsforremoval, int *colsforremoval, int nnonposind, int *ncompatind, bool formRedProb, bool &stop)
retrieves the compatible columns from the constraint matrix
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
void _updateComplementaryDualFixedPrimalVars(int *currFixedVars)
updating the dual columns related to the fixed primal variables.
BoolParam
boolean parameters
Definition soplex.h:943
@ TESTDUALINF
should dual infeasibility be tested in order to try to return a dual solution even if primal infeasib...
Definition soplex.h:951
@ FORCEBASIC
try to enforce that the optimal solution is a basic solutiong
Definition soplex.h:994
@ ENSURERAY
re-optimize the original problem to get a proof (ray) of infeasibility/unboundedness?
Definition soplex.h:991
@ ACCEPTCYCLING
should cycling solutions be accepted during iterative refinement?
Definition soplex.h:970
@ RATREC
apply rational reconstruction after each iterative refinement?
Definition soplex.h:973
@ RATFAC
should a rational factorization be performed after iterative refinement?
Definition soplex.h:954
@ USECOMPDUAL
should the dual of the complementary problem be used in the decomposition simplex?
Definition soplex.h:964
@ COMPUTEDEGEN
should the degeneracy be computed for each basis?
Definition soplex.h:961
@ LIFTING
should lifting be used to reduce range of nonzero matrix coefficients?
Definition soplex.h:945
@ EQTRANS
should LP be transformed to equality form before a rational solve?
Definition soplex.h:948
@ FULLPERTURBATION
perturb the entire problem or only the relevant bounds of s single pivot?
Definition soplex.h:988
@ USEDECOMPDUALSIMPLEX
should the decomposition based dual simplex be used to solve the LP? Setting this to true forces the ...
Definition soplex.h:958
@ POWERSCALING
round scaling factors for iterative refinement to powers of two?
Definition soplex.h:976
@ BOOLPARAM_COUNT
number of boolean parameters
Definition soplex.h:997
@ PERSISTENTSCALING
use persistent scaling?
Definition soplex.h:985
@ ROWBOUNDFLIPS
use bound flipping also for row representation?
Definition soplex.h:982
@ RATFACJUMP
continue iterative refinement with exact basic solution if not optimal?
Definition soplex.h:979
@ EXPLICITVIOL
should row and bound violations be computed explicitly in the update of reduced problem in the decomp...
Definition soplex.h:967
RangeType
type of bounds and sides
Definition soplex.h:1739
@ RANGETYPE_UPPER
upper bound is finite, lower bound is infinite
Definition soplex.h:1747
@ RANGETYPE_FIXED
lower bound equals upper bound
Definition soplex.h:1753
@ RANGETYPE_BOXED
lower and upper bound finite, but different
Definition soplex.h:1750
@ RANGETYPE_LOWER
lower bound is finite, upper bound is infinite
Definition soplex.h:1744
@ RANGETYPE_FREE
both bounds are infinite
Definition soplex.h:1741
void _formDecompReducedProblem(bool &stop)
forms the reduced problem
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:1648
void _checkBasisScaling()
check correctness of (un)scaled basis matrix operations
void printDecompDisplayLine(SPxSolverBase< R > &solver, const SPxOut::Verbosity origVerb, bool force, bool forceHead)
prints a display line of the flying table for the DBDS
RangeType _rangeTypeRational(const Rational &lower, const Rational &upper) const
determines RangeType from rational bounds
SPxEquiliSC< R > _scalerUniequi
Definition soplex.h:1664
void getRhsReal(VectorBase< R > &rhs) const
gets right-hand side vector
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)
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:266
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.
R operator()(RowViolation i, RowViolation j) const
Definition soplex.h:1787
std::string name[SoPlexBase< R >::BOOLPARAM_COUNT]
array of names for boolean parameters
Definition soplex.h:1448
std::string description[SoPlexBase< R >::BOOLPARAM_COUNT]
array of descriptions for boolean parameters
Definition soplex.h:1450
bool defaultValue[SoPlexBase< R >::BOOLPARAM_COUNT]
array of default values for boolean parameters
Definition soplex.h:1452
std::string name[SoPlexBase< R >::INTPARAM_COUNT]
array of names for integer parameters
Definition soplex.h:1460
int lower[SoPlexBase< R >::INTPARAM_COUNT]
array of lower bounds for int parameter values
Definition soplex.h:1466
int upper[SoPlexBase< R >::INTPARAM_COUNT]
array of upper bounds for int parameter values
Definition soplex.h:1468
int defaultValue[SoPlexBase< R >::INTPARAM_COUNT]
array of default values for integer parameters
Definition soplex.h:1464
std::string description[SoPlexBase< R >::INTPARAM_COUNT]
array of descriptions for integer parameters
Definition soplex.h:1462
Real upper[SoPlexBase< R >::REALPARAM_COUNT]
array of upper bounds for real parameter values
Definition soplex.h:1484
Real defaultValue[SoPlexBase< R >::REALPARAM_COUNT]
array of default values for real parameters
Definition soplex.h:1480
Real lower[SoPlexBase< R >::REALPARAM_COUNT]
array of lower bounds for real parameter values
Definition soplex.h:1482
std::string description[SoPlexBase< R >::REALPARAM_COUNT]
array of descriptions for real parameters
Definition soplex.h:1478
std::string name[SoPlexBase< R >::REALPARAM_COUNT]
array of names for real parameters
Definition soplex.h:1476