|
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
113 if (!checkBasisDim(rStatus, cStatus))
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
145 if (!checkBasisDim(rStatus, cStatus))
159 rStatus[m_old_i] = rStatus[m_i];
170 #ifdef CHECK_BASIC_DIM
171 if (!checkBasisDim(rStatus, cStatus))
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)
213 else if( EQrel(newLo, newUp, eps()))
216 assert( EQrel(newLo, x[m_j], eps()));
218 if( EQrel(m_oldLo, m_oldUp, 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())
226 || (! EQrel(m_oldLo, x[m_j], eps()) && !( EQrel(m_oldUp, x[m_j], eps()))))
237 assert( EQrel(m_oldLo, x[m_j], eps()) || EQrel(m_oldUp, x[m_j], eps()));
245 else if( EQrel(newLo, m_oldUp, eps()))
251 assert( EQrel(m_rhs, x[m_j]*aij, eps()) || EQrel(m_lhs, x[m_j]*aij, eps()));
260 assert( EQrel(m_oldUp, x[m_j], eps()));
268 else if( EQrel(newUp, m_oldLo, eps()))
274 assert( EQrel(m_rhs, x[m_j]*aij, eps()) || EQrel(m_lhs, x[m_j]*aij, eps()));
283 assert( EQrel(m_oldLo, x[m_j], eps()));
304 if( EQrel(m_oldLo, x[m_j], eps()))
312 assert( EQrel(m_rhs, x[m_j]*aij, eps()) || EQrel(m_lhs, x[m_j]*aij, eps()));
321 if( EQrel(m_oldUp, x[m_j], eps()))
329 assert( EQrel(m_rhs, x[m_j]*aij, eps()) || EQrel(m_lhs, x[m_j]*aij, eps()));
346 #ifdef CHECK_BASIC_DIM
347 if (!checkBasisDim(rStatus, cStatus))
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])
383 assert( EQrel(oldLo, x[cIdx], eps()) || EQrel(oldUp, x[cIdx], eps()));
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)
409 assert( EQrel(m_lRhs, m_rhs, eps()) || EQrel(m_lRhs, m_lhs, eps()));
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
448 if (!checkBasisDim(rStatus, cStatus))
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
498 if (!checkBasisDim(rStatus, cStatus))
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
658 if (!checkBasisDim(rStatus, cStatus))
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
797 if (!checkBasisDim(rStatus, cStatus))
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
857 if (!checkBasisDim(rStatus, cStatus))
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
902 if (!checkBasisDim(rStatus, cStatus))
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
1009 if(m_isFirst && !checkBasisDim(rStatus, cStatus))
1028 #ifdef CHECK_BASIC_DIM
1029 if (!checkBasisDim(rStatus, cStatus))
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));
3787 int numRangedRows = 0;
3788 int numBoxedCols = 0;
3793 for( int k = 0; k < m_hist.size(); ++k)
3817 for( int i = 0; i < lp. nRows(); ++i)
3823 for( int j = 0; j < lp. nCols(); ++j)
3830 << numRangedRows << " ranged rows, "
3831 << numBoxedCols << " boxed columns"
3858 for( int i = 0; i < lp. nRows(); ++i)
3861 for( int j = 0; j < lp. nCols(); ++j)
3921 << lp. nRows() << " rows "
3922 << lp. nCols() << " columns "
3923 << lp. nNzos() << " nonzeros"
3930 for( int i = 0; i < lp. nRows(); ++i)
3934 for( int j = 0; j < lp. nCols(); ++j)
3939 << numRangedRows << " ranged rows, "
3940 << numBoxedCols << " boxed columns"
3977 assert(x. dim() == r. dim());
3978 assert(y. dim() == s. dim());
3984 for( int j = 0; j < x. dim(); ++j)
3990 for( int i = 0; i < y. dim(); ++i)
3998 for( int k = m_hist.size()-1; k >= 0; --k)
4037 #ifdef CHECK_BASIC_DIM
|