solverational.cpp
Go to the documentation of this file.
56 _solver.getBasis(_basisStatusRows.get_ptr(), _basisStatusCols.get_ptr(), _basisStatusRows.size(), _basisStatusCols.size()); 59 // store objective, bounds, and sides of real LP in case they will be modified during iterative refinement 63 if( realParam(SoPlex::OBJLIMIT_LOWER) > -realParam(SoPlex::INFTY) || realParam(SoPlex::OBJLIMIT_UPPER) < realParam(SoPlex::INFTY) ) 171 ///@todo this should be stored already earlier, possible switch use solRational above and solFeas here 315 if( _status == SPxSolver::OPTIMAL || _status == SPxSolver::INFEASIBLE || _status == SPxSolver::UNBOUNDED ) 334 // restore objective, bounds, and sides of real LP in case they have been modified during iterative refinement 337 // since the real LP is loaded in the solver, we need to also pass the basis information to the solver if 418 result = _solveRealStable(acceptUnbounded, acceptInfeasible, primalReal, dualReal, _basisStatusRows, _basisStatusCols, _hasBasis); 428 // the floating-point solve returns a Farkas ray if and only if the simplifier was not used, which is exactly 456 // store floating-point solution of original LP as current rational solution and ensure that solution vectors have 475 // it may happen that lower and upper are only equal in the real LP but different in the rational LP; we do 476 // not check this to avoid rational comparisons, but simply switch the basis status to the lower bound; this 493 // it may happen that left-hand and right-hand side are different in the rational, but equal in the real LP, 494 // leading to a fixed basis status; this is critical because rows with fixed basis status are ignored in the 495 // computation of the dual violation; to avoid rational comparisons we do not check this but simply switch to 506 // we assume that the objective function vector has less nonzeros than the reduced cost vector, and so multiplying 507 // with -1 first and subtracting the dual activity should be faster than adding the dual activity and negating 530 const int maxDimRational = numColsRational() > numRowsRational() ? numColsRational() : numRowsRational(); 610 // if the activity is feasible, but too far from the bound, this violates complementary slackness; we 633 // if the activity is feasible, but too far from the bound, this violates complementary slackness; we 652 if( ((maximizing && basisStatusCol != SPxSolver::ON_LOWER) || (!maximizing && basisStatusCol != SPxSolver::ON_UPPER)) 663 if( ((maximizing && basisStatusCol != SPxSolver::ON_UPPER) || (!maximizing && basisStatusCol != SPxSolver::ON_LOWER)) 685 if( ((maximizing && basisStatusRow != SPxSolver::ON_LOWER) || (!maximizing && basisStatusRow != SPxSolver::ON_UPPER)) 696 if( ((maximizing && basisStatusRow != SPxSolver::ON_UPPER) || (!maximizing && basisStatusRow != SPxSolver::ON_LOWER)) 710 // output violations; the reduced cost violations for artificially introduced slack columns are actually violations of the dual multipliers 724 << std::setw(10) << rationalToString(boundsViolation > sideViolation ? boundsViolation : sideViolation, 2) << " & " 725 << std::setw(10) << rationalToString(redCostViolation > dualViolation ? redCostViolation : dualViolation, 2) << "\n"); 739 MSG_INFO1( spxout, spxout << "Tolerances reached but minRounds forcing additional refinement rounds.\n" ); 766 && lastStallRefinements >= intParam(SoPlex::RATFAC_MINSTALLS) && _hasBasis && factorSolNewBasis; 786 MSG_DEBUG( spxout << "Next rational reconstruction after refinement " << nextRatrecRefinement << ".\n" ); 795 _factorizeColumnRational(sol, _basisStatusRows, _basisStatusCols, stoppedTime, stoppedIter, error, optimal); 824 // compute primal scaling factor; limit increase in scaling by tolerance used in floating point solve 938 // compute dual scaling factor; limit increase in scaling by tolerance used in floating point solve 1001 // ensure that artificial slack columns are basic and inequality constraints are nonbasic; otherwise we may end 1002 // up with dual violation on inequality constraints after removing the slack columns; do not change this in the 1003 // floating-point solver, though, because the solver may require its original basis to detect optimality 1027 MSG_DEBUG( spxout << "basis (status = " << _solver.basis().status() << ") desc before set:\n"; _solver.basis().desc().dump() ); 1029 MSG_DEBUG( spxout << "basis (status = " << _solver.basis().status() << ") desc after set:\n"; _solver.basis().desc().dump() ); 1032 MSG_DEBUG( spxout << "setting basis in solver " << (_hasBasis ? "successful" : "failed") << " (3)\n" ); 1038 result = _solveRealStable(acceptUnbounded, acceptInfeasible, primalReal, dualReal, _basisStatusRows, _basisStatusCols, _hasBasis, primalScale > 1e20 || dualScale > 1e20); 1125 // it may happen that lower and upper are only equal in the real LP but different in the rational LP; we 1126 // do not check this to avoid rational comparisons, but simply switch the basis status to the lower 1221 if( ((maximizing && basisStatusCol != SPxSolver::ON_LOWER) || (!maximizing && basisStatusCol != SPxSolver::ON_UPPER)) 1233 if( ((maximizing && basisStatusCol != SPxSolver::ON_UPPER) || (!maximizing && basisStatusCol != SPxSolver::ON_LOWER)) 1259 if( ((maximizing && basisStatusRow != SPxSolver::ON_LOWER) || (!maximizing && basisStatusRow != SPxSolver::ON_UPPER)) 1271 if( ((maximizing && basisStatusRow != SPxSolver::ON_UPPER) || (!maximizing && basisStatusRow != SPxSolver::ON_LOWER)) 1295 if( debugRedCostViolation > _solver.opttol() || debugDualViolation > _solver.opttol() || debugBasicDualViolation > 1e-9 ) 1315 // it may happen that left-hand and right-hand side are different in the rational, but equal in the real LP, 1316 // leading to a fixed basis status; this is critical because rows with fixed basis status are ignored in the 1317 // computation of the dual violation; to avoid rational comparisons we do not check this but simply switch 1343 // update or recompute reduced cost values depending on which looks faster; adding one to the length of the 1358 // we assume that the objective function vector has less nonzeros than the reduced cost vector, and so multiplying 1359 // with -1 first and subtracting the dual activity should be faster than adding the dual activity and negating 1368 MSG_INFO2( spxout, spxout << "Corrected " << numCorrectedPrimals << " primal variables and " << numCorrectedDuals << " dual values.\n" ); 1428 _performOptIRStable(sol, false, false, 0, primalFeasible, dualFeasible, infeasible, unbounded, stopped, stoppedIter, error); 1457 // because the right-hand side and all bounds (but tau's upper bound) are zero, tau should be approximately 1487 // if the problem has been found to be infeasible and an approximate Farkas proof is available, we compute a 1488 // scaled unit box around the origin that provably contains no feasible solution; this currently only works for 1507 _performOptIRStable(sol, false, false, 0, primalFeasible, dualFeasible, infeasible, unbounded, stopped, stoppedIter, error); 1527 // else we should have either a refined Farkas proof or an approximate feasible solution to the original 1571 /// reduces matrix coefficient in absolute value by the lifting procedure of Thiele et al. 2013 1610 MSG_DEBUG( std::cout << " --> nonzero " << k << " has value " << rationalToString(value) << " in row " << colVector.index(k) << "\n" ); 1630 _realLP->changeBounds(liftingColumnIndex, -realParam(SoPlex::INFTY), realParam(SoPlex::INFTY)); 1677 MSG_DEBUG( std::cout << " --> nonzero " << k << " has value " << rationalToString(value) << " in row " << colVector.index(k) << "\n" ); 1697 _realLP->changeBounds(liftingColumnIndex, -realParam(SoPlex::INFTY), realParam(SoPlex::INFTY)); 1741 MSG_INFO1( spxout, spxout << "Added " << numColsRational() - _beforeLiftCols << " columns and " 1780 ///@todo if we know the mapping between original and lifting columns, we simply need to add the reduced cost of 1781 /// the lifting column to the reduced cost of the original column; this is not implemented now, because for 1810 MSG_INFO1( spxout, spxout << "Warning: lost basis during project phase because of nonbasic lifting column.\n" ); 1819 MSG_INFO1( spxout, spxout << "Warning: lost basis during project phase because of basic lifting row.\n" ); 1878 // representable, the user might have constructed the constraint in the real LP by rounding down the 1879 // left-hand side and rounding up the right-hand side; if the basis status is fixed, we need to adjust it 1914 /// introduces slack variables to transform inequality constraints into equations for both rational and real LP, 1986 MSG_INFO1( spxout, spxout << "Added " << _slackCols.num() << " slack columns to transform rows to equality form.\n" ); 2039 assert(_basisStatusRows[row] != SPxSolver::BASIC || _basisStatusCols[col] != SPxSolver::BASIC); 2105 /// transforms LP to unboundedness problem by moving the objective function to the constraints, changing right-hand 2106 /// side and bounds to zero, and adding an auxiliary variable for the decrease in the objective function 2251 _hasBasis = (_basisStatusCols[numOrigCols] != SPxSolver::BASIC && _basisStatusRows[numOrigRows] == SPxSolver::BASIC); 2375 /// transforms LP to feasibility problem by removing the objective function, shifting variables, and homogenizing the 2414 // set objective coefficients to zero; shift primal space such as to guarantee that the zero solution is within 2617 LPColRational((intParam(SoPlex::OBJSENSE) == SoPlex::OBJSENSE_MAXIMIZE ? Rational::POSONE : Rational::NEGONE), 2727 bool shifted = (_lowerFinite(_colTypes[c]) && _feasLower[c] > 0) || (_upperFinite(_colTypes[c]) && _feasUpper[c] < 0); 2803 Given constraints of the form \f$ lhs <= Ax <= rhs \f$, a farkas proof y should satisfy \f$ y^T A = 0 \f$ and 2804 \f$ y_+^T lhs - y_-^T rhs > 0 \f$, where \f$ y_+, y_- \f$ denote the positive and negative parts of \f$ y \f$. 2805 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 2812 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 2813 bounds on \f$ x \f$ imply that all feasible \f$ x \f$ satisfy (*), and if not then compute bounds on \f$ x \f$ to 2822 \f$ B \f$ can be increased by iteratively including variable bounds smaller than \f$ B \f$. The speed of this 2823 method can be further improved by using interval arithmetic for all computations. For related information see 2845 // prepare ytransA and ytransb; since we want exact arithmetic, we set the zero threshold of the semi-sparse 2851 ///@todo this currently works only if all constraints are equations aggregate rows and sides using the multipliers of the Farkas ray 2864 // if we choose minus ytransb as vector of multipliers for the bound constraints on the variables, we obtain an 2865 // exactly feasible dual solution for the LP with zero objective function; we aggregate the bounds of the 2891 MSG_DEBUG( std::cout << "max ytransA*[x_l,x_u] = " << (isTempFinite ? rationalToString(temp) : "infinite") << "\n" ); 2893 // ytransb - temp is the increase in the dual objective along the Farkas ray; if this is positive, the dual is 2905 // if ytransb is negative, try to make it zero by including a positive lower bound or a negative upper bound 2925 // if ytransb is still zero then the zero solution is inside the bounds and cannot be cut off by the Farkas 2929 MSG_INFO1( spxout, spxout << "Approximate Farkas proof to weak. Could not compute Farkas box. (1)\n" ); 2939 // if the one norm is zero then ytransA is zero the Farkas proof should have been verified above 2942 // initialize variables in loop: size of Farkas box B, flag whether B has been increased, and number of current 2954 // if all nonzeros have been inspected once without increasing B, we abort; otherwise, we start another round 2968 // if the multiplier is positive we inspect the lower bound: if it is finite and within the Farkas box, we can 2985 MSG_INFO1( spxout, spxout << "Approximate Farkas proof to weak. Could not compute Farkas box. (2)\n" ); 3003 // if the multiplier is negative we inspect the upper bound: if it is finite and within the Farkas box, we can 3018 MSG_INFO1( spxout, spxout << "Approximate Farkas proof to weak. Could not compute Farkas box. (2)\n" ); 3039 // currently this bound cannot be used to increase B; we will check it again in the next round, because B might 3047 MSG_INFO1( spxout, spxout << "Computed Farkas box: provably no feasible solutions with components less than " 3055 SPxSolver::Status SoPlex::_solveRealForRational(bool fromscratch, VectorReal& primal, VectorReal& dual, DataArray< SPxSolver::VarStatus >& basisStatusRows, DataArray< SPxSolver::VarStatus >& basisStatusCols, bool& returnedBasis) 3098 simplificationStatus = _simplifier->simplify(_solver, realParam(SoPlex::EPSILON_ZERO), realParam(SoPlex::FPFEASTOL), realParam(SoPlex::FPOPTTOL), keepbounds); 3123 else if( simplificationStatus == SPxSimplifier::VANISHED || simplificationStatus == SPxSimplifier::OKAY ) 3125 result = simplificationStatus == SPxSimplifier::VANISHED ? SPxSolver::OPTIMAL : _solver.status(); 3132 // unsimplify if simplifier is active and LP is solved to optimality; this must be done here and not at solution 3137 assert(simplificationStatus == SPxSimplifier::VANISHED || simplificationStatus == SPxSimplifier::OKAY); 3168 _solver.getBasis(basisStatusRows.get_ptr(), basisStatusCols.get_ptr(), basisStatusRows.size(), basisStatusCols.size()); 3172 _simplifier->unsimplify(tmpPrimal, tmpDual, tmpSlacks, tmpRedCost, basisStatusRows.get_ptr(), basisStatusCols.get_ptr()); 3177 _simplifier->getBasis(basisStatusRows.get_ptr(), basisStatusCols.get_ptr(), basisStatusRows.size(), basisStatusCols.size()); 3183 // if the original problem is not in the solver because of scaling, we also need to store the basis 3199 _solver.getBasis(basisStatusRows.get_ptr(), basisStatusCols.get_ptr(), basisStatusRows.size(), basisStatusCols.size()); 3220 _solver.getBasis(basisStatusRows.get_ptr(), basisStatusCols.get_ptr(), basisStatusRows.size(), basisStatusCols.size()); 3244 // if the original problem is not in the solver because of scaling, we also need to store the basis 3247 _solver.getBasis(basisStatusRows.get_ptr(), basisStatusCols.get_ptr(), basisStatusRows.size(), basisStatusCols.size()); 3281 SPxSolver::Status SoPlex::_solveRealStable(bool acceptUnbounded, bool acceptInfeasible, VectorReal& primal, VectorReal& dual, DataArray< SPxSolver::VarStatus >& basisStatusRows, DataArray< SPxSolver::VarStatus >& basisStatusCols, bool& returnedBasis, const bool forceNoSimplifier) 3312 result = _solveRealForRational(fromScratch, primal, dual, basisStatusRows, basisStatusCols, returnedBasis); 3331 && (intParam(SoPlex::SIMPLIFIER) != SoPlex::SIMPLIFIER_OFF || intParam(SoPlex::SCALER) != SoPlex::SCALER_OFF) ) 3489 void SoPlex::_factorizeColumnRational(SolRational& sol, DataArray< SPxSolver::VarStatus >& basisStatusRows, DataArray< SPxSolver::VarStatus >& basisStatusCols, bool& stoppedTime, bool& stoppedIter, bool& error, bool& optimal) 3640 MSG_INFO2( spxout, spxout << "Rational factorization hit time limit while solving for primal.\n" ); 3718 MSG_INFO2( spxout, spxout << "Rational factorization hit time limit while solving for dual.\n" ); 3739 if( ((maximizing && basisStatusRows[i] != SPxSolver::ON_LOWER) || (!maximizing && basisStatusRows[i] != SPxSolver::ON_UPPER)) 3749 << " and [lhs,rhs] = [" << rationalToString(lhsRational(i)) << "," << rationalToString(rhsRational(i)) << "]" 3755 if( ((maximizing && basisStatusRows[i] != SPxSolver::ON_UPPER) || (!maximizing && basisStatusRows[i] != SPxSolver::ON_LOWER)) 3764 << " and [lhs,rhs] = [" << rationalToString(lhsRational(i)) << "," << rationalToString(rhsRational(i)) << "]" 3780 assert(basisStatusCols[i] != SPxSolver::BASIC || basicDual * colVectorRational(i) == objRational(i)); 3789 if( ((maximizing && basisStatusCols[i] != SPxSolver::ON_LOWER) || (!maximizing && basisStatusCols[i] != SPxSolver::ON_UPPER)) 3801 if( ((maximizing && basisStatusCols[i] != SPxSolver::ON_UPPER) || (!maximizing && basisStatusCols[i] != SPxSolver::ON_LOWER)) 3886 bool SoPlex::_reconstructSolutionRational(SolRational& sol, DataArray< SPxSolver::VarStatus >& basisStatusRows, DataArray< SPxSolver::VarStatus >& basisStatusCols, const Rational& denomBoundSquared) 3924 // we want to notify the user whether the reconstructed solution is basic; otherwise, this would be redundant 3937 MSG_DEBUG( std::cout << "Lower bound of variable " << c << " violated by " << rationalToString(lowerRational(c) - _workSol._primal[c]) << "\n" ); 3945 MSG_DEBUG( std::cout << "Upper bound of variable " << c << " violated by " << rationalToString(_workSol._primal[c] - upperRational(c)) << "\n" ); 3960 // we want to notify the user whether the reconstructed solution is basic; otherwise, this would be redundant 3973 MSG_DEBUG( std::cout << "Lhs of row " << r << " violated by " << rationalToString(lhsRational(r) - _workSol._slacks[r]) << "\n" ); 3981 MSG_DEBUG( std::cout << "Rhs of row " << r << " violated by " << rationalToString(_workSol._slacks[r] - rhsRational(r)) << "\n" ); 4002 // check dual multipliers before reduced costs because this check is faster since it does not require the 4055 // compute reduced cost vector; we assume that the objective function vector has less nonzeros than the reduced 4056 // cost vector, and so multiplying with -1 first and subtracting the dual activity should be faster than adding
virtual void subDualActivity(const VectorBase< R > &dual, VectorBase< R > &activity) const Updates "dual" activity of the columns for a given dual vector, i.e., y^T A; activity does not need t... Definition: spxlpbase.h:1727 textbook ratio test without stabilization Definition: soplex.h:1054 virtual Status getPrimal(Vector &vector) const get solution vector for primal variables. Definition: spxsolve.cpp:1219 int unbdRefinements number of refinement steps during undboundedness test Definition: statistics.h:113 Safe arrays of data objects.Class DataArray provides safe arrays of Data Objects. For general C++ obj... Definition: dataarray.h:63 bool GE(Real a, Real b, Real eps=Param::epsilon()) returns true iff a >= b + eps Definition: spxdefines.h:401 void reDim(int newdim, const bool setZero=true) Resets DVectorBase's dimension to newdim. Definition: dvectorbase.h:249 Rational & addProduct(const Rational &r, const Rational &s) add product of two rationals Definition: rational.cpp:3372 void _transformEquality() introduces slack variables to transform inequality constraints into equations for both rational and r... Definition: solverational.cpp:1916 Timer * syncTime time for synchronization between real and rational LP (included in solving time) Definition: statistics.h:92 Basis is not known to be dual nor primal feasible. Definition: spxbasis.h:94 int feasRefinements number of refinement steps during infeasibility test Definition: statistics.h:112 Implementation of Sparse Linear Solver with Rational precision.This class implements a SLinSolverRati... Definition: slufactor_rational.h:42 virtual void getBasis(SPxSolver::VarStatus[], SPxSolver::VarStatus[], const int rowsSize=-1, const int colsSize=-1) const =0 get optimal basis. virtual void unsimplify(const Vector &, const Vector &, const Vector &, const Vector &, const SPxSolver::VarStatus[], const SPxSolver::VarStatus[]) reconstructs an optimal solution for the unsimplified LP. Definition: spxsimplifier.h:189 const VectorBase< R > & maxObj() const Returns objective vector for maximization problem. Definition: spxlpbase.h:384 virtual void changeRhs(const VectorBase< R > &newRhs) Changes right hand side vector for constraints to newRhs. Definition: spxlpbase.h:1371 void _transformUnbounded() transforms LP to unboundedness problem by moving the objective function to the constraints, changing right-hand side and bounds to zero, and adding an auxiliary variable for the decrease in the objective function Definition: solverational.cpp:2107 bool setBoolParam(const BoolParam param, const bool value, const bool quiet=false, const bool init=false) sets boolean parameter value; returns true on success Definition: soplex.cpp:4896 virtual void unscaleSlacks(Vector &s) const unscale dense slack vector given in s. Definition: spxscaler.cpp:279 the problem was so much simplified that it vanished Definition: spxsimplifier.h:87 continue iterative refinement with exact basic solution if not optimal? Definition: soplex.h:833 void setBasis(const VarStatus rows[], const VarStatus cols[]) set the lp solver's basis. Definition: spxsolver.cpp:1795 virtual Result simplify(SPxLP &lp, Real eps, Real delta)=0 simplify SPxLP lp with identical primal and dual feasibility tolerance. virtual void changeObj(const VectorBase< R > &newObj) Changes objective vector to newObj. Definition: spxlpbase.h:1182 type of computational form, i.e., column or row representation Definition: soplex.h:852 virtual void removeRowRange(int start, int end, int perm[]=0) Removes rows from start to end (including both). Definition: spxlpbase.h:883 int num() const Returns the number of LPColBases currently in LPColSetBase. Definition: lpcolsetbase.h:80 SPxSolver::Status _solveRealStable(bool acceptUnbounded, bool acceptInfeasible, VectorReal &primal, VectorReal &dual, DataArray< SPxSolver::VarStatus > &basisStatusRows, DataArray< SPxSolver::VarStatus > &basisStatusCols, bool &returnedBasis, const bool forceNoSimplifier=false) solves real LP with recovery mechanism Definition: solverational.cpp:3281 virtual Status getRedCost(Vector &vector) const get vector of reduced costs. Definition: spxsolve.cpp:1299 virtual bool isUnsimplified() const specifies whether an optimal solution has already been unsimplified. Definition: spxsimplifier.h:194 const VectorRational & rhsRational() const returns right-hand side vector Definition: soplex.cpp:1084 virtual Real time() const =0 bound flipping ratio test for long steps in the dual simplex Definition: soplex.h:1063 const SVectorBase< R > & colVector(int i) const Returns column vector of column i. Definition: spxlpbase.h:341 virtual void addCols(const LPColSetBase< R > &pset) Definition: spxlpbase.h:702 virtual void changeLhs(const VectorBase< R > &newLhs) Changes left hand side vector for constraints to newLhs. Definition: spxlpbase.h:1342 void _transformFeasibility() transforms LP to feasibility problem by removing the objective function, shifting variables... Definition: solverational.cpp:2377 Abstract ratio test base class.Class SPxRatioTester is the virtual base class for computing the ratio... Definition: spxratiotester.h:40 should cycling solutions be accepted during iterative refinement? Definition: soplex.h:824 DataArray< SPxSolver::VarStatus > _storedBasisStatusCols Definition: soplex.h:1394 Implementation of Sparse Linear Solver with Rational precision. void _performFeasIRStable(SolRational &sol, bool &withDualFarkas, bool &stopped, bool &stoppedIter, bool &error) performs iterative refinement on the auxiliary problem for testing feasibility Definition: solverational.cpp:1472 virtual void changeRhs(const Vector &newRhs) Definition: changesoplex.cpp:1129 Rational & subProduct(const Rational &r, const Rational &s) subtract product of two rationals Definition: rational.cpp:3381 bool _upperFinite(const RangeType &rangeType) const checks whether RangeType corresponds to finite upper bound Definition: soplex.cpp:6450 virtual void unscaleDual(Vector &pi) const unscale dense dual solution vector given in pi. Definition: spxscaler.cpp:296 LP has been proven to be primal infeasible. Definition: spxsolver.h:208 SPxSolver::Status _solveRealForRational(bool fromscratch, VectorReal &primal, VectorReal &dual, DataArray< SPxSolver::VarStatus > &basisStatusRows, DataArray< SPxSolver::VarStatus > &basisStatusCols, bool &returnedBasis) solves real LP during iterative refinement Definition: solverational.cpp:3055 void _untransformUnbounded(SolRational &sol, bool unbounded) undoes transformation to unboundedness problem Definition: solverational.cpp:2223 bool setIntParam(const IntParam param, const int value, const bool quiet=false, const bool init=false) sets integer parameter value; returns true on success Definition: soplex.cpp:4939 Ids for LP columns.Class SPxColId provides DataKeys for the column indices of an SPxLP. Definition: spxid.h:36 minimum number of stalling refinements since last pivot to trigger rational factorization ... Definition: soplex.h:912 int sign(const Rational &r) Sign function; returns 1 if r > 0, 0 if r = 0, and -1 if r < 0. Definition: rational.cpp:3938 Wrapper for GMP type mpq_class.We wrap mpq_class so that we can replace it by a double type if GMP is... Definition: rational.h:45 virtual void changeRowObj(const Vector &newObj) Definition: changesoplex.cpp:709 should a rational factorization be performed after iterative refinement? Definition: soplex.h:821 Real opttol() const allowed optimality, i.e., dual feasibility tolerance. Definition: spxsolver.h:697 bool _isSolveStopped(bool &stoppedTime, bool &stoppedIter) const should solving process be stopped? Definition: soplex.cpp:6364 Real realParam(const RealParam param) const returns real parameter value Definition: soplex.cpp:4866 steepest edge pricer with exact initialization of norms Definition: soplex.h:1047 virtual void changeLower(const Vector &newLower) Definition: changesoplex.cpp:805 virtual void changeUpper(const VectorBase< R > &newUpper) Changes vector of upper bounds to newUpper. Definition: spxlpbase.h:1278 virtual void start()=0 start timer, resume accounting user, system and real time. const UnitVectorRational * _unitVectorRational(const int i) returns pointer to a constant unit vector available until destruction of the SoPlex class ... Definition: soplex.cpp:7376 const SPxRatioTester * ratiotester() const return loaded SPxRatioTester. Definition: spxsolver.h:1636 bool _lowerFinite(const RangeType &rangeType) const checks whether RangeType corresponds to finite lower bound Definition: soplex.cpp:6442 Rational reconstruction of solution vector. virtual void changeLower(const VectorBase< R > &newLower) Changes vector of lower bounds to newLower. Definition: spxlpbase.h:1247 virtual void changeRange(const VectorBase< R > &newLhs, const VectorBase< R > &newRhs) Changes left and right hand side vectors. Definition: spxlpbase.h:1392 DataArray< SPxSolver::VarStatus > _basisStatusCols Definition: soplex.h:1432 bool reconstructVector(VectorRational &input, const Rational &denomBoundSquared, const DIdxSet *indexSet) Definition: ratrecon.cpp:228 nothing known about basis status (possibly due to a singular basis in transformed problem) ... Definition: spxsolver.h:184 bool boolParam(const BoolParam param) const returns boolean parameter value Definition: soplex.cpp:4846 #define MSG_INFO2(spxout, x) Prints out message x if the verbosity level is at least SPxOut::INFO2. Definition: spxdefines.h:115 virtual Status getDual(Vector &vector) const get current solution vector for dual variables. Definition: spxsolve.cpp:1268 void _solveRealLPAndRecordStatistics() call floating-point solver and update statistics on iterations etc. Definition: soplex.cpp:7109 int index(int n) const Returns index of the n 'th nonzero element. Definition: ssvectorbase.h:174 lower threshold in lifting (nonzero matrix coefficients with smaller absolute value will be reformula... Definition: soplex.h:1184 Timer * rationalTime time for rational LP solving (included in solving time) Definition: statistics.h:94 void _performOptIRStable(SolRational &sol, bool acceptUnbounded, bool acceptInfeasible, int minRounds, bool &primalFeasible, bool &dualFeasible, bool &infeasible, bool &unbounded, bool &stopped, bool &stoppedIter, bool &error) solves current problem with iterative refinement and recovery mechanism Definition: solverational.cpp:353 dual simplex algorithm, i.e., leaving for column and entering for row representation ... Definition: soplex.h:948 Status getBasis(VarStatus rows[], VarStatus cols[], const int rowsSize=-1, const int colsSize=-1) const get current basis, and return solver status. Definition: spxsolver.cpp:1722 void setTimeLimit(const Real limit) set time limit on factorization Definition: slufactor_rational.h:227 void _restoreLPReal() restores objective, bounds, and sides of real LP Definition: solverational.cpp:1861 Class for collecting statistical information. void clearNum(int n) Sets n 'th nonzero element to 0 (index n must exist). Definition: ssvectorbase.h:258 void _performUnboundedIRStable(SolRational &sol, bool &hasUnboundedRay, bool &stopped, bool &stoppedIter, bool &error) performs iterative refinement on the auxiliary problem for testing unboundedness Definition: solverational.cpp:1406 round scaling factors for iterative refinement to powers of two? Definition: soplex.h:830 void _computeInfeasBox(SolRational &sol, bool transformed) Definition: solverational.cpp:2828 Statistics * _statistics statistics since last call to solveReal() or solveRational() Definition: soplex.h:1308 virtual void changeLhs(const Vector &newLhs) Definition: changesoplex.cpp:1026 RangeType _switchRangeType(const RangeType &rangeType) const switches RANGETYPE_LOWER to RANGETYPE_UPPER and vice versa Definition: soplex.cpp:6429 void solveRight(VectorRational &x, const VectorRational &b) Solves . Definition: slufactor_rational.cpp:42 #define MSG_ERROR(x) Prints out message x if the verbosity level is at least SPxOut::ERROR. Definition: spxdefines.h:109 Abstract pricer base class.Class SPxPricer is a pure virtual class defining the interface for pricer ... Definition: spxpricer.h:46 bool _reconstructSolutionRational(SolRational &sol, DataArray< SPxSolver::VarStatus > &basisStatusRows, DataArray< SPxSolver::VarStatus > &basisStatusCols, const Rational &denomBoundSquared) attempts rational reconstruction of primal-dual solution Definition: solverational.cpp:3886 virtual void unscalePrimal(Vector &x) const unscale dense primal solution vector given in x. Definition: spxscaler.cpp:262 void setEpsilon(R eps) Changes the non-zero epsilon, invalidating the setup. */. Definition: ssvectorbase.h:110 Dynamic index set.Class DIdxSet provides dynamic IdxSet in the sense, that no restrictions are posed ... Definition: didxset.h:42 #define MSG_INFO1(spxout, x) Prints out message x if the verbosity level is at least SPxOut::INFO1. Definition: spxdefines.h:113 Real luSolveTimeRational time for solving linear systems in rational precision Definition: statistics.h:100 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 ... Definition: soplex.cpp:6301 Status load(const SVectorRational *vec[], int dim) Definition: slufactor_rational.cpp:928 virtual void changeBounds(const VectorBase< R > &newLower, const VectorBase< R > &newUpper) Changes variable bounds to newLower and newUpper. Definition: spxlpbase.h:1309 virtual const Vector & unsimplifiedPrimal()=0 returns a reference to the unsimplified primal solution. Preconfigured SoPlex LP solver. const SVectorRational & colVectorRational(int i) const returns vector of column i Definition: soplex.cpp:1147 virtual void unscaleRedCost(Vector &r) const unscale dense reduced cost vector given in r. Definition: spxscaler.cpp:313 lower and upper bound finite, but different Definition: soplex.h:1413 int luFactorizationsRational number of basis matrix factorizations in rational precision Definition: statistics.h:107 void _storeLPReal() stores objective, bounds, and sides of real LP Definition: solverational.cpp:1840 VectorBase< R > & multAdd(const S &x, const VectorBase< T > &vec) Addition of scaled vector. Definition: vectorbase.h:369 column representation Ax - s = 0, lower <= x <= upper, lhs <= s <= rhs Definition: soplex.h:935 Everything should be within this namespace. working tolerance for feasibility in floating-point solver during iterative refinement ... Definition: soplex.h:1175 apply rational reconstruction after each iterative refinement? Definition: soplex.h:827 solve() aborted due to detection of cycling. Definition: spxsolver.h:197 Saving LPs in a form suitable for SoPlex.Class SPxLPBase provides the data structures required for sa... Definition: spxlpbase.h:76 working tolerance for optimality in floating-point solver during iterative refinement ... Definition: soplex.h:1178 #define MSG_WARNING(spxout, x) Prints out message x if the verbosity level is at least SPxOut::WARNING. Definition: spxdefines.h:111 void setup() Initializes nonzero indices for elements with absolute values above epsilon and sets all other elemen... Definition: ssvectorbase.h:132 virtual Status getSlacks(Vector &vector) const get vector of slack variables. Definition: spxsolve.cpp:1378 const VectorRational & lhsRational() const returns left-hand side vector Definition: soplex.cpp:1102 DataArray< SPxSolver::VarStatus > _basisStatusRows Definition: soplex.h:1431 virtual void changeElement(int i, int j, const R &val) Changes LP element (i, j) to val. Definition: spxlpbase.h:1532 virtual void changeMaxObj(const VectorBase< R > &newObj) Changes objective vector to newObj. Definition: spxlpbase.h:1218 virtual const Vector & unsimplifiedDual()=0 returns a reference to the unsimplified dual solution. should dual infeasibility be tested in order to try to return a dual solution even if primal infeasib... Definition: soplex.h:818 void _factorizeColumnRational(SolRational &sol, DataArray< SPxSolver::VarStatus > &basisStatusRows, DataArray< SPxSolver::VarStatus > &basisStatusCols, bool &stoppedTime, bool &stoppedIter, bool &error, bool &optimal) factorizes rational basis matrix in column representation Definition: solverational.cpp:3489 int intParam(const IntParam param) const returns integer parameter value Definition: soplex.cpp:4856 should lifting be used to reduce range of nonzero matrix coefficients? Definition: soplex.h:812 virtual void removeColRange(int start, int end, int perm[]=0) Removes columns from start to end (including both). Definition: spxlpbase.h:980 const SVectorBase< R > & rowVector(int i) const Gets row vector of row i. Definition: spxlpbase.h:212 virtual Status getDualfarkas(Vector &vector) const get dual farkas proof of infeasibility. Definition: spxsolve.cpp:1360 virtual void addPrimalActivity(const SVectorBase< R > &primal, VectorBase< R > &activity) const Updates activity of the rows for a given primal vector; activity does not need to be zero... Definition: spxlpbase.h:1655 Timer * transformTime time for transforming LPs (included in solving time) Definition: statistics.h:93 std::string rationalToString(const Rational &r, const int precision) convert rational number to string Definition: rational.cpp:3468 virtual void addDualActivity(const SVectorBase< R > &dual, VectorBase< R > &activity) const Updates "dual" activity of the columns for a given dual vector, i.e., y^T A; activity does not need t... Definition: spxlpbase.h:1709 geometric frequency at which to apply rational reconstruction Definition: soplex.h:1196 #define MSG_INFO3(spxout, x) Prints out message x if the verbosity level is at least SPxOut::INFO3. Definition: spxdefines.h:117 void _enableSimplifierAndScaler() enables simplifier and scaler according to current parameters Definition: soplex.cpp:7017 primal simplex algorithm, i.e., entering for column and leaving for row representation ... Definition: soplex.h:945 should LP be transformed to equality form before a rational solve? Definition: soplex.h:815 virtual void setTerminationValue(Real value=infinity) set objective limit. Definition: spxsolver.cpp:1542 void solveLeft(VectorRational &x, const VectorRational &b) Solves . Definition: slufactor_rational.cpp:209 virtual void writeFile(const char *filename, const NameSet *rowNames=0, const NameSet *colNames=0, const DIdxSet *p_intvars=0) const Write loaded LP to filename. Definition: spxlpbase.h:1080 upper threshold in lifting (nonzero matrix coefficients with larger absolute value will be reformulat... Definition: soplex.h:1187 DataArray< SPxSolver::VarStatus > _storedBasisStatusRows Definition: soplex.h:1393 Real luFactorizationTimeRational time for factorizing bases matrices in rational precision Definition: statistics.h:99 void _lift() reduces matrix coefficient in absolute value by the lifting procedure of Thiele et al... Definition: solverational.cpp:1572 virtual void computePrimalActivity(const VectorBase< R > &primal, VectorBase< R > &activity) const Computes activity of the rows for a given primal vector; activity does not need to be zero... Definition: spxlpbase.h:1619 int rationalReconstructions number of rational reconstructions performed Definition: statistics.h:108 void _untransformEquality(SolRational &sol) undoes transformation to equality form Definition: solverational.cpp:1993 int pivotRefinements number of refinement steps until final basis is reached Definition: statistics.h:111 const SVectorBase< R > & colVector(int i) const Returns colVector of i 'th LPColBase in LPColSetBase. Definition: lpcolsetbase.h:206 upper bound is finite, lower bound is infinite Definition: soplex.h:1410 virtual void changeUpper(const Vector &newUpper) Definition: changesoplex.cpp:910 dual infeasibility was detected Definition: spxsimplifier.h:85 void _untransformFeasibility(SolRational &sol, bool infeasible) undoes transformation to feasibility problem Definition: solverational.cpp:2640 void setDelta(Real d) set parameter delta, i.e., set feastol and opttol to same value. Definition: spxsolver.cpp:928 virtual void changeObj(const Vector &newObj) Definition: changesoplex.cpp:660 |