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])
826 if (up[leave] > low[leave])
857 Real maxabs, max, sel;
866 assert(!instable ||
solver()->instableEnterId.isValid());
888 Real stab, bestDelta;
894 leave =
maxSelect(sel, lowstab, bestDelta, max);
896 leave =
maxSelect(sel, stab, bestDelta, max);
926 Real stab, bestDelta;
932 leave =
minSelect(sel, lowstab, bestDelta, max);
934 leave =
minSelect(sel, stab, bestDelta, max);
960 << std::setprecision(4) << sel <<
" " 962 << std::setprecision(6) << maxabs
966 <<
": skipping instable pivot" << std::endl;
969 if( polish && leave >= 0 )
977 if( leaveId.isSPxRowId() )
1044 sel = (lcb[nr] - cvec[nr]) / d;
1046 sel = (ucb[nr] - cvec[nr]) / d;
1063 sel = (lpb[nr] - pvec[nr]) / d;
1065 sel = (upb[nr] - pvec[nr]) / d;
1070 if ((*up)[nr] != (*low)[nr])
1078 (*up)[nr] = x + sel * d;
1085 (*low)[nr] = x + sel * d;
1097 (*up)[nr] = (*low)[nr] = x;
1160 if ((*up)[nr] != (*low)[nr])
1168 (*up)[nr] = x + sel * d;
1175 (*low)[nr] = x + sel * d;
1187 (*up)[nr] = (*low)[nr] = x;
1194 const SPxId& enterId,
1204 if (x < maxabs *
SHORT && -x < maxabs *
SHORT)
1214 if (x < maxabs *
SHORT && -x < maxabs *
SHORT)
1236 assert(!instable ||
solver()->instableLeaveNum >= 0);
1248 enterId =
maxDelta(nr, max, maxabs);
1257 Real bestDelta, stab;
1264 enterId =
maxSelect(nr, sel, lowstab, bestDelta, max);
1268 enterId =
maxSelect(nr, sel, stab, bestDelta, max);
1279 while (cnt <
TRIES);
1287 enterId =
minDelta(nr, max, maxabs);
1296 Real bestDelta, stab;
1303 enterId =
minSelect(nr, sel, lowstab, bestDelta, max);
1307 enterId =
minSelect(nr, sel, stab, bestDelta, max);
1318 while (cnt <
TRIES);
1332 << sel <<
'\t' << x <<
" (" << maxabs <<
")" << std::endl;
1336 <<
": skipping instable pivot" << std::endl;
1339 if( polish && enterId.
isValid() )
Fast shifting ratio test.
SPxId coId(int i) const
id of i 'th covector.
bool maxReEnter(Real &sel, Real maxabs, const SPxId &id, int nr)
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
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.
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.
bool minReEnter(Real &sel, Real maxabs, const SPxId &id, int nr)
numerical stability check.
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.