28 #define MAX_RELAX_COUNT 2 29 #define LONGSTEP_FREQ 100 49 for(
int i = 0; i < nflips; ++i )
76 range = lower - upper;
84 range = upper - lower;
96 <<
" lower: " << lower
97 <<
" upper: " << upper
101 MSG_DEBUG( std::cout <<
"PVEC flipped from: " << stat
105 <<
" lower: " << lower
106 <<
" upper: " << upper
111 assert(
spxAbs(range) < 1e20);
113 if( objChange != 0.0 )
126 range = lower - upper;
134 range = upper - lower;
146 <<
" lower: " << lower
147 <<
" upper: " << upper
151 MSG_DEBUG( std::cout <<
"COPVEC flipped from: " << stat
155 <<
" lower: " << lower
156 <<
" upper: " << upper
161 assert(
spxAbs(range) < 1e20);
163 if( objChange != 0.0 )
172 if( baseId.isSPxRowId() )
182 range = upper - lower;
189 range = lower - upper;
200 <<
" lower: " << lower
201 <<
" upper: " << upper
208 assert(baseId.isSPxColId());
218 range = upper - lower;
225 range = lower - upper;
236 <<
" lower: " << lower
237 <<
" upper: " << upper
242 MSG_DEBUG( std::cout <<
"basic row/col flipped from: " << stat
246 <<
" lower: " << lower
247 <<
" upper: " << upper
250 assert(
spxAbs(range) < 1e20);
296 for( ; idx < last; ++idx )
304 Real y = upp[i] - vec[i];
312 if( curVal < minVal )
325 Real y = low[i] - vec[i];
333 if( curVal < minVal )
370 for( ; idx < last; ++idx )
378 Real y = low[i] - vec[i];
387 if( curVal < minVal )
400 Real y = upp[i] - vec[i];
408 if( curVal < minVal )
448 val = (max * x > 0) ? upp[idx] : low[idx];
449 val = (val - vec[idx]) / x;
450 if( upp[idx] == low[idx] )
453 if( vec[idx] > upp[idx] )
459 else if( (max > 0 && val < -degeneps) || (max < 0 && val > degeneps) )
476 val = (max * x > 0.0) ? upp[idx] : low[idx];
477 val = (val - vec[idx]) / x;
478 if( upp[idx] == low[idx] )
481 if( vec[idx] > upp[idx] )
487 else if( (max > 0 && val < -degeneps) || (max < 0 && val > degeneps) )
514 assert( src ==
FVEC );
523 val = (max * x > 0) ? upp[idx] : low[idx];
524 val = (val - vec[idx]) / x;
525 if( upp[idx] == low[idx] )
531 else if( (max > 0 && val < -degeneps) || (max < 0 && val > degeneps) )
558 MSG_DEBUG( std::cout <<
"DLBFRT06 resetting long step history" << std::endl; )
563 MSG_DEBUG( std::cout <<
"DLBFRT07 switching to fast ratio test" << std::endl; )
660 for( npassedBp = 0; npassedBp < nBp && slope > 0; ++npassedBp)
663 if( npassedBp > sorted )
682 if( absupd > moststable )
699 if( absupd > moststable )
705 assert(npassedBp >= 0);
708 if( slope >
delta && npassedBp >= nBp - 1 )
711 <<
": unboundedness in ratio test" << std::endl; )
719 <<
": number of flip candidates: " 728 for( stableBp = npassedBp + 1; stableBp < nBp; ++stableBp )
730 Real stableDelta = 0;
732 if( stableBp > sorted )
747 if(
spxAbs(x) > moststable )
750 stableDelta = (x > 0.0) ? upb[idx] : lpb[idx];
751 stableDelta = (stableDelta - pvec[idx]) / x;
753 if( stableDelta <= bestDelta)
770 if(
spxAbs(x) > moststable )
772 stableDelta = (x > 0.0) ? ucb[idx] : lcb[idx];
773 stableDelta = (stableDelta - cvec[idx]) / x;
775 if( stableDelta <= bestDelta )
784 if( stableDelta >
delta + bestDelta )
794 bool foundStable =
false;
799 if( moststable > stab )
805 foundStable =
getData(val, enterId, idx, stab, degeneps, pupd, pvec, lpb, upb,
PVEC, max);
807 foundStable =
getData(val, enterId, idx, stab, degeneps, cupd, cvec, lcb, ucb,
COPVEC, max);
814 while( !foundStable && npassedBp >= 0 )
822 foundStable =
getData(val, enterId, idx, stab, degeneps, pupd, pvec, lpb, upb,
PVEC, max);
824 foundStable =
getData(val, enterId, idx, stab, degeneps, cupd, cvec, lcb, ucb,
COPVEC, max);
838 <<
": no valid enterId found - relaxing..." 851 <<
" no valid enterId found - breaking..." 867 if( npassedBp >= 10 )
882 <<
" number of candidates: " 901 MSG_DEBUG( std::cout <<
"DEBFRT06 resetting long step history" << std::endl; )
907 MSG_DEBUG( std::cout <<
"DEBFRT07 switching to fast ratio test" << std::endl; )
980 slope =
spxAbs(enterTest);
999 for( npassedBp = 0; npassedBp < nBp && slope > 0; ++npassedBp)
1002 if( npassedBp > sorted )
1026 slope -= (upper * absupd) - (lower * absupd);
1028 if( absupd > moststable )
1029 moststable = absupd;
1032 assert(npassedBp >= 0);
1035 if( slope >
delta && npassedBp >= nBp - 1 )
1038 <<
": unboundedness in ratio test" << std::endl; )
1046 <<
": number of flip candidates: " 1055 for( stableBp = npassedBp + 1; stableBp < nBp; ++stableBp )
1057 Real stableDelta = 0;
1059 if( stableBp > sorted )
1065 Real x = upd[breakpointidx];
1066 if(
spxAbs(x) > moststable )
1068 stableDelta = (x > 0.0) ? ub[breakpointidx] : lb[breakpointidx];
1069 stableDelta = (stableDelta - vec[breakpointidx]) / x;
1071 if( stableDelta <= bestDelta)
1078 else if( stableDelta >
delta + bestDelta )
1088 bool foundStable =
false;
1093 if( moststable > stab )
1097 assert(breakpointidx >= 0);
1098 foundStable =
getData(val, leaveIdx, breakpointidx, moststable, degeneps, upd, vec, lb, ub,
FVEC, max);
1105 while( !foundStable && npassedBp >= 0 )
1110 if( breakpointidx >= 0 )
1112 foundStable =
getData(val, leaveIdx, breakpointidx, moststable, degeneps, upd, vec, lb, ub,
FVEC, max);
1121 assert(leaveIdx < 0);
1126 <<
": no valid leaveIdx found - relaxing..." 1139 <<
" no valid leaveIdx found - breaking..." 1155 if( npassedBp >= 10 )
1168 <<
": selected Index: " 1170 <<
" number of candidates: " const VectorBase< R > & rhs() const
Returns right hand side vector.
Rational spxAbs(const Rational &r)
Absolute.
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().
void collectBreakpointsMax(int &nBp, int &minIdx, const int *idx, int nnz, const Real *upd, const Real *vec, const Real *upp, const Real *low, BreakpointSource src)
bool isSetup() const
Returns setup status.
int boundflips
number of performed bound flips
const VectorBase< R > & upper() const
Returns upper bound vector.
const Vector & fTest() const
Violations of fVec.
SPxOut * spxout
message handler
THREADLOCAL const Real infinity
DVector * theUbound
Upper bound for vars.
DVector * theCoUbound
Upper bound for covars.
Real delta
allowed bound violation
Status & rowStatus(int i)
virtual int selectLeave(Real &val, Real enterTest, bool polish=false)
Real fastDelta
currently allowed infeasibility.
void setValue(int i, R x)
Sets i 'th element to x.
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)
const Vector & lcBound() const
int dim() const
dimension of basis matrix.
void shiftLBbound(int i, Real to)
shift i 'th lbBound to to.
Real epsilon
|value| < epsilon is considered 0.
Ids for LP columns.Class SPxColId provides DataKeys for the column indices of an SPxLP.
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.
void collectBreakpointsMin(int &nBp, int &minIdx, const int *idx, int nnz, const Real *upd, const Real *vec, const Real *upp, const Real *low, BreakpointSource src)
const R * get_const_ptr() const
Conversion to C-style pointer.
Wrapper for different output streams and verbosity levels.
const Vector & ubBound() const
upper bound for fVec.
Real minStability(Real maxabs)
Compute stability requirement.
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.
void resetTols()
resets tolerances (epsilon).
const R * values() const
Returns array values.
void shiftLPbound(int i, Real to)
shift i 'th lpBound to to.
Row and columns Id's SPxLP.
DVector * theLbound
Lower bound for vars.
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?
DVector theLBbound
Lower Basic Feasibility bound.
bool isBasic(SPxBasis::Desc::Status stat) const
does stat describe a basic index ?
const VectorBase< R > & lhs() const
Returns left hand side vector.
void clear()
Clears vector.
void shiftUCbound(int i, Real to)
shift i 'th ucBound to to.
bool updateNonbasicValue(Real objChange)
DVector theURbound
Upper Row Feasibility bound.
virtual SPxId selectEnter(Real &val, int leaveIdx, bool polish=false)
SSVectorBase< R > & multAdd(S xx, const SVectorBase< T > &vec)
Addition of a scaled vector.
void shiftUBbound(int i, Real to)
shift i 'th ubBound to to.
Status & colStatus(int i)
Generic QuickSort implementation.
const int * indexMem() const
Returns array indices.
DVector theUBbound
Upper Basic Feasibility bound.
Bound flipping ratio test (long step dual) for SoPlex.
DVector * theCoLbound
Lower bound for covars.
void reDim(int newdim)
Resets dimension to newdim.
Debugging, floating point type and parameter definitions.
void clearIdx(int i)
Clears element i.
UpdateVector & pVec() const
pricing vector.
SPxSolver * thesolver
the solver
const Vector & lpBound() const
DVector theLRbound
Lower Row Feasibility bound.
DVector theUCbound
Upper Column Feasibility bound.
int size() const
Returns the number of nonzeros.
Everything should be within this namespace.
void shiftUPbound(int i, Real to)
shift i 'th upBound to to.
void shiftLCbound(int i, Real to)
shift i 'th lcBound to to.
void tighten()
tightens stability requirements.
#define MSG_WARNING(spxout, x)
Prints out message x if the verbosity level is at least SPxOut::WARNING.
primal variable is set to its lower bound
bool getData(Real &val, SPxId &enterId, int idx, Real stab, Real degeneps, const Real *upd, const Real *vec, const Real *low, const Real *upp, BreakpointSource src, Real max)
void setup()
Initializes nonzero indices for elements with absolute values above epsilon and sets all other elemen...
DVector theLCbound
Lower Column Feasibility bound.
int leaveCount
number of LEAVE iterations
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.
const Vector & upBound() const
virtual SPxId selectEnter(Real &val, int, bool polish=false)
bool isSPxRowId() const
is id a row id?
bool isValid() const
returns TRUE iff the id is a valid column or row identifier.
Real theShift
sum of all shifts applied to any bound.
void flipAndUpdate(int &usedBp)
DataArray< Breakpoint > breakpoints
int enterCount
number of ENTER iterations
bool isCoBasic(int i) const
is the i 'th covector basic ?
dual variable has two bounds
Ids for LP rows.Class SPxRowId provides DataKeys for the row indices of an SPxLP. ...
const SVector & vector(int i) const
i 'th vector.
SSVector & delta()
update vector , writeable
const SPxBasis & basis() const
Return current basis.
void setup4solve2(SSVector *p_y2, SSVector *p_rhs2)
Setup vectors to be solved within Simplex loop.
Status
Status of a variable.
void add(int i, R x)
Adds nonzero (i, x) to SSVectorBase.
const VectorBase< R > & lower() const
Returns (internal and possibly scaled) lower bound vector.
SPxSolver::Type m_type
internal storage of type
const Desc & desc() const
Representation rep() const
return the current basis representation.
columnwise representation.
void setup4coSolve2(SSVector *p_z, SSVector *p_rhs)
Setup vectors to be cosolved within Simplex loop.