18#include "absl/strings/str_format.h"
35 return absl::StrFormat(
"[%g, %g]", lb, ub);
39double trunc(
double d) {
return d > 0 ? floor(d) : ceil(d); }
49 in_mip_context_(false),
50 infinite_time_limit_(
TimeLimit::Infinite()),
51 time_limit_(infinite_time_limit_.get()) {}
58#define RUN_PREPROCESSOR(name) \
59 RunAndPushIfRelevant(std::unique_ptr<Preprocessor>(new name(¶meters_)), \
60 #name, time_limit_, lp)
72 const int kMaxNumPasses = 20;
73 for (
int i = 0; i < kMaxNumPasses; ++i) {
74 const int old_stack_size = preprocessors_.size();
87 if (preprocessors_.size() == old_stack_size) {
90 LOG(
INFO) <<
"Reached fixed point after presolve pass #" << i;
105 const int old_stack_size = preprocessors_.size();
111 if (old_stack_size != preprocessors_.size()) {
127 return !preprocessors_.empty();
130#undef RUN_PREPROCESSOR
132void MainLpPreprocessor::RunAndPushIfRelevant(
133 std::unique_ptr<Preprocessor> preprocessor,
const std::string&
name,
139 const double start_time =
time_limit->GetElapsedTime();
150 if (preprocessor->Run(lp)) {
151 const EntryIndex new_num_entries = lp->
num_entries();
152 const double preprocess_time =
time_limit->GetElapsedTime() - start_time;
155 "%s(%fs): %d(%d) rows, %d(%d) columns, %d(%d) entries.",
name,
161 static_cast<int64>(new_num_entries.value()),
162 static_cast<int64>(new_num_entries.value() -
163 initial_num_entries_.value()));
165 status_ = preprocessor->status();
166 preprocessors_.push_back(std::move(preprocessor));
171 status_ = preprocessor->status();
173 LOG(
INFO) <<
name <<
" detected that the problem is "
181 while (!preprocessors_.empty()) {
182 preprocessors_.back()->RecoverSolution(solution);
183 preprocessors_.pop_back();
192 is_column_deleted_.
clear();
193 stored_value_.
clear();
203 if (
col >= is_column_deleted_.
size()) {
204 is_column_deleted_.
resize(
col + 1,
false);
208 is_column_deleted_[
col] =
true;
209 stored_value_[
col] = fixed_value;
210 stored_status_[
col] = status;
217 ColIndex old_index(0);
218 for (ColIndex
col(0);
col < is_column_deleted_.
size(); ++
col) {
219 if (is_column_deleted_[
col]) {
232 for (; old_index < num_cols; ++old_index) {
248 if (
row >= is_row_deleted_.
size()) {
251 is_row_deleted_[
row] =
true;
255 if (
row >= is_row_deleted_.
size())
return;
256 is_row_deleted_[
row] =
false;
260 return is_row_deleted_;
266 RowIndex old_index(0);
267 const RowIndex end = is_row_deleted_.
size();
268 for (RowIndex
row(0);
row < end; ++
row) {
269 if (is_row_deleted_[
row]) {
283 for (; old_index < num_rows; ++old_index) {
302 if (lower_bound == upper_bound) {
307 if (
value == lower_bound) {
311 if (
value == upper_bound) {
334Fractional ComputeMaxVariableBoundsMagnitude(
const LinearProgram& lp) {
336 const ColIndex num_cols = lp.num_variables();
337 for (ColIndex
col(0);
col < num_cols; ++
col) {
339 max_bounds_magnitude,
340 std::max(MagnitudeOrZeroIfInfinite(lp.variable_lower_bounds()[
col]),
341 MagnitudeOrZeroIfInfinite(lp.variable_upper_bounds()[
col])));
343 return max_bounds_magnitude;
351 column_deletion_helper_.
Clear();
353 for (ColIndex
col(0);
col < num_cols; ++
col) {
360 if (objective_coefficient == 0) {
372 value = objective_coefficient > 0 ? lower_bound : upper_bound;
374 VLOG(1) <<
"Problem INFEASIBLE_OR_UNBOUNDED, empty column " <<
col
375 <<
" has a minimization cost of " << objective_coefficient
377 <<
" [" << lower_bound <<
"," << upper_bound <<
"]";
385 col,
value, ComputeVariableStatus(
value, lower_bound, upper_bound));
389 return !column_deletion_helper_.
IsEmpty();
407void SubtractColumnMultipleFromConstraintBound(ColIndex
col,
411 const RowIndex
row = e.row();
425struct ColumnWithRepresentativeAndScaledCost {
426 ColumnWithRepresentativeAndScaledCost(ColIndex _col, ColIndex _representative,
433 bool operator<(
const ColumnWithRepresentativeAndScaledCost& other)
const {
436 return col < other.col;
457 int num_proportionality_classes = 0;
458 std::vector<ColIndex> proportional_columns;
464 ++num_proportionality_classes;
467 proportional_columns.push_back(
col);
470 if (proportional_columns.empty())
return false;
471 VLOG(1) <<
"The problem contains " << proportional_columns.size()
472 <<
" columns which belong to " << num_proportionality_classes
473 <<
" proportionality classes.";
477 column_factors_.
assign(num_cols, 0.0);
478 for (
const ColIndex
col : proportional_columns) {
492 for (
const ColIndex
col : proportional_columns) {
496 const bool is_rc_positive_or_zero =
498 const bool is_rc_negative_or_zero =
500 bool is_slope_upper_bounded = is_rc_positive_or_zero;
501 bool is_slope_lower_bounded = is_rc_negative_or_zero;
502 if (column_factors_[
col] < 0.0) {
503 std::swap(is_slope_lower_bounded, is_slope_upper_bounded);
507 column_factors_[
col];
508 if (is_slope_lower_bounded) {
512 if (is_slope_upper_bounded) {
519 for (
const ColIndex
col : proportional_columns) {
527 VLOG(1) <<
"Problem INFEASIBLE_OR_UNBOUNDED, no feasible dual values"
528 <<
" can satisfy the constraints of the proportional columns"
530 <<
" the associated quantity must be in ["
540 for (
const ColIndex
col : proportional_columns) {
544 column_factors_[
col];
547 bool variable_can_be_fixed =
false;
555 variable_can_be_fixed =
true;
556 target_bound = (column_factors_[
col] >= 0.0) ? upper_bound : lower_bound;
560 variable_can_be_fixed =
true;
561 target_bound = (column_factors_[
col] >= 0.0) ? lower_bound : upper_bound;
564 if (variable_can_be_fixed) {
569 VLOG(1) <<
"Problem INFEASIBLE_OR_UNBOUNDED.";
576 ComputeVariableStatus(
target_bound, lower_bound, upper_bound));
582 std::vector<ColumnWithRepresentativeAndScaledCost> sorted_columns;
583 for (
const ColIndex
col : proportional_columns) {
588 sorted_columns.
push_back(ColumnWithRepresentativeAndScaledCost(
593 std::sort(sorted_columns.begin(), sorted_columns.end());
602 for (
int i = 0; i < sorted_columns.size();) {
603 const ColIndex target_col = sorted_columns[i].col;
604 const ColIndex target_representative = sorted_columns[i].representative;
605 const Fractional target_scaled_cost = sorted_columns[i].scaled_cost;
612 for (++i; i < sorted_columns.size(); ++i) {
613 if (sorted_columns[i].
representative != target_representative)
break;
614 if (std::abs(sorted_columns[i].
scaled_cost - target_scaled_cost) >=
619 const ColIndex
col = sorted_columns[i].col;
622 lower_bounds_[
col] = lower_bound;
623 upper_bounds_[
col] = upper_bound;
624 merged_columns_[
col] = target_col;
629 column_factors_[
col] / column_factors_[target_col];
640 MinInMagnitudeOrZeroIfInfinite(lower_bound, upper_bound);
641 Fractional lower_diff = (lower_bound - target_value) * bound_factor;
642 Fractional upper_diff = (upper_bound - target_value) * bound_factor;
643 if (bound_factor < 0.0) {
644 std::swap(lower_diff, upper_diff);
649 SubtractColumnMultipleFromConstraintBound(
col, target_value, lp);
652 ComputeVariableStatus(target_value, lower_bound, upper_bound));
658 if (num_merged > 0) {
659 merged_columns_[target_col] = target_col;
660 const Fractional target_value = MinInMagnitudeOrZeroIfInfinite(
661 lower_bounds_[target_col], upper_bounds_[target_col]);
665 SubtractColumnMultipleFromConstraintBound(target_col, target_value, lp);
672 return !column_deletion_helper_.
IsEmpty();
683 const ColIndex num_cols = merged_columns_.
size();
686 DenseRow distance_to_bound(num_cols, 0.0);
687 DenseRow wanted_value(num_cols, 0.0);
691 for (ColIndex
col(0);
col < num_cols; ++
col) {
692 if (merged_columns_[
col] ==
col) {
696 if (distance_to_upper_bound < distance_to_lower_bound) {
697 distance_to_bound[
col] = distance_to_upper_bound;
698 is_distance_to_upper_bound[
col] =
true;
700 distance_to_bound[
col] = distance_to_lower_bound;
701 is_distance_to_upper_bound[
col] =
false;
703 is_representative_basic[
col] =
710 lower_bounds_[
col], upper_bounds_[
col]);
717 for (ColIndex
col(0);
col < num_cols; ++
col) {
729 const bool to_upper_bound =
730 (bound_factor > 0.0) == is_distance_to_upper_bound[
representative];
731 if (width <= scaled_distance) {
733 to_upper_bound ? lower_bounds_[
col] : upper_bounds_[
col];
736 lower_bounds_[
col], upper_bounds_[
col]);
737 distance_to_bound[
representative] -= width * std::abs(bound_factor);
740 to_upper_bound ? upper_bounds_[
col] - scaled_distance
741 : lower_bounds_[
col] + scaled_distance;
764 const bool use_this_variable =
765 (error * bound_factor > 0.0) ? (upper_bounds_[
col] ==
kInfinity)
767 if (use_this_variable) {
800 row_factors_.
assign(num_rows, 0.0);
801 for (RowIndex
row(0);
row < num_rows; ++
row) {
803 if (!row_transpose.
IsEmpty()) {
822 transpose,
parameters_.preprocessor_zero_tolerance());
824 int num_proportional_rows = 0;
825 for (RowIndex
row(0);
row < num_rows; ++
row) {
828 mapping[representative_row_as_col] = representative_row_as_col;
829 is_a_representative[
ColToRowIndex(representative_row_as_col)] =
true;
830 ++num_proportional_rows;
836 for (RowIndex
row(0);
row < num_rows; ++
row) {
842 const RowIndex representative_row =
ColToRowIndex(mapping[row_as_col]);
845 row_factors_[representative_row] / row_factors_[
row];
849 std::swap(implied_lb, implied_ub);
855 lower_bound_sources_[representative_row] =
row;
859 upper_bound_sources_[representative_row] =
row;
867 for (RowIndex
row(0);
row < num_rows; ++
row) {
868 if (!is_a_representative[
row])
continue;
869 const RowIndex lower_source = lower_bound_sources_[
row];
870 const RowIndex upper_source = upper_bound_sources_[
row];
875 if (lower_source == upper_source) {
879 row_deletion_helper_.
UnmarkRow(lower_source);
892 row_deletion_helper_.
UnmarkRow(lower_source);
897 row_deletion_helper_.
UnmarkRow(upper_source);
905 RowIndex new_representative = lower_source;
906 RowIndex other = upper_source;
907 if (std::abs(row_factors_[new_representative]) <
908 std::abs(row_factors_[other])) {
909 std::swap(new_representative, other);
914 row_factors_[new_representative] / row_factors_[other];
918 std::swap(new_lb, new_ub);
921 lower_bound_sources_[new_representative] = new_representative;
922 upper_bound_sources_[new_representative] = new_representative;
925 lower_bound_sources_[new_representative] = other;
929 if (new_ub < lp->constraint_upper_bounds()[new_representative]) {
930 upper_bound_sources_[new_representative] = other;
934 const RowIndex new_lower_source =
935 lower_bound_sources_[new_representative];
936 if (new_lower_source == upper_bound_sources_[new_representative]) {
937 row_deletion_helper_.
UnmarkRow(new_lower_source);
938 lower_bound_sources_[new_representative] =
kInvalidRow;
939 upper_bound_sources_[new_representative] =
kInvalidRow;
948 if (new_lb > new_ub) {
949 if (lower_bound_sources_[new_representative] == new_representative) {
955 row_deletion_helper_.
UnmarkRow(new_representative);
962 return !row_deletion_helper_.
IsEmpty();
975 for (RowIndex
row(0);
row < num_rows; ++
row) {
976 const RowIndex lower_source = lower_bound_sources_[
row];
977 const RowIndex upper_source = upper_bound_sources_[
row];
992 const Fractional corrected_dual_value = lp_is_maximization_problem_
995 if (corrected_dual_value != 0.0) {
1006 const Fractional factor = row_factors_[
row] / row_factors_[lower_source];
1016 const Fractional factor = row_factors_[
row] / row_factors_[upper_source];
1043 for (ColIndex
col(0);
col < num_cols; ++
col) {
1046 if (lower_bound == upper_bound) {
1051 SubtractColumnMultipleFromConstraintBound(
col, fixed_value, lp);
1058 return !column_deletion_helper_.
IsEmpty();
1082 for (ColIndex
col(0);
col < num_cols; ++
col) {
1086 const RowIndex
row = e.row();
1089 implied_lower_bounds[
row] += lower * coeff;
1090 implied_upper_bounds[
row] += upper * coeff;
1092 implied_lower_bounds[
row] += upper * coeff;
1093 implied_upper_bounds[
row] += lower * coeff;
1101 int num_implied_free_constraints = 0;
1102 int num_forcing_constraints = 0;
1103 is_forcing_up_.
assign(num_rows,
false);
1105 for (RowIndex
row(0);
row < num_rows; ++
row) {
1106 if (row_degree[
row] == 0)
continue;
1112 implied_upper_bounds[
row]) ||
1115 VLOG(1) <<
"implied bound " << implied_lower_bounds[
row] <<
" "
1116 << implied_upper_bounds[
row];
1117 VLOG(1) <<
"constraint bound " << lower <<
" " << upper;
1126 is_forcing_down[
row] =
true;
1127 ++num_forcing_constraints;
1131 implied_lower_bounds[
row])) {
1132 is_forcing_up_[
row] =
true;
1133 ++num_forcing_constraints;
1144 implied_lower_bounds[
row]) &&
1148 ++num_implied_free_constraints;
1152 if (num_implied_free_constraints > 0) {
1153 VLOG(1) << num_implied_free_constraints <<
" implied free constraints.";
1156 if (num_forcing_constraints > 0) {
1157 VLOG(1) << num_forcing_constraints <<
" forcing constraints.";
1160 costs_.
resize(num_cols, 0.0);
1161 for (ColIndex
col(0);
col < num_cols; ++
col) {
1165 bool is_forced =
false;
1168 if (is_forcing_down[e.row()]) {
1169 const Fractional candidate = e.coefficient() < 0.0 ? lower : upper;
1178 target_bound = std::abs(lower) < std::abs(upper) ? lower : upper;
1181 VLOG(1) <<
"A variable is forced in both directions! bounds: ["
1182 << std::fixed << std::setprecision(10) << lower <<
", "
1183 << upper <<
"]. coeff:" << e.coefficient();
1190 if (is_forcing_up_[e.row()]) {
1191 const Fractional candidate = e.coefficient() < 0.0 ? upper : lower;
1196 target_bound = std::abs(lower) < std::abs(upper) ? lower : upper;
1199 VLOG(1) <<
"A variable is forced in both directions! bounds: ["
1200 << std::fixed << std::setprecision(10) << lower <<
", "
1201 << upper <<
"]. coeff:" << e.coefficient();
1220 for (RowIndex
row(0);
row < num_rows; ++
row) {
1227 if (is_forcing_down[
row] || is_forcing_up_[
row]) {
1235 return !column_deletion_helper_.
IsEmpty();
1246 const ColIndex num_cols = deleted_columns_.
num_cols();
1248 for (ColIndex
col(0);
col < num_cols; ++
col) {
1251 const RowIndex
row = e.row();
1253 last_deleted_row[
col] =
row;
1271 for (RowIndex
row(0);
row < num_rows; ++
row) {
1277 if (last_deleted_row[
col] !=
row)
continue;
1280 const Fractional reduced_cost = costs_[
col] - scalar_product;
1282 if (is_forcing_up_[
row] == !lp_is_maximization_problem_) {
1283 if (
bound < new_dual_value) {
1284 new_dual_value =
bound;
1285 new_basic_column =
col;
1288 if (
bound > new_dual_value) {
1289 new_dual_value =
bound;
1290 new_basic_column =
col;
1310struct ColWithDegree {
1313 ColWithDegree(ColIndex c, EntryIndex n) :
col(c),
num_entries(n) {}
1314 bool operator<(
const ColWithDegree& other)
const {
1316 return col < other.col;
1333 const int size = num_rows.value();
1342 for (ColIndex
col(0);
col < num_cols; ++
col) {
1346 Fractional entry_lb = e.coefficient() * lower_bound;
1347 Fractional entry_ub = e.coefficient() * upper_bound;
1348 if (e.coefficient() < 0.0) std::swap(entry_lb, entry_ub);
1349 lb_sums[e.row()].Add(entry_lb);
1350 ub_sums[e.row()].Add(entry_ub);
1360 for (RowIndex
row(0);
row < num_rows; ++
row) {
1369 variable_offsets_.
assign(num_cols, 0.0);
1386 std::vector<ColWithDegree> col_by_degree;
1387 for (ColIndex
col(0);
col < num_cols; ++
col) {
1388 col_by_degree.push_back(
1391 std::sort(col_by_degree.begin(), col_by_degree.end());
1394 int num_already_free_variables = 0;
1395 int num_implied_free_variables = 0;
1396 int num_fixed_variables = 0;
1397 for (ColWithDegree col_with_degree : col_by_degree) {
1398 const ColIndex
col = col_with_degree.col;
1404 ++num_already_free_variables;
1407 if (lower_bound == upper_bound)
continue;
1415 if (used_rows[e.row()])
continue;
1421 if (coeff < 0.0) std::swap(entry_lb, entry_ub);
1427 Fractional implied_lb = -ub_sums[e.row()].SumWithout(entry_ub) / coeff;
1428 Fractional implied_ub = -lb_sums[e.row()].SumWithout(entry_lb) / coeff;
1429 if (coeff < 0.0) std::swap(implied_lb, implied_ub);
1430 overall_implied_lb =
std::max(overall_implied_lb, implied_lb);
1431 overall_implied_ub =
std::min(overall_implied_ub, implied_ub);
1438 overall_implied_ub)) {
1446 overall_implied_lb) ||
1452 ++num_fixed_variables;
1455 overall_implied_lb)) {
1461 ++num_fixed_variables;
1468 overall_implied_lb) &&
1471 ++num_implied_free_variables;
1474 used_rows[e.row()] =
true;
1497 MinInMagnitudeOrZeroIfInfinite(lower_bound, upper_bound);
1498 if (offset != 0.0) {
1499 variable_offsets_[
col] = offset;
1500 SubtractColumnMultipleFromConstraintBound(
col, offset, lp);
1502 postsolve_status_of_free_variables_[
col] =
1503 ComputeVariableStatus(offset, lower_bound, upper_bound);
1506 VLOG(1) << num_already_free_variables <<
" free variables in the problem.";
1507 VLOG(1) << num_implied_free_variables <<
" implied free columns.";
1508 VLOG(1) << num_fixed_variables <<
" variables can be fixed.";
1509 return num_implied_free_variables > 0;
1516 for (ColIndex
col(0);
col < num_cols; ++
col) {
1524 postsolve_status_of_free_variables_[
col];
1546 for (ColIndex doubleton_col(0); doubleton_col < num_cols; ++doubleton_col) {
1555 r.col = doubleton_col;
1559 if (row_deletion_helper_.
IsRowMarked(e.row()))
break;
1560 r.row[
index] = e.row();
1561 r.coeff[
index] = e.coefficient();
1565 if (
index != NUM_ROWS)
continue;
1577 if (std::abs(r.coeff[DELETED]) < std::abs(r.coeff[MODIFIED])) {
1578 std::swap(r.coeff[DELETED], r.coeff[MODIFIED]);
1579 std::swap(r.row[DELETED], r.row[MODIFIED]);
1586 r.deleted_row_as_column.Swap(
1595 new_variable_lb /= r.coeff[DELETED];
1596 new_variable_ub /= r.coeff[DELETED];
1597 if (r.coeff[DELETED] < 0.0) std::swap(new_variable_lb, new_variable_ub);
1603 r.deleted_row_as_column.AddMultipleToSparseVectorAndIgnoreCommonIndex(
1604 -r.coeff[MODIFIED] / r.coeff[DELETED],
ColToRowIndex(r.col),
1610 if (r.objective_coefficient != 0.0) {
1613 if (
col == r.col)
continue;
1616 e.coefficient() * r.objective_coefficient / r.coeff[DELETED];
1622 if (std::abs(new_objective) >
parameters_.drop_tolerance()) {
1630 restore_stack_.push_back(r);
1633 if (!row_deletion_helper_.
IsEmpty()) {
1646 for (
const RestoreInfo& r :
Reverse(restore_stack_)) {
1678 if (
col == r.col)
continue;
1679 new_variable_value -= (e.coefficient() / r.coeff[DELETED]) *
1692 r.objective_coefficient -
1693 r.coeff[MODIFIED] * solution->
dual_values[r.row[MODIFIED]];
1696 current_reduced_cost / r.coeff[DELETED];
1723 if (deleted_rows_as_column_.
IsEmpty()) {
1736 const RowIndex
row = e.row();
1744 const bool is_constraint_upper_bound_relevant =
1745 e.coefficient() > 0.0 ? !is_unbounded_up : is_unbounded_up;
1746 activity_sign_correction_[
row] =
1747 is_constraint_upper_bound_relevant ? 1.0 : -1.0;
1748 rhs_[
row] = is_constraint_upper_bound_relevant
1756 is_unbounded_[
col] =
true;
1757 Fractional initial_feasible_value = MinInMagnitudeOrZeroIfInfinite(
1761 col, initial_feasible_value,
1762 ComputeVariableStatus(initial_feasible_value,
1785 for (RowIndex
row(0);
row < num_rows; ++
row) {
1787 dual_ub_[
row] = 0.0;
1790 dual_lb_[
row] = 0.0;
1795 may_have_participated_lb_.
assign(num_cols,
false);
1796 may_have_participated_ub_.
assign(num_cols,
false);
1799 std::deque<ColIndex> columns_to_process;
1801 std::vector<RowIndex> changed_rows;
1802 for (ColIndex
col(0);
col < num_cols; ++
col) {
1803 columns_to_process.push_back(
col);
1809 const int limit = 5 * num_cols.value();
1810 for (
int count = 0; !columns_to_process.empty() && count < limit; ++count) {
1811 const ColIndex
col = columns_to_process.front();
1812 columns_to_process.pop_front();
1813 in_columns_to_process[
col] =
false;
1825 rc_lb.
Add(col_cost);
1826 rc_ub.
Add(col_cost);
1828 if (row_deletion_helper_.
IsRowMarked(e.row()))
continue;
1831 rc_lb.
Add(-coeff * dual_ub_[e.row()]);
1832 rc_ub.
Add(-coeff * dual_lb_[e.row()]);
1834 rc_lb.
Add(-coeff * dual_lb_[e.row()]);
1835 rc_ub.
Add(-coeff * dual_ub_[e.row()]);
1843 bool can_be_removed =
false;
1845 bool rc_is_away_from_zero;
1846 if (rc_ub.
Sum() <= low_tolerance) {
1847 can_be_removed =
true;
1849 rc_is_away_from_zero = rc_ub.
Sum() <= -high_tolerance;
1850 can_be_removed = !may_have_participated_ub_[
col];
1852 if (rc_lb.
Sum() >= -low_tolerance) {
1856 can_be_removed =
true;
1858 rc_is_away_from_zero = rc_lb.
Sum() >= high_tolerance;
1859 can_be_removed = !may_have_participated_lb_[
col];
1863 if (can_be_removed) {
1875 if (rc_is_away_from_zero) {
1876 VLOG(1) <<
"Problem INFEASIBLE_OR_UNBOUNDED, variable " <<
col
1878 <<
" and its reduced cost is in [" << rc_lb.
Sum() <<
", "
1879 << rc_ub.
Sum() <<
"]";
1891 if (col_cost != 0.0)
continue;
1896 if (IsConstraintBlockingVariable(*lp, e.coefficient(), e.row())) {
1921 changed_rows.clear();
1923 if (row_deletion_helper_.
IsRowMarked(e.row()))
continue;
1925 const RowIndex
row = e.row();
1929 if (candidate < dual_ub_[
row]) {
1930 dual_ub_[
row] = candidate;
1931 may_have_participated_lb_[
col] =
true;
1936 if (candidate > dual_lb_[
row]) {
1937 dual_lb_[
row] = candidate;
1938 may_have_participated_lb_[
col] =
true;
1946 if (candidate > dual_lb_[
row]) {
1947 dual_lb_[
row] = candidate;
1948 may_have_participated_ub_[
col] =
true;
1953 if (candidate < dual_ub_[
row]) {
1954 dual_ub_[
row] = candidate;
1955 may_have_participated_ub_[
col] =
true;
1962 if (!changed_rows.empty()) {
1964 for (
const RowIndex
row : changed_rows) {
1968 if (!in_columns_to_process[
col]) {
1969 columns_to_process.push_back(
col);
1970 in_columns_to_process[
col] =
true;
1982 for (ColIndex
col(0);
col < end; ++
col) {
1992 return !column_deletion_helper_.
IsEmpty() || !row_deletion_helper_.
IsEmpty();
2005 for (RowIndex
row(0);
row < num_rows; ++
row) {
2010 if (is_unbounded_[
col]) {
2011 last_deleted_column[
row] =
col;
2018 const ColIndex num_cols = is_unbounded_.
size();
2019 for (ColIndex
col(0);
col < num_cols; ++
col) {
2020 if (!is_unbounded_[
col])
continue;
2024 const RowIndex
row = e.row();
2040 if (activity * activity_sign_correction_[
row] < 0.0) {
2042 if (std::abs(
bound) > std::abs(primal_value_shift)) {
2043 primal_value_shift =
bound;
2052 activity_sign_correction_[row_at_bound] == 1.0
2067 for (RowIndex
row(0);
row < num_rows; ++
row) {
2075 return !row_deletion_helper_.
IsEmpty();
2097 for (ColIndex
col(0);
col < num_cols; ++
col) {
2104 for (RowIndex
row(0);
row < num_rows; ++
row) {
2105 if (degree[
row] == 0) {
2112 VLOG(1) <<
"Problem PRIMAL_INFEASIBLE, constraint " <<
row
2113 <<
" is empty and its range ["
2123 return !row_deletion_helper_.
IsEmpty();
2140 is_maximization_(lp.IsMaximizationProblem()),
2142 cost_(lp.objective_coefficients()[e.
col]),
2143 variable_lower_bound_(lp.variable_lower_bounds()[e.
col]),
2144 variable_upper_bound_(lp.variable_upper_bounds()[e.
col]),
2145 constraint_lower_bound_(lp.constraint_lower_bounds()[e.
row]),
2146 constraint_upper_bound_(lp.constraint_upper_bounds()[e.
row]),
2147 constraint_status_(status) {}
2155 SingletonRowUndo(deleted_columns, solution);
2158 ZeroCostSingletonColumnUndo(
parameters, deleted_rows, solution);
2161 SingletonColumnInEqualityUndo(
parameters, deleted_rows, solution);
2164 MakeConstraintAnEqualityUndo(solution);
2169void SingletonPreprocessor::DeleteSingletonRow(MatrixEntry e,
2175 if (e.coeff < 0.0) {
2176 std::swap(implied_lower_bound, implied_upper_bound);
2183 std::abs(
parameters_.preprocessor_zero_tolerance() / e.coeff);
2185 implied_lower_bound - potential_error > old_lower_bound
2186 ? implied_lower_bound
2189 implied_upper_bound + potential_error < old_upper_bound
2190 ? implied_upper_bound
2193 if (new_upper_bound < new_lower_bound) {
2196 VLOG(1) <<
"Problem ProblemStatus::INFEASIBLE_OR_UNBOUNDED, singleton "
2197 "row causes the bound of the variable "
2198 << e.col <<
" to be infeasible by "
2199 << new_lower_bound - new_upper_bound;
2205 new_upper_bound = new_lower_bound;
2208 new_lower_bound = new_upper_bound;
2210 DCHECK_EQ(new_lower_bound, new_upper_bound);
2224void SingletonUndo::SingletonRowUndo(
const SparseMatrix& deleted_columns,
2225 ProblemSolution* solution)
const {
2226 DCHECK_EQ(0, solution->dual_values[e_.row]);
2231 const VariableStatus status = solution->variable_statuses[e_.col];
2235 Fractional implied_lower_bound = constraint_lower_bound_ / e_.coeff;
2236 Fractional implied_upper_bound = constraint_upper_bound_ / e_.coeff;
2237 if (e_.coeff < 0.0) {
2238 std::swap(implied_lower_bound, implied_upper_bound);
2240 const bool lower_bound_changed = implied_lower_bound > variable_lower_bound_;
2241 const bool upper_bound_changed = implied_upper_bound < variable_upper_bound_;
2243 if (!lower_bound_changed && !upper_bound_changed)
return;
2251 ScalarProduct(solution->dual_values, deleted_columns.column(e_.col));
2252 const Fractional reduced_cost_for_minimization =
2253 is_maximization_ ? -reduced_cost : reduced_cost;
2256 DCHECK(lower_bound_changed || upper_bound_changed);
2257 if (reduced_cost_for_minimization >= 0.0 && !lower_bound_changed) {
2261 if (reduced_cost_for_minimization <= 0.0 && !upper_bound_changed) {
2272 solution->dual_values[e_.row] = reduced_cost / e_.coeff;
2275 (!lower_bound_changed || !upper_bound_changed)) {
2276 new_constraint_status = lower_bound_changed
2280 if (e_.coeff < 0.0) {
2288 solution->constraint_statuses[e_.row] = new_constraint_status;
2291void SingletonPreprocessor::UpdateConstraintBoundsWithVariableBounds(
2292 MatrixEntry e, LinearProgram* lp) {
2293 Fractional lower_delta = -e.coeff * lp->variable_upper_bounds()[e.col];
2294 Fractional upper_delta = -e.coeff * lp->variable_lower_bounds()[e.col];
2295 if (e.coeff < 0.0) {
2296 std::swap(lower_delta, upper_delta);
2298 lp->SetConstraintBounds(e.row,
2299 lp->constraint_lower_bounds()[e.row] + lower_delta,
2300 lp->constraint_upper_bounds()[e.row] + upper_delta);
2303bool SingletonPreprocessor::IntegerSingletonColumnIsRemovable(
2304 const MatrixEntry& matrix_entry,
const LinearProgram& lp)
const {
2306 DCHECK(lp.IsVariableInteger(matrix_entry.col));
2307 const SparseMatrix& transpose = lp.GetTransposeSparseMatrix();
2319 coefficient_ratio,
parameters_.solution_feasibility_tolerance())) {
2324 lp.constraint_lower_bounds()[matrix_entry.row];
2326 const Fractional lower_bound_ratio = constraint_lb / matrix_entry.coeff;
2328 lower_bound_ratio,
parameters_.solution_feasibility_tolerance())) {
2333 lp.constraint_upper_bounds()[matrix_entry.row];
2335 const Fractional upper_bound_ratio = constraint_ub / matrix_entry.coeff;
2337 upper_bound_ratio,
parameters_.solution_feasibility_tolerance())) {
2344void SingletonPreprocessor::DeleteZeroCostSingletonColumn(
2345 const SparseMatrix& transpose, MatrixEntry e, LinearProgram* lp) {
2347 const SparseColumn& column = transpose.column(transpose_col);
2354 UpdateConstraintBoundsWithVariableBounds(e, lp);
2359void SingletonUndo::ZeroCostSingletonColumnUndo(
2360 const GlopParameters&
parameters,
const SparseMatrix& deleted_rows,
2361 ProblemSolution* solution)
const {
2364 if (variable_upper_bound_ == variable_lower_bound_) {
2365 solution->primal_values[e_.col] = variable_lower_bound_;
2377 solution->primal_values[e_.col] = variable_lower_bound_;
2381 solution->primal_values[e_.col] = variable_upper_bound_;
2384 if (constraint_upper_bound_ == constraint_lower_bound_) {
2394 ScalarProduct(solution->primal_values, deleted_rows.column(row_as_col));
2401 const auto is_smaller_with_tolerance = [tolerance](
Fractional a,
2405 if (variable_lower_bound_ != -
kInfinity) {
2407 activity + e_.coeff * variable_lower_bound_;
2408 if (is_smaller_with_tolerance(constraint_lower_bound_, activity_at_lb) &&
2409 is_smaller_with_tolerance(activity_at_lb, constraint_upper_bound_)) {
2410 solution->primal_values[e_.col] = variable_lower_bound_;
2415 if (variable_upper_bound_ !=
kInfinity) {
2417 activity + e_.coeff * variable_upper_bound_;
2418 if (is_smaller_with_tolerance(constraint_lower_bound_, actibity_at_ub) &&
2419 is_smaller_with_tolerance(actibity_at_ub, constraint_upper_bound_)) {
2420 solution->primal_values[e_.col] = variable_upper_bound_;
2429 if (constraint_lower_bound_ == -
kInfinity &&
2431 solution->primal_values[e_.col] = 0.0;
2439 if (constraint_lower_bound_ == constraint_upper_bound_) {
2440 solution->primal_values[e_.col] =
2441 (constraint_lower_bound_ - activity) / e_.coeff;
2446 bool set_constraint_to_lower_bound;
2447 if (constraint_lower_bound_ == -
kInfinity) {
2448 set_constraint_to_lower_bound =
false;
2449 }
else if (constraint_upper_bound_ ==
kInfinity) {
2450 set_constraint_to_lower_bound =
true;
2454 const Fractional to_lb = (constraint_lower_bound_ - activity) / e_.coeff;
2455 const Fractional to_ub = (constraint_upper_bound_ - activity) / e_.coeff;
2456 set_constraint_to_lower_bound =
2457 std::max(variable_lower_bound_ - to_lb, to_lb - variable_upper_bound_) <
2458 std::max(variable_lower_bound_ - to_ub, to_ub - variable_upper_bound_);
2461 if (set_constraint_to_lower_bound) {
2462 solution->primal_values[e_.col] =
2463 (constraint_lower_bound_ - activity) / e_.coeff;
2466 solution->primal_values[e_.col] =
2467 (constraint_upper_bound_ - activity) / e_.coeff;
2472void SingletonPreprocessor::DeleteSingletonColumnInEquality(
2473 const SparseMatrix& transpose, MatrixEntry e, LinearProgram* lp) {
2476 const SparseColumn& row_as_column = transpose.column(transpose_col);
2477 undo_stack_.push_back(
2488 const Fractional rhs = lp->constraint_upper_bounds()[e.row];
2491 lp->SetObjectiveOffset(lp->objective_offset() + rhs * multiplier);
2496 lp->objective_coefficients()[
col] - e.coefficient() * multiplier;
2503 if (std::abs(new_cost) <
parameters_.preprocessor_zero_tolerance()) {
2506 lp->SetObjectiveCoefficient(
col, new_cost);
2511 UpdateConstraintBoundsWithVariableBounds(e, lp);
2515void SingletonUndo::SingletonColumnInEqualityUndo(
2516 const GlopParameters&
parameters,
const SparseMatrix& deleted_rows,
2517 ProblemSolution* solution)
const {
2519 ZeroCostSingletonColumnUndo(
parameters, deleted_rows, solution);
2523 solution->dual_values[e_.row] += cost_ / e_.coeff;
2530void SingletonUndo::MakeConstraintAnEqualityUndo(
2531 ProblemSolution* solution)
const {
2533 solution->constraint_statuses[e_.row] = constraint_status_;
2537bool SingletonPreprocessor::MakeConstraintAnEqualityIfPossible(
2538 const SparseMatrix& transpose, MatrixEntry e, LinearProgram* lp) {
2541 const Fractional cst_lower_bound = lp->constraint_lower_bounds()[e.row];
2542 const Fractional cst_upper_bound = lp->constraint_upper_bounds()[e.row];
2543 if (cst_lower_bound == cst_upper_bound)
return true;
2549 const DenseRow& variable_ubs = lp->variable_upper_bounds();
2550 const DenseRow& variable_lbs = lp->variable_lower_bounds();
2551 if (e.row >= row_sum_is_cached_.
size() || !row_sum_is_cached_[e.row]) {
2552 if (e.row >= row_sum_is_cached_.
size()) {
2553 const int new_size = e.row.value() + 1;
2554 row_sum_is_cached_.
resize(new_size);
2555 row_lb_sum_.resize(new_size);
2556 row_ub_sum_.resize(new_size);
2558 row_sum_is_cached_[e.row] =
true;
2559 row_lb_sum_[e.row].Add(cst_lower_bound);
2560 row_ub_sum_[e.row].Add(cst_upper_bound);
2571 if (column_deletion_helper_.
IsColumnMarked(row_as_col))
continue;
2572 if (entry.coefficient() > 0.0) {
2573 row_lb_sum_[e.row].Add(-entry.coefficient() * variable_ubs[row_as_col]);
2574 row_ub_sum_[e.row].Add(-entry.coefficient() * variable_lbs[row_as_col]);
2576 row_lb_sum_[e.row].Add(-entry.coefficient() * variable_lbs[row_as_col]);
2577 row_ub_sum_[e.row].Add(-entry.coefficient() * variable_ubs[row_as_col]);
2589 c > 0.0 ? row_lb_sum_[e.row].SumWithout(-c * variable_ubs[e.col]) / c
2590 : row_ub_sum_[e.row].SumWithout(-c * variable_ubs[e.col]) / c;
2592 c > 0.0 ? row_ub_sum_[e.row].SumWithout(-c * variable_lbs[e.col]) / c
2593 : row_lb_sum_[e.row].SumWithout(-c * variable_lbs[e.col]) / c;
2599 lp->GetObjectiveCoefficientForMinimizationVersion(e.col);
2606 ub, lp->variable_upper_bounds()[e.col])) {
2612 lp->SetConstraintBounds(e.row, cst_upper_bound, cst_upper_bound);
2619 lp->SetConstraintBounds(e.row, cst_lower_bound, cst_lower_bound);
2625 VLOG(1) <<
"Problem ProblemStatus::INFEASIBLE_OR_UNBOUNDED, singleton "
2627 << e.col <<
" has a cost (for minimization) of " <<
cost
2628 <<
" and is unbounded towards kInfinity.";
2645 lp->SetVariableBounds(e.col, lp->variable_lower_bounds()[e.col],
kInfinity);
2648 lp->variable_lower_bounds()[e.col], lb)) {
2654 lp->SetConstraintBounds(e.row, cst_lower_bound, cst_lower_bound);
2661 lp->SetConstraintBounds(e.row, cst_upper_bound, cst_upper_bound);
2667 VLOG(1) <<
"Problem ProblemStatus::INFEASIBLE_OR_UNBOUNDED, singleton "
2669 << e.col <<
" has a cost (for minimization) of " <<
cost
2670 <<
" and is unbounded towards -kInfinity.";
2675 lp->SetVariableBounds(e.col, -
kInfinity,
2676 lp->variable_upper_bounds()[e.col]);
2679 if (lp->constraint_lower_bounds()[e.row] ==
2680 lp->constraint_upper_bounds()[e.row]) {
2681 undo_stack_.push_back(SingletonUndo(
2695 ColIndex num_cols(matrix.
num_cols());
2696 RowIndex num_rows(matrix.
num_rows());
2701 std::vector<ColIndex> column_to_process;
2702 for (ColIndex
col(0);
col < num_cols; ++
col) {
2704 if (column_degree[
col] == 1) {
2705 column_to_process.push_back(
col);
2711 std::vector<RowIndex> row_to_process;
2712 for (RowIndex
row(0);
row < num_rows; ++
row) {
2714 if (row_degree[
row] == 1) {
2715 row_to_process.push_back(
row);
2721 (!column_to_process.empty() || !row_to_process.empty())) {
2723 const ColIndex
col = column_to_process.back();
2724 column_to_process.pop_back();
2725 if (column_degree[
col] <= 0)
continue;
2726 const MatrixEntry e = GetSingletonColumnMatrixEntry(
col, matrix);
2728 !IntegerSingletonColumnIsRemovable(e, *lp)) {
2735 DeleteZeroCostSingletonColumn(transpose, e, lp);
2736 }
else if (MakeConstraintAnEqualityIfPossible(transpose, e, lp)) {
2737 DeleteSingletonColumnInEquality(transpose, e, lp);
2741 --row_degree[e.row];
2742 if (row_degree[e.row] == 1) {
2747 const RowIndex
row = row_to_process.back();
2748 row_to_process.pop_back();
2749 if (row_degree[
row] <= 0)
continue;
2750 const MatrixEntry e = GetSingletonRowMatrixEntry(
row, transpose);
2752 DeleteSingletonRow(e, lp);
2753 --column_degree[e.col];
2754 if (column_degree[e.col] == 1) {
2763 return !column_deletion_helper_.
IsEmpty() || !row_deletion_helper_.
IsEmpty();
2781 for (
int i = undo_stack_.size() - 1; i >= 0; --i) {
2782 undo_stack_[i].Undo(
parameters_, deleted_columns_, deleted_rows_, solution);
2786MatrixEntry SingletonPreprocessor::GetSingletonColumnMatrixEntry(
2791 return MatrixEntry(e.row(),
col, e.coefficient());
2795 LOG(DFATAL) <<
"No unmarked entry in a column that is supposed to have one.";
2797 return MatrixEntry(RowIndex(0), ColIndex(0), 0.0);
2800MatrixEntry SingletonPreprocessor::GetSingletonRowMatrixEntry(
2801 RowIndex
row,
const SparseMatrix& transpose) {
2806 return MatrixEntry(
row,
col, e.coefficient());
2810 LOG(DFATAL) <<
"No unmarked entry in a row that is supposed to have one.";
2812 return MatrixEntry(RowIndex(0), ColIndex(0), 0.0);
2823 if (num_cols == 0)
return false;
2829 Fractional num_non_zero_objective_coefficients = 0.0;
2830 for (ColIndex
col(0);
col < num_cols; ++
col) {
2832 row_degree[e.row()] += 1.0;
2835 num_non_zero_objective_coefficients += 1.0;
2847 const EntryIndex initial_num_entries = lp->
num_entries();
2848 int num_zeroed_objective_coefficients = 0;
2849 for (ColIndex
col(0);
col < num_cols; ++
col) {
2857 std::max(std::abs(lower_bound), std::abs(upper_bound));
2858 if (max_magnitude ==
kInfinity || max_magnitude == 0)
continue;
2859 const Fractional threshold = allowed_impact / max_magnitude;
2861 threshold, row_degree);
2864 num_non_zero_objective_coefficients *
2868 ++num_zeroed_objective_coefficients;
2875 <<
" near-zero entries.";
2877 if (num_zeroed_objective_coefficients > 0) {
2878 VLOG(1) <<
"Removed " << num_zeroed_objective_coefficients
2879 <<
" near-zero objective coefficients.";
2897 if (num_cols == 0)
return false;
2899 changed_columns_.clear();
2900 int num_singletons = 0;
2901 for (ColIndex
col(0);
col < num_cols; ++
col) {
2913 changed_columns_.push_back(
col);
2916 VLOG(1) <<
"Changed the sign of " << changed_columns_.size() <<
" columns.";
2917 VLOG(1) << num_singletons <<
" singleton columns left.";
2918 return !changed_columns_.empty();
2925 for (
int i = 0; i < changed_columns_.size(); ++i) {
2926 const ColIndex
col = changed_columns_[i];
2960 for (RowIndex
row(0);
row < num_rows; ++
row) {
2975 int entry_index = 0;
2979 r.col[entry_index] =
col;
2980 r.coeff[entry_index] = e.coefficient();
2988 if (entry_index < 2)
continue;
2994 for (
int col_choice = 0; col_choice < NUM_DOUBLETON_COLS; ++col_choice) {
2995 const ColIndex
col = r.col[col_choice];
3004 if (r.lb[DELETED] == r.ub[DELETED] || r.lb[MODIFIED] == r.ub[MODIFIED]) {
3021 const Fractional carry_over_offset = r.rhs / r.coeff[MODIFIED];
3023 -r.coeff[DELETED] / r.coeff[MODIFIED];
3025 carry_over_factor == 0.0) {
3033 r.lb[DELETED] * carry_over_factor + carry_over_offset;
3035 r.ub[DELETED] * carry_over_factor + carry_over_offset;
3036 if (carry_over_factor < 0) {
3037 std::swap(carried_over_lb, carried_over_ub);
3039 if (carried_over_lb <= lb) {
3044 lb = carried_over_lb;
3049 carry_over_factor > 0 ? r.lb[DELETED] : r.ub[DELETED]);
3051 if (carried_over_ub >= ub) {
3056 ub = carried_over_ub;
3061 carry_over_factor > 0 ? r.ub[DELETED] : r.lb[DELETED]);
3070 restore_stack_.push_back(r);
3079 -r.coeff[MODIFIED] / r.coeff[DELETED];
3080 const Fractional constant_offset_factor = r.rhs / r.coeff[DELETED];
3082 if (!
IsFinite(substitution_factor) || substitution_factor == 0.0 ||
3083 !
IsFinite(constant_offset_factor)) {
3087 r.column[DELETED].AddMultipleToSparseVectorAndDeleteCommonIndex(
3096 r.objective_coefficient[MODIFIED] +
3097 substitution_factor * r.objective_coefficient[DELETED];
3098 if (std::abs(new_objective) >
parameters_.drop_tolerance()) {
3108 SubtractColumnMultipleFromConstraintBound(r.col[DELETED],
3109 constant_offset_factor, lp);
3118 return !column_deletion_helper_.
IsEmpty();
3127 for (
const RestoreInfo& r :
Reverse(restore_stack_)) {
3130 LOG(DFATAL) <<
"FIXED variable produced by DoubletonPreprocessor!";
3137 ABSL_FALLTHROUGH_INTENDED;
3144 ABSL_FALLTHROUGH_INTENDED;
3152 ? r.bound_backtracking_at_lower_bound
3153 : r.bound_backtracking_at_upper_bound;
3154 const ColIndex bounded_var = r.col[bound_backtracking.
col_choice];
3155 const ColIndex basic_var =
3156 r.col[OtherColChoice(bound_backtracking.
col_choice)];
3171 solution->
primal_values[r.col[MODIFIED]] * r.coeff[MODIFIED]) /
3184 const ColChoice col_choice =
3191 r.objective_coefficient[col_choice] -
3193 solution->
dual_values[r.row] = current_reduced_cost / r.coeff[col_choice];
3198 saved_row_upper_bounds_, solution);
3207 for (RowIndex
row(0);
row < num_rows; ++
row) {
3211 if (row_lower_bounds[
row] == row_upper_bounds[
row])
continue;
3223void DoubletonEqualityRowPreprocessor::
3224 SwapDeletedAndModifiedVariableRestoreInfo(RestoreInfo* r) {
3226 swap(r->col[DELETED], r->col[MODIFIED]);
3227 swap(r->coeff[DELETED], r->coeff[MODIFIED]);
3228 swap(r->lb[DELETED], r->lb[MODIFIED]);
3229 swap(r->ub[DELETED], r->ub[MODIFIED]);
3230 swap(r->column[DELETED], r->column[MODIFIED]);
3231 swap(r->objective_coefficient[DELETED], r->objective_coefficient[MODIFIED]);
3241 if (
parameters_.solve_dual_problem() == GlopParameters::NEVER_DO) {
3268 if (
parameters_.solve_dual_problem() == GlopParameters::LET_SOLVER_DECIDE) {
3269 if (1.0 * primal_num_rows_.value() <
3270 parameters_.dualizer_threshold() * primal_num_cols_.value()) {
3280 variable_lower_bounds_.
assign(num_cols, 0.0);
3281 variable_upper_bounds_.
assign(num_cols, 0.0);
3282 for (ColIndex
col(0);
col < num_cols; ++
col) {
3287 variable_lower_bounds_[
col] = lower;
3288 variable_upper_bounds_[
col] = upper;
3289 const Fractional value = MinInMagnitudeOrZeroIfInfinite(lower, upper);
3292 SubtractColumnMultipleFromConstraintBound(
col,
value, lp);
3300 dual_status_correspondence_.
clear();
3301 for (RowIndex
row(0);
row < primal_num_rows_; ++
row) {
3304 if (lower_bound == upper_bound) {
3311 LOG(DFATAL) <<
"There should be no free constraint in this lp.";
3314 slack_or_surplus_mapping_.
clear();
3315 for (ColIndex
col(0);
col < primal_num_cols_; ++
col) {
3325 for (ColIndex
col(0);
col < primal_num_cols_; ++
col) {
3358 DenseRow new_primal_values(primal_num_cols_, 0.0);
3362 for (ColIndex
col(0);
col < primal_num_cols_; ++
col) {
3369 const Fractional shift = MinInMagnitudeOrZeroIfInfinite(lower, upper);
3380 new_variable_statuses[
col] = ComputeVariableStatus(shift, lower, upper);
3389 const ColIndex end = dual_status_correspondence_.
size();
3394 const ColIndex
col = slack_or_surplus_mapping_[
index - begin];
3402 new_primal_values[
col] = variable_upper_bounds_[
col];
3405 new_primal_values[
col] = variable_lower_bounds_[
col];
3413 DenseColumn new_dual_values(primal_num_rows_, 0.0);
3420 Fractional sign = primal_is_maximization_problem_ ? -1 : 1;
3421 for (RowIndex
row(0);
row < primal_num_rows_; ++
row) {
3439 new_constraint_statuses[
row] =
3446 new_dual_values[
row] +=
3492 bool all_variable_domains_contain_zero =
true;
3494 variable_initial_lbs_.
assign(num_cols, 0.0);
3495 variable_initial_ubs_.
assign(num_cols, 0.0);
3496 for (ColIndex
col(0);
col < num_cols; ++
col) {
3499 if (0.0 < variable_initial_lbs_[
col] || 0.0 > variable_initial_ubs_[
col]) {
3500 all_variable_domains_contain_zero =
false;
3503 VLOG(1) <<
"Maximum variable bounds magnitude (before shift): "
3504 << ComputeMaxVariableBoundsMagnitude(*lp);
3507 if (all_variable_domains_contain_zero)
return false;
3511 int num_bound_shifts = 0;
3515 offsets_.
assign(num_cols, 0.0);
3516 for (ColIndex
col(0);
col < num_cols; ++
col) {
3517 if (0.0 < variable_initial_lbs_[
col] || 0.0 > variable_initial_ubs_[
col]) {
3518 Fractional offset = MinInMagnitudeOrZeroIfInfinite(
3519 variable_initial_lbs_[
col], variable_initial_ubs_[
col]);
3527 offset = trunc(offset);
3531 offsets_[
col] = offset;
3533 variable_initial_ubs_[
col] - offset);
3536 row_offsets[e.row()].Add(e.coefficient() * offset);
3542 VLOG(1) <<
"Maximum variable bounds magnitude (after " << num_bound_shifts
3543 <<
" shifts): " << ComputeMaxVariableBoundsMagnitude(*lp);
3546 for (RowIndex
row(0);
row < num_rows; ++
row) {
3560 for (ColIndex
col(0);
col < num_cols; ++
col) {
3566 ABSL_FALLTHROUGH_INTENDED;
3594 variable_lower_bounds_.
assign(num_cols, 0.0);
3595 variable_upper_bounds_.
assign(num_cols, 0.0);
3596 for (ColIndex
col(0);
col < num_cols; ++
col) {
3628 for (ColIndex
col(0);
col < num_cols; ++
col) {
3631 ABSL_FALLTHROUGH_INTENDED;
3639 ABSL_FALLTHROUGH_INTENDED;
3690 for (RowIndex
row(0);
row < num_rows; ++
row) {
3697 switch (variable_status) {
#define DCHECK_LE(val1, val2)
#define DCHECK_NE(val1, val2)
#define DCHECK_GE(val1, val2)
#define DCHECK(condition)
#define DCHECK_EQ(val1, val2)
#define VLOG(verboselevel)
void resize(size_type new_size)
void push_back(const value_type &x)
void swap(StrongVector &x)
void Add(const FpNumber &value)
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
bool IsColumnMarked(ColIndex col) const
void MarkColumnForDeletionWithState(ColIndex col, Fractional value, VariableStatus status)
void MarkColumnForDeletion(ColIndex col)
const DenseBooleanRow & GetMarkedColumns() const
const DenseRow & GetStoredValue() const
void RestoreDeletedColumns(ProblemSolution *solution) const
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
ProblemStatus ChangeStatusToDualStatus(ProblemStatus status) const
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
SparseMatrix * GetMutableTransposeSparseMatrix()
void SetObjectiveScalingFactor(Fractional objective_scaling_factor)
void SetVariableBounds(ColIndex col, Fractional lower_bound, Fractional upper_bound)
const SparseMatrix & GetTransposeSparseMatrix() const
void SetObjectiveOffset(Fractional objective_offset)
ColIndex GetFirstSlackVariable() const
Fractional ScaleObjective(GlopParameters::CostScalingAlgorithm method)
const DenseColumn & constraint_lower_bounds() const
Fractional GetObjectiveCoefficientForMinimizationVersion(ColIndex col) const
void SetConstraintBounds(RowIndex row, Fractional lower_bound, Fractional upper_bound)
void Swap(LinearProgram *linear_program)
const DenseRow & variable_upper_bounds() const
Fractional objective_offset() const
SparseColumn * GetMutableSparseColumn(ColIndex col)
const DenseColumn & constraint_upper_bounds() const
const DenseRow & objective_coefficients() const
void UseTransposeMatrixAsReference()
void AddSlackVariablesWhereNecessary(bool detect_integer_constraints)
bool IsVariableInteger(ColIndex col) const
void SetObjectiveCoefficient(ColIndex col, Fractional value)
void DeleteRows(const DenseBooleanColumn &rows_to_delete)
void DeleteColumns(const DenseBooleanRow &columns_to_delete)
bool IsMaximizationProblem() const
ColIndex num_variables() const
void PopulateFromDual(const LinearProgram &dual, RowToColMapping *duplicated_rows)
const SparseMatrix & GetSparseMatrix() const
const DenseRow & variable_lower_bounds() const
Fractional objective_scaling_factor() const
void SetMaximizationProblem(bool maximize)
const SparseColumn & GetSparseColumn(ColIndex col) const
EntryIndex num_entries() const
RowIndex num_constraints() const
void RecoverSolution(ProblemSolution *solution) const override
bool Run(LinearProgram *lp) final
ProblemStatus status() const
bool IsSmallerWithinPreprocessorZeroTolerance(Fractional a, Fractional b) const
Preprocessor(const GlopParameters *parameters)
const GlopParameters & parameters_
bool IsSmallerWithinFeasibilityTolerance(Fractional a, Fractional b) const
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
void MarkRowForDeletion(RowIndex row)
void UnmarkRow(RowIndex row)
void RestoreDeletedRows(ProblemSolution *solution) const
const DenseBooleanColumn & GetMarkedRows() const
bool IsRowMarked(RowIndex row) const
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
SingletonUndo(OperationType type, const LinearProgram &lp, MatrixEntry e, ConstraintStatus status)
@ ZERO_COST_SINGLETON_COLUMN
@ MAKE_CONSTRAINT_AN_EQUALITY
@ SINGLETON_COLUMN_IN_EQUALITY
void Undo(const GlopParameters ¶meters, const SparseMatrix &deleted_columns, const SparseMatrix &deleted_rows, ProblemSolution *solution) const
void PopulateFromTranspose(const Matrix &input)
ColIndex num_cols() const
SparseColumn * mutable_column(ColIndex col)
const SparseColumn & column(ColIndex col) const
RowIndex num_rows() const
void PopulateFromZero(RowIndex num_rows, ColIndex num_cols)
void ScaleColumnVector(bool up, DenseColumn *column_vector) const
void ScaleRowVector(bool up, DenseRow *row_vector) const
Fractional LookUpCoefficient(Index index) const
void RemoveNearZeroEntriesWithWeights(Fractional threshold, const DenseVector &weights)
void MultiplyByConstant(Fractional factor)
typename Iterator::Entry Entry
Fractional GetFirstCoefficient() const
void PopulateFromSparseVector(const SparseVector &sparse_vector)
EntryIndex num_entries() const
void resize(IntType size)
void assign(IntType size, const T &v)
Fractional SumWithout(Fractional x) const
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
void RemoveZeroCostUnconstrainedVariable(ColIndex col, Fractional target_bound, LinearProgram *lp)
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
SharedTimeLimit * time_limit
RowIndex ColToRowIndex(ColIndex col)
bool IsFinite(Fractional value)
Fractional ScalarProduct(const DenseRowOrColumn1 &u, const DenseRowOrColumn2 &v)
const ColIndex kInvalidCol(-1)
StrictITIVector< ColIndex, Fractional > DenseRow
std::string GetProblemStatusString(ProblemStatus problem_status)
void FixConstraintWithFixedStatuses(const DenseColumn &row_lower_bounds, const DenseColumn &row_upper_bounds, ProblemSolution *solution)
ColIndex RowToColIndex(RowIndex row)
ConstraintStatus VariableToConstraintStatus(VariableStatus status)
Fractional PreciseScalarProduct(const DenseRowOrColumn &u, const DenseRowOrColumn2 &v)
const RowIndex kInvalidRow(-1)
ColMapping FindProportionalColumns(const SparseMatrix &matrix, Fractional tolerance)
void Scale(LinearProgram *lp, SparseMatrixScaler *scaler)
@ INFEASIBLE_OR_UNBOUNDED
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
bool IsSmallerWithinTolerance(FloatType x, FloatType y, FloatType tolerance)
bool IsIntegerWithinTolerance(FloatType x, FloatType tolerance)
BeginEndReverseIteratorWrapper< Container > Reverse(const Container &c)
#define RUN_PREPROCESSOR(name)
#define RETURN_IF_NULL(x)
#define RETURN_VALUE_IF_NULL(x, v)
std::vector< double > lower_bounds
std::vector< double > upper_bounds
#define SCOPED_INSTRUCTION_COUNT(time_limit)
VariableStatusRow variable_statuses
ConstraintStatusColumn constraint_statuses
#define VLOG_IS_ON(verboselevel)