75 x = (*thePvec)[i] -
lhs(i);
82 return rhs(i) - (*thePvec)[i];
89 return maxObj(i) - (*thePvec)[i];
94 x =
maxObj(i) - (*thePvec)[i];
95 return (x < 0) ? x : -x;
110 int ninfeasibilities = 0;
113 for(
int i = 0; i <
coDim(); ++i)
140 if( ninfeasibilities > sparsitythreshold)
146 ninfeasibilities = 0;
149 else if(
theTest[i] < -pricingTol )
160 (*spxout) <<
" --- using hypersparse pricing, ";
162 (*
spxout) <<
" --- using sparse pricing, ";
163 (*spxout) <<
"sparsity: " 164 << std::setw(6) << std::fixed << std::setprecision(4)
166 << std::scientific << std::setprecision(
int(prec))
235 int ninfeasibilities = 0;
239 for (i =
dim() - 1; i >= 0; --i)
263 if( ninfeasibilities > sparsitythreshold )
269 ninfeasibilities = 0;
283 (*spxout) <<
" --- using hypersparse pricing, ";
285 (*
spxout) <<
" --- using sparse pricing, ";
286 (*spxout) <<
"sparsity: " 287 << std::setw(6) << std::fixed << std::setprecision(4)
288 << (
Real) ninfeasibilities/
dim()
289 << std::scientific << std::setprecision(
int(prec))
311 for (i = idx.
size() - 1; i >= 0; --i)
313 int j = idx.
index(i);
341 else if(
theTest[j] < -pricingTol )
362 for (i = idx.
size() - 1; i >= 0; --i)
364 int j = idx.
index(i);
444 enterTest =
coTest()[enterIdx];
456 enterMax = enterLB - enterUB;
457 enterPric = (*thePvec)[enterIdx];
458 enterRO =
maxObj(enterIdx);
459 objChange -= enterVal * enterRO;
462 else if(
EQ( enterLB, enterUB ) )
472 enterMax = enterUB - enterLB;
473 enterPric = (*thePvec)[enterIdx];
474 enterRO =
maxObj(enterIdx);
475 objChange -= enterVal * enterRO;
478 else if(
EQ( enterLB, enterUB ) )
488 enterPric = (*thePvec)[enterIdx];
489 enterRO =
maxObj(enterIdx);
502 enterPric = (*theCoPvec)[enterIdx];
504 objChange -= enterRO * enterVal;
514 enterPric = (*theCoPvec)[enterIdx];
516 objChange -= enterRO * enterVal;
526 enterPric = (*theCoPvec)[enterIdx];
527 if (enterPric > enterRO)
535 enterPric = (*theCoPvec)[enterIdx];
560 MSG_DEBUG( std::cout <<
"DENTER03 SPxSolver::getEnterVals() : col " << enterIdx
563 <<
" objChange: " << objChange
584 enterTest =
coTest()[enterIdx];
596 enterMax = enterUB - enterLB;
597 enterPric = (*theCoPvec)[enterIdx];
599 objChange -= enterRO * enterVal;
602 else if(
EQ( enterLB, enterUB ) )
612 enterMax = enterLB - enterUB;
613 enterPric = (*theCoPvec)[enterIdx];
615 objChange -= enterRO * enterVal;
618 else if(
EQ( enterLB, enterUB ) )
628 MSG_ERROR( std::cerr <<
"EENTER99 ERROR: not yet debugged!" << std::endl; )
643 enterPric = (*thePvec)[enterIdx];
644 enterRO =
lhs(enterIdx);
645 objChange -= enterRO * enterVal;
655 enterPric = (*thePvec)[enterIdx];
656 enterRO =
rhs(enterIdx);
657 objChange -= enterRO * enterVal;
662 assert(
rhs(enterIdx) ==
lhs(enterIdx));
666 enterPric = (*thePvec)[enterIdx];
667 enterRO =
rhs(enterIdx);
673 enterPric = (*thePvec)[enterIdx];
674 if (enterPric >
rhs(enterIdx))
680 enterRO =
rhs(enterIdx);
689 enterRO =
lhs(enterIdx);
699 MSG_DEBUG( std::cout <<
"DENTER05 SPxSolver::getEnterVals() : row " 700 << enterIdx <<
": " << enterStat
702 <<
" objChange: " << objChange
779 MSG_ERROR( std::cerr <<
"EENTER98 ERROR: not yet debugged!" << std::endl; )
807 objChange += leavebound *
maxRowObj(leaveIdx);
814 objChange += leavebound *
maxRowObj(leaveIdx);
821 objChange += leavebound *
maxRowObj(leaveIdx);
830 objChange += leavebound *
maxRowObj(leaveIdx);
837 objChange += leavebound *
maxRowObj(leaveIdx);
845 MSG_DEBUG( std::cout <<
"DENTER06 SPxSolver::getEnterVals2(): row " 846 << idx <<
": " << leaveStat
848 <<
" objChange: " << objChange
929 objChange +=
maxObj(idx) * leavebound;
936 objChange +=
maxObj(idx) * leavebound;
943 objChange +=
maxObj(idx) * leavebound;
953 objChange +=
maxObj(idx) * leavebound;
960 objChange +=
maxObj(idx) * leavebound;
968 MSG_DEBUG( std::cout <<
"DENTER07 SPxSolver::getEnterVals2(): col " 969 << idx <<
": " << leaveStat
971 <<
" objChange: " << objChange
1019 (*theFrhs)[enterIdx] += leaveVal;
1039 int enterIdx =
number(enterId);
1042 theTest[enterIdx] = enterTest;
1055 Real sign = (direction > 0 ? 1.0 : -1.0);
1074 Real sign = (direction > 0 ? -1.0 : 1.0);
1106 Real objChange = 0.0;
1113 enterVal, enterMax, enterPric, enterStat, enterRO, objChange);
1115 if (!polish && enterTest > -
epsilon())
1120 MSG_DEBUG( std::cout <<
"DENTER08 rejecting false enter pivot" << std::endl; )
1135 #ifdef ENABLE_ADDITIONAL_CHECKS 1149 << tmp.
length() << std::endl; )
1162 Real leaveVal = -enterMax;
1203 (*theCoPvec) -= (*coSolveVector3);
1211 (*theCoPvec) -= (*coSolveVector3);
1230 MSG_DEBUG( std::cout <<
"IEBFRT02 breakpoints passed / bounds flipped = " <<
boundflips << std::endl; )
1234 (*theCoPrhs)[leaveIdx] = enterRO;
1276 (*theFvec)[leaveIdx] = enterVal - leaveVal;
1294 else if (
NE(leaveVal, -enterMax))
1314 MSG_DEBUG( std::cout <<
"DENTER09 rejecting enter pivot and looking for others" << std::endl; )
1316 rejectEnter(enterId, enterTest / 10.0, enterStat);
1321 MSG_DEBUG( std::cout <<
"DENTER10 rejecting enter pivot in instable state, resetting values" << std::endl; )
1335 else if (!polish && leaveVal < infinity && leaveVal > -
infinity)
1338 assert(leaveVal == -enterMax);
1340 change(-1, enterId, enterVec);
1345 ungetEnterVal(enterId, enterStat, leaveVal, *enterVec, objChange);
1350 MSG_DEBUG( std::cout <<
"DENTER11 moving entering variable from one bound to the other" << std::endl; )
1372 <<
"enter() for feasibility test" << std::endl; )
1395 MSG_INFO3( (*
spxout), (*
spxout) <<
"IENTER11 clean up step to reduce numerical errors" << std::endl; )
1406 <<
"enter()" << std::endl; )
const VectorBase< Real > & rhs() const
Returns right hand side vector.
Rational spxAbs(const Rational &r)
Absolute.
bool enter(SPxId &id, bool polish=false)
Exception class for things that should NEVER happen.This class is derived from the SoPlex exception b...
bool isSetup() const
Returns setup status.
void coSolve(Vector &x, const Vector &rhs)
Cosolves linear system with basis matrix.
primal variable is fixed to both bounds
int boundflips
number of performed bound flips
primal or dual variable has no status
const VectorBase< Real > & upper() const
Returns upper bound vector.
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
THREADLOCAL const Real infinity
int max() const
returns the maximal number of indices which can be stored in IdxSet.
Pricing pricing() const
return current Pricing.
virtual void rejectEnter(SPxId enterId, Real enterTest, SPxBasis::Desc::Status enterStat)
Abstract pricer base class.
Real leavetol() const
feasibility tolerance maintained by ratio test during LEAVE algorithm.
void computeTest()
compute test vector in ENTERing Simplex.
Exception classes for SoPlex.
Status & rowStatus(int i)
bool sparsePricingEnterCo
true if sparsePricing is turned on in the entering Simplex
Abstract ratio test base class.
void computePrimalray4Col(Real direction, SPxId enterId)
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.
bool isId(const SPxId &p_id) const
Is p_id an SPxId ?
virtual void perturbMinEnter(void)
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.
Real sparsePricingFactor
enable sparse pricing when viols < factor * dim()
Ids for LP columns.Class SPxColId provides DataKeys for the column indices of an SPxLP.
virtual void perturbMaxEnter(void)
perturb basis bounds.
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.
int dim() const
Dimension of VectorBase.
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: ...
int m_numCycle
actual number of degenerate steps so far.
SPxStatus status() const
returns current SPxStatus.
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
SSVector * coSolveVector3
when 3 systems are to be solved at a time; typically reserved for bound flipping ratio test (basic so...
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.
const SVSet * thecovectors
the LP coVectors according to representation
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< Real > & lhs() const
Returns left hand side vector.
SSVector * coSolveVector3rhs
when 3 systems are to be solved at a time; typically reserved for bound flipping ratio test (basic so...
bool updateNonbasicValue(Real objChange)
void updateTest()
recompute test vector.
DVector theURbound
Upper Row Feasibility bound.
virtual void ungetEnterVal(SPxId enterId, SPxBasis::Desc::Status enterStat, Real leaveVal, const SVector &vec, Real &objChange)
bool isConsistent() const
consistency check.
bool sparsePricingEnter
true if sparsePricing is turned on in the entering Simplex for slack variables
int remainingRoundsEnterCo
const VectorBase< Real > & maxRowObj() const
const Vector & test() const
Violations of pVec.
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.
Debugging, floating point type and parameter definitions.
int totalboundflips
total number of bound flips
bool EQ(Real a, Real b, Real eps=Param::epsilon())
returns true iff |a-b| <= eps
DVector theLRbound
Lower Row Feasibility bound.
DVector theUCbound
Upper Column Feasibility bound.
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.
SSVector * coSolveVector2rhs
when 2 systems are to be solved at a time; typically for speepest edge weights
void updateCoTest()
recompute coTest vector.
primal variable is set to its lower bound
const VectorBase< Real > & maxObj() const
Returns objective vector for maximization problem.
std::streamsize precision() const
void setup()
Initializes nonzero indices for elements with absolute values above epsilon and sets all other elemen...
DVector theLCbound
Lower Column Feasibility bound.
Real & value()
update multiplicator , writeable
const Vector & coTest() const
violations of coPvec.
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
int enterCycles
the number of degenerate steps during the entering algorithm
DSVector primalRay
stores primal ray in case of unboundedness
Type type() const
return current Type.
DataArray< int > isInfeasibleCo
0: index not violated, 1: index violated, 2: index violated and among candidate list ...
int coDim() const
codimension.
virtual void getEnterVals(SPxId id, Real &enterTest, Real &enterUB, Real &enterLB, Real &enterVal, Real &enterMax, Real &enterPric, SPxBasis::Desc::Status &enterStat, Real &enterRO, Real &objChange)
virtual int selectLeave(Real &val, Real enterTest, bool polish=false)=0
selects index to leave the basis.
bool hyperPricingEnter
true if hyper sparse pricing is turned on in the entering Simplex
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
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.
const SVector & vector(int i) const
i 'th vector.
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.
void computePvec()
compute entire pVec().
void computeDualfarkas4Row(Real direction, SPxId enterId)
Status
Status of a variable.
SSVector * coSolveVector2
when 2 systems are to be solved at a time; typically for speepest edge weights
LP has been proven to be primal unbounded.
DIdxSet infeasibilitiesCo
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.
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.
virtual void getEnterVals2(int leaveIdx, Real enterMax, Real &leaveBound, Real &objChange)
void computeCoTest()
compute coTest vector.