26 #define STEEP_REFINETOL 2.0 182 Real rhov_1 = 1.0 / rhoVec[n];
189 << rhoVec[n] <<
" with smaller absolute value than 0.5*theeps = " << 0.5*
theeps << std::endl; )
196 for(
int i = 0; i < len; ++i)
198 int j = rhoIdx.
index(i);
199 coWeights_ptr[j] += rhoVec[j] * (beta_q * rhoVec[j] - 2.0 * rhov_1 * workVec_ptr[j]);
201 if (coWeights_ptr[j] < delta)
202 coWeights_ptr[j] = delta;
203 else if (coWeights_ptr[j] >=
infinity)
204 coWeights_ptr[j] = 1.0 /
theeps;
206 coWeights_ptr[n] = beta_q;
213 return viol * viol / tol;
215 return viol * viol / weight;
249 for(
int i = 0; i < nsorted; ++i )
443 if (n >= 0 && n < thesolver->dim())
460 for (j = coPidx.
size() - 1; j >= 0; --j)
463 xi_ip = xi_p * coPvec[i];
464 coWeights_ptr[i] += xi_ip * (xi_ip *
pi_p - 2.0 * workVec_ptr[i]);
469 if (coWeights_ptr[i] < delta)
470 coWeights_ptr[i] = delta;
472 else if (coWeights_ptr[i] >
infinity)
476 for (j = pIdx.
size() - 1; j >= 0; --j)
479 xi_ip = xi_p * pVec[i];
485 if (weights_ptr[i] < delta)
486 weights_ptr[i] = delta;
540 for(
int i = 0; i < nsorted; ++i )
593 for(
int i = 0; i < nsorted; ++i )
977 for (i = 0; i < j; ++i)
998 for (i = 0; i < j; ++i)
1008 #ifdef ENABLE_CONSISTENCY_CHECKS 1020 MSG_ERROR( std::cerr <<
"ESTEEP03 x[" << i <<
"] = " << x << std::endl; )
Rational spxAbs(const Rational &r)
Absolute.
SPxId coId(int i) const
id of i 'th covector.
int iteration() const
returns number of basis changes since last load().
virtual SPxId selectEnter()
void reDim(int newdim, const bool setZero=true)
Resets DVectorBase's dimension to newdim.
int selectLeaveX(Real tol)
implementation of full pricing
void coSolve(Vector &x, const Vector &rhs)
Cosolves linear system with basis matrix.
SPxId selectEnterHyperCoDim(Real &best, Real feastol)
implementation of hyper sparse pricing in the entering Simplex
int buildBestPriceVectorLeave(Real feastol)
prepare data structures for hyper sparse pricing
const Vector & fTest() const
Violations of fVec.
virtual void setType(SPxSolver::Type)
set entering/leaving algorithm
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
R length2() const
Squared norm.
DIdxSet bestPrices
array of best pricing candidates
T * get_ptr()
get a C pointer to the data.
virtual void load(SPxSolver *base)
sets the solver
Real leavetol() const
feasibility tolerance maintained by ratio test during LEAVE algorithm.
Representation
LP basis representation.
bool sparsePricingEnterCo
true if sparsePricing is turned on in the entering Simplex
Real computePrice(Real viol, Real weight, Real tol)
DVector weights
vector to store pricing weights or norms
DataArray< int > isInfeasible
0: index not violated, 1: index violated, 2: index violated and among candidate list ...
DataArray< IdxElement > prices
temporary array of precomputed pricing values
starting with multipliers set to 1
void clear()
removes all indices.
int lastUpdate() const
returns number of basis changes since last refactorization.
int dim() const
dimension of basis matrix.
void setup4solve(SSVector *p_y, SSVector *p_rhs)
Setup vectors to be solved within Simplex loop.
void clear()
remove all elements.
virtual int selectLeave()
virtual void addedCoVecs(int n)
n covectors have been added to loaded LP.
SSVector workVec
working vector
bool weightsAreSetup
are the weights already set up?
const R * get_const_ptr() const
Conversion to C-style pointer.
int dim() const
Dimension of VectorBase.
Generic Ids for LP rows or columns.Both SPxColIds and SPxRowIds may be treated uniformly as SPxIds: ...
UpdateVector & coPvec() const
copricing vector.
void remove(int n, int m)
removes indices at position numbers n through m.
R * get_ptr()
Conversion to C-style pointer.
SPxId selectEnterX(Real tol)
choose the best entering index among columns and rows but prefer sparsity
const R * values() const
Returns array values.
bool refined
has a refinement step already been tried?
virtual void setRep(SPxSolver::Representation rep)
set row/column representation
virtual void entered4(SPxId id, int n)
virtual bool isConsistent() const
int size() const
returns the number of used indices.
virtual void left4(int n, SPxId id)
#define MSG_ERROR(x)
Prints out message x if the verbosity level is at least SPxOut::ERROR.
void append(const T &t)
append element t.
SPxId id(int i) const
id of i 'th vector.
UpdateVector & fVec() const
feasibility vector.
void addIdx(int i)
adds index i to the index set
const T * get_const_ptr() const
get a const C pointer to the data.
virtual void addedVecs(int n)
n vectors have been added to loaded LP.
SPxSolver * thesolver
the solver
void clear()
Clears vector.
starting with exactly computed values
DataArray< IdxElement > pricesCo
temporary array of precomputed pricing values
void setEpsilon(R eps)
Changes the non-zero epsilon, invalidating the setup. */.
bool isConsistent() const
consistency check.
bool sparsePricingEnter
true if sparsePricing is turned on in the entering Simplex for slack variables
DIdxSet bestPricesCo
array of best pricing candidates
void setup4coSolve(SSVector *p_y, SSVector *p_rhs)
Setup vectors to be cosolved within Simplex loop.
SPxId selectEnterSparseCoDim(Real &best, Real tol)
implementation of sparse pricing for the entering Simplex
const Vector & test() const
Violations of pVec.
#define MSG_INFO3(spxout, x)
Prints out message x if the verbosity level is at least SPxOut::INFO3.
Real epsilon() const
values are considered to be 0.
SPxId selectEnterHyperDim(Real &best, Real feastol)
implementation of hyper sparse pricing in the entering Simplex
void reDim(int newdim)
Resets dimension to newdim.
Debugging, floating point type and parameter definitions.
Sequential object-oriented SimPlex.SPxSolver is an LP solver class using the revised Simplex algorith...
UpdateVector & pVec() const
pricing vector.
int selectLeaveHyper(Real tol)
implementation of hyper sparse pricing in the leaving Simplex
R length2() const
Squared euclidian norm.
int dim() const
Dimension of vector.
void setup_and_assign(SSVectorBase< S > &rhs)
Sets up rhs vector, and assigns it.
Everything should be within this namespace.
void setupWeights(SPxSolver::Type type)
setup steepest edge weights
const IdxSet & idx() const
nonzero indices of update vector
void solve4update(SSVector &x, const SVector &rhs)
solves linear system with basis matrix.
int selectLeaveSparse(Real tol)
implementation of sparse pricing in the leaving Simplex
SPxId buildBestPriceVectorEnterDim(Real &best, Real feastol)
build up vector of pricing values for later use
#define SPARSITY_TRADEOFF
int SPxQuicksortPart(T *keys, COMPARATOR &compare, int start, int end, int size, int start2=0, int end2=0, bool type=true)
Generic implementation of Partial QuickSort.
Real theeps
violation bound
const Vector & coTest() const
violations of coPvec.
virtual void clear()
clear solver and preferences
bool isValid() const
returns TRUE iff the id is a valid column or row identifier.
int size() const
return nr. of elements.
Type type() const
return current Type.
DataArray< int > isInfeasibleCo
0: index not violated, 1: index violated, 2: index violated and among candidate list ...
virtual void removedVec(int i)
the i'th vector has been removed from the loaded LP.
int coDim() const
codimension.
bool hyperPricingEnter
true if hyper sparse pricing is turned on in the entering Simplex
#define MSG_INFO1(spxout, x)
Prints out message x if the verbosity level is at least SPxOut::INFO1.
virtual void removedCoVec(int i)
the i'th covector has been removed from the loaded LP.
#define MSGinconsistent(name)
const SVector & vector(int i) const
i 'th vector.
SSVector & delta()
update vector , writeable
SPxId selectEnterDenseCoDim(Real &best, Real tol)
implementation of selectEnter() in dense case
void reMax(int newMax=1, int newSize=-1)
reset maximum number of elements.
SSVector workRhs
working vector
int index(int n) const
access n 'th index.
void setMax(int newmax=1)
sets the maximum number of indices.
SPxId buildBestPriceVectorEnterCoDim(Real &best, Real feastol)
const SPxBasis & basis() const
Return current basis.
virtual void removedCoVecs(const int perm[])
n covectors have been removed from loaded LP.
DIdxSet infeasibilitiesCo
bool hyperPricingLeave
true if hyper sparse pricing is turned on in the leaving Simplex
const IdxElement * elements
SPxId selectEnterDenseDim(Real &best, Real tol)
implementation of selectEnter() in dense case (slack variables)
Set of indices.Class IdxSet provides a set of indices. At construction it must be given an array of i...
R length2() const
Squared norm.
const SVector & unitVector(int i) const
return i 'th unit vector.
SPxId selectEnterSparseDim(Real &best, Real tol)
implementation of sparse pricing for the entering Simplex (slack variables)
virtual void removedVecs(const int perm[])
n vectors have been removed from loaded LP.