Lines Matching defs:row
87 const Simplex::Unknown &SimplexBase::unknownFromRow(unsigned row) const {
88 assert(row < getNumRows() && "Invalid row");
89 return unknownFromIndex(rowUnknown[row]);
102 Simplex::Unknown &SimplexBase::unknownFromRow(unsigned row) {
103 assert(row < getNumRows() && "Invalid row");
104 return unknownFromIndex(rowUnknown[row]);
108 // Resize the tableau to accommodate the extra row.
118 /// Add a new row to the tableau corresponding to the given constant term and
140 // a row ax + by + cz + d, we express it in terms of our internal variables
161 // coefficient for that variable (scaled by the common row denominator) to
162 // the corresponding entry in the new row.
167 // If the variable is in row position, we need to add that row to the new
168 // row, scaled by the coefficient for the variable, accounting for the two
216 /// A*y is zero or lexicopositive. Begin by considering A_1, the first row of A.
217 /// If this row is all zeros, then (A*y)_1 = (A_1)*y = 0; proceed to the next
218 /// row. If we run out of rows, A*y is zero and we are done; otherwise, we
219 /// encounter some row A_i that has a non-zero element. Every column is
221 /// occur, so the element in this row for any column, if non-zero, must be
233 /// add these to the set of ignored columns and continue to the next row. If we
243 /// Given a row that has a non-integer sample value, add an inequality such
248 /// Let the row be
256 /// becuse the row unknown's value always equals this expression, even if *we*
281 LogicalResult LexSimplexBase::addCut(unsigned row) {
282 DynamicAPInt d = tableau(row, 0);
285 tableau(cutRow, 1) = -mod(-tableau(row, 1), d); // -c%d.
288 tableau(cutRow, col) = mod(tableau(row, col), d); // b_i%d.
299 unsigned row = u.pos;
300 if (tableau(row, 1) % tableau(row, 0) != 0)
301 return row;
313 // Otherwise, for the variable whose row has a non-integral sample value,
348 SymbolicLexSimplex::getSymbolicSampleNumerator(unsigned row) const {
352 sample.emplace_back(tableau(row, col));
353 sample.emplace_back(tableau(row, 1));
358 SymbolicLexSimplex::getSymbolicSampleIneq(unsigned row) const {
359 SmallVector<DynamicAPInt, 8> sample = getSymbolicSampleNumerator(row);
379 bool SymbolicLexSimplex::isSymbolicSampleIntegral(unsigned row) const {
380 DynamicAPInt denom = tableau(row, 0);
381 return tableau(row, 1) % denom == 0 &&
382 isRangeDivisibleBy(tableau.getRow(row).slice(3, nSymbol), denom);
385 /// This proceeds similarly to LexSimplexBase::addCut(). We are given a row that
388 /// Let the row be
418 LogicalResult SymbolicLexSimplex::addSymbolicCut(unsigned row) {
419 DynamicAPInt d = tableau(row, 0);
420 if (isRangeDivisibleBy(tableau.getRow(row).slice(3, nSymbol), d)) {
424 return addCut(row);
432 divCoeffs.emplace_back(mod(-tableau(row, col), divDenom)); // (-a_i%d)s_i
433 divCoeffs.emplace_back(mod(-tableau(row, 1), divDenom)); // -c%d.
447 tableau(cutRow, 1) = -mod(-tableau(row, 1), d); // -(-c%d).
449 tableau(cutRow, col) = -mod(-tableau(row, col), d); // -(-a_i%d)s_i.
453 tableau(cutRow, col) = mod(tableau(row, col), d); // (b_i%d)y_i.
502 for (unsigned row = 0, e = getNumRows(); row < e; ++row)
503 if (tableau(row, 2) < 0)
504 return row;
506 for (unsigned row = 0, e = getNumRows(); row < e; ++row) {
507 if (tableau(row, 2) > 0)
509 if (domainSimplex.isSeparateInequality(getSymbolicSampleIneq(row))) {
511 return row;
521 assert(!u.isSymbol && "Symbol should not be in row orientation!");
531 while (std::optional<unsigned> row = maybeGetAlwaysViolatedRow())
532 if (moveRowUnknownToColumn(*row).failed())
593 // negative values, and hence constitutes a row for which we need to
605 // First, we consider the part of the domain where the row is not
606 // violated. We don't have to do any pivots for the row in this case,
617 // row when we come back from recursing. We will need this to recurse
618 // on the other part of the split domain, where the row is violated.
633 if (std::optional<unsigned> row = maybeGetNonIntegralVarRow()) {
634 if (addSymbolicCut(*row).failed()) {
664 "The split row should have been returned to row orientation!");
688 bool LexSimplex::rowIsViolated(unsigned row) const {
689 if (tableau(row, 2) < 0)
691 if (tableau(row, 2) == 0 && tableau(row, 1) < 0)
697 for (unsigned row = 0, e = getNumRows(); row < e; ++row)
698 if (rowIsViolated(row))
699 return row;
715 // Move the row unknown to column orientation while preserving lexicopositivity
716 // of the basis transform. The sample value of the row must be non-positive.
719 // pivot exists, i.e., some violated row has no positive coefficient for any
720 // basis unknown. The row can be represented as (s + c_1*u_1 + ... + c_n*u_n)/d,
724 // any feasible assignment would violate this row and therefore the constraints
751 // pivot row a b -> pivot row 1/a -b/a
752 // other row c d other row c/a d - bc/a
756 // case for the pivot row, since it continues to represent the same unknown. The
777 LogicalResult LexSimplexBase::moveRowUnknownToColumn(unsigned row) {
780 if (tableau(row, col) <= 0)
783 !maybeColumn ? col : getLexMinPivotColumn(row, *maybeColumn, col);
789 pivot(row, *maybeColumn);
793 unsigned LexSimplexBase::getLexMinPivotColumn(unsigned row, unsigned colA,
800 // pivot row a p b
801 // other row c q d
806 // pivot row 1/a -p/a -b/a
807 // other row c/a q - pc/a d - bc/a
809 // Let the sample value of the pivot row be s = pM + b before the pivot. Since
810 // the pivot row represents a violated constraint we know that s < 0.
819 // If the variable is the pivot row, its sample value goes from s to 0, for a
822 // If the variable is a non-pivot row, its sample value changes from
827 // fixed for all calls to this function since the row and tableau are fixed.
839 auto getSampleChangeCoeffForVar = [this, row](unsigned col,
841 DynamicAPInt a = tableau(row, col);
851 // Pivot row case.
852 if (u.pos == row)
855 // Non-pivot row case.
874 /// Find a pivot to change the sample value of the row in the specified
875 /// direction. The returned pivot row will involve `row` if and only if the
878 /// To increase (resp. decrease) the value of a row, we need to find a live
887 Simplex::findPivot(int row, Direction direction) const {
890 DynamicAPInt elem = tableau(row, j);
905 tableau(row, *col) < 0 ? flippedDirection(direction) : direction;
906 std::optional<unsigned> maybePivotRow = findPivotRow(row, newDirection, *col);
907 return Pivot{maybePivotRow.value_or(row), *col};
910 /// Swap the associated unknowns for the row and the column.
912 /// First we swap the index associated with the row and column. Then we update
914 void SimplexBase::swapRowWithCol(unsigned row, unsigned col) {
915 std::swap(rowUnknown[row], colUnknown[col]);
917 Unknown &uRow = unknownFromRow(row);
921 uRow.pos = row;
924 void SimplexBase::pivot(Pivot pair) { pivot(pair.row, pair.column); }
928 /// Let R be the pivot row unknown and let C be the pivot col unknown.
933 /// Let u be some other row unknown.
939 /// pivot row a b -> pivot row 1/a -b/a
940 /// other row c d other row c/a d - bc/a
945 /// pivot row a/p b/p -> pivot row p/a -b/a
946 /// other row c/q d/q other row cp/aq (da - bc)/aq
948 /// The pivot row transform is accomplished be swapping a with the pivot row's
949 /// common denominator and negating the pivot row except for the pivot column
957 // We need to negate the whole pivot row except for the pivot column.
959 // If the denominator is negative, we negate the row by simply negating the
972 for (unsigned row = 0, numRows = getNumRows(); row < numRows; ++row) {
973 if (row == pivotRow)
975 if (tableau(row, pivotCol) == 0) // Nothing to do.
977 tableau(row, 0) *= tableau(pivotRow, 0);
981 // Add rather than subtract because the pivot row has been negated.
982 tableau(row, col) = tableau(row, col) * tableau(pivotRow, 0) +
983 tableau(row, pivotCol) * tableau(pivotRow, col);
985 tableau(row, pivotCol) *= tableau(pivotRow, pivotCol);
986 tableau.normalizeRow(row);
992 /// bring the row to a non-negative sample value, and failure otherwise.
995 "unknown should be in row position");
1009 /// Find a row that can be used to pivot the column in the specified direction.
1013 /// If skipRow is set, this row is not considered, and (if it is restricted) its
1019 /// If the direction is up (resp. down) and a restricted row has a negative
1020 /// (positive) coefficient for the column, then this row imposes a bound on how
1021 /// much the sample value of the column can change. Such a row with constant
1024 /// non-negative here since the row is restricted and the tableau is consistent)
1026 /// We iterate through the rows and pick the row which imposes the most
1027 /// stringent bound, since pivoting with a row changes the row's sample value to
1040 for (unsigned row = nRedundant, e = getNumRows(); row < e; ++row) {
1041 if (skipRow && row == *skipRow)
1043 DynamicAPInt elem = tableau(row, col);
1046 if (!unknownFromRow(row).restricted)
1050 DynamicAPInt constTerm = tableau(row, 1);
1053 retRow = row;
1060 if ((diff == 0 && rowUnknown[row] < rowUnknown[*retRow]) ||
1062 retRow = row;
1155 // Move this unknown to the last row and remove the last row from the
1166 // This doesn't find a pivot row only if the column has zero
1167 // coefficients for every row.
1170 // initially as a row. Such a row could never have been pivoted to a column. So
1171 // a pivot row will always be found if we have a constraint.
1173 // If we have a variable, then the column has zero coefficients for every row
1174 // iff no constraints have been added with a non-zero coefficient for this row.
1176 for (unsigned row = nRedundant, e = getNumRows(); row < e; ++row)
1177 if (tableau(row, col) != 0)
1178 return row;
1186 // We try to find any pivot row for this column that preserves tableau
1190 // If no pivot row is found in either direction, then the unknown is
1192 // all. To do this, we just need to find any row with a non-zero
1194 // find such a row for a constraint.
1203 std::optional<unsigned> row = findAnyPivotRow(column);
1204 assert(row && "Pivot should always exist for a constraint!");
1205 pivot(*row, column);
1216 // any pivot at all, i.e., any row with non-zero coefficient for the
1220 // long as we get the unknown to row orientation and remove it.
1222 std::optional<unsigned> row = findAnyPivotRow(column);
1223 assert(row && "Pivot should always exist for a constraint!");
1224 pivot(*row, column);
1346 unsigned row) {
1347 // Keep trying to find a pivot for the row in the specified direction.
1348 while (std::optional<Pivot> maybePivot = findPivot(row, direction)) {
1349 // If findPivot returns a pivot involving the row itself, then the optimum
1351 if (maybePivot->row == row)
1356 // The row has reached its optimal sample value, which we return.
1358 // denominator for this row.
1359 return Fraction(tableau(row, 1), tableau(row, 0));
1371 unsigned row = con[conIndex].pos;
1372 return computeRowOptimum(direction, row);
1389 unsigned row = u.pos;
1390 MaybeOptimum<Fraction> optimum = computeRowOptimum(direction, row);
1394 llvm_unreachable("Could not restore row!");
1407 /// Redundant constraints are those that are in row orientation and lie in
1414 /// Mark the specified row redundant.
1417 /// rows (namely, to row nRedundant) and incrementing nRedundant to
1418 /// accomodate the new redundant row.
1421 "Unknown should be in row position!");
1457 unsigned row = u.pos;
1458 MaybeOptimum<Fraction> minimum = computeRowOptimum(Direction::Down, row);
1463 llvm_unreachable("Could not restore non-redundant row!");
1494 /// The product tableau has row layout:
1534 auto appendRowFromA = [&](unsigned row) {
1537 result.tableau(resultRow, col) = a.tableau(row, col);
1538 result.rowUnknown.emplace_back(a.rowUnknown[row]);
1545 auto appendRowFromB = [&](unsigned row) {
1547 result.tableau(resultRow, 0) = b.tableau(row, 0);
1548 result.tableau(resultRow, 1) = b.tableau(row, 1);
1552 result.tableau(resultRow, offset + col) = b.tableau(row, col);
1553 result.rowUnknown.emplace_back(indexFromBIndex(b.rowUnknown[row]));
1559 for (unsigned row = 0; row < a.nRedundant; ++row)
1560 appendRowFromA(row);
1561 for (unsigned row = 0; row < b.nRedundant; ++row)
1562 appendRowFromB(row);
1563 for (unsigned row = a.nRedundant, e = a.getNumRows(); row < e; ++row)
1564 appendRowFromA(row);
1565 for (unsigned row = b.nRedundant, e = b.getNumRows(); row < e; ++row)
1566 appendRowFromB(row);
1583 // If the variable is in row position, its sample value is the
1615 // If the variable is in row position, its sample value is the
1688 // tableau before returning. We instead add a row for the objective function
1690 // state, and finally rollback the addition of the row before returning.
1693 unsigned row = simplex.con[conIndex].pos;
1695 simplex.computeRowOptimum(Simplex::Direction::Up, row);
1697 dualDenom = simplex.tableau(row, 0);
1705 // negative of its coefficient at the objective row. If the inequality is
1706 // in row orientation, the corresponding dual variable is zero.
1729 dual.emplace_back(-simplex.tableau(row, simplex.con[i].pos));
1731 dual.emplace_back(simplex.tableau(row, simplex.con[i + 1].pos));
1971 /// Each row in the basis matrix is a vector, and the set of basis vectors
2146 for (unsigned row = 0, e = getNumRows(); row < e; ++row) {
2147 if (row > 0)
2149 os << "r" << row << ": " << rowUnknown[row];
2157 for (unsigned row = 0, numRows = getNumRows(); row < numRows; ++row)
2159 updatePrintMetrics<DynamicAPInt>(tableau(row, col), ptm);
2161 for (unsigned row = 0, numRows = getNumRows(); row < numRows; ++row) {
2163 printWithPrintMetrics<DynamicAPInt>(os, tableau(row, col), MIN_SPACING,