29 #define FREE_LHS_RHS 1 30 #define FREE_CONSTRAINT 1 31 #define EMPTY_CONSTRAINT 1 32 #define ROW_SINGLETON 1 33 #define AGGREGATE_VARS 1 34 #define FORCE_CONSTRAINT 1 37 #define EMPTY_COLUMN 1 38 #define FIX_VARIABLE 1 39 #define FREE_ZERO_OBJ_VARIABLE 1 40 #define ZERO_OBJ_COL_SINGLETON 1 41 #define DOUBLETON_EQUATION 1 42 #define FREE_COL_SINGLETON 1 44 #define DOMINATED_COLUMN 1 45 #define WEAKLY_DOMINATED_COLUMN 1 46 #define MULTI_AGGREGATE 1 48 #define TRIVIAL_HEURISTICS 1 57 #define DUPLICATE_ROWS 1 58 #define DUPLICATE_COLS 1 62 #define CHECK_BASIC_DIM 71 for(
int rs = 0; rs <
nRows; ++rs)
77 for(
int cs = 0; cs <
nCols; ++cs)
82 assert(numBasis == nRows);
83 return numBasis ==
nRows;
90 assert(
isZero(s[m_i], 1e-9));
97 MSG_DEBUG( std::cout <<
"RowObjPS: removing slack column " << m_j <<
" (" << cStatus[m_j] <<
") for row " << m_i <<
" (" << rStatus[m_i] <<
").\n" );
101 switch( cStatus[m_j] )
110 rStatus[m_i] = cStatus[m_j];
117 #ifdef CHECK_BASIC_DIM 133 rStatus[m_old_i] = rStatus[m_i];
138 for (
int k = 0; k < m_row.size(); ++k)
139 slack += m_row.value(k) * x[m_row.index(k)];
149 #ifdef CHECK_BASIC_DIM 164 rStatus[m_old_i] = rStatus[m_i];
175 #ifdef CHECK_BASIC_DIM 190 rStatus[m_old_i] = rStatus[m_i];
192 Real aij = m_col[m_i];
195 s[m_i] = aij * x[m_j];
200 for(
int k = 0; k < m_col.size(); ++k)
202 if (m_col.index(k) != m_i)
203 val -= m_col.value(k) * y[m_col.index(k)];
206 Real newLo = (aij > 0) ? m_lhs/aij : m_rhs/aij;
207 Real newUp = (aij > 0) ? m_rhs/aij : m_lhs/aij;
212 if(newLo <= m_oldLo && newUp >= m_oldUp)
221 assert(
EQrel(newLo, x[m_j],
eps()));
229 else if((
EQrel(m_oldLo, x[m_j],
eps()) && r[m_j] <= -
eps())
230 || (
EQrel(m_oldUp, x[m_j],
eps()) && r[m_j] >=
eps())
250 else if(
EQrel(newLo, m_oldUp,
eps()))
265 assert(
EQrel(m_oldUp, x[m_j],
eps()));
273 else if(
EQrel(newUp, m_oldLo,
eps()))
288 assert(
EQrel(m_oldLo, x[m_j],
eps()));
351 #ifdef CHECK_BASIC_DIM 366 rStatus[m_old_i] = rStatus[m_i];
372 int cBasisCandidate = -1;
373 Real maxViolation = -1.0;
376 for(
int k = 0; k < m_row.size(); ++k)
378 int cIdx = m_row.index(k);
379 Real aij = m_row.value(k);
380 Real oldLo = m_oldLowers[k];
381 Real oldUp = m_oldUppers[k];
383 switch(cStatus[cIdx])
394 if( violation > maxViolation && ( (
EQrel(oldLo, x[cIdx],
eps()) && r[cIdx] < -
eps()) || (
EQrel(oldUp, x[cIdx],
eps()) && r[cIdx] >
eps()) ) )
396 maxViolation = violation;
397 cBasisCandidate =
cIdx;
412 if(cBasisCandidate >= 0)
416 assert(cBasisCandidate == m_row.index(bas_k));
421 Real aij = m_row.value(bas_k);
422 Real multiplier = r[cBasisCandidate]/aij;
423 r[cBasisCandidate] = 0.0;
425 for(
int k = 0; k < m_row.size(); ++k)
431 r[m_row.index(k)] -= m_row.value(k) * multiplier;
435 Real val = m_objs[bas_k];
438 for(
int k = 0; k < basis_col.
size(); ++k)
440 if (basis_col.
index(k) != m_i)
441 val -= basis_col.
value(k) * y[basis_col.
index(k)];
452 #ifdef CHECK_BASIC_DIM 469 cStatus[m_old_j] = cStatus[m_j];
475 for(
int k = 0; k < m_col.size(); ++k)
476 s[m_col.index(k)] += m_col.value(k) * x[m_j];
481 for(
int k = 0; k < m_col.size(); ++k)
482 val -= m_col.value(k) * y[m_col.index(k)];
487 if( m_lower == m_upper )
489 assert(
EQrel(m_lower, m_val));
495 assert(
EQrel(m_val, m_lower) ||
EQrel(m_val, m_upper) || m_val == 0.0);
500 #ifdef CHECK_BASIC_DIM 516 cStatus[m_j] = m_status;
526 cStatus[m_old_j] = cStatus[m_j];
528 int rIdx = m_old_i - m_col.size() + 1;
530 for(
int k = 0; k < m_col.size(); ++k)
532 int rIdx_new = m_col.index(k);
533 s[
rIdx] = s[rIdx_new];
534 y[
rIdx] = y[rIdx_new];
535 rStatus[
rIdx] = rStatus[rIdx_new];
547 for(
int k = 0; k < m_rows.size(); ++k)
550 const SVector& row = m_rows[k];
552 for(
int l = 0; l < row.
size(); ++l)
554 if (row.
index(l) != m_j)
563 Real z = (m_lRhs[k] / scale) - (val / scale);
568 Real up = z * scale / row[m_j];
578 if (m_bnd < minRowUp)
590 for(
int k = 0; k < m_rows.size(); ++k)
593 const SVector& row = m_rows[k];
595 for(
int l = 0; l < row.
size(); ++l)
597 if (row.
index(l) != m_j)
606 Real z = (m_lRhs[k] / scale) - (val / scale);
611 Real lo = z * scale / row[m_j];
621 if (m_bnd > maxRowLo)
630 for(
int k = 0; k < m_col.size(); ++k)
631 s[m_col.index(k)] = slack[k] + m_col.value(k) * x[m_j];
636 for(
int k = 0; k < m_col.size(); ++k)
638 int idx = m_col.index(k);
639 y[idx] = m_rowObj[idx];
643 for(
int k = 0; k < m_col.size(); ++k)
665 #ifdef CHECK_BASIC_DIM 680 cStatus[m_old_j] = cStatus[m_j];
683 Real aij = m_row[m_j];
689 throw SPxException(
"Simplifier: infinite activities - aborting unsimplification");
699 Real z1 = (m_lhs / scale1) - (s[m_i] / scale1);
700 Real z2 = (m_rhs / scale2) - (s[m_i] / scale2);
707 Real lo = (aij > 0) ? z1 * scale1 / aij : z2 * scale2 / aij;
708 Real up = (aij > 0) ? z2 * scale2 / aij : z1 * scale1 / aij;
715 assert(
LErel(lo, up));
720 if ( m_lower <= -infinity && m_upper >=
infinity )
725 else if ( m_lower == m_upper )
745 if ( m_lower <= -infinity && m_upper >=
infinity )
750 else if ( m_lower == m_upper )
770 if ( m_lower <= -infinity && m_upper >=
infinity )
777 assert(
EQrel(m_lower, m_upper));
815 s[m_i] += aij * x[m_j];
818 r[m_j] = -1.0 * aij * y[m_i];
822 #ifdef CHECK_BASIC_DIM 838 rStatus[m_old_i] = rStatus[m_i];
843 cStatus[m_old_j] = cStatus[m_j];
847 Real aij = m_row[m_j];
849 for(
int k = 0; k < m_row.size(); ++k)
851 if (m_row.index(k) != m_j)
852 val += m_row.value(k) * x[m_row.index(k)];
860 Real z = (m_lRhs / scale) - (val / scale);
865 x[m_j] = z * scale / aij;
869 y[m_i] = m_obj / aij;
882 #ifdef CHECK_BASIC_DIM 899 (( m_maxSense && ((r[m_j] > 0 && m_strictUp) || (r[m_j] < 0 && m_strictLo))) ||
900 (!m_maxSense && ((r[m_j] > 0 && m_strictLo) || (r[m_j] < 0 && m_strictUp)))))))
903 Real aik = m_col[m_i];
905 for(
int _k = 0; _k < m_col.size(); ++_k)
907 if (m_col.index(_k) != m_i)
908 val -= m_col.value(_k) * y[m_col.index(_k)];
914 r[m_j] = m_jObj - val * m_aij / aik;
923 if(
GT(r[m_j], 0) || (
isZero(r[m_j]) &&
EQ(x[m_j], m_Lo_j)) )
932 #ifdef CHECK_BASIC_DIM 947 for(
int i = m_perm.size() - 1; i >= 0; --i)
951 int rIdx_new = m_perm[i];
953 s[
rIdx] = s[rIdx_new];
954 y[
rIdx] = y[rIdx_new];
955 rStatus[
rIdx] = rStatus[rIdx_new];
961 for(
int k = 0; k < m_scale.size(); ++k)
963 if (m_scale.index(k) != m_i)
964 s[m_scale.index(k)] = s[m_i] / m_scale.value(k);
968 bool haveSetBasis =
false;
970 for(
int k = 0; k < m_scale.size(); ++k)
972 int i = m_scale.index(k);
978 y[i] = m_rowObj.value(k);
985 if (rStatus[m_i] ==
SPxSolver::FIXED && (i == m_maxLhsIdx || i == m_minRhsIdx))
988 y[i] = y[m_i] * m_scale.value(k);
991 if(m_isLhsEqualRhs[k])
995 else if(i == m_maxLhsIdx)
1001 assert(i == m_minRhsIdx);
1007 haveSetBasis =
true;
1012 y[i] = y[m_i] * m_scale.value(k);
1013 y[m_i] = m_i_rowObj;
1018 haveSetBasis =
true;
1023 y[i] = y[m_i] * m_scale.value(k);
1024 y[m_i] = m_i_rowObj;
1029 haveSetBasis =
true;
1034 y[i] = m_rowObj.value(k);
1039 #ifdef CHECK_BASIC_DIM 1059 #ifdef CHECK_BASIC_DIM 1072 for(
int i = m_perm.size() - 1; i >= 0; --i)
1076 int cIdx_new = m_perm[i];
1078 x[
cIdx] = x[cIdx_new];
1079 r[
cIdx] = r[cIdx_new];
1080 cStatus[
cIdx] = cStatus[cIdx_new];
1129 assert(
LErel(m_loJ, 0.0));
1130 assert(
GErel(m_upJ, 0.0));
1131 assert(
LErel(m_loK, 0.0));
1132 assert(
GErel(m_upK, 0.0));
1140 else if (
LErel(m_loK, 0.0) &&
GErel(m_upK, 0.0))
1152 else if (
LErel(m_loJ, 0.0) &&
GErel(m_upJ, 0.0))
1167 Real z1 = (x[m_k] / scale1) - (m_loK / scale1);
1168 Real z2 = (x[m_k] / scale2) - (m_upK / scale2);
1175 if( m_loJ <= -infinity && m_upJ >=
infinity && m_loK <= -infinity && m_upK >=
infinity )
1180 else if( m_scale > 0.0 )
1182 if(
GErel(x[m_k], m_upK + m_scale * m_upJ) )
1187 x[m_k] -= m_scale * x[m_j];
1189 else if(
GErel(x[m_k], m_loK + m_scale * m_upJ) && m_upJ <
infinity )
1193 x[m_k] -= m_scale * x[m_j];
1195 else if(
GErel(x[m_k], m_upK + m_scale * m_loJ) && m_upK <
infinity )
1200 x[m_j] = z2 * scale2 / m_scale;
1202 else if(
GErel(x[m_k], m_loK + m_scale * m_loJ) && m_loJ > -
infinity )
1206 x[m_k] -= m_scale * x[m_j];
1208 else if(
GErel(x[m_k], m_loK + m_scale * m_loJ) && m_loK > -
infinity )
1213 x[m_j] = z1 * scale1 / m_scale;
1215 else if(
LTrel(x[m_k], m_loK + m_scale * m_loJ) )
1220 x[m_k] -= m_scale * x[m_j];
1229 assert(m_scale < 0.0);
1231 if(
GErel(x[m_k], m_upK + m_scale * m_loJ) )
1236 x[m_k] -= m_scale * x[m_j];
1238 else if(
GErel(x[m_k], m_loK + m_scale * m_loJ) && m_loJ > -
infinity )
1242 x[m_k] -= m_scale * x[m_j];
1244 else if(
GErel(x[m_k], m_upK + m_scale * m_upJ) && m_upK <
infinity )
1249 x[m_j] = z2 * scale2 / m_scale;
1251 else if(
GErel(x[m_k], m_loK + m_scale * m_upJ) && m_upJ <
infinity )
1255 x[m_k] -= m_scale * x[m_j];
1257 else if(
GErel(x[m_k], m_loK + m_scale * m_upJ) && m_loK > -
infinity )
1262 x[m_j] = z1 * scale1 / m_scale;
1264 else if(
LTrel(x[m_k], m_loK + m_scale * m_upJ) )
1269 x[m_k] -= m_scale * x[m_j];
1279 r[m_j] = m_scale * r[m_k];
1287 s[m_old_i] = s[m_i];
1288 y[m_old_i] = y[m_i];
1289 rStatus[m_old_i] = rStatus[m_i];
1292 x[m_old_j] = x[m_j];
1293 r[m_old_j] = r[m_j];
1294 cStatus[m_old_j] = cStatus[m_j];
1298 Real aij = m_row[m_j];
1299 int active_idx = -1;
1301 assert(m_row.size() == 2);
1302 for(
int k = 0; k < 2; ++k )
1304 if( m_row.index(k) != m_j )
1306 active_idx = m_row.index(k);
1307 val = m_row.value(k) * x[active_idx];
1311 assert(active_idx >= 0);
1318 Real z = (m_rhs / scale) - (val / scale);
1323 x[m_j] = z * scale / aij;
1326 if( isOptimal && (
LT(x[m_j], m_lower,
eps()) ||
GT(x[m_j], m_upper,
eps())) )
1328 MSG_ERROR( std::cerr <<
"EMAISM: numerical violation after disaggregating variable" << std::endl; )
1334 for(
int k = 0; k < m_col.size(); ++k)
1336 if(m_col.index(k) != m_i)
1337 dualVal += m_col.value(k) * y[m_col.index(k)];
1340 z = m_obj - dualVal;
1347 &&
NE(x[active_idx], m_oldupper,
eps())) ||
1349 &&
NE(x[active_idx], m_oldlower,
eps())) )
1352 r[active_idx] = 0.0;
1353 assert(
NE(m_upper, m_lower));
1354 if(
EQ(x[m_j], m_upper,
eps()) )
1356 else if(
EQ(x[m_j], m_lower,
eps()) )
1372 #ifdef CHECK_BASIC_DIM 1386 s[m_old_i] = s[m_i];
1387 y[m_old_i] = y[m_i];
1388 rStatus[m_old_i] = rStatus[m_i];
1391 x[m_old_j] = x[m_j];
1392 r[m_old_j] = r[m_j];
1393 cStatus[m_old_j] = cStatus[m_j];
1397 Real aij = m_row[m_j];
1399 for(
int k = 0; k < m_row.size(); ++k)
1401 if(m_row.index(k) != m_j)
1402 val += m_row.value(k) * x[m_row.index(k)];
1410 Real z = (m_const / scale) - (val / scale);
1415 x[m_j] = z * scale / aij;
1419 if( isOptimal && (
LT(x[m_j], m_lower,
eps()) ||
GT(x[m_j], m_upper,
eps())) )
1420 MSG_ERROR( std::cerr <<
"numerical violation in original space due to MultiAggregation\n"; )
1426 for(
int k = 0; k < m_col.size(); ++k)
1428 if(m_col.index(k) != m_i)
1429 dualVal += m_col.value(k) * y[m_col.index(k)];
1432 z = m_obj - dualVal;
1447 #ifdef CHECK_BASIC_DIM 1460 switch(cStatus[m_j])
1463 if(
LT(x[m_j], m_origupper,
eps()) &&
GT(x[m_j], m_origlower,
eps()))
1465 else if(
LT(x[m_j], m_origupper,
eps()))
1467 else if(
GT(x[m_j], m_origlower,
eps()))
1472 if(
GT(x[m_j], m_origlower,
eps()))
1477 if(
LT(x[m_j], m_origupper,
eps()))
1485 #ifdef CHECK_BASIC_DIM 1495 for(
int i = lp.
nRows() - 1; i >= 0; --i )
1527 for(
int i = lp.
nRows()-1; i >= 0; --i)
1537 else if (lhs > -
infinity && lhs < -maxVal)
1542 else if (lhs < infinity && lhs > maxVal)
1556 else if (rhs > -
infinity && rhs < -maxVal)
1561 else if (rhs < infinity && rhs > maxVal)
1580 for(
int j = 0; j < lp.
nCols(); ++j)
1590 else if (lo > -
infinity && lo < -maxVal)
1595 else if (lo < infinity && lo > maxVal)
1609 else if (up > -
infinity && up < -maxVal)
1614 else if (up < infinity && up > maxVal)
1626 Real absBnd = (lo > up) ? lo : up;
1635 while(i < col.
size())
1639 if (
isZero(aij * absBnd, tol))
1642 int row_j = row.
pos(j);
1650 <<
" removed, absBnd=" << absBnd
1660 else if(
isZero(aij, tol) )
1678 else if (obj > -
infinity && obj < -maxVal)
1683 else if (obj < infinity && obj > maxVal)
1690 if (remRows + remNzos + chgLRhs + chgBnds + objCnt > 0)
1698 << remRows <<
" rows, " 1699 << remNzos <<
" non-zeros, " 1700 << chgBnds <<
" col bounds, " 1701 << chgLRhs <<
" row bounds, " 1702 << objCnt <<
" objective coefficients" << std::endl; )
1711 bool minNegInfinite =
false;
1712 bool maxInfinite =
false;
1717 for (
int l = 0; l < row.
size(); ++l)
1719 if (colNumber < 0 || row.
index(l) != colNumber)
1725 minNegInfinite =
true;
1729 else if (
LT(row.
value(l), 0.0))
1732 minNegInfinite =
true;
1745 else if (
LT(row.
value(l), 0.0))
1776 minVal = (side - minRes)/val;
1781 maxVal = (side - maxRes)/val;
1783 else if(
GT(val, 0.0))
1788 minVal = (side - maxRes)/val;
1793 maxVal = (side - minRes)/val;
1814 bool zerovalid =
true;
1822 for(
int j = lp.
nCols()-1; j >= 0; --j)
1829 for(
int k = 0; k < col.
size(); ++k)
1860 lower =
MINIMUM(-largeValue, upper);
1872 lowersol[j] = lower;
1873 uppersol[j] = upper;
1875 if(downLocks[j] > upLocks[j])
1877 else if(downLocks[j] < upLocks[j])
1880 locksol[j] = (lower + upper)/2.0;
1882 lowerObj += lp.
maxObj(j)*lowersol[j];
1883 upperObj += lp.
maxObj(j)*uppersol[j];
1884 lockObj += lp.
maxObj(j)*locksol[j];
1920 for(
int i = lp.
nRows()-1; i >= 0; --i)
1925 for(
int k = 0; k < row.
size(); k++)
1942 for(
int j = lp.
nCols()-1; j >= 0; --j )
1949 pseudoObj += val*lp.
lower(j);
1955 pseudoObj += val*lp.
upper(j);
1964 for(
int j = lp.
nCols()-1; j >= 0; --j)
1983 else if(objval > 0.0)
2008 for(
int i = lp.
nRows()-1; i >= 0; --i)
2012 if (row.
size() == 0)
2020 <<
" rhs=" << lp.
rhs(i) << std::endl; )
2036 for(
int j = lp.
nCols()-1; j >= 0; --j)
2040 if (col.
size() == 0)
2043 <<
": empty -> maxObj=" << lp.
maxObj(j)
2044 <<
" lower=" << lp.
lower(j)
2045 <<
" upper=" << lp.
upper(j); )
2094 if (remRows + remCols > 0)
2100 << remRows <<
" rows, " 2101 << remCols <<
" cols" 2110 assert(row.
size() == 1);
2113 int j = row.
index(0);
2118 <<
": singleton -> val=" << aij
2119 <<
" lhs=" << lp.
lhs(i)
2120 <<
" rhs=" << lp.
rhs(i); )
2146 <<
" (" << lp.
lower(j)
2148 <<
" (" << lp.
upper(j)
2149 <<
")" << std::endl; )
2151 bool stricterUp =
false;
2152 bool stricterLo =
false;
2184 assert(row.
size() == 2);
2188 assert(rhs < infinity && rhs > -
infinity);
2190 int j = row.
index(0);
2191 int k = row.
index(1);
2205 MSG_DEBUG( (*
spxout) <<
"IMAISM22 row " << i <<
": doubleton equation -> " 2206 << aij <<
" x_" << j <<
" + " << aik <<
" x_" << k <<
" = " << rhs; )
2213 if( aij * aik < 0.0 )
2216 new_lo_j = (upper_k >=
infinity) ? -
infinity : (rhs - aik * upper_k) / aij;
2217 new_up_j = (lower_k <= -
infinity) ?
infinity : (rhs - aik * lower_k) / aij;
2218 new_lo_k = (upper_j >=
infinity) ? -
infinity : (rhs - aij * upper_j) / aik;
2219 new_up_k = (lower_j <= -
infinity) ?
infinity : (rhs - aij * lower_j) / aik;
2221 else if( aij * aik > 0.0 )
2224 new_lo_j = (lower_k <= -
infinity) ? -
infinity : (rhs - aik * lower_k) / aij;
2226 new_lo_k = (lower_j <= -
infinity) ? -
infinity : (rhs - aij * lower_j) / aik;
2232 bool flip_jk =
false;
2233 if( new_lo_j <= -infinity && new_up_j >=
infinity )
2238 else if( new_lo_k <= -infinity && new_up_k >=
infinity )
2243 else if(
LE(new_lo_j, lower_j) &&
GE(new_up_j, upper_j) )
2245 if(
LE(new_lo_k, lower_k) &&
GE(new_up_k, upper_k) )
2256 else if(
LE(new_lo_k, lower_k) &&
GE(new_up_k, upper_k) )
2272 Real _lower_j = lower_j;
2273 Real _upper_j = upper_j;
2288 Real aggr_coef = - (aik / aij);
2289 Real aggr_const = rhs / aij;
2292 << aggr_const <<
" + " << aggr_coef <<
" * x_" << k << std::endl; )
2295 for(
int r = 0; r < col_j.
size(); ++r )
2297 int row_r = col_j.
index(r);
2309 lp.
changeLhs(row_r, lhs_r - aggr_const * arj);
2314 lp.
changeRhs(row_r, rhs_r - aggr_const * arj);
2318 Real newcoef = aggr_coef * arj;
2319 int pos_rk = col_k.
pos(row_r);
2339 lp.
changeObj(k, obj_k + aggr_coef * obj_j);
2351 Real z1 = (rhs / scale1) - (aij * upper_j / scale1);
2352 Real z2 = (rhs / scale2) - (aij * lower_j / scale2);
2366 else if(
LT(aik * aij, 0.0,
epsZero()) )
2375 Real oldlower_k = lower_k;
2376 Real oldupper_k = upper_k;
2391 m_hist.append(
new (AggregationPSptr)
AggregationPS(lp, i, j, rhs, oldupper_k, oldlower_k));
2427 int oldRows = lp.
nRows();
2429 bool redundantLower;
2430 bool redundantUpper;
2434 for(
int i = lp.
nRows()-1; i >= 0; --i)
2445 for(
int k = 0; k < row.
size(); ++k)
2448 int j = row.
index(k);
2452 MSG_WARNING( (*
spxout), (*
spxout) <<
"Warning: tiny nonzero coefficient " << aij <<
" in row " << i <<
"\n" );
2460 lhsBnd += aij * lp.
lower(j);
2465 rhsBnd += aij * lp.
upper(j);
2472 rhsBnd += aij * lp.
lower(j);
2477 lhsBnd += aij * lp.
upper(j);
2483 if (rhsCnt <= 1 || lhsCnt <= 1)
2485 for(
int k = 0; k < row.
size(); ++k)
2488 int j = row.
index(k);
2490 redundantLower =
false;
2491 redundantUpper =
false;
2507 Real z = (lp.
lhs(i) / scale) - (rhsBnd / scale);
2515 lo = lp.
upper(j) + z * scale / aij;
2517 lo = z * scale / aij;
2525 <<
": redundant lower bound on x" << j
2526 <<
" -> lower=" << lo
2527 <<
" (" << lp.
lower(j)
2528 <<
")" << std::endl; )
2530 redundantLower =
true;
2544 Real z = (lp.
rhs(i) / scale) - (lhsBnd / scale);
2552 up = lp.
lower(j) + z * scale / aij;
2554 up = z * scale / aij;
2562 <<
": redundant upper bound on x" << j
2563 <<
" -> upper=" << up
2564 <<
" (" << lp.
upper(j)
2565 <<
")" << std::endl; )
2567 redundantUpper =
true;
2576 lhsBnd -= aij * lp.
lower(j);
2590 rhsBnd -= aij * lp.
upper(j);
2611 Real z = (lp.
lhs(i) / scale) - (rhsBnd / scale);
2619 up = lp.
lower(j) + z * scale / aij;
2621 up = z * scale / aij;
2629 <<
": redundant upper bound on x" << j
2630 <<
" -> upper=" << up
2631 <<
" (" << lp.
upper(j)
2632 <<
")" << std::endl; )
2634 redundantUpper =
true;
2647 Real z = (lp.
rhs(i) / scale) - (lhsBnd / scale);
2655 lo = lp.
upper(j) + z * scale / aij;
2657 lo = z * scale / aij;
2665 <<
": redundant lower bound on x" << j
2666 <<
" -> lower=" << lo
2667 <<
" (" << lp.
lower(j)
2668 <<
")" << std::endl; )
2670 redundantLower =
true;
2679 lhsBnd -= aij * lp.
upper(j);
2693 rhsBnd -= aij * lp.
lower(j);
2708 redundantLhs =
false;
2709 redundantRhs =
false;
2715 <<
": redundant lhs -> lhsBnd=" << lhsBnd
2716 <<
" lhs=" << lp.
lhs(i)
2719 redundantLhs =
true;
2724 <<
": redundant rhs -> rhsBnd=" << rhsBnd
2725 <<
" rhs=" << lp.
rhs(i)
2728 redundantRhs =
true;
2760 <<
": infeasible -> lhs=" << lp.
lhs(i)
2761 <<
" rhs=" << lp.
rhs(i)
2762 <<
" lhsBnd=" << lhsBnd
2763 <<
" rhsBnd=" << rhsBnd
2773 <<
": unconstrained -> removed" << std::endl; )
2780 remNzos += row.
size();
2789 #if EMPTY_CONSTRAINT 2791 if (row.
size() == 0)
2799 <<
" rhs=" << lp.
rhs(i) << std::endl; )
2819 if (row.
size() == 1)
2835 #if FORCE_CONSTRAINT 2841 <<
": forcing constraint fix on lhs ->" 2842 <<
" lhs=" << lp.
lhs(i)
2843 <<
" rhsBnd=" << rhsBnd
2850 for(
int k = 0; k < row.
size(); ++k)
2853 int j = row.
index(k);
2857 lowers[k] = lp.
lower(j);
2858 uppers[k] = lp.
upper(j);
2873 remNzos += row.
size();
2884 <<
": forcing constraint fix on rhs ->" 2885 <<
" rhs=" << lp.
rhs(i)
2886 <<
" lhsBnd=" << lhsBnd
2893 for(
int k = 0; k < row.
size(); ++k)
2896 int j = row.
index(k);
2900 lowers[k] = lp.
lower(j);
2901 uppers[k] = lp.
upper(j);
2916 remNzos += row.
size();
2926 assert(remRows > 0 || remNzos == 0);
2928 if (remRows + chgLRhs + chgBnds > 0)
2938 << remRows <<
" rows, " 2939 << remNzos <<
" non-zeros, " 2940 << chgBnds <<
" col bounds, " 2941 << chgLRhs <<
" row bounds; kept " 2942 << keptBnds <<
" column bounds, " 2943 << keptLRhs <<
" row bounds" 2971 int oldCols = lp.
nCols();
2972 int oldRows = lp.
nRows();
2974 for(
int j = lp.
nCols()-1; j >= 0; --j)
2982 <<
": infeasible bounds on x" << j
2983 <<
" -> lower=" << lp.
lower(j)
2984 <<
" upper=" << lp.
upper(j)
2990 if (col.
size() == 0)
2994 <<
": empty -> maxObj=" << lp.
maxObj(j)
2995 <<
" lower=" << lp.
lower(j)
2996 <<
" upper=" << lp.
upper(j); )
3054 for(
int k = 0; k < col.
size(); ++k)
3056 if (!loFree && !upFree)
3059 int i = col.
index(k);
3064 if (col.
value(k) > 0.0)
3072 else if (col.
value(k) < 0.0)
3090 <<
" unconstrained above ->"; )
3111 <<
" unconstrained below ->"; )
3129 #if FREE_ZERO_OBJ_VARIABLE 3130 bool unconstrained_below = loFree && lp.
lower(j) <= -
infinity;
3131 bool unconstrained_above = upFree && lp.
upper(j) >=
infinity;
3133 if (unconstrained_below || unconstrained_above)
3137 <<
" unconstrained " 3138 << (unconstrained_below ?
"below" :
"above")
3139 <<
" with zero objective (" << lp.
maxObj(j)
3140 <<
")" << std::endl; )
3146 SPxQuicksort(col_idx_sorted.mem(), col_idx_sorted.size(), compare);
3154 remRows += col.
size();
3155 for(
int k = col_idx_sorted.size()-1; k >= 0; --k)
3162 for(
int k = 0; k < col.
size(); ++k)
3164 int l = col.
index(k);
3183 <<
" fixed -> lower=" << lp.
lower(j)
3184 <<
" upper=" << lp.
upper(j) << std::endl; )
3189 remNzos += col.
size();
3199 if (col.
size() == 1)
3202 int i = col.
index(0);
3207 #if ZERO_OBJ_COL_SINGLETON 3209 <<
": singleton in row " << i
3210 <<
" with zero objective"; )
3218 lhs = lp.
lhs(i) - aij * lp.
upper(j);
3220 rhs = lp.
rhs(i) - aij * lp.
lower(j);
3225 lhs = lp.
lhs(i) - aij * lp.
lower(j);
3227 rhs = lp.
rhs(i) - aij * lp.
upper(j);
3241 <<
" (" << lp.
lhs(i)
3243 <<
" (" << lp.
rhs(i)
3244 <<
")" << std::endl; )
3279 #if DOUBLETON_EQUATION 3281 <<
": singleton in row " << i
3282 <<
" with doubleton equation ->"; )
3291 if (row.
index(0) == j)
3296 else if (row.
index(1) == j)
3318 Real z1 = (lhs / scale1) - (aij * lp.
upper(j) / scale1);
3319 Real z2 = (lhs / scale2) - (aij * lp.
lower(j) / scale2);
3346 <<
": lower=" << lp.
lower(k)
3348 <<
") upper=" << lp.
upper(k)
3350 <<
")" << std::endl; )
3378 #if FREE_COL_SINGLETON 3385 <<
": free singleton in inequality constraint" << std::endl; )
3432 <<
": free singleton removed" << std::endl; )
3436 for (
int h = 0; h < row.size(); ++h)
3438 int k = row.
index(h);
3442 Real new_obj = lp.
obj(k) - (lp.
obj(j) * row.value(h) / aij);
3449 remNzos += row.size();
3461 if (remCols + remRows > 0)
3469 << remRows <<
" rows, " 3470 << remCols <<
" cols, " 3471 << remNzos <<
" non-zeros, " 3472 << chgBnds <<
" col bounds" 3494 int oldRows = lp.
nRows();
3495 int oldCols = lp.
nCols();
3504 for(
int i = lp.
nRows()-1; i >= 0; --i)
3510 <<
": unconstrained" << std::endl; )
3531 for(
int j = 0; j < lp.
nCols(); ++j)
3545 dualVarUp[i] = bound;
3547 dualVarLo[i] = bound;
3552 dualVarLo[i] = bound;
3554 dualVarUp[i] = bound;
3561 for(
int j = 0; j < lp.
nCols(); ++j)
3563 dualConsLo[j] = dualConsUp[j] = 0.0;
3567 for(
int k = 0; k < col.
size(); ++k)
3573 int i = col.
index(k);
3582 dualConsLo[j] += aij * dualVarLo[i];
3587 dualConsUp[j] += aij * dualVarUp[i];
3594 dualConsUp[j] += aij * dualVarLo[i];
3599 dualConsLo[j] += aij * dualVarUp[i];
3604 for(
int j = lp.
nCols()-1; j >= 0; --j)
3610 if (
LTrel(dualConsUp[j], dualConsLo[j],
opttol()))
3613 <<
": dual infeasible -> dual lhs bound=" << dualConsLo[j]
3614 <<
" dual rhs bound=" << dualConsUp[j] << std::endl; )
3624 #if DOMINATED_COLUMN 3626 <<
": dominated -> maxObj=" << obj
3627 <<
" dual rhs bound=" << dualConsUp[j] << std::endl; )
3647 #if DOMINATED_COLUMN 3649 <<
": dominated -> maxObj=" << obj
3650 <<
" dual lhs bound=" << dualConsLo[j] << std::endl; )
3672 #if WEAKLY_DOMINATED_COLUMN 3674 <<
": weakly dominated -> maxObj=" << obj
3675 <<
" dual rhs bound=" << dualConsUp[j] << std::endl; )
3687 #if WEAKLY_DOMINATED_COLUMN 3689 <<
": weakly dominated -> maxObj=" << obj
3690 <<
" dual lhs bound=" << dualConsLo[j] << std::endl; )
3717 assert(remRows > 0 || remCols > 0 || remNzos == 0);
3719 if (remCols + remRows > 0)
3726 << remRows <<
" rows, " 3727 << remCols <<
" cols, " 3728 << remNzos <<
" non-zeros" 3746 int oldRows = lp.
nRows();
3747 int oldCols = lp.
nCols();
3752 for(
int j = lp.
nCols()-1; j >= 0; --j)
3762 for(
int k = 0; k < col.
size(); ++k)
3790 if (upLocks[j] == 1 || downLocks[j] == 1)
3796 bool bestislhs =
true;
3798 for(
int k = 0; k < col.
size(); ++k)
3810 rowNumber = col.
index(k);
3811 lhs = lp.
lhs(rowNumber);
3812 rhs = lp.
rhs(rowNumber);
3821 maxOtherLocks = INT_MAX;
3830 && ((col.
value(k) > 0.0 && lp.
maxObj(j) <= 0.0 && downLocks[j] == 1 && upLocks[j] <= maxOtherLocks)
3831 || (col.
value(k) < 0.0 && lp.
maxObj(j) >= 0.0 && upLocks[j] == 1 && downLocks[j] <= maxOtherLocks));
3833 && ((col.
value(k) > 0.0 && lp.
maxObj(j) >= 0.0 && upLocks[j] == 1 && downLocks[j] <= maxOtherLocks)
3834 || (col.
value(k) < 0.0 && lp.
maxObj(j) <= 0.0 && downLocks[j] == 1 && upLocks[j] <= maxOtherLocks));
3836 if (aggLhs || aggRhs)
3853 assert(
LE(minVal, maxVal));
3859 bestpos = col.
index(k);
3874 assert(
LE(minVal, maxVal));
3879 bestpos = col.
index(k);
3892 Real aggConstant = (bestislhs ? lp.
lhs(bestpos) : lp.
rhs(bestpos));
3893 Real aggAij = bestRow[j];
3896 (*
spxout) <<
"IMAISM51 col " << j
3897 <<
": Aggregating row: " << bestpos
3898 <<
" Aggregation Constant=" << aggConstant
3899 <<
" Coefficient of aggregated col=" << aggAij << std::endl;
3906 for(
int k = 0; k < col.
size(); ++k)
3908 if(col.
index(k) != bestpos)
3910 int rowNumber = col.
index(k);
3918 for(
int l = 0; l < bestRow.
size(); l++)
3920 if(bestRow.
index(l) != j)
3924 - updateRow[j]*bestRow.
value(l)/aggAij);
3932 lp.
changeRhs(rowNumber, updateRhs - updateRow[j]*aggConstant/aggAij);
3934 lp.
changeLhs(rowNumber, updateLhs - updateRow[j]*aggConstant/aggAij);
3936 assert(
LE(lp.
lhs(rowNumber), lp.
rhs(rowNumber)));
3940 for(
int l = 0; l < bestRow.
size(); l++)
3942 if(bestRow.
index(l) != j)
3959 assert(remRows > 0 || remCols > 0 || remNzos == 0);
3961 if (remCols + remRows > 0)
3968 << remRows <<
" rows, " 3969 << remCols <<
" cols, " 3970 << remNzos <<
" non-zeros" 3992 int oldRows = lp.
nRows();
4001 for (
int i = 0; i < lp.
nRows(); ++i)
4005 if (row.
size() == 1)
4015 << rs_remRows <<
" rows, " 4016 << rs_remRows <<
" non-zeros" 4044 classSize[0] = lp.
nRows();
4046 for(
int i = 1; i < lp.
nRows(); ++i)
4057 for(
int j = 0; j < lp.
nCols(); ++j)
4061 for(
int k = 0; k < col.
size(); ++k)
4064 int i = col.
index(k);
4066 if (scale[i] == 0.0)
4070 if (--classSize[pClass[i]] == 0)
4071 idxSet.addIdx(pClass[i]);
4075 for(
int m = 0; m < col.
size(); ++m)
4077 int k = pClass[col.
index(m)];
4088 int classIdx = idxSet.index(0);
4095 classIdx = idxSet.index(0);
4100 ++classSize[classIdx];
4102 oldVal = m_classSetRows[k].value(l);
4114 for(
int k = 0; k < lp.
nRows(); ++k )
4117 for(
int k = 0; k < lp.
nRows(); ++k)
4123 const int nRowsOld_tmp = lp.
nRows();
4127 for(
int j = 0; j < nRowsOld_tmp; ++j)
4132 int idxFirstDupRows = -1;
4133 int idxLastDupRows = -1;
4136 for(
int k = 0; k < lp.
nRows(); ++k)
4142 if(idxFirstDupRows < 0)
4144 idxFirstDupRows = k;
4147 for(
int l = 1; l <
m_dupRows[k].size(); ++l)
4158 int k_tmp, j_tmp = -1;
4159 for (k_tmp = j_tmp = 0; k_tmp < nRowsOld_tmp; ++k_tmp)
4161 if (perm_tmp[k_tmp] >= 0)
4162 perm_tmp[k_tmp] = j_tmp++;
4167 bool doChangeRanges =
false;
4171 for(
int k = 0; k < lp.
nRows(); ++k)
4176 <<
" duplicate rows found" << std::endl; )
4190 for(
int l = 0; l <
m_dupRows[k].size(); ++l)
4193 isLhsEqualRhs[l] = (lp.
lhs(i) == lp.
rhs(i));
4200 maxLhs = lp.
lhs(rowIdx);
4201 minRhs = lp.
rhs(rowIdx);
4205 Real scaledLhs, scaledRhs;
4206 Real factor = scale[rowIdx] / scale[i];
4218 if (scaledLhs > maxLhs)
4223 if (scaledRhs < minRhs)
4235 Real newLhs = (maxLhs > lp.
lhs(rowIdx)) ? maxLhs : lp.
lhs(rowIdx);
4236 Real newRhs = (minRhs < lp.
rhs(rowIdx)) ? minRhs : lp.
rhs(rowIdx);
4238 if(k == idxLastDupRows)
4241 for(
int j = 0; j < nRowsOld_tmp; ++j)
4243 da_perm[j] = perm_tmp[j];
4247 m_hist.append(
new (DuplicateRowsPSptr)
DuplicateRowsPS(lp, rowIdx, maxLhsIdx, minRhsIdx,
m_dupRows[k], scale, da_perm, isLhsEqualRhs,
true,
EQrel(newLhs, newRhs), k==idxFirstDupRows));
4254 m_hist.append(
new (DuplicateRowsPSptr)
DuplicateRowsPS(lp, rowIdx, maxLhsIdx, minRhsIdx,
m_dupRows[k], scale, da_perm_empty, isLhsEqualRhs,
false,
EQrel(newLhs, newRhs), k == idxFirstDupRows));
4257 if (maxLhs > lp.
lhs(rowIdx) || minRhs < lp.
rhs(rowIdx))
4260 doChangeRanges =
true;
4264 MSG_DEBUG( (*
spxout) <<
"IMAISM55 duplicate rows yield infeasible bounds:" 4265 <<
" lhs=" << newLhs
4266 <<
" rhs=" << newRhs << std::endl; )
4271 if( newRhs < newLhs )
4274 newLhsVec[rowIdx] = newLhs;
4275 newRhsVec[rowIdx] = newRhs;
4288 const int nRowsOld = lp.
nRows();
4292 for(
int i = 0; i < nRowsOld; ++i)
4305 for(
int i = 0; i < nRowsOld; ++i)
4308 assert(perm[i] == perm_tmp[i]);
4318 if (remRows + remNzos > 0)
4324 << remRows <<
" rows, " 4325 << remNzos <<
" non-zeros" 4371 classSize[0] = lp.
nCols();
4373 for(
int j = 1; j < lp.
nCols(); ++j)
4384 for(
int i = 0; i < lp.
nRows(); ++i)
4388 for(
int k = 0; k < row.
size(); ++k)
4391 int j = row.
index(k);
4393 if (scale[j] == 0.0)
4397 if (--classSize[pClass[j]] == 0)
4398 idxSet.addIdx(pClass[j]);
4402 for(
int m = 0; m < row.
size(); ++m)
4404 int k = pClass[row.
index(m)];
4415 int classIdx = idxSet.index(0);
4423 classIdx = idxSet.index(0);
4428 ++classSize[classIdx];
4430 oldVal = m_classSetCols[k].value(l);
4443 for(
int k = 0; k < lp.
nCols(); ++k )
4446 for(
int k = 0; k < lp.
nCols(); ++k)
4449 fixAndRemCol[k] =
false;
4453 bool hasDuplicateCol =
false;
4456 for(
int k = 0; k < lp.
nCols(); ++k)
4461 <<
" duplicate columns found" << std::endl; )
4463 if (!hasDuplicateCol)
4468 hasDuplicateCol =
true;
4471 for(
int l = 0; l <
m_dupCols[k].size(); ++l)
4473 for(
int m = 0; m <
m_dupCols[k].size(); ++m)
4478 if (l != m && !remCol[j1] && !remCol[j2])
4484 Real factor = scale[j1] / scale[j2];
4485 Real objDif = cj1 - cj2 * scale[j1] / scale[j2];
4516 else if (factor < 0)
4531 <<
" replaced by one" << std::endl; )
4539 MSG_DEBUG( (*
spxout) <<
"IMAISM80 not removing two duplicate columns " << j1
4541 <<
" because zero not contained in their bounds" << std::endl; )
4550 if (factor > 0 && objDif > 0)
4561 <<
" first one fixed at upper bound=" << lp.
upper(j1) << std::endl; )
4568 else if (factor < 0 && objDif < 0)
4579 <<
" first one fixed at lower bound=" << lp.
lower(j1) << std::endl; )
4590 if (factor < 0 && objDif > 0)
4601 <<
" first one fixed at upper bound=" << lp.
upper(j1) << std::endl; )
4610 else if (factor > 0 && objDif < 0)
4621 <<
" first one fixed at lower bound=" << lp.
lower(j1) << std::endl; )
4632 fixAndRemCol[j1] =
true;
4643 for(
int j = 0; j < lp.
nCols(); ++j)
4655 const int nColsOld = lp.
nCols();
4659 for(
int j = 0; j < nColsOld; ++j)
4672 for(
int j = 0; j < nColsOld; ++j)
4679 for(
int j = 0; j < nColsOld; ++j)
4681 da_perm[j] = perm[j];
4684 if (hasDuplicateCol)
4693 assert(remCols > 0 || remNzos == 0);
4701 << remCols <<
" cols, " 4702 << remNzos <<
" non-zeros" 4723 <<
": lower=" << lp.
lower(j)
4724 <<
" upper=" << lp.
upper(j)
4729 for(
int k = 0; k < col.
size(); ++k)
4731 int i = col.
index(k);
4741 Real rhs = (lp.
rhs(i) / scale) - (y / scale);
4750 <<
" (" << lp.
rhs(i)
4751 <<
") aij=" << col.
value(k)
4764 Real lhs = (lp.
lhs(i) / scale) - (y / scale);
4773 <<
" (" << lp.
lhs(i)
4774 <<
") aij=" << col.
value(k)
4779 assert(lp.
lhs(i) <= lp.
rhs(i));
4817 for(
int k = 0; k <
m_hist.size(); ++k)
4843 int numRangedRows = 0;
4844 int numBoxedCols = 0;
4845 int numEqualities = 0;
4847 for(
int i = 0; i < lp.
nRows(); ++i )
4857 for(
int j = 0; j < lp.
nCols(); ++j)
4861 (*spxout) <<
"LP has " 4862 << numEqualities <<
" equations, " 4863 << numRangedRows <<
" ranged rows, " 4864 << numBoxedCols <<
" boxed columns" 4892 for(
int i = 0; i < lp.
nRows(); ++i)
4895 for(
int j = 0; j < lp.
nCols(); ++j)
4937 #if TRIVIAL_HEURISTICS 4964 << m_remCols <<
" columns, " 4977 << lp.
nRows() <<
" rows " 4978 << lp.
nCols() <<
" columns " 4979 << lp.
nNzos() <<
" nonzeros" 4983 int numRangedRows = 0;
4984 int numBoxedCols = 0;
4985 int numEqualities = 0;
4987 for(
int i = 0; i < lp.
nRows(); ++i )
4997 for(
int j = 0; j < lp.
nCols(); ++j)
5001 (*spxout) <<
"Reduced LP has " 5002 << numEqualities <<
" equations, " 5003 << numRangedRows <<
" ranged rows, " 5004 << numBoxedCols <<
" boxed columns" 5045 assert(x.
dim() == r.
dim());
5046 assert(y.
dim() == s.
dim());
5051 for(
int j = 0; j < x.
dim(); ++j)
5057 for(
int i = 0; i < y.
dim(); ++i)
5065 for(
int k =
m_hist.size()-1; k >= 0; --k)
5103 #ifdef CHECK_BASIC_DIM 5139 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
virtual void addObjoffset(const Real val)
add objective offset.
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.
#define MSG_ERROR(x)
Prints out message x if the verbosity level is at least SPxOut::ERROR.
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
#define MSG_INFO3(spxout, x)
Prints out message x if the verbosity level is at least SPxOut::INFO3.
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
Result aggregateVars(SPxLP &lp, const SVector &row, int &i)
aggregate two variables that appear in an equation.
#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.
friend class AggregationPS
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 execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis, bool isOptimal) const
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.