49 int ninfeasibilities = 0;
52 for(
int i = 0; i <
dim(); ++i )
69 if( ninfeasibilities > sparsitythreshold )
91 (*spxout) <<
" --- using hypersparse pricing, ";
93 (*
spxout) <<
" --- using sparse pricing, ";
94 (*spxout) <<
"sparsity: " 95 << std::setw(6) << std::fixed << std::setprecision(4)
96 << (
Real) ninfeasibilities/
dim()
97 << std::scientific << std::setprecision(
int(prec))
108 assert(&ftest == &
fTest());
114 for (
int j = idx.
size() - 1; j >= 0; --j)
116 int i = idx.
index(j);
194 leaveId =
baseId(leaveIdx);
222 assert(
lhs(leaveNum) ==
rhs(leaveNum));
223 leavebound = -
rhs(leaveNum);
232 leavebound = -
rhs(leaveNum);
239 leavebound = -
lhs(leaveNum);
249 leavebound = -
lhs(leaveNum);
257 leavebound = -
rhs(leaveNum);
266 MSG_DEBUG( std::cout <<
"DLEAVE51 SPxSolver::getLeaveVals() : row " << leaveNum
269 <<
" objChange: " << objChange
314 objChange +=
maxObj(leaveNum) * leavebound;
324 objChange +=
theUCbound[leaveNum] * leavebound;
331 objChange +=
theLCbound[leaveNum] * leavebound;
340 objChange +=
theUCbound[leaveNum] * leavebound;
348 objChange +=
theLCbound[leaveNum] * leavebound;
356 MSG_DEBUG( std::cout <<
"DLEAVE52 SPxSolver::getLeaveVals() : col " << leaveNum
359 <<
" objChange: " << objChange
432 newUBbound = -
lhs(idx);
433 newLBbound = -
rhs(idx);
434 enterBound = -
rhs(idx);
435 objChange -= newCoPrhs *
rhs(idx);
443 newLBbound = -
rhs(idx);
444 newUBbound = -
lhs(idx);
445 enterBound = -
lhs(idx);
446 objChange -= newCoPrhs *
lhs(idx);
453 MSG_ERROR( std::cerr <<
"ELEAVE53 ERROR: not yet debugged!" << std::endl; )
464 <<
"ERROR! Tried to put a fixed row variable into the basis: " 466 <<
", lhs=" <<
lhs(idx)
467 <<
", rhs=" <<
rhs(idx) << std::endl; )
473 MSG_DEBUG( std::cout <<
"DLEAVE55 SPxSolver::getLeaveVals2(): row " << idx
476 <<
" objChange: " << objChange
536 objChange -= newCoPrhs * enterBound;
547 objChange -= newCoPrhs * enterBound;
563 <<
"ERROR! Tried to put a fixed column variable into the basis. " 565 <<
", lower=" <<
lower(idx)
566 <<
", upper=" <<
upper(idx) << std::endl; )
572 MSG_DEBUG( std::cout <<
"DLEAVE57 SPxSolver::getLeaveVals2(): col " << idx
575 <<
" objChange: " << objChange
591 MSG_DEBUG( std::cout <<
"DLEAVE58 rejectLeave() : row " << leaveNum
593 <<
" -> " << leaveStat << std::endl; )
606 MSG_DEBUG( std::cout <<
"DLEAVE59 rejectLeave() : col " << leaveNum
608 <<
" -> " << leaveStat << std::endl; )
624 Real sign = (direction > 0 ? 1.0 : -1.0);
635 Real sign = (direction > 0 ? -1.0 : 1.0);
646 assert(leaveIdx <
dim() && leaveIdx >= 0);
662 #ifdef ENABLE_ADDITIONAL_CHECKS 673 <<
": coPvec.delta error = " << tmp.
length()
690 Real objChange = 0.0;
692 getLeaveVals(leaveIdx, leaveStat, leaveId, leaveMax, leavebound, leaveNum, objChange);
706 Real enterVal = leaveMax;
712 MSG_DEBUG( std::cout <<
"DLEAVE71 trigger recomputation of nonbasic value due to shifts in ratiotest" << std::endl; )
737 if (
NE(enterVal, leaveMax))
739 MSG_DEBUG( std::cout <<
"DLEAVE61 rejecting leave A (leaveIdx=" << leaveIdx
740 <<
", theCoTest=" <<
theCoTest[leaveIdx] <<
")" 757 instableLeaveNum = leaveIdx;
770 <<
"leave() for feasibility test" << std::endl; )
791 MSG_INFO3( (*
spxout), (*
spxout) <<
"ILEAVE11 clean up step to reduce numerical errors" << std::endl; )
804 <<
"in leave()" << std::endl; )
824 if (enterId !=
baseId(leaveIdx))
844 MSG_DEBUG( std::cout <<
"ILBFRT02 breakpoints passed / bounds flipped = " <<
boundflips << std::endl; )
869 MSG_DEBUG( std::cout <<
"ILBFRT02 breakpoints passed / bounds flipped = " <<
boundflips << std::endl; )
875 #ifdef ENABLE_ADDITIONAL_CHECKS 898 <<
"in leave()" << std::endl; )
921 rejectLeave(leaveNum, leaveId, leaveStat, &newVector);
925 MSG_DEBUG( std::cout <<
"DLEAVE63 rejecting leave B (leaveIdx=" << leaveIdx
927 <<
")" << std::endl; )
948 getLeaveVals2(leaveMax, enterId, enterBound, newUBbound, newLBbound, newCoPrhs, objChange);
960 (*theCoPrhs)[leaveIdx] = newCoPrhs;
999 change(leaveIdx, none, 0);
1006 (*theCoPrhs)[leaveIdx] =
theLRbound[leaveNum];
1011 (*theCoPrhs)[leaveIdx] =
theLCbound[leaveNum];
1022 (*theCoPrhs)[leaveIdx] =
theURbound[leaveNum];
1027 (*theCoPrhs)[leaveIdx] =
theUCbound[leaveNum];
1059 #ifdef ENABLE_ADDITIONAL_CHECKS 1069 <<
": fVec error = " << tmp.
length() << std::endl; )
const VectorBase< R > & rhs() const
Returns right hand side vector.
void computeFtest()
compute basis feasibility test vector.
Rational spxAbs(const Rational &r)
Absolute.
int iteration() const
returns number of basis changes since last load().
Exception class for things that should NEVER happen.This class is derived from the SoPlex exception b...
bool isSetup() const
Returns setup status.
virtual void rejectLeave(int leaveNum, SPxId leaveId, SPxBasis::Desc::Status leaveStat, const SVector *newVec=0)
void coSolve(Vector &x, const Vector &rhs)
Cosolves linear system with basis matrix.
primal variable is fixed to both bounds
UpdateVector primVec
primal vector
int boundflips
number of performed bound flips
const VectorBase< Real > & upper() const
Returns upper bound vector.
const Vector & fTest() const
Violations of fVec.
Desc::Status dualColStatus(int i) const
dual Status for the i'th column variable of the loaded LP.
DIdxSet updateViols
store indices that were changed in the previous iteration and must be checked in hyper pricing ...
SPxOut * spxout
message handler
bool sparsePricingLeave
These values enable or disable sparse pricing.
THREADLOCAL const Real infinity
bool leave(int i, bool polish=false)
Abstract pricer base class.
Real leavetol() const
feasibility tolerance maintained by ratio test during LEAVE algorithm.
SSVector * solveVector3
when 3 systems are to be solved at a time; typically reserved for bound flipping ratio test (basic so...
void updateFtest()
update basis feasibility test vector.
void computePrimalray4Row(Real direction)
Exception classes for SoPlex.
Status & rowStatus(int i)
Abstract ratio test base class.
virtual void perturbMaxLeave(void)
perturb nonbasic bounds.
int m_maxCycle
maximum steps before cycling is detected.
DataArray< int > isInfeasible
0: index not violated, 1: index violated, 2: index violated and among candidate list ...
bool NE(Real a, Real b, Real eps=Param::epsilon())
returns true iff |a-b| > eps
Real length() const
Floating point approximation of euclidian norm (without any approximation guarantee).
int number(const SPxRowId &id) const
Returns the row number of the row with identifier id.
void clear()
removes all indices.
int lastUpdate() const
returns number of basis changes since last refactorization.
int dim() const
dimension of basis matrix.
Vector & multBaseWith(Vector &x) const
Basis-vector product.
virtual SPxId selectEnter(Real &val, int leaveIdx, bool polish=false)=0
selects variable Id to enter the basis.
Real sparsePricingFactor
enable sparse pricing when viols < factor * dim()
SSVector * solveVector2rhs
when 2 systems are to be solved at a time; typically for speepest edge weights
Ids for LP columns.Class SPxColId provides DataKeys for the column indices of an SPxLP.
int sign(const Rational &r)
Sign function; returns 1 if r > 0, 0 if r = 0, and -1 if r < 0.
virtual void doPupdate(void)
virtual Real value()
current objective value.
Desc::Status dualRowStatus(int i) const
dual Status for the i'th row variable of the loaded LP.
virtual const std::string what() const
returns exception message
dual variable is left free, but unset
Wrapper for different output streams and verbosity levels.
void add(const SVectorBase< S > &vec)
Append nonzeros of sv.
const Vector & fRhs() const
right-hand side vector for fVec
primal variable is set to its upper bound
Generic Ids for LP rows or columns.Both SPxColIds and SPxRowIds may be treated uniformly as SPxIds: ...
UpdateVector & coPvec() const
copricing vector.
int remainingRoundsLeave
number of dense rounds/refactorizations until sparsePricing is enabled again
int m_numCycle
actual number of degenerate steps so far.
SPxStatus status() const
returns current SPxStatus.
SSVector * solveVector3rhs
when 3 systems are to be solved at a time; typically reserved for bound flipping ratio test (basic so...
const SVector & baseVec(int i) const
returns the i'th basic vector.
bool m_pricingViolCoUpToDate
true, if the stored violation in coDim is up to date
virtual const SVector * enterVector(const SPxId &p_id)
Get pointer to the id 'th vector.
Real m_pricingViol
maximal feasibility violation of current solution
Real entertol() const
feasibility tolerance maintained by ratio test during ENTER algorithm.
void update()
Perform the update.
int size() const
returns the number of used indices.
#define MSG_INFO2(spxout, x)
Prints out message x if the verbosity level is at least SPxOut::INFO2.
#define MSG_ERROR(x)
Prints out message x if the verbosity level is at least SPxOut::ERROR.
int size() const
Returns number of elements.
UpdateVector & fVec() const
feasibility vector.
bool isSPxColId() const
is id a column id?
dual variable is set to its upper bound
DVector theLBbound
Lower Basic Feasibility bound.
virtual void setupPupdate(void)
void addIdx(int i)
adds index i to the index set
bool isBasic(SPxBasis::Desc::Status stat) const
does stat describe a basic index ?
Real delta() const
guaranteed primal and dual bound violation for optimal solution, returning the maximum of feastol() a...
primal variable is left free, but unset
const VectorBase< R > & lhs() const
Returns left hand side vector.
void clear()
Clears vector.
bool updateNonbasicValue(Real objChange)
DVector theURbound
Upper Row Feasibility bound.
bool isConsistent() const
consistency check.
virtual void getLeaveVals2(Real leaveMax, SPxId enterId, Real &enterBound, Real &newUBbound, Real &newLBbound, Real &newCoPrhs, Real &objChange)
int leaveCycles
the number of degenerate steps during the leaving algorithm
int index(int n) const
Returns index of the n 'th nonzero element.
Status & colStatus(int i)
DVector theUBbound
Upper Basic Feasibility bound.
#define MSG_INFO3(spxout, x)
Prints out message x if the verbosity level is at least SPxOut::INFO3.
virtual void change(int i, SPxId &id, const SVector *enterVec, const SSVector *eta=0)
performs basis update.
Real m_pricingViolCo
maximal feasibility violation of current solution in coDim
Real epsilon() const
values are considered to be 0.
void computeDualfarkas4Col(Real direction)
Debugging, floating point type and parameter definitions.
int totalboundflips
total number of bound flips
virtual void getLeaveVals(int i, SPxBasis::Desc::Status &leaveStat, SPxId &leaveId, Real &leaveMax, Real &leavebound, int &leaveNum, Real &objChange)
SSVector * solveVector2
when 2 systems are to be solved at a time; typically for speepest edge weights
DVector theLRbound
Lower Row Feasibility bound.
DVector theUCbound
Upper Column Feasibility bound.
static const Real reject_leave_tol
VectorBase< R > & multAdd(const S &x, const VectorBase< T > &vec)
Addition of scaled vector.
Exception base class.This class implements a base class for our SoPlex exceptions We provide a what()...
int size() const
Returns the number of nonzeros.
Everything should be within this namespace.
const IdxSet & idx() const
nonzero indices of update vector
void clear()
Remove all indices.
void solve4update(SSVector &x, const SVector &rhs)
solves linear system with basis matrix.
primal variable is set to its lower bound
const VectorBase< R > & maxObj() const
Returns objective vector for maximization problem.
std::streamsize precision() const
DVector theLCbound
Lower Column Feasibility bound.
Real & value()
update multiplicator , writeable
void computeFrhs()
compute feasibility vector from scratch.
virtual void perturbMinLeave(void)
bool isSPxRowId() const
is id a row id?
SPxRatioTester * theratiotester
bool isValid() const
returns TRUE iff the id is a valid column or row identifier.
dual variable is set to its lower bound
DSVector primalRay
stores primal ray in case of unboundedness
Type type() const
return current Type.
Real theShift
sum of all shifts applied to any bound.
Real length() const
Floating point approximation of euclidian norm (without any approximation guarantee).
bool isConsistent() const
DSVector dualFarkas
stores dual farkas proof in case of infeasibility
Array< UnitVector > unitVecs
array of unit vectors
dual variable has two bounds
bool recomputedVectors
flag to perform clean up step to reduce numerical errors only once
Exception class for status exceptions during the computationsThis class is derived from the SoPlex ex...
Ids for LP rows.Class SPxRowId provides DataKeys for the row indices of an SPxLP. ...
bool initialized
true, if all vectors are setup.
void forceRecompNonbasicValue()
void solve(Vector &x, const Vector &rhs)
SSVector & delta()
update vector , writeable
bool m_pricingViolUpToDate
true, if the stored violation is up to date
int index(int n) const
access n 'th index.
const SPxBasis & basis() const
Return current basis.
Status
Status of a variable.
LP has been proven to be primal unbounded.
bool hyperPricingLeave
true if hyper sparse pricing is turned on in the leaving Simplex
const VectorBase< Real > & lower() const
Returns (internal and possibly scaled) lower bound vector.
const Desc & desc() const
Representation rep() const
return the current basis representation.
Set of indices.Class IdxSet provides a set of indices. At construction it must be given an array of i...
columnwise representation.
R value(int n) const
Returns value of the n 'th nonzero element.
virtual void factorize()
Factorize basis matrix.
void setBasisStatus(SPxBasis::SPxStatus stat)
set the lp solver's basis status.
void setMax(int newmax=1)
Reset nonzero memory to >= newmax.
LP has been proven to be primal infeasible.