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) )
557 MSG_DEBUG( std::cout <<
"DLBFRT06 resetting long step history" << std::endl; )
562 MSG_DEBUG( std::cout <<
"DLBFRT07 switching to fast ratio test" << std::endl; )
659 for( npassedBp = 0; npassedBp < nBp && slope > 0; ++npassedBp)
662 if( npassedBp > sorted )
681 if( absupd > moststable )
698 if( absupd > moststable )
704 assert(npassedBp >= 0);
707 if( slope >
delta && npassedBp >= nBp - 1 )
710 <<
": unboundedness in ratio test" << std::endl; )
718 <<
": number of flip candidates: " 727 for( stableBp = npassedBp + 1; stableBp < nBp; ++stableBp )
729 Real stableDelta = 0;
731 if( stableBp > sorted )
746 if(
spxAbs(x) > moststable )
749 stableDelta = (x > 0.0) ? upb[idx] : lpb[idx];
750 stableDelta = (stableDelta - pvec[idx]) / x;
752 if( stableDelta <= bestDelta)
769 if(
spxAbs(x) > moststable )
771 stableDelta = (x > 0.0) ? ucb[idx] : lcb[idx];
772 stableDelta = (stableDelta - cvec[idx]) / x;
774 if( stableDelta <= bestDelta )
783 if( stableDelta >
delta + bestDelta )
793 bool foundStable =
false;
798 if( moststable > stab )
804 foundStable =
getData(val, enterId, idx, stab, degeneps, pupd, pvec, lpb, upb,
PVEC, max);
806 foundStable =
getData(val, enterId, idx, stab, degeneps, cupd, cvec, lcb, ucb,
COPVEC, max);
813 while( !foundStable && npassedBp >= 0 )
821 foundStable =
getData(val, enterId, idx, stab, degeneps, pupd, pvec, lpb, upb,
PVEC, max);
823 foundStable =
getData(val, enterId, idx, stab, degeneps, cupd, cvec, lcb, ucb,
COPVEC, max);
837 <<
": no valid enterId found - relaxing..." 850 <<
" no valid enterId found - breaking..." 866 if( npassedBp >= 10 )
881 <<
" number of candidates: " 899 MSG_DEBUG( std::cout <<
"DEBFRT06 resetting long step history" << std::endl; )
905 MSG_DEBUG( std::cout <<
"DEBFRT07 switching to fast ratio test" << std::endl; )
978 slope =
spxAbs(enterTest);
997 for( npassedBp = 0; npassedBp < nBp && slope > 0; ++npassedBp)
1000 if( npassedBp > sorted )
1024 slope -= (upper * absupd) - (lower * absupd);
1026 if( absupd > moststable )
1027 moststable = absupd;
1030 assert(npassedBp >= 0);
1033 if( slope >
delta && npassedBp >= nBp - 1 )
1036 <<
": unboundedness in ratio test" << std::endl; )
1044 <<
": number of flip candidates: " 1053 for( stableBp = npassedBp + 1; stableBp < nBp; ++stableBp )
1055 Real stableDelta = 0;
1057 if( stableBp > sorted )
1063 Real x = upd[breakpointidx];
1064 if(
spxAbs(x) > moststable )
1066 stableDelta = (x > 0.0) ? ub[breakpointidx] : lb[breakpointidx];
1067 stableDelta = (stableDelta - vec[breakpointidx]) / x;
1069 if( stableDelta <= bestDelta)
1076 else if( stableDelta >
delta + bestDelta )
1086 bool foundStable =
false;
1091 if( moststable > stab )
1095 assert(breakpointidx >= 0);
1096 foundStable =
getData(val, leaveIdx, breakpointidx, moststable, degeneps, upd, vec, lb, ub,
FVEC, max);
1103 while( !foundStable && npassedBp >= 0 )
1108 if( breakpointidx >= 0 )
1110 foundStable =
getData(val, leaveIdx, breakpointidx, moststable, degeneps, upd, vec, lb, ub,
FVEC, max);
1119 assert(leaveIdx < 0);
1124 <<
": no valid leaveIdx found - relaxing..." 1137 <<
" no valid leaveIdx found - breaking..." 1153 if( npassedBp >= 10 )
1166 <<
": selected Index: " 1168 <<
" number of candidates: " Rational spxAbs(const Rational &r)
Absolute.
int dim() const
dimension of basis matrix.
bool isSPxRowId() const
is id a row id?
const R * values() const
Returns array values.
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)
Representation rep() const
return the current basis representation.
int boundflips
number of performed bound flips
Desc::Status dualStatus(const SPxColId &id) const
dual Status for the column variable with ID id of the loaded LP.
SPxOut * spxout
message handler
DVector * theUbound
Upper bound for vars.
bool isValid() const
returns TRUE iff the id is a valid column or row identifier.
int iteration() const
returns number of basis changes since last load().
const Vector & fTest() const
Violations of fVec.
DVector * theCoUbound
Upper bound for covars.
bool isSPxColId() const
is id a column id?
Real delta
allowed bound violation
const Vector & lbBound() const
lower bound for fVec.
Status & rowStatus(int i)
int number(const SPxRowId &id) const
Returns the row number of the row with identifier id.
Real fastDelta
currently allowed infeasibility.
void setValue(int i, R x)
Sets i 'th element to x.
const R * get_const_ptr() const
Conversion to C-style pointer.
UpdateVector & fVec() const
feasibility vector.
const VectorBase< R > & lower() const
Returns lower bound vector.
void shiftLBbound(int i, Real to)
shift i 'th lbBound to to.
Real epsilon
|value| < epsilon is considered 0.
UpdateVector & pVec() const
pricing vector.
virtual int selectLeave(Real &val, Real enterTest)
const Vector & ubBound() const
upper bound for fVec.
Ids for LP columns.Class SPxColId provides DataKeys for the column indices of an SPxLP.
SPxId coId(int i) const
id of i 'th covector.
void relax()
relaxes stability requirements.
const VectorBase< R > & upper() const
Returns upper bound vector.
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)
Wrapper for different output streams and verbosity levels.
virtual int selectLeave(Real &val, Real)
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: ...
void resetTols()
resets tolerances (epsilon).
UpdateVector & coPvec() const
copricing vector.
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 SPxBasis & basis() const
Return current basis.
DVector theLBbound
Lower Basic Feasibility bound.
bool isCoBasic(int i) const
is the i 'th covector basic ?
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.
const Vector & lcBound() const
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.
DVector theUBbound
Upper Basic Feasibility bound.
const Vector & upBound() const
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.
bool isSetup() const
Returns setup status.
void clearIdx(int i)
Clears element i.
SPxSolver * thesolver
the solver
DVector theLRbound
Lower Row Feasibility bound.
DVector theUCbound
Upper Column Feasibility bound.
const VectorBase< R > & lhs() const
Returns left hand side vector.
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
const SVector & vector(int i) const
i 'th vector.
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.
SPxId id(int i) const
id of i 'th vector.
const Vector & lpBound() const
Real theShift
sum of all shifts applied to any bound.
void flipAndUpdate(int &usedBp)
DataArray< Breakpoint > breakpoints
const VectorBase< R > & rhs() const
Returns right hand side vector.
virtual SPxId selectEnter(Real &val, int)
bool isBasic(SPxBasis::Desc::Status stat) const
does stat describe a basic index ?
int enterCount
number of ENTER iterations
const int * indexMem() const
Returns array indices.
dual variable has two bounds
Ids for LP rows.Class SPxRowId provides DataKeys for the row indices of an SPxLP. ...
const Desc & desc() const
SSVector & delta()
update vector , writeable
void setup4solve2(SSVector *p_y2, SSVector *p_rhs2)
Setup vectors to be solved within Simplex loop.
const Vector & ucBound() const
Status
Status of a variable.
void add(int i, R x)
Adds nonzero (i, x) to SSVectorBase.
SPxSolver::Type m_type
internal storage of type
columnwise representation.
int size() const
Returns the number of nonzeros.
virtual SPxId selectEnter(Real &val, int leaveIdx)
void setup4coSolve2(SSVector *p_z, SSVector *p_rhs)
Setup vectors to be cosolved within Simplex loop.