|
Go to the documentation of this file. 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 52 #define DUPLICATE_ROWS 1 53 #define DUPLICATE_COLS 1 57 #define CHECK_BASIC_DIM 66 for( int rs = 0; rs < nRows; ++rs) 72 for( int cs = 0; cs < nCols; ++cs) 77 assert(numBasis == nRows); 78 return numBasis == nRows; 85 assert( isZero(s[m_i], 1e-9)); 92 MSG_DEBUG( std::cout << "RowObjPS: removing slack column " << m_j << " (" << cStatus[m_j] << ") for row " << m_i << " (" << rStatus[m_i] << ").\n" ); 96 switch( cStatus[m_j] ) 105 rStatus[m_i] = cStatus[m_j]; 112 #ifdef CHECK_BASIC_DIM 128 rStatus[m_old_i] = rStatus[m_i]; 133 for ( int k = 0; k < m_row.size(); ++k) 134 slack += m_row.value(k) * x[m_row.index(k)]; 144 #ifdef CHECK_BASIC_DIM 159 rStatus[m_old_i] = rStatus[m_i]; 170 #ifdef CHECK_BASIC_DIM 185 rStatus[m_old_i] = rStatus[m_i]; 187 Real aij = m_col[m_i]; 190 s[m_i] = aij * x[m_j]; 195 for( int k = 0; k < m_col.size(); ++k) 197 if (m_col.index(k) != m_i) 198 val -= m_col.value(k) * y[m_col.index(k)]; 201 Real newLo = (aij > 0) ? m_lhs/aij : m_rhs/aij; 202 Real newUp = (aij > 0) ? m_rhs/aij : m_lhs/aij; 207 if(newLo <= m_oldLo && newUp >= m_oldUp) 216 assert( EQrel(newLo, x[m_j], eps())); 224 else if(( EQrel(m_oldLo, x[m_j], eps()) && r[m_j] <= - eps()) 225 || ( EQrel(m_oldUp, x[m_j], eps()) && r[m_j] >= eps()) 245 else if( EQrel(newLo, m_oldUp, eps())) 260 assert( EQrel(m_oldUp, x[m_j], eps())); 268 else if( EQrel(newUp, m_oldLo, eps())) 283 assert( EQrel(m_oldLo, x[m_j], eps())); 346 #ifdef CHECK_BASIC_DIM 361 rStatus[m_old_i] = rStatus[m_i]; 367 int cBasisCandidate = -1; 368 Real maxViolation = -1.0; 371 for( int k = 0; k < m_row.size(); ++k) 373 int cIdx = m_row.index(k); 374 Real aij = m_row.value(k); 375 Real oldLo = m_oldLowers[k]; 376 Real oldUp = m_oldUppers[k]; 378 switch(cStatus[cIdx]) 389 if( violation > maxViolation && ( ( EQrel(oldLo, x[cIdx], eps()) && r[cIdx] < - eps()) || ( EQrel(oldUp, x[cIdx], eps()) && r[cIdx] > eps()) ) ) 391 maxViolation = violation; 392 cBasisCandidate = cIdx; 407 if(cBasisCandidate >= 0) 411 assert(cBasisCandidate == m_row.index(bas_k)); 416 Real aij = m_row.value(bas_k); 417 Real multiplier = r[cBasisCandidate]/aij; 418 r[cBasisCandidate] = 0.0; 420 for( int k = 0; k < m_row.size(); ++k) 426 r[m_row.index(k)] -= m_row.value(k) * multiplier; 430 Real val = m_objs[bas_k]; 433 for( int k = 0; k < basis_col. size(); ++k) 435 if (basis_col. index(k) != m_i) 436 val -= basis_col. value(k) * y[basis_col. index(k)]; 447 #ifdef CHECK_BASIC_DIM 464 cStatus[m_old_j] = cStatus[m_j]; 470 for( int k = 0; k < m_col.size(); ++k) 471 s[m_col.index(k)] += m_col.value(k) * x[m_j]; 476 for( int k = 0; k < m_col.size(); ++k) 477 val -= m_col.value(k) * y[m_col.index(k)]; 482 if( m_lower == m_upper ) 484 assert( EQrel(m_lower, m_val)); 490 assert( EQrel(m_val, m_lower) || EQrel(m_val, m_upper) || m_val == 0.0); 495 #ifdef CHECK_BASIC_DIM 511 cStatus[m_j] = m_status; 521 cStatus[m_old_j] = cStatus[m_j]; 523 int rIdx = m_old_i - m_col.size() + 1; 525 for( int k = 0; k < m_col.size(); ++k) 527 int rIdx_new = m_col.index(k); 528 s[ rIdx] = s[rIdx_new]; 529 y[ rIdx] = y[rIdx_new]; 530 rStatus[ rIdx] = rStatus[rIdx_new]; 542 for( int k = 0; k < m_rows.size(); ++k) 545 const SVector& row = m_rows[k]; 547 for( int l = 0; l < row. size(); ++l) 549 if (row. index(l) != m_j) 558 Real z = (m_lRhs[k] / scale) - (val / scale); 563 Real up = z * scale / row[m_j]; 573 if (m_bnd < minRowUp) 585 for( int k = 0; k < m_rows.size(); ++k) 588 const SVector& row = m_rows[k]; 590 for( int l = 0; l < row. size(); ++l) 592 if (row. index(l) != m_j) 601 Real z = (m_lRhs[k] / scale) - (val / scale); 606 Real lo = z * scale / row[m_j]; 616 if (m_bnd > maxRowLo) 625 for( int k = 0; k < m_col.size(); ++k) 626 s[m_col.index(k)] = slack[k] + m_col.value(k) * x[m_j]; 631 for( int k = 0; k < m_col.size(); ++k) 632 y[m_col.index(k)] = m_rowObj.value(k); 635 for( int k = 0; k < m_col.size(); ++k) 657 #ifdef CHECK_BASIC_DIM 672 cStatus[m_old_j] = cStatus[m_j]; 675 Real aij = m_row[m_j]; 681 throw SPxException( "Simplifier: scaling factor is too big - aborting unsimplification"); 691 Real z1 = (m_lhs / scale1) - (s[m_i] / scale1); 692 Real z2 = (m_rhs / scale2) - (s[m_i] / scale2); 699 Real lo = (aij > 0) ? z1 * scale1 / aij : z2 * scale2 / aij; 700 Real up = (aij > 0) ? z2 * scale2 / aij : z1 * scale1 / aij; 707 assert( LErel(lo, up)); 712 if ( m_lower == m_upper ) 732 if ( m_lower == m_upper ) 752 assert( EQrel(m_lower, m_upper)); 789 s[m_i] += aij * x[m_j]; 792 r[m_j] = -1.0 * aij * y[m_i]; 796 #ifdef CHECK_BASIC_DIM 812 rStatus[m_old_i] = rStatus[m_i]; 817 cStatus[m_old_j] = cStatus[m_j]; 821 Real aij = m_row[m_j]; 823 for( int k = 0; k < m_row.size(); ++k) 825 if (m_row.index(k) != m_j) 826 val += m_row.value(k) * x[m_row.index(k)]; 834 Real z = (m_lRhs / scale) - (val / scale); 839 x[m_j] = z * scale / aij; 843 y[m_i] = m_obj / aij; 856 #ifdef CHECK_BASIC_DIM 873 (( m_maxSense && ((r[m_j] > 0 && m_strictUp) || (r[m_j] < 0 && m_strictLo))) || 874 (!m_maxSense && ((r[m_j] > 0 && m_strictLo) || (r[m_j] < 0 && m_strictUp))))))) 877 Real aik = m_col[m_i]; 879 for( int _k = 0; _k < m_col.size(); ++_k) 881 if (m_col.index(_k) != m_i) 882 val -= m_col.value(_k) * y[m_col.index(_k)]; 888 r[m_j] = m_jObj - val * m_aij / aik; 901 #ifdef CHECK_BASIC_DIM 916 for( int i = m_perm.size() - 1; i >= 0; --i) 920 int rIdx_new = m_perm[i]; 922 s[ rIdx] = s[rIdx_new]; 923 y[ rIdx] = y[rIdx_new]; 924 rStatus[ rIdx] = rStatus[rIdx_new]; 930 for( int k = 0; k < m_scale.size(); ++k) 932 if (m_scale.index(k) != m_i) 933 s[m_scale.index(k)] = s[m_i] / m_scale.value(k); 937 bool haveSetBasis = false; 939 for( int k = 0; k < m_scale.size(); ++k) 941 int i = m_scale.index(k); 947 y[i] = m_rowObj.value(k); 954 if (rStatus[m_i] == SPxSolver::FIXED && (i == m_maxLhsIdx || i == m_minRhsIdx)) 957 y[i] = y[m_i] * m_scale.value(k); 960 if(m_isLhsEqualRhs[k]) 964 else if(i == m_maxLhsIdx) 970 assert(i == m_minRhsIdx); 981 y[i] = y[m_i] * m_scale.value(k); 992 y[i] = y[m_i] * m_scale.value(k); 1003 y[i] = m_rowObj.value(k); 1008 #ifdef CHECK_BASIC_DIM 1028 #ifdef CHECK_BASIC_DIM 1041 for( int i = m_perm.size() - 1; i >= 0; --i) 1045 int cIdx_new = m_perm[i]; 1047 x[ cIdx] = x[cIdx_new]; 1048 r[ cIdx] = r[cIdx_new]; 1049 cStatus[ cIdx] = cStatus[cIdx_new]; 1097 assert(x[m_k] == 0.0); 1098 assert( LErel(m_loJ, 0.0)); 1099 assert( GErel(m_upJ, 0.0)); 1100 assert( LErel(m_loK, 0.0)); 1101 assert( GErel(m_upK, 0.0)); 1109 else if ( LErel(m_loK, 0.0) && GErel(m_upK, 0.0)) 1121 else if ( LErel(m_loJ, 0.0) && GErel(m_upJ, 0.0)) 1136 Real z1 = (x[m_k] / scale1) - (m_loK / scale1); 1137 Real z2 = (x[m_k] / scale2) - (m_upK / scale2); 1144 if( m_loJ <= -infinity && m_upJ >= infinity && m_loK <= -infinity && m_upK >= infinity ) 1149 else if( m_scale > 0.0 ) 1151 if( GErel(x[m_k], m_upK + m_scale * m_upJ) ) 1156 x[m_k] -= m_scale * x[m_j]; 1158 else if( GErel(x[m_k], m_loK + m_scale * m_upJ) && m_upJ < infinity ) 1162 x[m_k] -= m_scale * x[m_j]; 1164 else if( GErel(x[m_k], m_upK + m_scale * m_loJ) && m_upK < infinity ) 1169 x[m_j] = z2 * scale2 / m_scale; 1171 else if( GErel(x[m_k], m_loK + m_scale * m_loJ) && m_loJ > - infinity ) 1175 x[m_k] -= m_scale * x[m_j]; 1177 else if( GErel(x[m_k], m_loK + m_scale * m_loJ) && m_loK > - infinity ) 1182 x[m_j] = z1 * scale1 / m_scale; 1184 else if( LTrel(x[m_k], m_loK + m_scale * m_loJ) ) 1189 x[m_k] -= m_scale * x[m_j]; 1198 assert(m_scale < 0.0); 1200 if( GErel(x[m_k], m_upK + m_scale * m_loJ) ) 1205 x[m_k] -= m_scale * x[m_j]; 1207 else if( GErel(x[m_k], m_loK + m_scale * m_loJ) && m_loJ > - infinity ) 1211 x[m_k] -= m_scale * x[m_j]; 1213 else if( GErel(x[m_k], m_upK + m_scale * m_upJ) && m_upK < infinity ) 1218 x[m_j] = z2 * scale2 / m_scale; 1220 else if( GErel(x[m_k], m_loK + m_scale * m_upJ) && m_upJ < infinity ) 1224 x[m_k] -= m_scale * x[m_j]; 1226 else if( GErel(x[m_k], m_loK + m_scale * m_upJ) && m_loK > - infinity ) 1231 x[m_j] = z1 * scale1 / m_scale; 1233 else if( LTrel(x[m_k], m_loK + m_scale * m_upJ) ) 1238 x[m_k] -= m_scale * x[m_j]; 1248 r[m_j] = m_scale * r[m_k]; 1253 for( int i = lp. nRows() - 1; i >= 0; --i ) 1285 for( int i = lp. nRows()-1; i >= 0; --i) 1295 else if (lhs > - infinity && lhs < -maxVal) 1300 else if (lhs < infinity && lhs > maxVal) 1314 else if (rhs > - infinity && rhs < -maxVal) 1319 else if (rhs < infinity && rhs > maxVal) 1338 for( int j = 0; j < lp. nCols(); ++j) 1348 else if (lo > - infinity && lo < -maxVal) 1353 else if (lo < infinity && lo > maxVal) 1367 else if (up > - infinity && up < -maxVal) 1372 else if (up < infinity && up > maxVal) 1384 Real absBnd = (lo > up) ? lo : up; 1393 while(i < col. size()) 1397 if ( isZero(aij * absBnd, tol)) 1406 << " removed, absBnd=" << absBnd 1416 else if( isZero(aij, tol) ) 1434 else if (obj > - infinity && obj < -maxVal) 1439 else if (obj < infinity && obj > maxVal) 1446 if (remRows + remNzos + chgLRhs + chgBnds + objCnt > 0) 1454 << remRows << " rows, " 1455 << remNzos << " non-zeros, " 1456 << chgBnds << " col bounds, " 1457 << chgLRhs << " row bounds, " 1458 << objCnt << " objective coefficients" << std::endl; ) 1471 for( int i = lp. nRows()-1; i >= 0; --i) 1475 if (row. size() == 0) 1483 << " rhs=" << lp. rhs(i) << std::endl; ) 1499 for( int j = lp. nCols()-1; j >= 0; --j) 1503 if (col. size() == 0) 1506 << ": empty -> maxObj=" << lp. maxObj(j) 1507 << " lower=" << lp. lower(j) 1508 << " upper=" << lp. upper(j); ) 1557 if (remRows + remCols > 0) 1563 << remRows << " rows, " 1564 << remCols << " cols" 1573 assert(row. size() == 1); 1576 int j = row. index(0); 1581 << ": singleton -> val=" << aij 1582 << " lhs=" << lp. lhs(i) 1583 << " rhs=" << lp. rhs(i); ) 1609 << " (" << lp. lower(j) 1611 << " (" << lp. upper(j) 1612 << ")" << std::endl; ) 1614 bool stricterUp = false; 1615 bool stricterLo = false; 1665 int oldRows = lp. nRows(); 1667 bool redundantLower; 1668 bool redundantUpper; 1672 for( int i = lp. nRows()-1; i >= 0; --i) 1683 for( int k = 0; k < row. size(); ++k) 1686 int j = row. index(k); 1690 MSG_WARNING( (* spxout), (* spxout) << "Warning: tiny nonzero coefficient " << aij << " in row " << i << "\n" ); 1698 lhsBnd += aij * lp. lower(j); 1703 rhsBnd += aij * lp. upper(j); 1710 rhsBnd += aij * lp. lower(j); 1715 lhsBnd += aij * lp. upper(j); 1721 if (rhsCnt <= 1 || lhsCnt <= 1) 1723 for( int k = 0; k < row. size(); ++k) 1726 int j = row. index(k); 1728 redundantLower = false; 1729 redundantUpper = false; 1745 Real z = (lp. lhs(i) / scale) - (rhsBnd / scale); 1753 lo = lp. upper(j) + z * scale / aij; 1755 lo = z * scale / aij; 1763 << ": redundant lower bound on x" << j 1764 << " -> lower=" << lo 1765 << " (" << lp. lower(j) 1766 << ")" << std::endl; ) 1768 redundantLower = true; 1782 Real z = (lp. rhs(i) / scale) - (lhsBnd / scale); 1790 up = lp. lower(j) + z * scale / aij; 1792 up = z * scale / aij; 1800 << ": redundant upper bound on x" << j 1801 << " -> upper=" << up 1802 << " (" << lp. upper(j) 1803 << ")" << std::endl; ) 1805 redundantUpper = true; 1814 lhsBnd -= aij * lp. lower(j); 1828 rhsBnd -= aij * lp. upper(j); 1849 Real z = (lp. lhs(i) / scale) - (rhsBnd / scale); 1857 up = lp. lower(j) + z * scale / aij; 1859 up = z * scale / aij; 1867 << ": redundant upper bound on x" << j 1868 << " -> upper=" << up 1869 << " (" << lp. upper(j) 1870 << ")" << std::endl; ) 1872 redundantUpper = true; 1885 Real z = (lp. rhs(i) / scale) - (lhsBnd / scale); 1893 lo = lp. upper(j) + z * scale / aij; 1895 lo = z * scale / aij; 1903 << ": redundant lower bound on x" << j 1904 << " -> lower=" << lo 1905 << " (" << lp. lower(j) 1906 << ")" << std::endl; ) 1908 redundantLower = true; 1917 lhsBnd -= aij * lp. upper(j); 1931 rhsBnd -= aij * lp. lower(j); 1946 redundantLhs = false; 1947 redundantRhs = false; 1953 << ": redundant lhs -> lhsBnd=" << lhsBnd 1954 << " lhs=" << lp. lhs(i) 1957 redundantLhs = true; 1962 << ": redundant rhs -> rhsBnd=" << rhsBnd 1963 << " rhs=" << lp. rhs(i) 1966 redundantRhs = true; 1998 << ": infeasible -> lhs=" << lp. lhs(i) 1999 << " rhs=" << lp. rhs(i) 2000 << " lhsBnd=" << lhsBnd 2001 << " rhsBnd=" << rhsBnd 2011 << ": unconstrained -> removed" << std::endl; ) 2018 remNzos += row. size(); 2027 #if EMPTY_CONSTRAINT 2029 if (row. size() == 0) 2037 << " rhs=" << lp. rhs(i) << std::endl; ) 2057 if (row. size() == 1) 2064 #if FORCE_CONSTRAINT 2070 << ": forcing constraint fix on lhs ->" 2071 << " lhs=" << lp. lhs(i) 2072 << " rhsBnd=" << rhsBnd 2079 for( int k = 0; k < row. size(); ++k) 2082 int j = row. index(k); 2086 lowers[k] = lp. lower(j); 2087 uppers[k] = lp. upper(j); 2102 remNzos += row. size(); 2113 << ": forcing constraint fix on rhs ->" 2114 << " rhs=" << lp. rhs(i) 2115 << " lhsBnd=" << lhsBnd 2122 for( int k = 0; k < row. size(); ++k) 2125 int j = row. index(k); 2129 lowers[k] = lp. lower(j); 2130 uppers[k] = lp. upper(j); 2145 remNzos += row. size(); 2155 assert(remRows > 0 || remNzos == 0); 2157 if (remRows + chgLRhs + chgBnds > 0) 2167 << remRows << " rows, " 2168 << remNzos << " non-zeros, " 2169 << chgBnds << " col bounds, " 2170 << chgLRhs << " row bounds; kept " 2171 << keptBnds << " column bounds, " 2172 << keptLRhs << " row bounds" 2200 int oldCols = lp. nCols(); 2201 int oldRows = lp. nRows(); 2203 for( int j = lp. nCols()-1; j >= 0; --j) 2211 << ": infeasible bounds on x" << j 2212 << " -> lower=" << lp. lower(j) 2213 << " upper=" << lp. upper(j) 2219 if (col. size() == 0) 2223 << ": empty -> maxObj=" << lp. maxObj(j) 2224 << " lower=" << lp. lower(j) 2225 << " upper=" << lp. upper(j); ) 2283 for( int k = 0; k < col. size(); ++k) 2285 if (!loFree && !upFree) 2288 int i = col. index(k); 2293 if (col. value(k) > 0.0) 2301 else if (col. value(k) < 0.0) 2319 << " unconstrained above ->"; ) 2340 << " unconstrained below ->"; ) 2358 #if FREE_ZERO_OBJ_VARIABLE 2359 bool unconstrained_below = loFree && lp. lower(j) <= - infinity; 2360 bool unconstrained_above = upFree && lp. upper(j) >= infinity; 2362 if (unconstrained_below || unconstrained_above) 2366 << " unconstrained " 2367 << (unconstrained_below ? "below" : "above") 2368 << " with zero objective (" << lp. maxObj(j) 2369 << ")" << std::endl; ) 2375 SPxQuicksort(col_idx_sorted.mem(), col_idx_sorted.size(), compare); 2383 remRows += col. size(); 2384 for( int k = col_idx_sorted.size()-1; k >= 0; --k) 2391 for( int k = 0; k < col. size(); ++k) 2393 int l = col. index(k); 2412 << " fixed -> lower=" << lp. lower(j) 2413 << " upper=" << lp. upper(j) << std::endl; ) 2418 remNzos += col. size(); 2428 if (col. size() == 1) 2431 int i = col. index(0); 2436 #if ZERO_OBJ_COL_SINGLETON 2438 << ": singleton in row " << i 2439 << " with zero objective"; ) 2447 lhs = lp. lhs(i) - aij * lp. upper(j); 2449 rhs = lp. rhs(i) - aij * lp. lower(j); 2454 lhs = lp. lhs(i) - aij * lp. lower(j); 2456 rhs = lp. rhs(i) - aij * lp. upper(j); 2470 << " (" << lp. lhs(i) 2472 << " (" << lp. rhs(i) 2473 << ")" << std::endl; ) 2508 #if DOUBLETON_EQUATION 2510 << ": singleton in row " << i 2511 << " with doubleton equation ->"; ) 2520 if (row. index(0) == j) 2525 else if (row. index(1) == j) 2547 Real z1 = (lhs / scale1) - (aij * lp. upper(j) / scale1); 2548 Real z2 = (lhs / scale2) - (aij * lp. lower(j) / scale2); 2575 << ": lower=" << lp. lower(k) 2577 << ") upper=" << lp. upper(k) 2579 << ")" << std::endl; ) 2607 #if FREE_COL_SINGLETON 2614 << ": free singleton in inequality constraint" << std::endl; ) 2661 << ": free singleton removed" << std::endl; ) 2665 for ( int h = 0; h < row.size(); ++h) 2667 int k = row. index(h); 2671 Real new_obj = lp. obj(k) - (lp. obj(j) * row.value(h) / aij); 2678 remNzos += row.size(); 2688 if (remCols + remRows > 0) 2696 << remRows << " rows, " 2697 << remCols << " cols, " 2698 << remNzos << " non-zeros, " 2699 << chgBnds << " col bounds" 2721 int oldRows = lp. nRows(); 2722 int oldCols = lp. nCols(); 2731 for( int i = lp. nRows()-1; i >= 0; --i) 2737 << ": unconstrained" << std::endl; ) 2758 for( int j = 0; j < lp. nCols(); ++j) 2772 dualVarUp[i] = bound; 2774 dualVarLo[i] = bound; 2779 dualVarLo[i] = bound; 2781 dualVarUp[i] = bound; 2787 for( int j = 0; j < lp. nCols(); ++j) 2789 dualConsLo[j] = dualConsUp[j] = 0.0; 2793 for( int k = 0; k < col. size(); ++k) 2799 int i = col. index(k); 2808 dualConsLo[j] += aij * dualVarLo[i]; 2813 dualConsUp[j] += aij * dualVarUp[i]; 2820 dualConsUp[j] += aij * dualVarLo[i]; 2825 dualConsLo[j] += aij * dualVarUp[i]; 2830 for( int j = lp. nCols()-1; j >= 0; --j) 2836 if ( LTrel(dualConsUp[j], dualConsLo[j], opttol())) 2839 << ": dual infeasible -> dual lhs bound=" << dualConsLo[j] 2840 << " dual rhs bound=" << dualConsUp[j] << std::endl; ) 2850 #if DOMINATED_COLUMN 2852 << ": dominated -> maxObj=" << obj 2853 << " dual rhs bound=" << dualConsUp[j] << std::endl; ) 2873 #if DOMINATED_COLUMN 2875 << ": dominated -> maxObj=" << obj 2876 << " dual lhs bound=" << dualConsLo[j] << std::endl; ) 2898 #if WEAKLY_DOMINATED_COLUMN 2900 << ": weakly dominated -> maxObj=" << obj 2901 << " dual rhs bound=" << dualConsUp[j] << std::endl; ) 2913 #if WEAKLY_DOMINATED_COLUMN 2915 << ": weakly dominated -> maxObj=" << obj 2916 << " dual lhs bound=" << dualConsLo[j] << std::endl; ) 2942 assert(remRows > 0 || remCols > 0 || remNzos == 0); 2944 if (remCols + remRows > 0) 2951 << remRows << " rows, " 2952 << remCols << " cols, " 2953 << remNzos << " non-zeros" 2973 int oldRows = lp. nRows(); 2982 for ( int i = 0; i < lp. nRows(); ++i) 2986 if (row. size() == 1) 2996 << rs_remRows << " rows, " 2997 << rs_remRows << " non-zeros" 3025 classSize[0] = lp. nRows(); 3027 for( int i = 1; i < lp. nRows(); ++i) 3038 for( int j = 0; j < lp. nCols(); ++j) 3042 for( int k = 0; k < col. size(); ++k) 3045 int i = col. index(k); 3047 if (scale[i] == 0.0) 3051 if (--classSize[pClass[i]] == 0) 3052 idxSet.addIdx(pClass[i]); 3056 for( int m = 0; m < col. size(); ++m) 3058 int k = pClass[col. index(m)]; 3069 int classIdx = idxSet.index(0); 3076 classIdx = idxSet.index(0); 3081 ++classSize[classIdx]; 3083 oldVal = m_classSetRows[k].value(l); 3095 for( int k = 0; k < lp. nRows(); ++k ) 3098 for( int k = 0; k < lp. nRows(); ++k) 3104 const int nRowsOld_tmp = lp. nRows(); 3108 for( int j = 0; j < nRowsOld_tmp; ++j) 3113 int idxFirstDupRows = -1; 3114 int idxLastDupRows = -1; 3117 for( int k = 0; k < lp. nRows(); ++k) 3123 if(idxFirstDupRows < 0) 3125 idxFirstDupRows = k; 3128 for( int l = 1; l < m_dupRows[k].size(); ++l) 3139 int k_tmp, j_tmp = -1; 3140 for (k_tmp = j_tmp = 0; k_tmp < nRowsOld_tmp; ++k_tmp) 3142 if (perm_tmp[k_tmp] >= 0) 3143 perm_tmp[k_tmp] = j_tmp++; 3148 bool doChangeRanges = false; 3152 for( int k = 0; k < lp. nRows(); ++k) 3157 << " duplicate rows found" << std::endl; ) 3171 for( int l = 0; l < m_dupRows[k].size(); ++l) 3174 isLhsEqualRhs[l] = (lp. lhs(i) == lp. rhs(i)); 3181 maxLhs = lp. lhs(rowIdx); 3182 minRhs = lp. rhs(rowIdx); 3186 Real scaledLhs, scaledRhs; 3187 Real factor = scale[rowIdx] / scale[i]; 3199 if (scaledLhs > maxLhs) 3204 if (scaledRhs < minRhs) 3216 Real newLhs = (maxLhs > lp. lhs(rowIdx)) ? maxLhs : lp. lhs(rowIdx); 3217 Real newRhs = (minRhs < lp. rhs(rowIdx)) ? minRhs : lp. rhs(rowIdx); 3219 if(k == idxLastDupRows) 3222 for( int j = 0; j < nRowsOld_tmp; ++j) 3224 da_perm[j] = perm_tmp[j]; 3228 m_hist.append( new (DuplicateRowsPSptr) DuplicateRowsPS(lp, rowIdx, maxLhsIdx, minRhsIdx, m_dupRows[k], scale, da_perm, isLhsEqualRhs, true, EQrel(newLhs, newRhs), k==idxFirstDupRows)); 3235 m_hist.append( new (DuplicateRowsPSptr) DuplicateRowsPS(lp, rowIdx, maxLhsIdx, minRhsIdx, m_dupRows[k], scale, da_perm_empty, isLhsEqualRhs, false, EQrel(newLhs, newRhs), k == idxFirstDupRows)); 3238 if (maxLhs > lp. lhs(rowIdx) || minRhs < lp. rhs(rowIdx)) 3241 doChangeRanges = true; 3246 << " lhs=" << newLhs 3247 << " rhs=" << newRhs << std::endl; ) 3252 if( newRhs < newLhs ) 3255 newLhsVec[rowIdx] = newLhs; 3256 newRhsVec[rowIdx] = newRhs; 3269 const int nRowsOld = lp. nRows(); 3273 for( int i = 0; i < nRowsOld; ++i) 3286 for( int i = 0; i < nRowsOld; ++i) 3289 assert(perm[i] == perm_tmp[i]); 3299 if (remRows + remNzos > 0) 3305 << remRows << " rows, " 3306 << remNzos << " non-zeros" 3352 classSize[0] = lp. nCols(); 3354 for( int j = 1; j < lp. nCols(); ++j) 3365 for( int i = 0; i < lp. nRows(); ++i) 3369 for( int k = 0; k < row. size(); ++k) 3372 int j = row. index(k); 3374 if (scale[j] == 0.0) 3378 if (--classSize[pClass[j]] == 0) 3379 idxSet.addIdx(pClass[j]); 3383 for( int m = 0; m < row. size(); ++m) 3385 int k = pClass[row. index(m)]; 3396 int classIdx = idxSet.index(0); 3404 classIdx = idxSet.index(0); 3409 ++classSize[classIdx]; 3411 oldVal = m_classSetCols[k].value(l); 3424 for( int k = 0; k < lp. nCols(); ++k ) 3427 for( int k = 0; k < lp. nCols(); ++k) 3430 fixAndRemCol[k] = false; 3434 bool hasDuplicateCol = false; 3437 for( int k = 0; k < lp. nCols(); ++k) 3442 << " duplicate columns found" << std::endl; ) 3444 if (!hasDuplicateCol) 3449 hasDuplicateCol = true; 3452 for( int l = 0; l < m_dupCols[k].size(); ++l) 3454 for( int m = 0; m < m_dupCols[k].size(); ++m) 3459 if (l != m && !remCol[j1] && !remCol[j2]) 3465 Real factor = scale[j1] / scale[j2]; 3466 Real objDif = cj1 - cj2 * scale[j1] / scale[j2]; 3497 else if (factor < 0) 3512 << " replaced by one" << std::endl; ) 3522 << " because zero not contained in their bounds" << std::endl; ) 3531 if (factor > 0 && objDif > 0) 3542 << " first one fixed at upper bound=" << lp. upper(j1) << std::endl; ) 3549 else if (factor < 0 && objDif < 0) 3560 << " first one fixed at lower bound=" << lp. lower(j1) << std::endl; ) 3571 if (factor < 0 && objDif > 0) 3582 << " first one fixed at upper bound=" << lp. upper(j1) << std::endl; ) 3591 else if (factor > 0 && objDif < 0) 3602 << " first one fixed at lower bound=" << lp. lower(j1) << std::endl; ) 3613 fixAndRemCol[j1] = true; 3624 for( int j = 0; j < lp. nCols(); ++j) 3636 const int nColsOld = lp. nCols(); 3640 for( int j = 0; j < nColsOld; ++j) 3653 for( int j = 0; j < nColsOld; ++j) 3660 for( int j = 0; j < nColsOld; ++j) 3662 da_perm[j] = perm[j]; 3665 if (hasDuplicateCol) 3674 assert(remCols > 0 || remNzos == 0); 3682 << remCols << " cols, " 3683 << remNzos << " non-zeros" 3702 << ": lower=" << lp. lower(j) 3703 << " upper=" << lp. upper(j) 3708 for( int k = 0; k < col. size(); ++k) 3710 int i = col. index(k); 3720 Real rhs = (lp. rhs(i) / scale) - (y / scale); 3729 << " (" << lp. rhs(i) 3730 << ") aij=" << col. value(k) 3743 Real lhs = (lp. lhs(i) / scale) - (y / scale); 3752 << " (" << lp. lhs(i) 3753 << ") aij=" << col. value(k) 3758 assert(lp. lhs(i) <= lp. rhs(i)); 3789 int numRangedRows = 0; 3790 int numBoxedCols = 0; 3795 for( int k = 0; k < m_hist.size(); ++k) 3819 for( int i = 0; i < lp. nRows(); ++i) 3825 for( int j = 0; j < lp. nCols(); ++j) 3832 << numRangedRows << " ranged rows, " 3833 << numBoxedCols << " boxed columns" 3860 for( int i = 0; i < lp. nRows(); ++i) 3863 for( int j = 0; j < lp. nCols(); ++j) 3923 << lp. nRows() << " rows " 3924 << lp. nCols() << " columns " 3925 << lp. nNzos() << " nonzeros" 3932 for( int i = 0; i < lp. nRows(); ++i) 3936 for( int j = 0; j < lp. nCols(); ++j) 3941 << numRangedRows << " ranged rows, " 3942 << numBoxedCols << " boxed columns" 3979 assert(x. dim() == r. dim()); 3980 assert(y. dim() == s. dim()); 3986 for( int j = 0; j < x. dim(); ++j) 3992 for( int i = 0; i < y. dim(); ++i) 4000 for( int k = m_hist.size()-1; k >= 0; --k) 4038 #ifdef CHECK_BASIC_DIM 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.
R obj(int i) const Returns objective value of column i.
DataArray< PostStep * > m_hist vector of presolve history.
Exception class for things that should NEVER happen.This class is derived from the SoPlex exception b...
int cIdx(int j) const returns for a given column index of the (reduced) LP the corresponding column index in the unsimplifi...
bool LTrel(Real a, Real b, Real eps=Param::epsilon()) returns true iff relDiff(a,b) <= -eps
free variable fixed to zero.
Safe arrays of data objects.Class DataArray provides safe arrays of Data Objects. For general C++ obj...
friend class FreeConstraintPS
Result removeRowSingleton(SPxLP &lp, const SVector &row, int &i) remove row singletons.
DataArray< int > m_stat preprocessing history.
void reDim(int newdim, const bool setZero=true) Resets DVectorBase's dimension to newdim.
int m_keptLRhs number of kept left- and right-hand sides
UnitVectorBase< Real > UnitVector
const VectorBase< R > & maxObj() const Returns objective vector for maximization problem.
virtual void changeRhs(const VectorBase< R > &newRhs) Changes right hand side vector for constraints to newRhs.
Real m_epsilon epsilon zero.
Postsolves variable bound fixing.
Result Result of the simplification.
the problem was so much simplified that it vanished
virtual void changeObj(const VectorBase< R > &newObj) Changes objective vector to newObj.
virtual void unsimplify(const Vector &x, const Vector &y, const Vector &s, const Vector &r, const SPxSolver::VarStatus rows[], const SPxSolver::VarStatus cols[]) reconstructs an optimal solution for the unsimplified LP.
Postsolves duplicate rows.
int m_remNzos number of removed nonzero coefficients
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis) const
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 LT(Real a, Real b, Real eps=Param::epsilon()) returns true iff a < b + eps
SPxLP::SPxSense m_thesense optimization sense.
const SVectorBase< R > & colVector(int i) const Returns column vector of column i.
bool NE(Real a, Real b, Real eps=Param::epsilon()) returns true iff |a-b| > eps
virtual void changeLhs(const VectorBase< R > &newLhs) Changes left hand side vector for constraints to newLhs.
virtual Result simplify(SPxLP &lp, Real eps, Real delta) simplify SPxLP lp with identical primal and dual feasibility tolerance.
int size() const Number of used indices.
friend class DuplicateRowsPS
virtual const char * getName() const get name of simplifying step.
const VectorBase< R > & lower() const Returns lower bound vector.
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.
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.
const VectorBase< R > & upper() const Returns upper bound vector.
virtual bool checkBasisDim(DataArray< SPxSolver::VarStatus > rows, DataArray< SPxSolver::VarStatus > cols) const
SVectorBase< R > & rowVector_w(int i)
virtual void removeRows(int perm[]) Removes multiple rows.
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis) const
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 void changeUpper(const VectorBase< R > &newUpper) Changes vector of upper bounds to newUpper.
Wrapper for different output streams and verbosity levels.
virtual void changeRowObj(const VectorBase< R > &newRowObj) Changes row objective function vector to newRowObj.
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis) const
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 addCol(const LPColBase< R > &col)
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis) const
Postsolves the case when constraints are removed due to a variable with zero objective that is free i...
virtual void changeLower(const VectorBase< R > &newLower) Changes vector of lower bounds to newLower.
int rIdx(int i) const returns for a given row index of the (reduced) LP the corresponding row index in the unsimplified LP...
friend class RowSingletonPS
Timer * m_timeUsed user time used for simplification
virtual void changeRange(const VectorBase< R > &newLhs, const VectorBase< R > &newRhs) Changes left and right hand side vectors.
nothing known about basis status (possibly due to a singular basis in transformed problem) ...
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis) const
Array< DSVector > m_classSetCols stores parallel classes with non-zero row entry
#define MSG_INFO2(spxout, x) Prints out message x if the verbosity level is at least SPxOut::INFO2.
Result duplicateCols(SPxLP &lp, bool &again) removes duplicate columns
void removeCol(SPxLP &lp, int j) removes a column in the LP.
int number(int i) const Number of index i.
bool GT(Real a, Real b, Real eps=Param::epsilon()) returns true iff a > b + eps
int & index(int n) Reference to index of n 'th nonzero.
Postsolves row singletons.
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis) const
Result simplifyRows(SPxLP &lp, bool &again) performs simplification steps on the rows of the LP.
int nCols() const Returns number of columns in LP.
friend class DoubletonEquationPS
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis) const
Postsolves doubleton equations combined with a column singleton.
Postsolves free column singletons.
int size() const return nr. of elements.
comparator for class SVector::Element: compare nonzeros according to value
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis) const
DataArray< int > m_cIdx column index vector in original LP.
Result m_result result of the simplification.
variable set to its upper bound.
int nNzos() const Returns number of nonzeros in LP.
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.
#define MSG_INFO1(spxout, x) Prints out message x if the verbosity level is at least SPxOut::INFO1.
int dim() const Dimension of vector.
primal infeasibility was detected
bool GErel(Real a, Real b, Real eps=Param::epsilon()) returns true iff relDiff(a,b) > -eps
virtual void changeBounds(const VectorBase< R > &newLower, const VectorBase< R > &newUpper) Changes variable bounds to newLower and newUpper.
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).
int nRows() const Returns number of rows in LP.
Postsolves row objectives.
DataArray< int > m_rIdx row index vector in original LP.
Postsolves column singletons with zero objective.
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)
const VectorBase< R > & lhs() const Returns left hand side vector.
Everything should be within this namespace.
bool isConsistent() const Consistency check.
bool EQrel(Real a, Real b, Real eps=Param::epsilon()) returns true iff |relDiff(a,b)| <= eps
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.
Exception class for incorrect usage of interface methods.
Save arrays of arbitrary types.
Real m_objoffset objective offset
friend class DuplicateColsPS
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis) const
bool NErel(Real a, Real b, Real eps=Param::epsilon()) returns true iff |relDiff(a,b)| > eps
comparator for class SVector::Element: compare nonzeros according to index
int m_chgBnds number of changed bounds
Postsolves duplicate columns.
SPxSense spxSense() const Returns the optimization sense.
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis) const
Result removeEmpty(SPxLP &lp) removed empty rows and empty columns.
Postsolves forcing constraints.
Result simplifyDual(SPxLP &lp, bool &again) performs simplification steps on the LP based on dual concepts.
Postsolves unconstraint constraints.
int m_remCols number of removed columns
const VectorBase< R > & rhs() const Returns right hand side vector.
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis) const
Postsolves variable fixing.
friend class FreeColSingletonPS
bool LErel(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.
friend class FreeZeroObjVariablePS
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.
#define MSG_INFO3(spxout, x) Prints out message x if the verbosity level is at least SPxOut::INFO3.
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.
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.
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis) const
const VectorBase< R > & maxRowObj() const
DataArray< SPxSolver::VarStatus > m_cBasisStat basis status of columns.
virtual void execute(DVector &x, DVector &y, DVector &s, DVector &r, DataArray< SPxSolver::VarStatus > &cBasis, DataArray< SPxSolver::VarStatus > &rBasis) const
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.
|