45 #define DELTA_SHIFT 1e-5 128 const int* last = idx + update.
delta().
size();
129 for (idx += start; idx < last; idx += incr)
142 mabs = (x > mabs) ? x : mabs;
162 mabs = (-x > mabs) ? -x : mabs;
186 const Real* uend = uval + update.
dim();
187 assert( uval == upd );
189 for (i = 0; uval < uend; ++uval, ++i)
208 mabs = (x > mabs) ? x : mabs;
227 mabs = (-x > mabs) ? -x : mabs;
283 const int* last = idx + update.
delta().
size();
284 for (idx += start; idx < last; idx += incr)
296 mabs = (x > mabs) ? x : mabs;
316 mabs = (-x > mabs) ? -x : mabs;
340 const Real* uend = uval + update.
dim();
341 assert( uval == upd );
343 for (i = 0; uval < uend; ++uval, ++i)
363 mabs = (x > mabs) ? x : mabs;
382 mabs = (-x > mabs) ? -x : mabs;
465 const int indc =
minDelta(max, maxabs,
468 const int indp =
minDelta(max, maxabs,
509 const int* last = idx + update.
delta().
size();
514 for (idx += start; idx < last; idx += incr)
525 y = (low[i] - vec[i]) / x;
541 y = (up[i] - vec[i]) / x;
556 if (nr < 0 && bestNr > 0)
559 bestDelta = up[bestNr] - vec[bestNr];
561 bestDelta = vec[bestNr] - low[bestNr];
588 const int* last = idx + update.
delta().
size();
593 for (idx += start; idx < last; idx += incr)
604 y = (up[i] - vec[i]) / x;
619 y = (low[i] - vec[i]) / x;
634 if (nr < 0 && bestNr > 0)
637 bestDelta = up[bestNr] - vec[bestNr];
639 bestDelta = vec[bestNr] - low[bestNr];
655 return maxSelect(val, stab, best, bestDelta, max,
671 indc =
maxSelect(val, stab, best, bestDelta, max,
674 indp =
maxSelect(val, stab, best, bestDelta, max,
700 return minSelect(val, stab, best, bestDelta, max,
714 int indc =
minSelect(val, stab, best, bestDelta, max,
717 int indp =
minSelect(val, stab, best, bestDelta, max,
742 if (sel > maxabs*
SHORT)
748 if (sel < -maxabs*SHORT)
764 if (sel > maxabs*
SHORT)
770 if ( sel < -maxabs*SHORT)
788 if (up[leave] > low[leave])
828 if (up[leave] > low[leave])
861 Real maxabs, max, sel;
870 assert(!instable ||
solver()->instableEnterId.isValid());
886 if( max == val || leave == -1 )
888 assert(max == val && leave == -1);
895 Real stab, bestDelta;
901 leave =
maxSelect(sel, lowstab, bestDelta, max);
903 leave =
maxSelect(sel, stab, bestDelta, max);
927 if( max == val || leave == -1 )
929 assert(max == val && leave == -1);
936 Real stab, bestDelta;
942 leave =
minSelect(sel, lowstab, bestDelta, max);
944 leave =
minSelect(sel, stab, bestDelta, max);
970 << std::setprecision(4) << sel <<
" " 972 << std::setprecision(6) << maxabs
976 <<
": skipping instable pivot" << std::endl;
979 if( polish && leave >= 0 )
987 if( leaveId.isSPxRowId() )
1055 sel = (lcb[nr] - cvec[nr]) / d;
1057 sel = (ucb[nr] - cvec[nr]) / d;
1074 sel = (lpb[nr] - pvec[nr]) / d;
1076 sel = (upb[nr] - pvec[nr]) / d;
1081 if ((*up)[nr] != (*low)[nr])
1114 (*up)[nr] = (*low)[nr] = x;
1179 if ((*up)[nr] != (*low)[nr])
1212 (*up)[nr] = (*low)[nr] = x;
1220 const SPxId& enterId,
1230 if (x < maxabs *
SHORT && -x < maxabs *
SHORT)
1240 if (x < maxabs *
SHORT && -x < maxabs *
SHORT)
1262 assert(!instable ||
solver()->instableLeaveNum >= 0);
1274 enterId =
maxDelta(nr, max, maxabs);
1283 Real bestDelta, stab;
1290 enterId =
maxSelect(nr, sel, lowstab, bestDelta, max);
1294 enterId =
maxSelect(nr, sel, stab, bestDelta, max);
1301 if (!
maxReEnter(sel, maxabs, enterId, nr, polish))
1305 while (cnt <
TRIES);
1313 enterId =
minDelta(nr, max, maxabs);
1322 Real bestDelta, stab;
1329 enterId =
minSelect(nr, sel, lowstab, bestDelta, max);
1333 enterId =
minSelect(nr, sel, stab, bestDelta, max);
1340 if (!
minReEnter(sel, maxabs, enterId, nr, polish))
1344 while (cnt <
TRIES);
1358 << sel <<
'\t' << x <<
" (" << maxabs <<
")" << std::endl;
1362 <<
": skipping instable pivot" << std::endl;
1365 if( polish && enterId.
isValid() )
Fast shifting ratio test.
SPxId coId(int i) const
id of i 'th covector.
const Vector & ucBound() const
int iteration() const
returns number of basis changes since last load().
bool isSetup() const
Returns setup status.
primal variable is fixed to both bounds
bool maxReEnter(Real &sel, Real maxabs, const SPxId &id, int nr, bool polish=false)
THREADLOCAL const Real infinity
bool maxShortLeave(Real &sel, int leave, Real maxabs)
int minSelect(Real &val, Real &stab, Real &best, Real &bestDelta, Real max, const UpdateVector &upd, const Vector &low, const Vector &up, int start=0, int incr=1) const
selects stable index for minimizing ratio test.
Real delta
allowed bound violation
minimize number of basic slack variables, i.e. more variables in between bounds
Real fastDelta
currently allowed infeasibility.
int number(const SPxRowId &id) const
Returns the row number of the row with identifier id.
virtual int selectLeave(Real &val, Real, bool polish=false)
bool isId(const SPxId &p_id) const
Is p_id an SPxId ?
bool minReLeave(Real &sel, int leave, Real maxabs, bool polish=false)
numerical stability tests.
const Vector & lcBound() const
void shiftLBbound(int i, Real to)
shift i 'th lbBound to to.
Real epsilon
|value| < epsilon is considered 0.
virtual void setType(SPxSolver::Type type)
Ids for LP columns.Class SPxColId provides DataKeys for the column indices of an SPxLP.
int maxDelta(Real &val, Real &maxabs, UpdateVector &update, const Vector &lowBound, const Vector &upBound, int start, int incr) const
Max phase 1 value.
void relax()
relaxes stability requirements.
Desc::Status dualStatus(const SPxColId &id) const
dual Status for the column variable with ID id of the loaded LP.
virtual Real value()
current objective value.
int * altIndexMem()
Returns array indices.
maximize number of basic slack variables, i.e. more variables on bounds
const R * get_const_ptr() const
Conversion to C-style pointer.
const Vector & ubBound() const
upper bound for fVec.
Real minStability(Real maxabs)
Compute stability requirement.
R * altValues()
Returns array values.
Generic Ids for LP rows or columns.Both SPxColIds and SPxRowIds may be treated uniformly as SPxIds: ...
UpdateVector & coPvec() const
copricing vector.
void resetTols()
resets tolerances (epsilon).
const R * values() const
Returns array values.
const Vector & lbBound() const
lower bound for fVec.
SPxId id(int i) const
id of i 'th vector.
UpdateVector & fVec() const
feasibility vector.
bool isSPxColId() const
is id a column id?
bool shortEnter(const SPxId &enterId, int nr, Real max, Real maxabs) const
Tests and returns whether a shortcut after phase 1 is feasible for the selected enter pivot...
bool isBasic(SPxBasis::Desc::Status stat) const
does stat describe a basic index ?
Dense vector with semi-sparse vector for updatesIn many algorithms vectors are updated in every itera...
void shiftUBbound(int i, Real to)
shift i 'th ubBound to to.
Status & colStatus(int i)
const int * indexMem() const
Returns array indices.
Real epsilon() const
values are considered to be 0.
Debugging, floating point type and parameter definitions.
void setSize(int n)
Sets number of nonzeros (thereby unSetup SSVectorBase).
void clearIdx(int i)
Clears element i.
bool isCoId(const SPxId &p_id) const
Is p_id a CoId.
Sequential object-oriented SimPlex.SPxSolver is an LP solver class using the revised Simplex algorith...
SolutionPolish polishObj
objective of solution polishing
UpdateVector & pVec() const
pricing vector.
bool minReEnter(Real &sel, Real maxabs, const SPxId &id, int nr, bool polish=false)
numerical stability check.
SPxSolver * thesolver
the solver
const Vector & lpBound() const
int dim() const
Dimension of vector.
int size() const
Returns the number of nonzeros.
Everything should be within this namespace.
void tighten()
tightens stability requirements.
bool iscoid
flag used in methods minSelect/maxSelect to retrieve correct basis status
virtual SPxSolver * solver() const
returns loaded LP solver.
int maxSelect(Real &val, Real &stab, Real &best, Real &bestDelta, Real max, const UpdateVector &upd, const Vector &low, const Vector &up, int start=0, int incr=1) const
selects stable index for maximizing ratio test.
bool minShortLeave(Real &sel, int leave, Real maxabs)
tests for stop after phase 1.
int minDelta(Real &val, Real &maxabs, UpdateVector &update, const Vector &lowBound, const Vector &upBound, int start, int incr) const
Min phase 1 value.
bool maxReLeave(Real &sel, int leave, Real maxabs, bool polish=false)
virtual void load(SPxSolver *solver)
const Vector & upBound() const
virtual SPxId selectEnter(Real &val, int, bool polish=false)
void forceSetup()
Forces setup status.
bool isSPxRowId() const
is id a row id?
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.
Real theShift
sum of all shifts applied to any bound.
int nCols() const
Returns number of columns in LP.
bool isCoBasic(int i) const
is the i 'th covector basic ?
DataArray< int > integerVariables
supplementary variable information, 0: continous variable, 1: integer variable
Real minStab
parameter for computing minimum stability requirement
dual variable has two bounds
const SVector & vector(int i) const
i 'th vector.
SSVector & delta()
update vector , writeable
const SPxBasis & basis() const
Return current basis.
Real stability() const
returns the stability of the basis matrix.
SPxSolver::Type m_type
internal storage of type
const Desc & desc() const
Representation rep() const
return the current basis representation.
columnwise representation.