29 #define FREE_LHS_RHS 1 30 #define FREE_CONSTRAINT 1 31 #define EMPTY_CONSTRAINT 1 32 #define ROW_SINGLETON 1 33 #define FORCE_CONSTRAINT 1 36 #define EMPTY_COLUMN 1 37 #define FIX_VARIABLE 1 38 #define FREE_ZERO_OBJ_VARIABLE 1 39 #define ZERO_OBJ_COL_SINGLETON 1 40 #define DOUBLETON_EQUATION 1 41 #define FREE_COL_SINGLETON 1 43 #define DOMINATED_COLUMN 1 44 #define WEAKLY_DOMINATED_COLUMN 1 45 #define MULTI_AGGREGATE 1 47 #define TRIVIAL_HEURISTICS 1 56 #define DUPLICATE_ROWS 1 57 #define DUPLICATE_COLS 1 61 #define CHECK_BASIC_DIM 70 for(
int rs = 0; rs <
nRows; ++rs)
76 for(
int cs = 0; cs <
nCols; ++cs)
81 assert(numBasis == nRows);
82 return numBasis ==
nRows;
89 assert(
isZero(s[m_i], 1e-9));
96 MSG_DEBUG( std::cout <<
"RowObjPS: removing slack column " << m_j <<
" (" << cStatus[m_j] <<
") for row " << m_i <<
" (" << rStatus[m_i] <<
").\n" );
100 switch( cStatus[m_j] )
109 rStatus[m_i] = cStatus[m_j];
116 #ifdef CHECK_BASIC_DIM 132 rStatus[m_old_i] = rStatus[m_i];
137 for (
int k = 0; k < m_row.size(); ++k)
138 slack += m_row.value(k) * x[m_row.index(k)];
148 #ifdef CHECK_BASIC_DIM 163 rStatus[m_old_i] = rStatus[m_i];
174 #ifdef CHECK_BASIC_DIM 189 rStatus[m_old_i] = rStatus[m_i];
191 Real aij = m_col[m_i];
194 s[m_i] = aij * x[m_j];
199 for(
int k = 0; k < m_col.size(); ++k)
201 if (m_col.index(k) != m_i)
202 val -= m_col.value(k) * y[m_col.index(k)];
205 Real newLo = (aij > 0) ? m_lhs/aij : m_rhs/aij;
206 Real newUp = (aij > 0) ? m_rhs/aij : m_lhs/aij;
211 if(newLo <= m_oldLo && newUp >= m_oldUp)
220 assert(
EQrel(newLo, x[m_j],
eps()));
228 else if((
EQrel(m_oldLo, x[m_j],
eps()) && r[m_j] <= -
eps())
229 || (
EQrel(m_oldUp, x[m_j],
eps()) && r[m_j] >=
eps())
249 else if(
EQrel(newLo, m_oldUp,
eps()))
264 assert(
EQrel(m_oldUp, x[m_j],
eps()));
272 else if(
EQrel(newUp, m_oldLo,
eps()))
287 assert(
EQrel(m_oldLo, x[m_j],
eps()));
350 #ifdef CHECK_BASIC_DIM 365 rStatus[m_old_i] = rStatus[m_i];
371 int cBasisCandidate = -1;
372 Real maxViolation = -1.0;
375 for(
int k = 0; k < m_row.size(); ++k)
377 int cIdx = m_row.index(k);
378 Real aij = m_row.value(k);
379 Real oldLo = m_oldLowers[k];
380 Real oldUp = m_oldUppers[k];
382 switch(cStatus[cIdx])
393 if( violation > maxViolation && ( (
EQrel(oldLo, x[cIdx],
eps()) && r[cIdx] < -
eps()) || (
EQrel(oldUp, x[cIdx],
eps()) && r[cIdx] >
eps()) ) )
395 maxViolation = violation;
396 cBasisCandidate =
cIdx;
411 if(cBasisCandidate >= 0)
415 assert(cBasisCandidate == m_row.index(bas_k));
420 Real aij = m_row.value(bas_k);
421 Real multiplier = r[cBasisCandidate]/aij;
422 r[cBasisCandidate] = 0.0;
424 for(
int k = 0; k < m_row.size(); ++k)
430 r[m_row.index(k)] -= m_row.value(k) * multiplier;
434 Real val = m_objs[bas_k];
437 for(
int k = 0; k < basis_col.
size(); ++k)
439 if (basis_col.
index(k) != m_i)
440 val -= basis_col.
value(k) * y[basis_col.
index(k)];
451 #ifdef CHECK_BASIC_DIM 468 cStatus[m_old_j] = cStatus[m_j];
474 for(
int k = 0; k < m_col.size(); ++k)
475 s[m_col.index(k)] += m_col.value(k) * x[m_j];
480 for(
int k = 0; k < m_col.size(); ++k)
481 val -= m_col.value(k) * y[m_col.index(k)];
486 if( m_lower == m_upper )
488 assert(
EQrel(m_lower, m_val));
494 assert(
EQrel(m_val, m_lower) ||
EQrel(m_val, m_upper) || m_val == 0.0);
499 #ifdef CHECK_BASIC_DIM 515 cStatus[m_j] = m_status;
525 cStatus[m_old_j] = cStatus[m_j];
527 int rIdx = m_old_i - m_col.size() + 1;
529 for(
int k = 0; k < m_col.size(); ++k)
531 int rIdx_new = m_col.index(k);
532 s[
rIdx] = s[rIdx_new];
533 y[
rIdx] = y[rIdx_new];
534 rStatus[
rIdx] = rStatus[rIdx_new];
546 for(
int k = 0; k < m_rows.size(); ++k)
549 const SVector& row = m_rows[k];
551 for(
int l = 0; l < row.
size(); ++l)
553 if (row.
index(l) != m_j)
562 Real z = (m_lRhs[k] / scale) - (val / scale);
567 Real up = z * scale / row[m_j];
577 if (m_bnd < minRowUp)
589 for(
int k = 0; k < m_rows.size(); ++k)
592 const SVector& row = m_rows[k];
594 for(
int l = 0; l < row.
size(); ++l)
596 if (row.
index(l) != m_j)
605 Real z = (m_lRhs[k] / scale) - (val / scale);
610 Real lo = z * scale / row[m_j];
620 if (m_bnd > maxRowLo)
629 for(
int k = 0; k < m_col.size(); ++k)
630 s[m_col.index(k)] = slack[k] + m_col.value(k) * x[m_j];
635 for(
int k = 0; k < m_col.size(); ++k)
636 y[m_col.index(k)] = m_rowObj.value(k);
639 for(
int k = 0; k < m_col.size(); ++k)
661 #ifdef CHECK_BASIC_DIM 676 cStatus[m_old_j] = cStatus[m_j];
679 Real aij = m_row[m_j];
685 throw SPxException(
"Simplifier: infinite activities - aborting unsimplification");
695 Real z1 = (m_lhs / scale1) - (s[m_i] / scale1);
696 Real z2 = (m_rhs / scale2) - (s[m_i] / scale2);
703 Real lo = (aij > 0) ? z1 * scale1 / aij : z2 * scale2 / aij;
704 Real up = (aij > 0) ? z2 * scale2 / aij : z1 * scale1 / aij;
711 assert(
LErel(lo, up));
716 if ( m_lower == m_upper )
736 if ( m_lower == m_upper )
756 assert(
EQrel(m_lower, m_upper));
793 s[m_i] += aij * x[m_j];
796 r[m_j] = -1.0 * aij * y[m_i];
800 #ifdef CHECK_BASIC_DIM 816 rStatus[m_old_i] = rStatus[m_i];
821 cStatus[m_old_j] = cStatus[m_j];
825 Real aij = m_row[m_j];
827 for(
int k = 0; k < m_row.size(); ++k)
829 if (m_row.index(k) != m_j)
830 val += m_row.value(k) * x[m_row.index(k)];
838 Real z = (m_lRhs / scale) - (val / scale);
843 x[m_j] = z * scale / aij;
847 y[m_i] = m_obj / aij;
860 #ifdef CHECK_BASIC_DIM 877 (( m_maxSense && ((r[m_j] > 0 && m_strictUp) || (r[m_j] < 0 && m_strictLo))) ||
878 (!m_maxSense && ((r[m_j] > 0 && m_strictLo) || (r[m_j] < 0 && m_strictUp)))))))
881 Real aik = m_col[m_i];
883 for(
int _k = 0; _k < m_col.size(); ++_k)
885 if (m_col.index(_k) != m_i)
886 val -= m_col.value(_k) * y[m_col.index(_k)];
892 r[m_j] = m_jObj - val * m_aij / aik;
901 if(
GT(r[m_j], 0) || (
isZero(r[m_j]) &&
EQ(x[m_j], m_Lo_j)) )
910 #ifdef CHECK_BASIC_DIM 925 for(
int i = m_perm.size() - 1; i >= 0; --i)
929 int rIdx_new = m_perm[i];
931 s[
rIdx] = s[rIdx_new];
932 y[
rIdx] = y[rIdx_new];
933 rStatus[
rIdx] = rStatus[rIdx_new];
939 for(
int k = 0; k < m_scale.size(); ++k)
941 if (m_scale.index(k) != m_i)
942 s[m_scale.index(k)] = s[m_i] / m_scale.value(k);
946 bool haveSetBasis =
false;
948 for(
int k = 0; k < m_scale.size(); ++k)
950 int i = m_scale.index(k);
956 y[i] = m_rowObj.value(k);
963 if (rStatus[m_i] ==
SPxSolver::FIXED && (i == m_maxLhsIdx || i == m_minRhsIdx))
966 y[i] = y[m_i] * m_scale.value(k);
969 if(m_isLhsEqualRhs[k])
973 else if(i == m_maxLhsIdx)
979 assert(i == m_minRhsIdx);
990 y[i] = y[m_i] * m_scale.value(k);
1001 y[i] = y[m_i] * m_scale.value(k);
1002 y[m_i] = m_i_rowObj;
1007 haveSetBasis =
true;
1012 y[i] = m_rowObj.value(k);
1017 #ifdef CHECK_BASIC_DIM 1037 #ifdef CHECK_BASIC_DIM 1050 for(
int i = m_perm.size() - 1; i >= 0; --i)
1054 int cIdx_new = m_perm[i];
1056 x[
cIdx] = x[cIdx_new];
1057 r[
cIdx] = r[cIdx_new];
1058 cStatus[
cIdx] = cStatus[cIdx_new];
1107 assert(
LErel(m_loJ, 0.0));
1108 assert(
GErel(m_upJ, 0.0));
1109 assert(
LErel(m_loK, 0.0));
1110 assert(
GErel(m_upK, 0.0));
1118 else if (
LErel(m_loK, 0.0) &&
GErel(m_upK, 0.0))
1130 else if (
LErel(m_loJ, 0.0) &&
GErel(m_upJ, 0.0))
1145 Real z1 = (x[m_k] / scale1) - (m_loK / scale1);
1146 Real z2 = (x[m_k] / scale2) - (m_upK / scale2);
1153 if( m_loJ <= -infinity && m_upJ >=
infinity && m_loK <= -infinity && m_upK >=
infinity )
1158 else if( m_scale > 0.0 )
1160 if(
GErel(x[m_k], m_upK + m_scale * m_upJ) )
1165 x[m_k] -= m_scale * x[m_j];
1167 else if(
GErel(x[m_k], m_loK + m_scale * m_upJ) && m_upJ <
infinity )
1171 x[m_k] -= m_scale * x[m_j];
1173 else if(
GErel(x[m_k], m_upK + m_scale * m_loJ) && m_upK <
infinity )
1178 x[m_j] = z2 * scale2 / m_scale;
1180 else if(
GErel(x[m_k], m_loK + m_scale * m_loJ) && m_loJ > -
infinity )
1184 x[m_k] -= m_scale * x[m_j];
1186 else if(
GErel(x[m_k], m_loK + m_scale * m_loJ) && m_loK > -
infinity )
1191 x[m_j] = z1 * scale1 / m_scale;
1193 else if(
LTrel(x[m_k], m_loK + m_scale * m_loJ) )
1198 x[m_k] -= m_scale * x[m_j];
1207 assert(m_scale < 0.0);
1209 if(
GErel(x[m_k], m_upK + m_scale * m_loJ) )
1214 x[m_k] -= m_scale * x[m_j];
1216 else if(
GErel(x[m_k], m_loK + m_scale * m_loJ) && m_loJ > -
infinity )
1220 x[m_k] -= m_scale * x[m_j];
1222 else if(
GErel(x[m_k], m_upK + m_scale * m_upJ) && m_upK <
infinity )
1227 x[m_j] = z2 * scale2 / m_scale;
1229 else if(
GErel(x[m_k], m_loK + m_scale * m_upJ) && m_upJ <
infinity )
1233 x[m_k] -= m_scale * x[m_j];
1235 else if(
GErel(x[m_k], m_loK + m_scale * m_upJ) && m_loK > -
infinity )
1240 x[m_j] = z1 * scale1 / m_scale;
1242 else if(
LTrel(x[m_k], m_loK + m_scale * m_upJ) )
1247 x[m_k] -= m_scale * x[m_j];
1257 r[m_j] = m_scale * r[m_k];
1266 s[m_old_i] = s[m_i];
1267 y[m_old_i] = y[m_i];
1268 rStatus[m_old_i] = rStatus[m_i];
1271 x[m_old_j] = x[m_j];
1272 r[m_old_j] = r[m_j];
1273 cStatus[m_old_j] = cStatus[m_j];
1277 Real aij = m_row[m_j];
1279 for(
int k = 0; k < m_row.size(); ++k)
1281 if(m_row.index(k) != m_j)
1282 val += m_row.value(k) * x[m_row.index(k)];
1290 Real z = (m_const / scale) - (val / scale);
1295 x[m_j] = z * scale / aij;
1298 assert(!isOptimal || (
GE(x[m_j], m_lower) &&
LE(x[m_j], m_upper)));
1303 for(
int k = 0; k < m_col.size(); ++k)
1305 if(m_col.index(k) != m_i)
1306 dualVal += m_col.value(k) * y[m_col.index(k)];
1309 z = m_obj - dualVal;
1324 #ifdef CHECK_BASIC_DIM 1337 switch(cStatus[m_j])
1340 if(
LT(x[m_j], m_origupper,
eps()) &&
GT(x[m_j], m_origlower,
eps()))
1342 else if(
LT(x[m_j], m_origupper,
eps()))
1344 else if(
GT(x[m_j], m_origlower,
eps()))
1349 if(
GT(x[m_j], m_origlower,
eps()))
1354 if(
LT(x[m_j], m_origupper,
eps()))
1362 #ifdef CHECK_BASIC_DIM 1372 for(
int i = lp.
nRows() - 1; i >= 0; --i )
1404 for(
int i = lp.
nRows()-1; i >= 0; --i)
1414 else if (lhs > -
infinity && lhs < -maxVal)
1419 else if (lhs < infinity && lhs > maxVal)
1433 else if (rhs > -
infinity && rhs < -maxVal)
1438 else if (rhs < infinity && rhs > maxVal)
1457 for(
int j = 0; j < lp.
nCols(); ++j)
1467 else if (lo > -
infinity && lo < -maxVal)
1472 else if (lo < infinity && lo > maxVal)
1486 else if (up > -
infinity && up < -maxVal)
1491 else if (up < infinity && up > maxVal)
1503 Real absBnd = (lo > up) ? lo : up;
1512 while(i < col.
size())
1516 if (
isZero(aij * absBnd, tol))
1525 <<
" removed, absBnd=" << absBnd
1535 else if(
isZero(aij, tol) )
1553 else if (obj > -
infinity && obj < -maxVal)
1558 else if (obj < infinity && obj > maxVal)
1565 if (remRows + remNzos + chgLRhs + chgBnds + objCnt > 0)
1573 << remRows <<
" rows, " 1574 << remNzos <<
" non-zeros, " 1575 << chgBnds <<
" col bounds, " 1576 << chgLRhs <<
" row bounds, " 1577 << objCnt <<
" objective coefficients" << std::endl; )
1586 bool minNegInfinite =
false;
1587 bool maxInfinite =
false;
1592 for (
int l = 0; l < row.
size(); ++l)
1594 if (colNumber < 0 || row.
index(l) != colNumber)
1600 minNegInfinite =
true;
1604 else if (
LT(row.
value(l), 0.0))
1607 minNegInfinite =
true;
1620 else if (
LT(row.
value(l), 0.0))
1651 minVal = (side - minRes)/val;
1656 maxVal = (side - maxRes)/val;
1658 else if(
GT(val, 0.0))
1663 minVal = (side - maxRes)/val;
1668 maxVal = (side - minRes)/val;
1689 bool zerovalid =
true;
1697 for(
int j = lp.
nCols()-1; j >= 0; --j)
1704 for(
int k = 0; k < col.
size(); ++k)
1735 lower =
MINIMUM(-largeValue, upper);
1747 lowersol[j] = lower;
1748 uppersol[j] = upper;
1750 if(downLocks[j] > upLocks[j])
1752 else if(downLocks[j] < upLocks[j])
1755 locksol[j] = (lower + upper)/2.0;
1757 lowerObj += lp.
maxObj(j)*lowersol[j];
1758 upperObj += lp.
maxObj(j)*uppersol[j];
1759 lockObj += lp.
maxObj(j)*locksol[j];
1795 for(
int i = lp.
nRows()-1; i >= 0; --i)
1800 for(
int k = 0; k < row.
size(); k++)
1817 for(
int j = lp.
nCols()-1; j >= 0; --j )
1824 pseudoObj += val*lp.
lower(j);
1830 pseudoObj += val*lp.
upper(j);
1839 for(
int j = lp.
nCols()-1; j >= 0; --j)
1858 else if(objval > 0.0)
1883 for(
int i = lp.
nRows()-1; i >= 0; --i)
1887 if (row.
size() == 0)
1895 <<
" rhs=" << lp.
rhs(i) << std::endl; )
1911 for(
int j = lp.
nCols()-1; j >= 0; --j)
1915 if (col.
size() == 0)
1918 <<
": empty -> maxObj=" << lp.
maxObj(j)
1919 <<
" lower=" << lp.
lower(j)
1920 <<
" upper=" << lp.
upper(j); )
1969 if (remRows + remCols > 0)
1975 << remRows <<
" rows, " 1976 << remCols <<
" cols" 1985 assert(row.
size() == 1);
1988 int j = row.
index(0);
1993 <<
": singleton -> val=" << aij
1994 <<
" lhs=" << lp.
lhs(i)
1995 <<
" rhs=" << lp.
rhs(i); )
2021 <<
" (" << lp.
lower(j)
2023 <<
" (" << lp.
upper(j)
2024 <<
")" << std::endl; )
2026 bool stricterUp =
false;
2027 bool stricterLo =
false;
2077 int oldRows = lp.
nRows();
2079 bool redundantLower;
2080 bool redundantUpper;
2084 for(
int i = lp.
nRows()-1; i >= 0; --i)
2095 for(
int k = 0; k < row.
size(); ++k)
2098 int j = row.
index(k);
2102 MSG_WARNING( (*
spxout), (*
spxout) <<
"Warning: tiny nonzero coefficient " << aij <<
" in row " << i <<
"\n" );
2110 lhsBnd += aij * lp.
lower(j);
2115 rhsBnd += aij * lp.
upper(j);
2122 rhsBnd += aij * lp.
lower(j);
2127 lhsBnd += aij * lp.
upper(j);
2133 if (rhsCnt <= 1 || lhsCnt <= 1)
2135 for(
int k = 0; k < row.
size(); ++k)
2138 int j = row.
index(k);
2140 redundantLower =
false;
2141 redundantUpper =
false;
2157 Real z = (lp.
lhs(i) / scale) - (rhsBnd / scale);
2165 lo = lp.
upper(j) + z * scale / aij;
2167 lo = z * scale / aij;
2175 <<
": redundant lower bound on x" << j
2176 <<
" -> lower=" << lo
2177 <<
" (" << lp.
lower(j)
2178 <<
")" << std::endl; )
2180 redundantLower =
true;
2194 Real z = (lp.
rhs(i) / scale) - (lhsBnd / scale);
2202 up = lp.
lower(j) + z * scale / aij;
2204 up = z * scale / aij;
2212 <<
": redundant upper bound on x" << j
2213 <<
" -> upper=" << up
2214 <<
" (" << lp.
upper(j)
2215 <<
")" << std::endl; )
2217 redundantUpper =
true;
2226 lhsBnd -= aij * lp.
lower(j);
2240 rhsBnd -= aij * lp.
upper(j);
2261 Real z = (lp.
lhs(i) / scale) - (rhsBnd / scale);
2269 up = lp.
lower(j) + z * scale / aij;
2271 up = z * scale / aij;
2279 <<
": redundant upper bound on x" << j
2280 <<
" -> upper=" << up
2281 <<
" (" << lp.
upper(j)
2282 <<
")" << std::endl; )
2284 redundantUpper =
true;
2297 Real z = (lp.
rhs(i) / scale) - (lhsBnd / scale);
2305 lo = lp.
upper(j) + z * scale / aij;
2307 lo = z * scale / aij;
2315 <<
": redundant lower bound on x" << j
2316 <<
" -> lower=" << lo
2317 <<
" (" << lp.
lower(j)
2318 <<
")" << std::endl; )
2320 redundantLower =
true;
2329 lhsBnd -= aij * lp.
upper(j);
2343 rhsBnd -= aij * lp.
lower(j);
2358 redundantLhs =
false;
2359 redundantRhs =
false;
2365 <<
": redundant lhs -> lhsBnd=" << lhsBnd
2366 <<
" lhs=" << lp.
lhs(i)
2369 redundantLhs =
true;
2374 <<
": redundant rhs -> rhsBnd=" << rhsBnd
2375 <<
" rhs=" << lp.
rhs(i)
2378 redundantRhs =
true;
2410 <<
": infeasible -> lhs=" << lp.
lhs(i)
2411 <<
" rhs=" << lp.
rhs(i)
2412 <<
" lhsBnd=" << lhsBnd
2413 <<
" rhsBnd=" << rhsBnd
2423 <<
": unconstrained -> removed" << std::endl; )
2430 remNzos += row.
size();
2439 #if EMPTY_CONSTRAINT 2441 if (row.
size() == 0)
2449 <<
" rhs=" << lp.
rhs(i) << std::endl; )
2469 if (row.
size() == 1)
2476 #if FORCE_CONSTRAINT 2482 <<
": forcing constraint fix on lhs ->" 2483 <<
" lhs=" << lp.
lhs(i)
2484 <<
" rhsBnd=" << rhsBnd
2491 for(
int k = 0; k < row.
size(); ++k)
2494 int j = row.
index(k);
2498 lowers[k] = lp.
lower(j);
2499 uppers[k] = lp.
upper(j);
2514 remNzos += row.
size();
2525 <<
": forcing constraint fix on rhs ->" 2526 <<
" rhs=" << lp.
rhs(i)
2527 <<
" lhsBnd=" << lhsBnd
2534 for(
int k = 0; k < row.
size(); ++k)
2537 int j = row.
index(k);
2541 lowers[k] = lp.
lower(j);
2542 uppers[k] = lp.
upper(j);
2557 remNzos += row.
size();
2567 assert(remRows > 0 || remNzos == 0);
2569 if (remRows + chgLRhs + chgBnds > 0)
2579 << remRows <<
" rows, " 2580 << remNzos <<
" non-zeros, " 2581 << chgBnds <<
" col bounds, " 2582 << chgLRhs <<
" row bounds; kept " 2583 << keptBnds <<
" column bounds, " 2584 << keptLRhs <<
" row bounds" 2612 int oldCols = lp.
nCols();
2613 int oldRows = lp.
nRows();
2615 for(
int j = lp.
nCols()-1; j >= 0; --j)
2623 <<
": infeasible bounds on x" << j
2624 <<
" -> lower=" << lp.
lower(j)
2625 <<
" upper=" << lp.
upper(j)
2631 if (col.
size() == 0)
2635 <<
": empty -> maxObj=" << lp.
maxObj(j)
2636 <<
" lower=" << lp.
lower(j)
2637 <<
" upper=" << lp.
upper(j); )
2695 for(
int k = 0; k < col.
size(); ++k)
2697 if (!loFree && !upFree)
2700 int i = col.
index(k);
2705 if (col.
value(k) > 0.0)
2713 else if (col.
value(k) < 0.0)
2731 <<
" unconstrained above ->"; )
2752 <<
" unconstrained below ->"; )
2770 #if FREE_ZERO_OBJ_VARIABLE 2771 bool unconstrained_below = loFree && lp.
lower(j) <= -
infinity;
2772 bool unconstrained_above = upFree && lp.
upper(j) >=
infinity;
2774 if (unconstrained_below || unconstrained_above)
2778 <<
" unconstrained " 2779 << (unconstrained_below ?
"below" :
"above")
2780 <<
" with zero objective (" << lp.
maxObj(j)
2781 <<
")" << std::endl; )
2787 SPxQuicksort(col_idx_sorted.mem(), col_idx_sorted.size(), compare);
2795 remRows += col.
size();
2796 for(
int k = col_idx_sorted.size()-1; k >= 0; --k)
2803 for(
int k = 0; k < col.
size(); ++k)
2805 int l = col.
index(k);
2824 <<
" fixed -> lower=" << lp.
lower(j)
2825 <<
" upper=" << lp.
upper(j) << std::endl; )
2830 remNzos += col.
size();
2840 if (col.
size() == 1)
2843 int i = col.
index(0);
2848 #if ZERO_OBJ_COL_SINGLETON 2850 <<
": singleton in row " << i
2851 <<
" with zero objective"; )
2859 lhs = lp.
lhs(i) - aij * lp.
upper(j);
2861 rhs = lp.
rhs(i) - aij * lp.
lower(j);
2866 lhs = lp.
lhs(i) - aij * lp.
lower(j);
2868 rhs = lp.
rhs(i) - aij * lp.
upper(j);
2882 <<
" (" << lp.
lhs(i)
2884 <<
" (" << lp.
rhs(i)
2885 <<
")" << std::endl; )
2920 #if DOUBLETON_EQUATION 2922 <<
": singleton in row " << i
2923 <<
" with doubleton equation ->"; )
2932 if (row.
index(0) == j)
2937 else if (row.
index(1) == j)
2959 Real z1 = (lhs / scale1) - (aij * lp.
upper(j) / scale1);
2960 Real z2 = (lhs / scale2) - (aij * lp.
lower(j) / scale2);
2987 <<
": lower=" << lp.
lower(k)
2989 <<
") upper=" << lp.
upper(k)
2991 <<
")" << std::endl; )
3019 #if FREE_COL_SINGLETON 3026 <<
": free singleton in inequality constraint" << std::endl; )
3073 <<
": free singleton removed" << std::endl; )
3077 for (
int h = 0; h < row.size(); ++h)
3079 int k = row.
index(h);
3083 Real new_obj = lp.
obj(k) - (lp.
obj(j) * row.value(h) / aij);
3090 remNzos += row.size();
3102 if (remCols + remRows > 0)
3110 << remRows <<
" rows, " 3111 << remCols <<
" cols, " 3112 << remNzos <<
" non-zeros, " 3113 << chgBnds <<
" col bounds" 3135 int oldRows = lp.
nRows();
3136 int oldCols = lp.
nCols();
3145 for(
int i = lp.
nRows()-1; i >= 0; --i)
3151 <<
": unconstrained" << std::endl; )
3172 for(
int j = 0; j < lp.
nCols(); ++j)
3186 dualVarUp[i] = bound;
3188 dualVarLo[i] = bound;
3193 dualVarLo[i] = bound;
3195 dualVarUp[i] = bound;
3202 for(
int j = 0; j < lp.
nCols(); ++j)
3204 dualConsLo[j] = dualConsUp[j] = 0.0;
3208 for(
int k = 0; k < col.
size(); ++k)
3214 int i = col.
index(k);
3223 dualConsLo[j] += aij * dualVarLo[i];
3228 dualConsUp[j] += aij * dualVarUp[i];
3235 dualConsUp[j] += aij * dualVarLo[i];
3240 dualConsLo[j] += aij * dualVarUp[i];
3245 for(
int j = lp.
nCols()-1; j >= 0; --j)
3251 if (
LTrel(dualConsUp[j], dualConsLo[j],
opttol()))
3254 <<
": dual infeasible -> dual lhs bound=" << dualConsLo[j]
3255 <<
" dual rhs bound=" << dualConsUp[j] << std::endl; )
3265 #if DOMINATED_COLUMN 3267 <<
": dominated -> maxObj=" << obj
3268 <<
" dual rhs bound=" << dualConsUp[j] << std::endl; )
3288 #if DOMINATED_COLUMN 3290 <<
": dominated -> maxObj=" << obj
3291 <<
" dual lhs bound=" << dualConsLo[j] << std::endl; )
3313 #if WEAKLY_DOMINATED_COLUMN 3315 <<
": weakly dominated -> maxObj=" << obj
3316 <<
" dual rhs bound=" << dualConsUp[j] << std::endl; )
3328 #if WEAKLY_DOMINATED_COLUMN 3330 <<
": weakly dominated -> maxObj=" << obj
3331 <<
" dual lhs bound=" << dualConsLo[j] << std::endl; )
3358 assert(remRows > 0 || remCols > 0 || remNzos == 0);
3360 if (remCols + remRows > 0)
3367 << remRows <<
" rows, " 3368 << remCols <<
" cols, " 3369 << remNzos <<
" non-zeros" 3387 int oldRows = lp.
nRows();
3388 int oldCols = lp.
nCols();
3393 for(
int j = lp.
nCols()-1; j >= 0; --j)
3403 for(
int k = 0; k < col.
size(); ++k)
3431 if (upLocks[j] == 1 || downLocks[j] == 1)
3437 bool bestislhs =
true;
3441 for(
int k = 0; k < col.
size(); ++k)
3453 rowNumber = col.
index(k);
3454 lhs = lp.
lhs(rowNumber);
3455 rhs = lp.
rhs(rowNumber);
3464 maxOtherLocks = INT_MAX;
3473 && ((col.
value(k) > 0.0 && lp.
maxObj(j) <= 0.0 && downLocks[j] == 1 && upLocks[j] <= maxOtherLocks)
3474 || (col.
value(k) < 0.0 && lp.
maxObj(j) >= 0.0 && upLocks[j] == 1 && downLocks[j] <= maxOtherLocks));
3476 && ((col.
value(k) > 0.0 && lp.
maxObj(j) >= 0.0 && upLocks[j] == 1 && downLocks[j] <= maxOtherLocks)
3477 || (col.
value(k) < 0.0 && lp.
maxObj(j) <= 0.0 && downLocks[j] == 1 && upLocks[j] <= maxOtherLocks));
3479 if (aggLhs || aggRhs)
3496 assert(
LE(minVal, maxVal));
3502 bestpos = col.
index(k);
3517 assert(
LE(minVal, maxVal));
3522 bestpos = col.
index(k);
3535 Real aggConstant = (bestislhs ? lp.
lhs(bestpos) : lp.
rhs(bestpos));
3536 Real aggAij = bestRow[j];
3539 (*
spxout) <<
"IMAISM51 col " << j
3540 <<
": Aggregating row: " << bestpos
3541 <<
" Aggregation Constant=" << aggConstant
3542 <<
" Coefficient of aggregated col=" << aggAij << std::endl;
3549 for(
int k = 0; k < col.
size(); ++k)
3551 if(col.
index(k) != bestpos)
3553 int rowNumber = col.
index(k);
3561 for(
int l = 0; l < bestRow.
size(); l++)
3563 if(bestRow.
index(l) != j)
3567 - updateRow[j]*bestRow.
value(l)/aggAij);
3575 lp.
changeRhs(rowNumber, updateRhs - updateRow[j]*aggConstant/aggAij);
3577 lp.
changeLhs(rowNumber, updateLhs - updateRow[j]*aggConstant/aggAij);
3579 assert(
LE(lp.
lhs(rowNumber), lp.
rhs(rowNumber)));
3583 for(
int l = 0; l < bestRow.
size(); l++)
3585 if(bestRow.
index(l) != j)
3602 assert(remRows > 0 || remCols > 0 || remNzos == 0);
3604 if (remCols + remRows > 0)
3611 << remRows <<
" rows, " 3612 << remCols <<
" cols, " 3613 << remNzos <<
" non-zeros" 3635 int oldRows = lp.
nRows();
3644 for (
int i = 0; i < lp.
nRows(); ++i)
3648 if (row.
size() == 1)
3658 << rs_remRows <<
" rows, " 3659 << rs_remRows <<
" non-zeros" 3687 classSize[0] = lp.
nRows();
3689 for(
int i = 1; i < lp.
nRows(); ++i)
3700 for(
int j = 0; j < lp.
nCols(); ++j)
3704 for(
int k = 0; k < col.
size(); ++k)
3707 int i = col.
index(k);
3709 if (scale[i] == 0.0)
3713 if (--classSize[pClass[i]] == 0)
3714 idxSet.addIdx(pClass[i]);
3718 for(
int m = 0; m < col.
size(); ++m)
3720 int k = pClass[col.
index(m)];
3731 int classIdx = idxSet.index(0);
3738 classIdx = idxSet.index(0);
3743 ++classSize[classIdx];
3745 oldVal = m_classSetRows[k].value(l);
3757 for(
int k = 0; k < lp.
nRows(); ++k )
3760 for(
int k = 0; k < lp.
nRows(); ++k)
3766 const int nRowsOld_tmp = lp.
nRows();
3770 for(
int j = 0; j < nRowsOld_tmp; ++j)
3775 int idxFirstDupRows = -1;
3776 int idxLastDupRows = -1;
3779 for(
int k = 0; k < lp.
nRows(); ++k)
3785 if(idxFirstDupRows < 0)
3787 idxFirstDupRows = k;
3790 for(
int l = 1; l <
m_dupRows[k].size(); ++l)
3801 int k_tmp, j_tmp = -1;
3802 for (k_tmp = j_tmp = 0; k_tmp < nRowsOld_tmp; ++k_tmp)
3804 if (perm_tmp[k_tmp] >= 0)
3805 perm_tmp[k_tmp] = j_tmp++;
3810 bool doChangeRanges =
false;
3814 for(
int k = 0; k < lp.
nRows(); ++k)
3819 <<
" duplicate rows found" << std::endl; )
3833 for(
int l = 0; l <
m_dupRows[k].size(); ++l)
3836 isLhsEqualRhs[l] = (lp.
lhs(i) == lp.
rhs(i));
3843 maxLhs = lp.
lhs(rowIdx);
3844 minRhs = lp.
rhs(rowIdx);
3848 Real scaledLhs, scaledRhs;
3849 Real factor = scale[rowIdx] / scale[i];
3861 if (scaledLhs > maxLhs)
3866 if (scaledRhs < minRhs)
3878 Real newLhs = (maxLhs > lp.
lhs(rowIdx)) ? maxLhs : lp.
lhs(rowIdx);
3879 Real newRhs = (minRhs < lp.
rhs(rowIdx)) ? minRhs : lp.
rhs(rowIdx);
3881 if(k == idxLastDupRows)
3884 for(
int j = 0; j < nRowsOld_tmp; ++j)
3886 da_perm[j] = perm_tmp[j];
3890 m_hist.append(
new (DuplicateRowsPSptr)
DuplicateRowsPS(lp, rowIdx, maxLhsIdx, minRhsIdx,
m_dupRows[k], scale, da_perm, isLhsEqualRhs,
true,
EQrel(newLhs, newRhs), k==idxFirstDupRows));
3897 m_hist.append(
new (DuplicateRowsPSptr)
DuplicateRowsPS(lp, rowIdx, maxLhsIdx, minRhsIdx,
m_dupRows[k], scale, da_perm_empty, isLhsEqualRhs,
false,
EQrel(newLhs, newRhs), k == idxFirstDupRows));
3900 if (maxLhs > lp.
lhs(rowIdx) || minRhs < lp.
rhs(rowIdx))
3903 doChangeRanges =
true;
3907 MSG_DEBUG( (*
spxout) <<
"IMAISM55 duplicate rows yield infeasible bounds:" 3908 <<
" lhs=" << newLhs
3909 <<
" rhs=" << newRhs << std::endl; )
3914 if( newRhs < newLhs )
3917 newLhsVec[rowIdx] = newLhs;
3918 newRhsVec[rowIdx] = newRhs;
3931 const int nRowsOld = lp.
nRows();
3935 for(
int i = 0; i < nRowsOld; ++i)
3948 for(
int i = 0; i < nRowsOld; ++i)
3951 assert(perm[i] == perm_tmp[i]);
3961 if (remRows + remNzos > 0)
3967 << remRows <<
" rows, " 3968 << remNzos <<
" non-zeros" 4014 classSize[0] = lp.
nCols();
4016 for(
int j = 1; j < lp.
nCols(); ++j)
4027 for(
int i = 0; i < lp.
nRows(); ++i)
4031 for(
int k = 0; k < row.
size(); ++k)
4034 int j = row.
index(k);
4036 if (scale[j] == 0.0)
4040 if (--classSize[pClass[j]] == 0)
4041 idxSet.addIdx(pClass[j]);
4045 for(
int m = 0; m < row.
size(); ++m)
4047 int k = pClass[row.
index(m)];
4058 int classIdx = idxSet.index(0);
4066 classIdx = idxSet.index(0);
4071 ++classSize[classIdx];
4073 oldVal = m_classSetCols[k].value(l);
4086 for(
int k = 0; k < lp.
nCols(); ++k )
4089 for(
int k = 0; k < lp.
nCols(); ++k)
4092 fixAndRemCol[k] =
false;
4096 bool hasDuplicateCol =
false;
4099 for(
int k = 0; k < lp.
nCols(); ++k)
4104 <<
" duplicate columns found" << std::endl; )
4106 if (!hasDuplicateCol)
4111 hasDuplicateCol =
true;
4114 for(
int l = 0; l <
m_dupCols[k].size(); ++l)
4116 for(
int m = 0; m <
m_dupCols[k].size(); ++m)
4121 if (l != m && !remCol[j1] && !remCol[j2])
4127 Real factor = scale[j1] / scale[j2];
4128 Real objDif = cj1 - cj2 * scale[j1] / scale[j2];
4159 else if (factor < 0)
4174 <<
" replaced by one" << std::endl; )
4182 MSG_DEBUG( (*
spxout) <<
"IMAISM80 not removing two duplicate columns " << j1
4184 <<
" because zero not contained in their bounds" << std::endl; )
4193 if (factor > 0 && objDif > 0)
4204 <<
" first one fixed at upper bound=" << lp.
upper(j1) << std::endl; )
4211 else if (factor < 0 && objDif < 0)
4222 <<
" first one fixed at lower bound=" << lp.
lower(j1) << std::endl; )
4233 if (factor < 0 && objDif > 0)
4244 <<
" first one fixed at upper bound=" << lp.
upper(j1) << std::endl; )
4253 else if (factor > 0 && objDif < 0)
4264 <<
" first one fixed at lower bound=" << lp.
lower(j1) << std::endl; )
4275 fixAndRemCol[j1] =
true;
4286 for(
int j = 0; j < lp.
nCols(); ++j)
4298 const int nColsOld = lp.
nCols();
4302 for(
int j = 0; j < nColsOld; ++j)
4315 for(
int j = 0; j < nColsOld; ++j)
4322 for(
int j = 0; j < nColsOld; ++j)
4324 da_perm[j] = perm[j];
4327 if (hasDuplicateCol)
4336 assert(remCols > 0 || remNzos == 0);
4344 << remCols <<
" cols, " 4345 << remNzos <<
" non-zeros" 4364 <<
": lower=" << lp.
lower(j)
4365 <<
" upper=" << lp.
upper(j)
4370 for(
int k = 0; k < col.
size(); ++k)
4372 int i = col.
index(k);
4382 Real rhs = (lp.
rhs(i) / scale) - (y / scale);
4391 <<
" (" << lp.
rhs(i)
4392 <<
") aij=" << col.
value(k)
4405 Real lhs = (lp.
lhs(i) / scale) - (y / scale);
4414 <<
" (" << lp.
lhs(i)
4415 <<
") aij=" << col.
value(k)
4420 assert(lp.
lhs(i) <= lp.
rhs(i));
4457 for(
int k = 0; k <
m_hist.size(); ++k)
4483 int numRangedRows = 0;
4484 int numBoxedCols = 0;
4486 for(
int i = 0; i < lp.
nRows(); ++i)
4489 for(
int j = 0; j < lp.
nCols(); ++j)
4493 (*spxout) <<
"LP has " 4494 << numRangedRows <<
" ranged rows, " 4495 << numBoxedCols <<
" boxed columns" 4523 for(
int i = 0; i < lp.
nRows(); ++i)
4526 for(
int j = 0; j < lp.
nCols(); ++j)
4566 #if TRIVIAL_HEURISTICS 4593 << m_remCols <<
" columns, " 4606 << lp.
nRows() <<
" rows " 4607 << lp.
nCols() <<
" columns " 4608 << lp.
nNzos() <<
" nonzeros" 4612 int numRangedRows = 0;
4613 int numBoxedCols = 0;
4615 for(
int i = 0; i < lp.
nRows(); ++i)
4619 for(
int j = 0; j < lp.
nCols(); ++j)
4623 (*spxout) <<
"Reduced LP has " 4624 << numRangedRows <<
" ranged rows, " 4625 << numBoxedCols <<
" boxed columns" 4665 assert(x.
dim() == r.
dim());
4666 assert(y.
dim() == s.
dim());
4671 for(
int j = 0; j < x.
dim(); ++j)
4677 for(
int i = 0; i < y.
dim(); ++i)
4685 for(
int k =
m_hist.size()-1; k >= 0; --k)
4723 #ifdef CHECK_BASIC_DIM 4759 os <<
"DUAL_INFEASIBLE";
const VectorBase< R > & rhs() const
Returns right hand side vector.
DVector m_prim
unsimplified primal solution vector.
Rational spxAbs(const Rational &r)
Absolute.
bool isNotZero(Real a, Real eps=Param::epsilon())
returns true iff |a| > eps
Real m_opttol
dual feasibility tolerance.
DataArray< PostStep * > m_hist
vector of presolve history.
Postsolves multi aggregation.
Exception class for things that should NEVER happen.This class is derived from the SoPlex exception b...
bool LTrel(Real a, Real b, Real eps=Param::epsilon())
returns true iff relDiff(a,b) <= -eps
free variable fixed to zero.
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis, bool isOptimal) const
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis, bool isOptimal) const
friend class FreeConstraintPS
Result removeRowSingleton(SPxLP &lp, const SVector &row, int &i)
remove row singletons.
DataArray< int > m_stat
preprocessing history.
bool GE(Real a, Real b, Real eps=Param::epsilon())
returns true iff a >= b + eps
void reDim(int newdim, const bool setZero=true)
Resets DVectorBase's dimension to newdim.
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis, bool isOptimal) const
int m_keptLRhs
number of kept left- and right-hand sides
UnitVectorBase< Real > UnitVector
const VectorBase< R > & upper() const
Returns upper bound vector.
Real m_epsilon
epsilon zero.
THREADLOCAL const Real infinity
Postsolves variable bound fixing.
Result
Result of the simplification.
the problem was so much simplified that it vanished
Postsolves duplicate rows.
int m_remNzos
number of removed nonzero coefficients
int size() const
Number of used indices.
void computeMinMaxResidualActivity(SPxLP &lp, int rowNumber, int colNumber, Real &minAct, Real &maxAct)
computes the minimum and maximum residual activity for a given row and column. If colNumber is set to...
Real m_feastol
primal feasibility tolerance.
DataArray< SPxSolver::VarStatus > m_rBasisStat
basis status of rows.
Real maxAbs(Real a, Real b)
returns max(|a|,|b|)
virtual void removeCols(int perm[])
Removes multiple columns.
bool LE(Real a, Real b, Real eps=Param::epsilon())
returns true iff a <= b + eps
bool LT(Real a, Real b, Real eps=Param::epsilon())
returns true iff a < b + eps
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis, bool isOptimal) const
SPxLP::SPxSense m_thesense
optimization sense.
bool NE(Real a, Real b, Real eps=Param::epsilon())
returns true iff |a-b| > eps
virtual Result simplify(SPxLP &lp, Real eps, Real delta)
simplify SPxLP lp with identical primal and dual feasibility tolerance.
friend class DuplicateRowsPS
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis, bool isOptimal) const
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis, bool isOptimal) const
int cIdx(int j) const
returns for a given column index of the (reduced) LP the corresponding column index in the unsimplifi...
variable fixed to identical bounds.
DVector m_dual
unsimplified dual solution vector.
R & value(int n)
Reference to value of n 'th nonzero.
General methods in LP preprocessing.
Postsolves empty constraints.
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis, bool isOptimal) const
int m_keptBnds
number of kept bounds
#define ASSERT_WARN(prefix, expr)
Macro to turn some assertions into warnings.
Real m_minReduction
minimal reduction (sum of removed rows/cols) to continue simplification
void remove(int n, int m)
Remove nonzeros n thru m.
void handleExtremes(SPxLP &lp)
handles extreme values by setting them to zero or infinity.
bool m_postsolved
status of postsolving.
int rIdx(int i) const
returns for a given row index of the (reduced) LP the corresponding row index in the unsimplified LP...
virtual void unsimplify(const Vector &x, const Vector &y, const Vector &s, const Vector &r, const SPxSolver::VarStatus rows[], const SPxSolver::VarStatus cols[], bool isOptimal=true)
reconstructs an optimal solution for the unsimplified LP.
SVectorBase< R > & rowVector_w(int i)
virtual void removeRows(int perm[])
Removes multiple rows.
void fixColumn(SPxLP &lp, int i, bool correctIdx=true)
handles the fixing of a variable. correctIdx is true iff the index mapping has to be updated...
virtual const std::string what() const
returns exception message
Wrapper for different output streams and verbosity levels.
int nRows() const
Returns number of rows in LP.
Exception class for out of memory exceptions.This class is derived from the SoPlex exception base cla...
virtual void start()=0
start timer, resume accounting user, system and real time.
virtual Real stop()=0
stop timer, return accounted user time.
void spx_alloc(T &p, int n=1)
Allocate memory.
simplification could be done
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis, bool isOptimal) const
Postsolves the case when constraints are removed due to a variable with zero objective that is free i...
int nNzos() const
Returns number of nonzeros in LP.
virtual const char * getName() const
get name of simplifying step.
friend class RowSingletonPS
Timer * m_timeUsed
user time used for simplification
nothing known about basis status (possibly due to a singular basis in transformed problem) ...
Array< DSVector > m_classSetCols
stores parallel classes with non-zero row entry
Result duplicateCols(SPxLP &lp, bool &again)
removes duplicate columns
void removeCol(SPxLP &lp, int j)
removes a column in the LP.
bool GT(Real a, Real b, Real eps=Param::epsilon())
returns true iff a > b + eps
SPxSense spxSense() const
Returns the optimization sense.
int & index(int n)
Reference to index of n 'th nonzero.
Postsolves row singletons.
virtual void changeMaxObj(const VectorBase< R > &newObj, bool scale=false)
Changes objective vector to newObj. scale determines whether the new data should be scaled...
std::ostream & operator<<(std::ostream &s, const VectorBase< R > &vec)
Output operator.
Result simplifyRows(SPxLP &lp, bool &again)
performs simplification steps on the rows of the LP.
bool checkSolution(SPxLP &lp, DVector sol)
checks a solution for feasibility
#define MSG_INFO2(spxout, x)
Prints out message x if the verbosity level is at least SPxOut::INFO2.
friend class DoubletonEquationPS
Postsolves doubleton equations combined with a column singleton.
Postsolves free column singletons.
virtual void changeLower(const VectorBase< R > &newLower, bool scale=false)
Changes vector of lower bounds to newLower. scale determines whether the new data should be scaled...
virtual void changeRhs(const VectorBase< R > &newRhs, bool scale=false)
Changes right hand side vector for constraints to newRhs. scale determines whether the new data shoul...
comparator for class SVector::Element: compare nonzeros according to value
R obj(int i) const
Returns objective value of column i.
const VectorBase< R > & lhs() const
Returns left hand side vector.
DataArray< int > m_cIdx
column index vector in original LP.
Result m_result
result of the simplification.
variable set to its upper bound.
bool GTrel(Real a, Real b, Real eps=Param::epsilon())
returns true iff relDiff(a,b) > eps
void SPxQuicksort(T *keys, int end, COMPARATOR &compare, int start=0, bool type=true)
Generic QuickSort implementation.
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis, bool isOptimal) const
virtual void changeBounds(const VectorBase< R > &newLower, const VectorBase< R > &newUpper, bool scale=false)
Changes variable bounds to newLower and newUpper. scale determines whether the new data should be sca...
primal infeasibility was detected
const VectorBase< R > & maxRowObj() const
bool GErel(Real a, Real b, Real eps=Param::epsilon())
returns true iff relDiff(a,b) > -eps
variable set to its lower bound.
Generic QuickSort implementation.
Array< DSVector > m_dupCols
arrange duplicate columns w.r.t. their pClass values
int m_remRows
number of removed rows
void add(int i, const R &v)
Append one nonzero (i,v).
virtual void changeUpper(const VectorBase< R > &newUpper, bool scale=false)
Changes vector of upper bounds to newUpper. scale determines whether the new data should be scaled...
Postsolves row objectives.
bool EQ(Real a, Real b, Real eps=Param::epsilon())
returns true iff |a-b| <= eps
virtual void changeObj(const VectorBase< R > &newObj, bool scale=false)
Changes objective vector to newObj. scale determines whether the new data should be scaled...
DataArray< int > m_rIdx
row index vector in original LP.
Postsolves column singletons with zero objective.
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis, bool isOptimal) const
virtual void addCol(const LPColBase< R > &col, bool scale=false)
int dim() const
Dimension of vector.
Exception base class.This class implements a base class for our SoPlex exceptions We provide a what()...
bool m_keepbounds
keep some bounds (for boundflipping)
Everything should be within this namespace.
virtual void changeRange(const VectorBase< R > &newLhs, const VectorBase< R > &newRhs, bool scale=false)
Changes left and right hand side vectors. scale determines whether the new data should be scaled...
bool EQrel(Real a, Real b, Real eps=Param::epsilon())
returns true iff |relDiff(a,b)| <= eps
virtual bool checkBasisDim(DataArray< SPxSolver::VarStatus > rows, DataArray< SPxSolver::VarStatus > cols) const
friend class ForceConstraintPS
void handleRowObjectives(SPxLP &lp)
handle row objectives
primal unboundedness was detected
#define MSG_WARNING(spxout, x)
Prints out message x if the verbosity level is at least SPxOut::WARNING.
Result duplicateRows(SPxLP &lp, bool &again)
removes duplicate rows.
Real m_cutoffbound
the cutoff bound that is found by heuristics
const VectorBase< R > & maxObj() const
Returns objective vector for maximization problem.
Exception class for incorrect usage of interface methods.
Result multiaggregation(SPxLP &lp, bool &again)
performs multi-aggregations of variable based upon constraint activitu.
Save arrays of arbitrary types.
Real m_objoffset
objective offset
friend class DuplicateColsPS
bool NErel(Real a, Real b, Real eps=Param::epsilon())
returns true iff |relDiff(a,b)| > eps
const SVectorBase< R > & rowVector(int i) const
Gets row vector of row i.
comparator for class SVector::Element: compare nonzeros according to index
virtual void changeRowObj(const VectorBase< R > &newRowObj, bool scale=false)
Changes row objective function vector to newRowObj. scale determines whether the new data should be s...
void trivialHeuristic(SPxLP &lp)
tries to find good lower bound solutions by applying some trivial heuristics
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis, bool isOptimal) const
int m_chgBnds
number of changed bounds
Postsolves duplicate columns.
Result removeEmpty(SPxLP &lp)
removed empty rows and empty columns.
int size() const
return nr. of elements.
Postsolves forcing constraints.
Result simplifyDual(SPxLP &lp, bool &again)
performs simplification steps on the LP based on dual concepts.
Postsolves unconstraint constraints.
int pos(int i) const
Position of index i.
bool isConsistent() const
Consistency check.
Postsolves variable bound tightening from pseudo objective propagation.
#define MSG_INFO1(spxout, x)
Prints out message x if the verbosity level is at least SPxOut::INFO1.
int m_remCols
number of removed columns
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis, bool isOptimal) const
const SVectorBase< R > & colVector(int i) const
Returns column vector of column i.
Postsolves variable fixing.
int nCols() const
Returns number of columns in LP.
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis, bool isOptimal) const
virtual void changeElement(int i, int j, const R &val, bool scale=false)
Changes LP element (i, j) to val. scale determines whether the new data should be scaled...
friend class FreeColSingletonPS
bool LErel(Real a, Real b, Real eps=Param::epsilon())
returns true iff relDiff(a,b) <= eps
virtual void changeLhs(const VectorBase< R > &newLhs, bool scale=false)
Changes left hand side vector for constraints to newLhs. scale determines whether the new data should...
Real m_pseudoobj
the pseudo objective function value
friend class FreeZeroObjVariablePS
void computeMinMaxValues(SPxLP &lp, Real side, Real val, Real minRes, Real maxRes, Real &minVal, Real &maxVal)
calculate min/max value for the multi aggregated variables
int m_addedcols
columns added by handleRowObjectives()
friend class ZeroObjColSingletonPS
bool isZero(Real a, Real eps=Param::epsilon())
returns true iff |a| <= eps
void removeRow(SPxLP &lp, int i)
removes a row in the LP.
friend class EmptyConstraintPS
virtual void reset()=0
initialize timer, set timing accounts to zero.
SPxOut * spxout
message handler
Save arrays of data objects.
SVectorBase< R > & colVector_w(int i)
Returns the LP as an LPRowSet.
int m_chgLRhs
number of change right-hand sides
Result simplifyCols(SPxLP &lp, bool &again)
performs simplification steps on the columns of the LP.
Array< DSVector > m_dupRows
arrange duplicate rows using bucket sort w.r.t. their pClass values
void reSize(int newsize)
reset size to newsize.
DVector m_slack
unsimplified slack vector.
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis, bool isOptimal) const
const VectorBase< R > & lower() const
Returns (internal and possibly scaled) lower bound vector.
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis, bool isOptimal) const
Set of indices.Class IdxSet provides a set of indices. At construction it must be given an array of i...
void spx_free(T &p)
Release memory.
DataArray< SPxSolver::VarStatus > m_cBasisStat
basis status of columns.
void propagatePseudoobj(SPxLP &lp)
tightens variable bounds by propagating the pseudo objective function value.
dual infeasibility was detected
Array< DSVector > m_classSetRows
stores parallel classes with non-zero colum entry
friend class FixVariablePS
DVector m_redCost
unsimplified reduced cost vector.