24 #include "absl/strings/str_cat.h"
25 #include "absl/strings/str_format.h"
31 #include "ortools/glop/parameters.pb.h"
39 ABSL_FLAG(
bool, simplex_display_numbers_as_fractions,
false,
40 "Display numbers as fractions.");
41 ABSL_FLAG(
bool, simplex_stop_after_first_basis,
false,
42 "Stop after first basis has been computed.");
43 ABSL_FLAG(
bool, simplex_stop_after_feasibility,
false,
44 "Stop after first phase has been completed.");
45 ABSL_FLAG(
bool, simplex_display_stats,
false,
"Display algorithm statistics.");
55 explicit Cleanup(std::function<
void()> closure)
56 : closure_(std::move(closure)) {}
57 ~Cleanup() { closure_(); }
60 std::function<void()> closure_;
64 #define DCHECK_COL_BOUNDS(col) \
67 DCHECK_GT(num_cols_, col); \
70 #define DCHECK_ROW_BOUNDS(row) \
73 DCHECK_GT(num_rows_, row); \
90 basis_factorization_(&compact_matrix_, &basis_),
91 variables_info_(compact_matrix_, lower_bound_, upper_bound_),
92 variable_values_(parameters_, compact_matrix_, basis_, variables_info_,
93 basis_factorization_),
94 dual_edge_norms_(basis_factorization_),
95 primal_edge_norms_(compact_matrix_, variables_info_,
96 basis_factorization_),
97 update_row_(compact_matrix_, transposed_matrix_, variables_info_, basis_,
98 basis_factorization_),
99 reduced_costs_(compact_matrix_,
objective_, basis_, variables_info_,
100 basis_factorization_, &random_),
101 entering_variable_(variables_info_, &random_, &reduced_costs_,
102 &primal_edge_norms_),
104 num_feasibility_iterations_(0),
105 num_optimization_iterations_(0),
107 feasibility_time_(0.0),
108 optimization_time_(0.0),
109 last_deterministic_time_update_(0.0),
112 function_stats_(
"SimplexFunctionStats"),
115 feasibility_phase_(true),
127 solution_state_ = state;
128 solution_state_has_been_set_externally_ =
true;
132 notify_that_matrix_is_unchanged_ =
true;
141 "The problem is not in the equations form.");
143 Cleanup update_deterministic_time_on_return(
148 const double start_time =
time_limit->GetElapsedTime();
151 dual_infeasibility_improvement_direction_.
clear();
155 feasibility_phase_ =
true;
157 num_feasibility_iterations_ = 0;
158 num_optimization_iterations_ = 0;
159 feasibility_time_ = 0.0;
160 optimization_time_ = 0.0;
167 solution_state_has_been_set_externally_ =
true;
170 ComputeNumberOfEmptyRows();
171 ComputeNumberOfEmptyColumns();
172 DisplayBasicVariableStatistics();
175 if (absl::GetFlag(FLAGS_simplex_stop_after_first_basis)) {
180 const bool use_dual = parameters_.use_dual_simplex();
181 const bool log_info = parameters_.log_search_progress() ||
VLOG_IS_ON(1);
183 LOG(
INFO) <<
"------ " << (use_dual ?
"Dual simplex." :
"Primal simplex.");
184 LOG(
INFO) <<
"The matrix has " << compact_matrix_.
num_rows() <<
" rows, "
185 << compact_matrix_.
num_cols() <<
" columns, "
191 if (log_info)
LOG(
INFO) <<
"------ First phase: feasibility.";
192 entering_variable_.
SetPricingRule(parameters_.feasibility_rule());
194 if (parameters_.perturb_costs_in_dual_simplex()) {
200 DisplayIterationInfo();
225 DisplayIterationInfo();
229 InitializeObjectiveAndTestIfUnchanged(lp);
240 feasibility_phase_ =
false;
241 feasibility_time_ =
time_limit->GetElapsedTime() - start_time;
242 entering_variable_.
SetPricingRule(parameters_.optimization_rule());
243 num_feasibility_iterations_ = num_iterations_;
245 if (log_info)
LOG(
INFO) <<
"------ Second phase: optimization.";
259 for (
int num_optims = 0;
263 num_optims <= parameters_.max_number_of_reoptimizations() &&
264 !objective_limit_reached_ &&
265 (num_iterations_ == 0 ||
266 num_iterations_ < parameters_.max_number_of_iterations()) &&
268 !absl::GetFlag(FLAGS_simplex_stop_after_feasibility) &&
290 if (!integrality_scale_.
empty() &&
310 DisplayIterationInfo();
319 const Fractional tolerance = parameters_.solution_feasibility_tolerance();
324 LOG(
INFO) <<
"DUAL_UNBOUNDED was reported, but the residual and/or "
325 <<
"dual infeasibility is above the tolerance";
335 parameters_.solution_feasibility_tolerance();
337 solution_tolerance ||
340 LOG(
INFO) <<
"OPTIMAL was reported, yet one of the residuals is "
341 "above the solution feasibility tolerance after the "
342 "shift/perturbation are removed.";
344 if (parameters_.change_status_to_imprecise()) {
351 parameters_.primal_feasibility_tolerance();
353 parameters_.dual_feasibility_tolerance();
358 if (primal_infeasibility > primal_tolerance &&
359 dual_infeasibility > dual_tolerance) {
361 LOG(
INFO) <<
"OPTIMAL was reported, yet both of the infeasibility "
362 "are above the tolerance after the "
363 "shift/perturbation are removed.";
365 if (parameters_.change_status_to_imprecise()) {
368 }
else if (primal_infeasibility > primal_tolerance) {
369 if (log_info)
LOG(
INFO) <<
"Re-optimizing with dual simplex ... ";
371 }
else if (dual_infeasibility > dual_tolerance) {
372 if (log_info)
LOG(
INFO) <<
"Re-optimizing with primal simplex ... ";
383 if (parameters_.change_status_to_imprecise() &&
385 const Fractional tolerance = parameters_.solution_feasibility_tolerance();
406 solution_objective_value_ = ComputeInitialProblemObjectiveValue();
417 solution_objective_value_ =
421 solution_objective_value_ = -solution_objective_value_;
425 total_time_ =
time_limit->GetElapsedTime() - start_time;
426 optimization_time_ = total_time_ - feasibility_time_;
427 num_optimization_iterations_ = num_iterations_ - num_feasibility_iterations_;
434 return problem_status_;
438 return solution_objective_value_;
448 return variable_values_.
Get(
col);
452 return solution_reduced_costs_[
col];
456 return solution_reduced_costs_;
460 return solution_dual_values_[
row];
472 return -variable_values_.
Get(SlackColIndex(
row));
490 return solution_primal_ray_;
494 return solution_dual_ray_;
499 return solution_dual_ray_row_combination_;
506 return basis_factorization_;
509 std::string RevisedSimplex::GetPrettySolverStats()
const {
510 return absl::StrFormat(
511 "Problem status : %s\n"
512 "Solving time : %-6.4g\n"
513 "Number of iterations : %u\n"
514 "Time for solvability (first phase) : %-6.4g\n"
515 "Number of iterations for solvability : %u\n"
516 "Time for optimization : %-6.4g\n"
517 "Number of iterations for optimization : %u\n"
518 "Stop after first basis : %d\n",
520 feasibility_time_, num_feasibility_iterations_, optimization_time_,
521 num_optimization_iterations_,
522 absl::GetFlag(FLAGS_simplex_stop_after_first_basis));
533 void RevisedSimplex::SetVariableNames() {
534 variable_name_.
resize(num_cols_,
"");
535 for (ColIndex
col(0);
col < first_slack_col_; ++
col) {
536 const ColIndex var_index =
col + 1;
539 for (ColIndex
col(first_slack_col_);
col < num_cols_; ++
col) {
540 const ColIndex var_index =
col - first_slack_col_ + 1;
546 ColIndex
col)
const {
548 if (lower_bound_[
col] == upper_bound_[
col]) {
558 return std::abs(lower_bound_[
col]) <= std::abs(upper_bound_[
col])
563 void RevisedSimplex::SetNonBasicVariableStatusAndDeriveValue(
569 bool RevisedSimplex::BasisIsConsistent()
const {
572 for (RowIndex
row(0);
row < num_rows_; ++
row) {
573 const ColIndex
col = basis_[
row];
574 if (!is_basic.IsSet(
col))
return false;
577 ColIndex cols_in_basis(0);
578 ColIndex cols_not_in_basis(0);
579 for (ColIndex
col(0);
col < num_cols_; ++
col) {
580 cols_in_basis += is_basic.IsSet(
col);
581 cols_not_in_basis += !is_basic.IsSet(
col);
582 if (is_basic.IsSet(
col) !=
588 if (cols_not_in_basis != num_cols_ -
RowToColIndex(num_rows_))
return false;
594 void RevisedSimplex::UpdateBasis(ColIndex entering_col, RowIndex basis_row,
603 DCHECK_NE(basis_[basis_row], entering_col);
606 const ColIndex leaving_col = basis_[basis_row];
612 variables_info_.
Update(leaving_col, leaving_variable_status);
617 basis_[basis_row] = entering_col;
625 class ColumnComparator {
628 bool operator()(ColIndex col_a, ColIndex col_b)
const {
629 return value_[col_a] < value_[col_b];
646 void RevisedSimplex::UseSingletonColumnInInitialBasis(
RowToColMapping* basis) {
653 std::vector<ColIndex> singleton_column;
654 DenseRow cost_variation(num_cols_, 0.0);
655 for (ColIndex
col(0);
col < num_cols_; ++
col) {
657 if (lower_bound_[
col] == upper_bound_[
col])
continue;
659 if (variable_values_.
Get(
col) == lower_bound_[
col]) {
660 cost_variation[
col] = objective_[
col] / std::abs(slope);
662 cost_variation[
col] = -objective_[
col] / std::abs(slope);
664 singleton_column.push_back(
col);
666 if (singleton_column.empty())
return;
673 ColumnComparator comparator(cost_variation);
674 std::sort(singleton_column.begin(), singleton_column.end(), comparator);
675 DCHECK_LE(cost_variation[singleton_column.front()],
676 cost_variation[singleton_column.back()]);
684 for (
const ColIndex
col : singleton_column) {
696 if (error_[
row] == 0.0)
continue;
704 if (new_value >= lower_bound_[
col] && new_value <= upper_bound_[
col]) {
719 if (variable_values[
col] == lower_bound_[
col] && error_sign > 0.0) {
721 error_[
row] -= coeff * box_width;
722 SetNonBasicVariableStatusAndDeriveValue(
col,
726 if (variable_values[
col] == upper_bound_[
col] && error_sign < 0.0) {
728 error_[
row] += coeff * box_width;
729 SetNonBasicVariableStatusAndDeriveValue(
col,
736 bool RevisedSimplex::InitializeMatrixAndTestIfUnchanged(
737 const LinearProgram& lp,
bool* only_change_is_new_rows,
738 bool* only_change_is_new_cols, ColIndex* num_new_cols) {
740 DCHECK(only_change_is_new_rows !=
nullptr);
741 DCHECK(only_change_is_new_cols !=
nullptr);
742 DCHECK(num_new_cols !=
nullptr);
748 lp.GetFirstSlackVariable() +
RowToColIndex(lp.num_constraints()));
750 const bool old_part_of_matrix_is_unchanged =
752 num_rows_, first_slack_col_, lp.GetSparseMatrix(), compact_matrix_);
757 if (old_part_of_matrix_is_unchanged && lp.num_constraints() == num_rows_ &&
758 lp.num_variables() == num_cols_) {
764 *only_change_is_new_rows = old_part_of_matrix_is_unchanged &&
765 lp.num_constraints() > num_rows_ &&
766 lp.GetFirstSlackVariable() == first_slack_col_;
770 *only_change_is_new_cols = old_part_of_matrix_is_unchanged &&
771 lp.num_constraints() == num_rows_ &&
772 lp.GetFirstSlackVariable() > first_slack_col_;
774 *only_change_is_new_cols ? lp.num_variables() - num_cols_ : ColIndex(0);
777 first_slack_col_ = lp.GetFirstSlackVariable();
780 num_rows_ = lp.num_constraints();
781 num_cols_ = lp.num_variables();
788 if (parameters_.use_transposed_matrix()) {
794 bool RevisedSimplex::OldBoundsAreUnchangedAndNewVariablesHaveOneBoundAtZero(
795 const LinearProgram& lp, ColIndex num_new_cols) {
797 DCHECK_EQ(lp.num_variables(), num_cols_);
798 DCHECK_LE(num_new_cols, first_slack_col_);
799 const ColIndex first_new_col(first_slack_col_ - num_new_cols);
802 for (ColIndex
col(0);
col < first_new_col; ++
col) {
803 if (lower_bound_[
col] != lp.variable_lower_bounds()[
col] ||
804 upper_bound_[
col] != lp.variable_upper_bounds()[
col]) {
809 for (ColIndex
col(first_new_col);
col < first_slack_col_; ++
col) {
810 if (lp.variable_lower_bounds()[
col] != 0.0 &&
811 lp.variable_upper_bounds()[
col] != 0.0) {
816 for (ColIndex
col(first_slack_col_);
col < num_cols_; ++
col) {
817 if (lower_bound_[
col - num_new_cols] != lp.variable_lower_bounds()[
col] ||
818 upper_bound_[
col - num_new_cols] != lp.variable_upper_bounds()[
col]) {
825 bool RevisedSimplex::InitializeBoundsAndTestIfUnchanged(
826 const LinearProgram& lp) {
828 lower_bound_.
resize(num_cols_, 0.0);
829 upper_bound_.
resize(num_cols_, 0.0);
832 bool bounds_are_unchanged =
true;
833 DCHECK_EQ(lp.num_variables(), num_cols_);
834 for (ColIndex
col(0);
col < lp.num_variables(); ++
col) {
835 if (lower_bound_[
col] != lp.variable_lower_bounds()[
col] ||
836 upper_bound_[
col] != lp.variable_upper_bounds()[
col]) {
837 bounds_are_unchanged =
false;
841 if (!bounds_are_unchanged) {
842 lower_bound_ = lp.variable_lower_bounds();
843 upper_bound_ = lp.variable_upper_bounds();
845 return bounds_are_unchanged;
848 bool RevisedSimplex::InitializeObjectiveAndTestIfUnchanged(
849 const LinearProgram& lp) {
852 bool objective_is_unchanged =
true;
853 objective_.
resize(num_cols_, 0.0);
854 DCHECK_EQ(num_cols_, lp.num_variables());
855 if (lp.IsMaximizationProblem()) {
857 for (ColIndex
col(0);
col < lp.num_variables(); ++
col) {
859 if (objective_[
col] != coeff) {
860 objective_is_unchanged =
false;
862 objective_[
col] = coeff;
864 objective_offset_ = -lp.objective_offset();
865 objective_scaling_factor_ = -lp.objective_scaling_factor();
867 for (ColIndex
col(0);
col < lp.num_variables(); ++
col) {
868 if (objective_[
col] != lp.objective_coefficients()[
col]) {
869 objective_is_unchanged =
false;
873 if (!objective_is_unchanged) {
874 objective_ = lp.objective_coefficients();
876 objective_offset_ = lp.objective_offset();
877 objective_scaling_factor_ = lp.objective_scaling_factor();
879 return objective_is_unchanged;
882 void RevisedSimplex::InitializeObjectiveLimit(
const LinearProgram& lp) {
883 objective_limit_reached_ =
false;
884 DCHECK(std::isfinite(objective_offset_));
885 DCHECK(std::isfinite(objective_scaling_factor_));
886 DCHECK_NE(0.0, objective_scaling_factor_);
889 for (
const bool set_dual : {
true,
false}) {
901 const Fractional limit = (objective_scaling_factor_ >= 0.0) != set_dual
902 ? parameters_.objective_lower_limit()
903 : parameters_.objective_upper_limit();
905 limit / objective_scaling_factor_ - objective_offset_;
907 dual_objective_limit_ = shifted_limit;
909 primal_objective_limit_ = shifted_limit;
914 void RevisedSimplex::InitializeVariableStatusesForWarmStart(
915 const BasisState& state, ColIndex num_new_cols) {
917 RowIndex num_basic_variables(0);
918 DCHECK_LE(num_new_cols, first_slack_col_);
919 const ColIndex first_new_col(first_slack_col_ - num_new_cols);
922 for (ColIndex
col(0);
col < num_cols_; ++
col) {
927 if (
col < first_new_col &&
col < state.statuses.size()) {
928 status = state.statuses[
col];
929 }
else if (
col >= first_slack_col_ &&
930 col - num_new_cols < state.statuses.size()) {
931 status = state.statuses[
col - num_new_cols];
936 if (num_basic_variables == num_rows_) {
937 VLOG(1) <<
"Too many basic variables in the warm-start basis."
938 <<
"Only keeping the first ones as VariableStatus::BASIC.";
941 ++num_basic_variables;
948 if ((status != default_status) &&
956 status = default_status;
971 Status RevisedSimplex::CreateInitialBasis() {
978 int num_free_variables = 0;
980 for (ColIndex
col(0);
col < num_cols_; ++
col) {
982 SetNonBasicVariableStatusAndDeriveValue(
col, status);
985 VLOG(1) <<
"Number of free variables in the problem: " << num_free_variables;
989 for (RowIndex
row(0);
row < num_rows_; ++
row) {
990 basis[
row] = SlackColIndex(
row);
995 if (!parameters_.use_dual_simplex() &&
996 parameters_.initial_basis() != GlopParameters::MAROS &&
997 parameters_.exploit_singleton_column_in_initial_basis()) {
1001 for (ColIndex
col(0);
col < num_cols_; ++
col) {
1005 if (objective > 0 &&
IsFinite(lower_bound_[
col]) &&
1007 SetNonBasicVariableStatusAndDeriveValue(
col,
1009 }
else if (objective < 0 &&
IsFinite(upper_bound_[
col]) &&
1011 SetNonBasicVariableStatusAndDeriveValue(
col,
1018 ComputeVariableValuesError();
1027 UseSingletonColumnInInitialBasis(&basis);
1030 for (RowIndex
row(0);
row < num_rows_; ++
row) {
1032 basis[
row] = SlackColIndex(
row);
1038 if (parameters_.initial_basis() == GlopParameters::NONE) {
1039 return InitializeFirstBasis(basis);
1041 if (parameters_.initial_basis() == GlopParameters::MAROS) {
1042 InitialBasis initial_basis(compact_matrix_, objective_, lower_bound_,
1044 if (parameters_.use_dual_simplex()) {
1047 initial_basis.GetDualMarosBasis(num_cols_, &basis);
1049 initial_basis.GetPrimalMarosBasis(num_cols_, &basis);
1051 int number_changed = 0;
1052 for (RowIndex
row(0);
row < num_rows_; ++
row) {
1053 if (basis[
row] != SlackColIndex(
row)) {
1057 VLOG(1) <<
"Number of Maros basis changes: " << number_changed;
1058 }
else if (parameters_.initial_basis() == GlopParameters::BIXBY ||
1059 parameters_.initial_basis() == GlopParameters::TRIANGULAR) {
1061 int num_fixed_variables = 0;
1062 for (RowIndex
row(0);
row < basis.size(); ++
row) {
1063 const ColIndex
col = basis[
row];
1064 if (lower_bound_[
col] == upper_bound_[
col]) {
1066 ++num_fixed_variables;
1070 if (num_fixed_variables == 0) {
1071 VLOG(1) <<
"Crash is set to " << parameters_.initial_basis()
1072 <<
" but there is no equality rows to remove from initial all "
1076 VLOG(1) <<
"Trying to remove " << num_fixed_variables
1077 <<
" fixed variables from the initial basis.";
1078 InitialBasis initial_basis(compact_matrix_, objective_, lower_bound_,
1081 if (parameters_.initial_basis() == GlopParameters::BIXBY) {
1082 if (parameters_.use_scaling()) {
1083 initial_basis.CompleteBixbyBasis(first_slack_col_, &basis);
1085 VLOG(1) <<
"Bixby initial basis algorithm requires the problem "
1086 <<
"to be scaled. Skipping Bixby's algorithm.";
1088 }
else if (parameters_.initial_basis() == GlopParameters::TRIANGULAR) {
1091 if (parameters_.use_dual_simplex()) {
1094 initial_basis.CompleteTriangularDualBasis(num_cols_, &basis);
1096 initial_basis.CompleteTriangularPrimalBasis(num_cols_, &basis);
1099 const Status status = InitializeFirstBasis(basis);
1103 VLOG(1) <<
"Reverting to all slack basis.";
1105 for (RowIndex
row(0);
row < num_rows_; ++
row) {
1106 basis[
row] = SlackColIndex(
row);
1112 LOG(
WARNING) <<
"Unsupported initial_basis parameters: "
1113 << parameters_.initial_basis();
1116 return InitializeFirstBasis(basis);
1119 Status RevisedSimplex::InitializeFirstBasis(
const RowToColMapping& basis) {
1125 for (RowIndex
row(0);
row < num_rows_; ++
row) {
1127 basis_[
row] = SlackColIndex(
row);
1141 if (condition_number_ub > parameters_.initial_condition_number_threshold()) {
1142 const std::string error_message =
1143 absl::StrCat(
"The matrix condition number upper bound is too high: ",
1144 condition_number_ub);
1145 VLOG(1) << error_message;
1150 for (RowIndex
row(0);
row < num_rows_; ++
row) {
1153 DCHECK(BasisIsConsistent());
1160 const Fractional tolerance = parameters_.primal_feasibility_tolerance();
1162 VLOG(1) << absl::StrCat(
1163 "The primal residual of the initial basis is above the tolerance, ",
1170 Status RevisedSimplex::Initialize(
const LinearProgram& lp) {
1171 parameters_ = initial_parameters_;
1172 PropagateParameters();
1179 ColIndex num_new_cols(0);
1180 bool only_change_is_new_rows =
false;
1181 bool only_change_is_new_cols =
false;
1182 bool matrix_is_unchanged =
true;
1183 bool only_new_bounds =
false;
1184 if (solution_state_.
IsEmpty() || !notify_that_matrix_is_unchanged_) {
1185 matrix_is_unchanged = InitializeMatrixAndTestIfUnchanged(
1186 lp, &only_change_is_new_rows, &only_change_is_new_cols, &num_new_cols);
1187 only_new_bounds = only_change_is_new_cols && num_new_cols > 0 &&
1188 OldBoundsAreUnchangedAndNewVariablesHaveOneBoundAtZero(
1191 CHECK(InitializeMatrixAndTestIfUnchanged(
1192 lp, &only_change_is_new_rows, &only_change_is_new_cols, &num_new_cols));
1194 notify_that_matrix_is_unchanged_ =
false;
1195 const bool objective_is_unchanged = InitializeObjectiveAndTestIfUnchanged(lp);
1196 const bool bounds_are_unchanged = InitializeBoundsAndTestIfUnchanged(lp);
1201 if (matrix_is_unchanged && parameters_.allow_simplex_algorithm_change()) {
1202 if (objective_is_unchanged && !bounds_are_unchanged) {
1203 parameters_.set_use_dual_simplex(
true);
1204 PropagateParameters();
1206 if (bounds_are_unchanged && !objective_is_unchanged) {
1207 parameters_.set_use_dual_simplex(
false);
1208 PropagateParameters();
1212 InitializeObjectiveLimit(lp);
1228 bool solve_from_scratch =
true;
1231 if (!solution_state_.
IsEmpty() && !solution_state_has_been_set_externally_) {
1232 if (!parameters_.use_dual_simplex()) {
1237 dual_edge_norms_.
Clear();
1238 dual_pricing_vector_.
clear();
1239 if (matrix_is_unchanged && bounds_are_unchanged) {
1243 solve_from_scratch =
false;
1244 }
else if (only_change_is_new_cols && only_new_bounds) {
1245 InitializeVariableStatusesForWarmStart(solution_state_, num_new_cols);
1246 const ColIndex first_new_col(first_slack_col_ - num_new_cols);
1247 for (ColIndex& col_ref : basis_) {
1248 if (col_ref >= first_new_col) {
1249 col_ref += num_new_cols;
1256 primal_edge_norms_.
Clear();
1258 solve_from_scratch =
false;
1264 primal_edge_norms_.
Clear();
1265 if (objective_is_unchanged) {
1266 if (matrix_is_unchanged) {
1267 if (!bounds_are_unchanged) {
1268 InitializeVariableStatusesForWarmStart(solution_state_,
1272 solve_from_scratch =
false;
1273 }
else if (only_change_is_new_rows) {
1276 InitializeVariableStatusesForWarmStart(solution_state_, ColIndex(0));
1283 dual_pricing_vector_.
clear();
1286 if (InitializeFirstBasis(basis_).ok()) {
1287 solve_from_scratch =
false;
1296 const bool log_info = parameters_.log_search_progress() ||
VLOG_IS_ON(1);
1297 if (solve_from_scratch && !solution_state_.
IsEmpty()) {
1300 InitializeVariableStatusesForWarmStart(solution_state_, ColIndex(0));
1308 basis_factorization_.
Clear();
1310 primal_edge_norms_.
Clear();
1311 dual_edge_norms_.
Clear();
1312 dual_pricing_vector_.
clear();
1317 if (InitializeFirstBasis(basis_).ok()) {
1318 solve_from_scratch =
false;
1321 LOG(
INFO) <<
"RevisedSimplex is not using the warm start "
1322 "basis because it is not factorizable.";
1327 if (solve_from_scratch) {
1328 if (log_info)
LOG(
INFO) <<
"Solve from scratch.";
1329 basis_factorization_.
Clear();
1331 primal_edge_norms_.
Clear();
1332 dual_edge_norms_.
Clear();
1333 dual_pricing_vector_.
clear();
1336 if (log_info)
LOG(
INFO) <<
"Incremental solve.";
1338 DCHECK(BasisIsConsistent());
1342 void RevisedSimplex::DisplayBasicVariableStatistics() {
1345 int num_fixed_variables = 0;
1346 int num_free_variables = 0;
1347 int num_variables_at_bound = 0;
1348 int num_slack_variables = 0;
1349 int num_infeasible_variables = 0;
1353 const Fractional tolerance = parameters_.primal_feasibility_tolerance();
1354 for (RowIndex
row(0);
row < num_rows_; ++
row) {
1355 const ColIndex
col = basis_[
row];
1358 ++num_free_variables;
1360 if (
value > upper_bound_[
col] + tolerance ||
1361 value < lower_bound_[
col] - tolerance) {
1362 ++num_infeasible_variables;
1364 if (
col >= first_slack_col_) {
1365 ++num_slack_variables;
1367 if (lower_bound_[
col] == upper_bound_[
col]) {
1368 ++num_fixed_variables;
1369 }
else if (variable_values[
col] == lower_bound_[
col] ||
1370 variable_values[
col] == upper_bound_[
col]) {
1371 ++num_variables_at_bound;
1375 VLOG(1) <<
"Basis size: " << num_rows_;
1376 VLOG(1) <<
"Number of basic infeasible variables: "
1377 << num_infeasible_variables;
1378 VLOG(1) <<
"Number of basic slack variables: " << num_slack_variables;
1379 VLOG(1) <<
"Number of basic variables at bound: " << num_variables_at_bound;
1380 VLOG(1) <<
"Number of basic fixed variables: " << num_fixed_variables;
1381 VLOG(1) <<
"Number of basic free variables: " << num_free_variables;
1384 void RevisedSimplex::SaveState() {
1387 solution_state_has_been_set_externally_ =
false;
1390 RowIndex RevisedSimplex::ComputeNumberOfEmptyRows() {
1392 for (ColIndex
col(0);
col < num_cols_; ++
col) {
1394 contains_data[e.row()] =
true;
1397 RowIndex num_empty_rows(0);
1398 for (RowIndex
row(0);
row < num_rows_; ++
row) {
1399 if (!contains_data[
row]) {
1401 VLOG(1) <<
"Row " <<
row <<
" is empty.";
1404 return num_empty_rows;
1407 ColIndex RevisedSimplex::ComputeNumberOfEmptyColumns() {
1408 ColIndex num_empty_cols(0);
1409 for (ColIndex
col(0);
col < num_cols_; ++
col) {
1412 VLOG(1) <<
"Column " <<
col <<
" is empty.";
1415 return num_empty_cols;
1418 void RevisedSimplex::CorrectErrorsOnVariableValues() {
1430 if (primal_residual >= parameters_.harris_tolerance_ratio() *
1431 parameters_.primal_feasibility_tolerance()) {
1433 VLOG(1) <<
"Primal infeasibility (bounds error) = "
1435 <<
", Primal residual |A.x - b| = "
1440 void RevisedSimplex::ComputeVariableValuesError() {
1444 for (ColIndex
col(0);
col < num_cols_; ++
col) {
1450 void RevisedSimplex::ComputeDirection(ColIndex
col) {
1454 direction_infinity_norm_ = 0.0;
1457 for (RowIndex
row(0);
row < num_rows_; ++
row) {
1461 direction_infinity_norm_ =
1466 for (
const auto e : direction_) {
1467 direction_infinity_norm_ =
1468 std::max(direction_infinity_norm_, std::abs(e.coefficient()));
1472 num_rows_ == 0 ? 0.0
1473 :
static_cast<double>(direction_.non_zeros.size()) /
1474 static_cast<double>(num_rows_.value())));
1477 Fractional RevisedSimplex::ComputeDirectionError(ColIndex
col) {
1480 for (
const auto e : direction_) {
1487 template <
bool is_entering_reduced_cost_positive>
1489 const ColIndex
col = basis_[
row];
1494 if (is_entering_reduced_cost_positive) {
1495 if (direction > 0.0) {
1496 return (upper_bound_[
col] -
value) / direction;
1498 return (lower_bound_[
col] -
value) / direction;
1501 if (direction > 0.0) {
1502 return (
value - lower_bound_[
col]) / direction;
1504 return (
value - upper_bound_[
col]) / direction;
1509 template <
bool is_entering_reduced_cost_positive>
1510 Fractional RevisedSimplex::ComputeHarrisRatioAndLeavingCandidates(
1511 Fractional bound_flip_ratio, SparseColumn* leaving_candidates)
const {
1514 parameters_.harris_tolerance_ratio() *
1515 parameters_.primal_feasibility_tolerance();
1516 const Fractional minimum_delta = parameters_.degenerate_ministep_factor() *
1517 parameters_.primal_feasibility_tolerance();
1523 leaving_candidates->Clear();
1530 ? parameters_.minimum_acceptable_pivot()
1531 : parameters_.ratio_test_zero_threshold();
1533 for (
const auto e : direction_) {
1534 const Fractional magnitude = std::abs(e.coefficient());
1535 if (magnitude <= threshold)
continue;
1537 GetRatio<is_entering_reduced_cost_positive>(e.row());
1538 if (
ratio <= harris_ratio) {
1539 leaving_candidates->SetCoefficient(e.row(),
ratio);
1551 harris_ratio =
std::min(harris_ratio,
1552 std::max(minimum_delta / magnitude,
1553 ratio + harris_tolerance / magnitude));
1556 return harris_ratio;
1569 if (current >= 0.0) {
1570 return candidate >= 0.0 && candidate <= current;
1572 return candidate >= current;
1580 Status RevisedSimplex::ChooseLeavingVariableRow(
1581 ColIndex entering_col,
Fractional reduced_cost,
bool* refactorize,
1591 int stats_num_leaving_choices = 0;
1592 equivalent_leaving_choices_.clear();
1594 stats_num_leaving_choices = 0;
1598 const Fractional entering_value = variable_values_.
Get(entering_col);
1600 (reduced_cost > 0.0) ? entering_value - lower_bound_[entering_col]
1601 : upper_bound_[entering_col] - entering_value;
1608 (reduced_cost > 0.0) ? ComputeHarrisRatioAndLeavingCandidates<true>(
1609 current_ratio, &leaving_candidates_)
1610 : ComputeHarrisRatioAndLeavingCandidates<false>(
1611 current_ratio, &leaving_candidates_);
1616 if (current_ratio <= harris_ratio) {
1618 *step_length = current_ratio;
1628 stats_num_leaving_choices = 0;
1630 equivalent_leaving_choices_.clear();
1633 if (
ratio > harris_ratio)
continue;
1634 ++stats_num_leaving_choices;
1635 const RowIndex
row = e.row();
1640 const Fractional candidate_magnitude = std::abs(direction_[
row]);
1641 if (candidate_magnitude < pivot_magnitude)
continue;
1642 if (candidate_magnitude == pivot_magnitude) {
1643 if (!IsRatioMoreOrEquallyStable(
ratio, current_ratio))
continue;
1644 if (
ratio == current_ratio) {
1646 equivalent_leaving_choices_.push_back(
row);
1650 equivalent_leaving_choices_.clear();
1651 current_ratio =
ratio;
1652 pivot_magnitude = candidate_magnitude;
1657 if (!equivalent_leaving_choices_.empty()) {
1658 equivalent_leaving_choices_.push_back(*leaving_row);
1660 equivalent_leaving_choices_[std::uniform_int_distribution<int>(
1661 0, equivalent_leaving_choices_.size() - 1)(random_)];
1673 if (current_ratio <= 0.0) {
1677 parameters_.degenerate_ministep_factor() *
1678 parameters_.primal_feasibility_tolerance();
1679 *step_length = minimum_delta / pivot_magnitude;
1681 *step_length = current_ratio;
1688 TestPivot(entering_col, *leaving_row);
1701 if (pivot_magnitude <
1702 parameters_.small_pivot_threshold() * direction_infinity_norm_) {
1707 VLOG(1) <<
"Refactorizing to avoid pivoting by "
1708 << direction_[*leaving_row]
1709 <<
" direction_infinity_norm_ = " << direction_infinity_norm_
1710 <<
" reduced cost = " << reduced_cost;
1711 *refactorize =
true;
1721 VLOG(1) <<
"Couldn't avoid pivoting by " << direction_[*leaving_row]
1722 <<
" direction_infinity_norm_ = " << direction_infinity_norm_
1723 <<
" reduced cost = " << reduced_cost;
1724 DCHECK_GE(std::abs(direction_[*leaving_row]),
1725 parameters_.minimum_acceptable_pivot());
1733 const bool is_reduced_cost_positive = (reduced_cost > 0.0);
1734 const bool is_leaving_coeff_positive = (direction_[*leaving_row] > 0.0);
1735 *
target_bound = (is_reduced_cost_positive == is_leaving_coeff_positive)
1736 ? upper_bound_[basis_[*leaving_row]]
1737 : lower_bound_[basis_[*leaving_row]];
1742 ratio_test_stats_.leaving_choices.Add(stats_num_leaving_choices);
1743 if (!equivalent_leaving_choices_.empty()) {
1744 ratio_test_stats_.num_perfect_ties.Add(
1745 equivalent_leaving_choices_.size());
1748 ratio_test_stats_.abs_used_pivot.Add(std::abs(direction_[*leaving_row]));
1770 bool operator<(
const BreakPoint& other)
const {
1771 if (
ratio == other.ratio) {
1773 return row > other.row;
1777 return ratio > other.ratio;
1788 void RevisedSimplex::PrimalPhaseIChooseLeavingVariableRow(
1789 ColIndex entering_col,
Fractional reduced_cost,
bool* refactorize,
1790 RowIndex* leaving_row,
Fractional* step_length,
1801 const Fractional entering_value = variable_values_.
Get(entering_col);
1802 Fractional current_ratio = (reduced_cost > 0.0)
1803 ? entering_value - lower_bound_[entering_col]
1804 : upper_bound_[entering_col] - entering_value;
1807 std::vector<BreakPoint> breakpoints;
1808 const Fractional tolerance = parameters_.primal_feasibility_tolerance();
1809 for (
const auto e : direction_) {
1811 reduced_cost > 0.0 ? e.coefficient() : -e.coefficient();
1812 const Fractional magnitude = std::abs(direction);
1813 if (magnitude < tolerance)
continue;
1828 const ColIndex
col = basis_[e.row()];
1834 const Fractional to_lower = (lower_bound - tolerance -
value) / direction;
1835 const Fractional to_upper = (upper_bound + tolerance -
value) / direction;
1839 if (to_lower >= 0.0 && to_lower < current_ratio) {
1840 breakpoints.push_back(
1841 BreakPoint(e.row(), to_lower, magnitude, lower_bound));
1843 if (to_upper >= 0.0 && to_upper < current_ratio) {
1844 breakpoints.push_back(
1845 BreakPoint(e.row(), to_upper, magnitude, upper_bound));
1851 std::make_heap(breakpoints.begin(), breakpoints.end());
1855 Fractional improvement = std::abs(reduced_cost);
1858 while (!breakpoints.empty()) {
1859 const BreakPoint top = breakpoints.front();
1867 if (top.coeff_magnitude > best_magnitude) {
1868 *leaving_row = top.row;
1869 current_ratio = top.ratio;
1870 best_magnitude = top.coeff_magnitude;
1876 improvement -= top.coeff_magnitude;
1877 if (improvement <= 0.0)
break;
1878 std::pop_heap(breakpoints.begin(), breakpoints.end());
1879 breakpoints.pop_back();
1885 parameters_.small_pivot_threshold() * direction_infinity_norm_;
1886 if (best_magnitude < threshold && !basis_factorization_.
IsRefactorized()) {
1887 *refactorize =
true;
1891 *step_length = current_ratio;
1895 Status RevisedSimplex::DualChooseLeavingVariableRow(RowIndex* leaving_row,
1910 equivalent_leaving_choices_.clear();
1912 const Fractional scaled_best_price = best_price * squared_norm[
row];
1913 if (squared_infeasibilities[
row] >= scaled_best_price) {
1914 if (squared_infeasibilities[
row] == scaled_best_price) {
1916 equivalent_leaving_choices_.push_back(
row);
1919 equivalent_leaving_choices_.clear();
1920 best_price = squared_infeasibilities[
row] / squared_norm[
row];
1926 if (!equivalent_leaving_choices_.empty()) {
1927 equivalent_leaving_choices_.push_back(*leaving_row);
1929 equivalent_leaving_choices_[std::uniform_int_distribution<int>(
1930 0, equivalent_leaving_choices_.size() - 1)(random_)];
1936 const ColIndex leaving_col = basis_[*leaving_row];
1938 if (
value < lower_bound_[leaving_col]) {
1939 *cost_variation = lower_bound_[leaving_col] -
value;
1943 *cost_variation = upper_bound_[leaving_col] -
value;
1957 if (
cost == 0.0)
return false;
1966 void RevisedSimplex::DualPhaseIUpdatePrice(RowIndex leaving_row,
1967 ColIndex entering_col) {
1970 const Fractional threshold = parameters_.ratio_test_zero_threshold();
1976 dual_pricing_vector_[leaving_row] / direction_[leaving_row];
1977 for (
const auto e : direction_) {
1978 dual_pricing_vector_[e.row()] -= e.coefficient() * step;
1979 is_dual_entering_candidate_.
Set(
1980 e.row(), IsDualPhaseILeavingCandidate(dual_pricing_vector_[e.row()],
1981 variable_type[basis_[e.row()]],
1984 dual_pricing_vector_[leaving_row] = step;
1988 dual_pricing_vector_[leaving_row] -=
1989 dual_infeasibility_improvement_direction_[entering_col];
1990 if (dual_infeasibility_improvement_direction_[entering_col] != 0.0) {
1991 --num_dual_infeasible_positions_;
1993 dual_infeasibility_improvement_direction_[entering_col] = 0.0;
1996 dual_infeasibility_improvement_direction_[basis_[leaving_row]] = 0.0;
1999 is_dual_entering_candidate_.
Set(
2001 IsDualPhaseILeavingCandidate(dual_pricing_vector_[leaving_row],
2002 variable_type[entering_col], threshold));
2005 template <
typename Cols>
2006 void RevisedSimplex::DualPhaseIUpdatePriceOnReducedCostChange(
2009 bool something_to_do =
false;
2014 for (ColIndex
col : cols) {
2017 (can_increase.IsSet(
col) && reduced_cost < -tolerance) ? 1.0
2018 : (can_decrease.IsSet(
col) && reduced_cost > tolerance) ? -1.0
2020 if (sign != dual_infeasibility_improvement_direction_[
col]) {
2022 --num_dual_infeasible_positions_;
2023 }
else if (dual_infeasibility_improvement_direction_[
col] == 0.0) {
2024 ++num_dual_infeasible_positions_;
2026 if (!something_to_do) {
2027 initially_all_zero_scratchpad_.
values.
resize(num_rows_, 0.0);
2029 initially_all_zero_scratchpad_.
non_zeros.clear();
2030 something_to_do =
true;
2033 col, sign - dual_infeasibility_improvement_direction_[
col],
2034 &initially_all_zero_scratchpad_);
2035 dual_infeasibility_improvement_direction_[
col] = sign;
2038 if (something_to_do) {
2043 const Fractional threshold = parameters_.ratio_test_zero_threshold();
2044 basis_factorization_.
RightSolve(&initially_all_zero_scratchpad_);
2045 if (initially_all_zero_scratchpad_.
non_zeros.empty()) {
2046 for (RowIndex
row(0);
row < num_rows_; ++
row) {
2047 if (initially_all_zero_scratchpad_[
row] == 0.0)
continue;
2048 dual_pricing_vector_[
row] += initially_all_zero_scratchpad_[
row];
2049 is_dual_entering_candidate_.
Set(
2050 row, IsDualPhaseILeavingCandidate(dual_pricing_vector_[
row],
2051 variable_type[basis_[
row]],
2056 for (
const auto e : initially_all_zero_scratchpad_) {
2057 dual_pricing_vector_[e.row()] += e.coefficient();
2058 initially_all_zero_scratchpad_[e.row()] = 0.0;
2059 is_dual_entering_candidate_.
Set(
2060 e.row(), IsDualPhaseILeavingCandidate(
2061 dual_pricing_vector_[e.row()],
2062 variable_type[basis_[e.row()]], threshold));
2065 initially_all_zero_scratchpad_.non_zeros.clear();
2069 Status RevisedSimplex::DualPhaseIChooseLeavingVariableRow(
2070 RowIndex* leaving_row,
Fractional* cost_variation,
2087 dual_pricing_vector_.
empty()) {
2089 num_dual_infeasible_positions_ = 0;
2092 dual_infeasibility_improvement_direction_.
AssignToZero(num_cols_);
2093 DualPhaseIUpdatePriceOnReducedCostChange(
2103 if (num_dual_infeasible_positions_ == 0)
return Status::OK();
2112 equivalent_leaving_choices_.clear();
2113 for (
const RowIndex
row : is_dual_entering_candidate_) {
2115 const Fractional scaled_best_price = best_price * squared_norm[
row];
2116 if (squared_cost >= scaled_best_price) {
2117 if (squared_cost == scaled_best_price) {
2119 equivalent_leaving_choices_.push_back(
row);
2122 equivalent_leaving_choices_.clear();
2123 best_price = squared_cost / squared_norm[
row];
2129 if (!equivalent_leaving_choices_.empty()) {
2130 equivalent_leaving_choices_.push_back(*leaving_row);
2132 equivalent_leaving_choices_[std::uniform_int_distribution<int>(
2133 0, equivalent_leaving_choices_.size() - 1)(random_)];
2139 *cost_variation = dual_pricing_vector_[*leaving_row];
2140 const ColIndex leaving_col = basis_[*leaving_row];
2141 if (*cost_variation < 0.0) {
2150 template <
typename BoxedVariableCols>
2151 void RevisedSimplex::MakeBoxedVariableDualFeasible(
2152 const BoxedVariableCols& cols,
bool update_basic_values) {
2154 std::vector<ColIndex> changed_cols;
2162 const Fractional dual_feasibility_tolerance =
2165 for (
const ColIndex
col : cols) {
2172 variable_values[
col] == upper_bound_[
col] ||
2174 if (reduced_cost > dual_feasibility_tolerance &&
2177 changed_cols.push_back(
col);
2178 }
else if (reduced_cost < -dual_feasibility_tolerance &&
2181 changed_cols.push_back(
col);
2185 if (!changed_cols.empty()) {
2187 update_basic_values);
2191 Fractional RevisedSimplex::ComputeStepToMoveBasicVariableToBound(
2196 const ColIndex leaving_col = basis_[leaving_row];
2197 const Fractional leaving_variable_value = variable_values_.
Get(leaving_col);
2207 return unscaled_step / direction_[leaving_row];
2210 bool RevisedSimplex::TestPivot(ColIndex entering_col, RowIndex leaving_row) {
2211 VLOG(1) <<
"Test pivot.";
2213 const ColIndex leaving_col = basis_[leaving_row];
2214 basis_[leaving_row] = entering_col;
2218 CompactSparseMatrixView basis_matrix(&compact_matrix_, &basis_);
2220 basis_[leaving_row] = leaving_col;
2227 void RevisedSimplex::PermuteBasis() {
2234 if (col_perm.empty())
return;
2240 if (!dual_pricing_vector_.
empty()) {
2257 Status RevisedSimplex::UpdateAndPivot(ColIndex entering_col,
2258 RowIndex leaving_row,
2261 const ColIndex leaving_col = basis_[leaving_row];
2263 lower_bound_[leaving_col] == upper_bound_[leaving_col]
2269 ratio_test_stats_.bound_shift.Add(variable_values_.
Get(leaving_col) -
2272 UpdateBasis(entering_col, leaving_row, leaving_variable_status);
2274 const Fractional pivot_from_direction = direction_[leaving_row];
2278 std::abs(pivot_from_update_row - pivot_from_direction);
2279 if (diff > parameters_.refactorization_threshold() *
2280 (1 + std::abs(pivot_from_direction))) {
2281 VLOG(1) <<
"Refactorizing: imprecise pivot " << pivot_from_direction
2282 <<
" diff = " << diff;
2286 basis_factorization_.
Update(entering_col, leaving_row, direction_));
2294 bool RevisedSimplex::NeedsBasisRefactorization(
bool refactorize) {
2297 const GlopParameters::PricingRule pricing_rule =
2298 feasibility_phase_ ? parameters_.feasibility_rule()
2299 : parameters_.optimization_rule();
2300 if (parameters_.use_dual_simplex()) {
2302 DCHECK_EQ(pricing_rule, GlopParameters::STEEPEST_EDGE);
2305 if (pricing_rule == GlopParameters::STEEPEST_EDGE &&
2313 Status RevisedSimplex::RefactorizeBasisIfNeeded(
bool* refactorize) {
2315 if (NeedsBasisRefactorization(*refactorize)) {
2320 *refactorize =
false;
2325 if (
col >= integrality_scale_.
size()) {
2326 integrality_scale_.
resize(
col + 1, 0.0);
2328 integrality_scale_[
col] = scale;
2333 Cleanup update_deterministic_time_on_return(
2340 std::vector<ColIndex> candidates;
2346 bool refactorize =
false;
2349 for (
int i = 0; i < 10; ++i) {
2352 if (num_pivots >= 5)
break;
2353 if (candidates.empty())
break;
2357 std::uniform_int_distribution<int>(0, candidates.size() - 1)(random_);
2358 const ColIndex entering_col = candidates[
index];
2359 std::swap(candidates[
index], candidates.back());
2360 candidates.pop_back();
2371 ComputeDirection(entering_col);
2373 RowIndex leaving_row;
2375 bool local_refactorize =
false;
2377 ChooseLeavingVariableRow(entering_col, fake_rc, &local_refactorize,
2380 if (local_refactorize)
continue;
2382 if (std::abs(step_length) <= 1e-6)
continue;
2383 if (leaving_row !=
kInvalidRow && std::abs(direction_[leaving_row]) < 0.1) {
2386 const Fractional step = (fake_rc > 0.0) ? -step_length : step_length;
2392 const auto get_diff = [
this](ColIndex
col,
Fractional old_value,
2394 if (
col >= integrality_scale_.
size() || integrality_scale_[
col] == 0.0) {
2398 return (std::abs(new_value * s - std::round(new_value * s)) -
2399 std::abs(old_value * s - std::round(old_value * s)));
2401 Fractional diff = get_diff(entering_col, variable_values_.
Get(entering_col),
2402 variable_values_.
Get(entering_col) + step);
2403 for (
const auto e : direction_) {
2404 const ColIndex
col = basis_[e.row()];
2406 const Fractional new_value = old_value - e.coefficient() * step;
2407 diff += get_diff(
col, old_value, new_value);
2411 if (diff > -1e-2)
continue;
2421 SetNonBasicVariableStatusAndDeriveValue(entering_col,
2423 }
else if (step < 0.0) {
2424 SetNonBasicVariableStatusAndDeriveValue(entering_col,
2432 const ColIndex leaving_col = basis_[leaving_row];
2435 entering_col, leaving_col, leaving_row, direction_, &update_row_);
2439 const Fractional dir = -direction_[leaving_row] * step;
2440 const bool is_degenerate =
2444 if (!is_degenerate) {
2448 UpdateAndPivot(entering_col, leaving_row,
target_bound));
2451 VLOG(1) <<
"Polish num_pivots: " << num_pivots <<
" gain:" << total_gain;
2470 Status RevisedSimplex::Minimize(TimeLimit*
time_limit) {
2472 Cleanup update_deterministic_time_on_return(
2474 num_consecutive_degenerate_iterations_ = 0;
2475 DisplayIterationInfo();
2476 bool refactorize =
false;
2478 if (feasibility_phase_) {
2494 CorrectErrorsOnVariableValues();
2495 DisplayIterationInfo();
2497 if (feasibility_phase_) {
2509 if (!feasibility_phase_ &&
2510 ComputeObjectiveValue() < primal_objective_limit_) {
2511 VLOG(1) <<
"Stopping the primal simplex because"
2512 <<
" the objective limit " << primal_objective_limit_
2513 <<
" has been reached.";
2515 objective_limit_reached_ =
true;
2518 }
else if (feasibility_phase_) {
2534 if (feasibility_phase_) {
2537 if (primal_infeasibility <
2538 parameters_.primal_feasibility_tolerance()) {
2541 VLOG(1) <<
"Infeasible problem! infeasibility = "
2542 << primal_infeasibility;
2550 VLOG(1) <<
"Optimal reached, double checking...";
2560 ComputeDirection(entering_col);
2564 entering_col, direction_, &reduced_cost)) {
2565 VLOG(1) <<
"Skipping col #" << entering_col <<
" whose reduced cost is "
2576 if (num_iterations_ == parameters_.max_number_of_iterations() ||
2582 RowIndex leaving_row;
2584 if (feasibility_phase_) {
2585 PrimalPhaseIChooseLeavingVariableRow(entering_col, reduced_cost,
2586 &refactorize, &leaving_row,
2590 ChooseLeavingVariableRow(entering_col, reduced_cost, &refactorize,
2593 if (refactorize)
continue;
2598 VLOG(1) <<
"Infinite step length, double checking...";
2602 if (feasibility_phase_) {
2604 VLOG(1) <<
"Unbounded feasibility problem !?";
2607 VLOG(1) <<
"Unbounded problem.";
2610 for (RowIndex
row(0);
row < num_rows_; ++
row) {
2611 const ColIndex
col = basis_[
row];
2612 solution_primal_ray_[
col] = -direction_[
row];
2614 solution_primal_ray_[entering_col] = 1.0;
2622 Fractional step = (reduced_cost > 0.0) ? -step_length : step_length;
2623 if (feasibility_phase_ && leaving_row !=
kInvalidRow) {
2633 step = ComputeStepToMoveBasicVariableToBound(leaving_row,
target_bound);
2637 const ColIndex leaving_col =
2643 bool is_degenerate =
false;
2645 Fractional dir = -direction_[leaving_row] * step;
2653 if (!is_degenerate) {
2654 DCHECK_EQ(step, ComputeStepToMoveBasicVariableToBound(leaving_row,
2662 entering_col, basis_[leaving_row], leaving_row, direction_,
2665 direction_, &update_row_);
2666 if (!is_degenerate) {
2675 UpdateAndPivot(entering_col, leaving_row,
target_bound));
2677 if (is_degenerate) {
2678 timer.AlsoUpdate(&iteration_stats_.degenerate);
2680 timer.AlsoUpdate(&iteration_stats_.normal);
2689 SetNonBasicVariableStatusAndDeriveValue(entering_col,
2691 }
else if (step < 0.0) {
2692 SetNonBasicVariableStatusAndDeriveValue(entering_col,
2699 if (feasibility_phase_ && leaving_row !=
kInvalidRow) {
2703 &objective_[leaving_col]);
2707 if (step_length == 0.0) {
2708 num_consecutive_degenerate_iterations_++;
2710 if (num_consecutive_degenerate_iterations_ > 0) {
2711 iteration_stats_.degenerate_run_size.Add(
2712 num_consecutive_degenerate_iterations_);
2713 num_consecutive_degenerate_iterations_ = 0;
2718 if (num_consecutive_degenerate_iterations_ > 0) {
2719 iteration_stats_.degenerate_run_size.Add(
2720 num_consecutive_degenerate_iterations_);
2735 Status RevisedSimplex::DualMinimize(TimeLimit*
time_limit) {
2736 Cleanup update_deterministic_time_on_return(
2738 num_consecutive_degenerate_iterations_ = 0;
2739 bool refactorize =
false;
2741 bound_flip_candidates_.clear();
2742 pair_to_ignore_.clear();
2745 RowIndex leaving_row;
2750 ColIndex entering_col;
2759 const bool old_refactorize_value = refactorize;
2776 !old_refactorize_value) {
2779 if (dual_residual_error >
2781 VLOG(1) <<
"Recomputing reduced costs. Dual residual = "
2782 << dual_residual_error;
2797 if (!feasibility_phase_) {
2798 MakeBoxedVariableDualFeasible(
2806 if (ComputeObjectiveValue() > dual_objective_limit_) {
2807 VLOG(1) <<
"Stopping the dual simplex because"
2808 <<
" the objective limit " << dual_objective_limit_
2809 <<
" has been reached.";
2811 objective_limit_reached_ =
true;
2817 DisplayIterationInfo();
2821 if (!feasibility_phase_) {
2824 MakeBoxedVariableDualFeasible(bound_flip_candidates_,
2826 bound_flip_candidates_.clear();
2831 direction_.non_zeros);
2835 if (feasibility_phase_) {
2844 VLOG(1) <<
"Optimal reached, double checking.";
2848 if (feasibility_phase_) {
2853 if (num_dual_infeasible_positions_ == 0) {
2865 for (std::pair<RowIndex, ColIndex> pair : pair_to_ignore_) {
2866 if (pair.first == leaving_row) {
2870 if (feasibility_phase_) {
2872 update_row_, cost_variation, &entering_col, &
ratio));
2875 update_row_, cost_variation, &bound_flip_candidates_, &entering_col,
2882 VLOG(1) <<
"No entering column. Double checking...";
2887 if (feasibility_phase_) {
2889 VLOG(1) <<
"Unbounded dual feasibility problem !?";
2893 solution_dual_ray_ =
2896 solution_dual_ray_row_combination_.
AssignToZero(num_cols_);
2898 solution_dual_ray_row_combination_[
col] =
2901 if (cost_variation < 0) {
2903 ChangeSign(&solution_dual_ray_row_combination_);
2911 if (std::abs(entering_coeff) < parameters_.dual_small_pivot_threshold() &&
2913 VLOG(1) <<
"Trying not to pivot by " << entering_coeff;
2922 ComputeDirection(entering_col);
2923 if (std::abs(direction_[leaving_row]) <
2924 parameters_.minimum_acceptable_pivot()) {
2925 VLOG(1) <<
"Do not pivot by " << entering_coeff
2926 <<
" because the direction is " << direction_[leaving_row];
2928 pair_to_ignore_.push_back({leaving_row, entering_col});
2931 pair_to_ignore_.clear();
2938 if (num_iterations_ == parameters_.max_number_of_iterations() ||
2945 timer.AlsoUpdate(&iteration_stats_.degenerate);
2947 timer.AlsoUpdate(&iteration_stats_.normal);
2959 if (feasibility_phase_) {
2960 DualPhaseIUpdatePrice(leaving_row, entering_col);
2963 ComputeStepToMoveBasicVariableToBound(leaving_row,
target_bound);
2970 entering_col, leaving_row, direction_,
2974 const ColIndex leaving_col = basis_[leaving_row];
2976 UpdateAndPivot(entering_col, leaving_row,
target_bound));
2986 if (std::abs(primal_step) * parameters_.primal_feasibility_tolerance() >
2995 ColIndex RevisedSimplex::SlackColIndex(RowIndex
row)
const {
3003 result.append(iteration_stats_.StatString());
3004 result.append(ratio_test_stats_.StatString());
3005 result.append(entering_variable_.
StatString());
3007 result.append(variable_values_.
StatString());
3008 result.append(primal_edge_norms_.
StatString());
3009 result.append(dual_edge_norms_.
StatString());
3011 result.append(basis_factorization_.
StatString());
3016 void RevisedSimplex::DisplayAllStats() {
3017 if (absl::GetFlag(FLAGS_simplex_display_stats)) {
3019 absl::FPrintF(stderr,
"%s", GetPrettySolverStats());
3023 Fractional RevisedSimplex::ComputeObjectiveValue()
const {
3029 Fractional RevisedSimplex::ComputeInitialProblemObjectiveValue()
const {
3033 return objective_scaling_factor_ * (sum + objective_offset_);
3041 PropagateParameters();
3044 void RevisedSimplex::PropagateParameters() {
3054 void RevisedSimplex::DisplayIterationInfo()
const {
3055 if (parameters_.log_search_progress() ||
VLOG_IS_ON(1)) {
3056 const int iter = feasibility_phase_
3058 : num_iterations_ - num_feasibility_iterations_;
3065 ? ComputeInitialProblemObjectiveValue()
3066 : (parameters_.use_dual_simplex()
3067 ? reduced_costs_.ComputeSumOfDualInfeasibilities()
3068 : variable_values_.ComputeSumOfPrimalInfeasibilities());
3069 LOG(
INFO) << (feasibility_phase_ ?
"Feasibility" :
"Optimization")
3070 <<
" phase, iteration # " << iter
3071 <<
", objective = " << absl::StrFormat(
"%.15E", objective);
3075 void RevisedSimplex::DisplayErrors()
const {
3076 if (parameters_.log_search_progress() ||
VLOG_IS_ON(1)) {
3077 LOG(
INFO) <<
"Primal infeasibility (bounds) = "
3079 LOG(
INFO) <<
"Primal residual |A.x - b| = "
3081 LOG(
INFO) <<
"Dual infeasibility (reduced costs) = "
3083 LOG(
INFO) <<
"Dual residual |c_B - y.B| = "
3090 std::string StringifyMonomialWithFlags(
const Fractional a,
3091 const std::string& x) {
3093 a, x, absl::GetFlag(FLAGS_simplex_display_numbers_as_fractions));
3099 std::string StringifyWithFlags(
const Fractional x) {
3101 absl::GetFlag(FLAGS_simplex_display_numbers_as_fractions));
3106 std::string RevisedSimplex::SimpleVariableInfo(ColIndex
col)
const {
3110 absl::StrAppendFormat(&output,
"%d (%s) = %s, %s, %s, [%s,%s]",
col.value(),
3111 variable_name_[
col],
3112 StringifyWithFlags(variable_values_.
Get(
col)),
3115 StringifyWithFlags(lower_bound_[
col]),
3116 StringifyWithFlags(upper_bound_[
col]));
3120 void RevisedSimplex::DisplayInfoOnVariables()
const {
3122 for (ColIndex
col(0);
col < num_cols_; ++
col) {
3126 objective_coefficient * variable_value;
3127 VLOG(3) << SimpleVariableInfo(
col) <<
". " << variable_name_[
col] <<
" = "
3128 << StringifyWithFlags(variable_value) <<
" * "
3129 << StringifyWithFlags(objective_coefficient)
3130 <<
"(obj) = " << StringifyWithFlags(objective_contribution);
3132 VLOG(3) <<
"------";
3136 void RevisedSimplex::DisplayVariableBounds() {
3139 for (ColIndex
col(0);
col < num_cols_; ++
col) {
3140 switch (variable_type[
col]) {
3144 VLOG(3) << variable_name_[
col]
3145 <<
" >= " << StringifyWithFlags(lower_bound_[
col]) <<
";";
3148 VLOG(3) << variable_name_[
col]
3149 <<
" <= " << StringifyWithFlags(upper_bound_[
col]) <<
";";
3152 VLOG(3) << StringifyWithFlags(lower_bound_[
col])
3153 <<
" <= " << variable_name_[
col]
3154 <<
" <= " << StringifyWithFlags(upper_bound_[
col]) <<
";";
3157 VLOG(3) << variable_name_[
col] <<
" = "
3158 << StringifyWithFlags(lower_bound_[
col]) <<
";";
3161 LOG(DFATAL) <<
"Column " <<
col <<
" has no meaningful status.";
3171 for (ColIndex
col(0);
col < num_cols_; ++
col) {
3172 ComputeDirection(
col);
3173 for (
const auto e : direction_) {
3174 if (column_scales ==
nullptr) {
3175 dictionary[e.row()].SetCoefficient(
col, e.coefficient());
3179 col < column_scales->
size() ? (*column_scales)[
col] : 1.0;
3181 ? (*column_scales)[
GetBasis(e.row())]
3183 dictionary[e.row()].SetCoefficient(
3184 col, direction_[e.row()] * (numerator / denominator));
3193 Status status = Initialize(linear_program);
3197 solution_objective_value_ = ComputeInitialProblemObjectiveValue();
3201 void RevisedSimplex::DisplayRevisedSimplexDebugInfo() {
3204 DisplayInfoOnVariables();
3206 std::string output =
"z = " + StringifyWithFlags(ComputeObjectiveValue());
3209 absl::StrAppend(&output, StringifyMonomialWithFlags(reduced_costs[
col],
3210 variable_name_[
col]));
3212 VLOG(3) << output <<
";";
3214 const RevisedSimplexDictionary dictionary(
nullptr,
this);
3216 for (
const SparseRow&
row : dictionary) {
3218 ColIndex basic_col = basis_[r];
3219 absl::StrAppend(&output, variable_name_[basic_col],
" = ",
3220 StringifyWithFlags(variable_values_.
Get(basic_col)));
3221 for (
const SparseRowEntry e :
row) {
3222 if (e.col() != basic_col) {
3223 absl::StrAppend(&output,
3224 StringifyMonomialWithFlags(e.coefficient(),
3225 variable_name_[e.col()]));
3228 VLOG(3) << output <<
";";
3230 VLOG(3) <<
"------";
3231 DisplayVariableBounds();
3236 void RevisedSimplex::DisplayProblem()
const {
3240 DisplayInfoOnVariables();
3241 std::string output =
"min: ";
3242 bool has_objective =
false;
3243 for (ColIndex
col(0);
col < num_cols_; ++
col) {
3245 has_objective |= (coeff != 0.0);
3246 absl::StrAppend(&output,
3247 StringifyMonomialWithFlags(coeff, variable_name_[
col]));
3249 if (!has_objective) {
3250 absl::StrAppend(&output,
" 0");
3252 VLOG(3) << output <<
";";
3253 for (RowIndex
row(0);
row < num_rows_; ++
row) {
3255 for (ColIndex
col(0);
col < num_cols_; ++
col) {
3256 absl::StrAppend(&output,
3257 StringifyMonomialWithFlags(
3259 variable_name_[
col]));
3261 VLOG(3) << output <<
" = 0;";
3263 VLOG(3) <<
"------";
3267 void RevisedSimplex::AdvanceDeterministicTime(TimeLimit*
time_limit) {
3270 const double deterministic_time_delta =
3271 current_deterministic_time - last_deterministic_time_update_;
3272 time_limit->AdvanceDeterministicTime(deterministic_time_delta);
3273 last_deterministic_time_update_ = current_deterministic_time;
3276 #undef DCHECK_COL_BOUNDS
3277 #undef DCHECK_ROW_BOUNDS
#define DCHECK_LE(val1, val2)
#define DCHECK_NE(val1, val2)
#define DCHECK_GE(val1, val2)
#define DCHECK_GT(val1, val2)
#define DCHECK_LT(val1, val2)
#define DCHECK(condition)
#define DCHECK_EQ(val1, val2)
#define VLOG(verboselevel)
void push_back(const value_type &x)
void ClearAndResize(IndexType size)
bool IsSet(IndexType i) const
std::string StatString() const
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
Fractional ComputeInfinityNormConditionNumberUpperBound() const
ABSL_MUST_USE_RESULT Status Refactorize()
const ColumnPermutation & GetColumnPermutation() const
ABSL_MUST_USE_RESULT Status Initialize()
bool IsRefactorized() const
ABSL_MUST_USE_RESULT Status Update(ColIndex entering_col, RowIndex leaving_variable_row, const ScatteredColumn &direction)
void RightSolveForProblemColumn(ColIndex col, ScatteredColumn *d) const
void SetColumnPermutationToIdentity()
void SetParameters(const GlopParameters ¶meters)
void RightSolve(ScatteredColumn *d) const
double DeterministicTime() const
ABSL_MUST_USE_RESULT Status ForceRefactorization()
std::string StatString() const
Fractional LookUpCoefficient(RowIndex index) const
Fractional EntryCoefficient(EntryIndex i) const
Fractional GetFirstCoefficient() const
RowIndex EntryRow(EntryIndex i) const
EntryIndex num_entries() const
void ColumnCopyToDenseColumn(ColIndex col, DenseColumn *dense_column) const
ColIndex num_cols() const
void ColumnAddMultipleToSparseScatteredColumn(ColIndex col, Fractional multiplier, ScatteredColumn *column) const
RowIndex num_rows() const
void PopulateFromTranspose(const CompactSparseMatrix &input)
void ColumnAddMultipleToDenseColumn(ColIndex col, Fractional multiplier, DenseColumn *dense_column) const
void PopulateFromMatrixView(const MatrixView &input)
EntryIndex num_entries() const
ColumnView column(ColIndex col) const
void UpdateBeforeBasisPivot(ColIndex entering_col, RowIndex leaving_row, const ScatteredColumn &direction, const ScatteredRow &unit_row_left_inverse)
void UpdateDataOnBasisPermutation(const ColumnPermutation &col_perm)
const DenseColumn & GetEdgeSquaredNorms()
bool NeedsBasisRefactorization()
void ResizeOnNewRows(RowIndex new_size)
void SetParameters(const GlopParameters ¶meters)
std::string StatString() const
ABSL_MUST_USE_RESULT Status PrimalChooseEnteringColumn(ColIndex *entering_col)
ABSL_MUST_USE_RESULT Status DualChooseEnteringColumn(const UpdateRow &update_row, Fractional cost_variation, std::vector< ColIndex > *bound_flip_candidates, ColIndex *entering_col, Fractional *step)
ABSL_MUST_USE_RESULT Status DualPhaseIChooseEnteringColumn(const UpdateRow &update_row, Fractional cost_variation, ColIndex *entering_col, Fractional *step)
void SetPricingRule(GlopParameters::PricingRule rule)
void SetParameters(const GlopParameters ¶meters)
std::string StatString() const
bool IsInEquationForm() const
bool IsMaximizationProblem() const
ABSL_MUST_USE_RESULT Status ComputeFactorization(const CompactSparseMatrixView &compact_matrix)
void UpdateBeforeBasisPivot(ColIndex entering_col, ColIndex leaving_col, RowIndex leaving_row, const ScatteredColumn &direction, UpdateRow *update_row)
void TestEnteringEdgeNormPrecision(ColIndex entering_col, const ScatteredColumn &direction)
void SetParameters(const GlopParameters ¶meters)
double DeterministicTime() const
bool NeedsBasisRefactorization() const
std::string StatString() const
void ResetForNewObjective()
Fractional ComputeMaximumDualResidual() const
void MakeReducedCostsPrecise()
bool AreReducedCostsRecomputed()
bool TestEnteringReducedCostPrecision(ColIndex entering_col, const ScatteredColumn &direction, Fractional *reduced_cost)
bool AreReducedCostsPrecise()
bool IsValidPrimalEnteringCandidate(ColIndex col) const
void SetNonBasicVariableCostToZero(ColIndex col, Fractional *current_cost)
void SetAndDebugCheckThatColumnIsDualFeasible(ColIndex col)
void UpdateBeforeBasisPivot(ColIndex entering_col, RowIndex leaving_row, const ScatteredColumn &direction, UpdateRow *update_row)
const DenseRow & GetReducedCosts()
Fractional GetDualFeasibilityTolerance() const
Fractional ComputeMaximumDualInfeasibility() const
void MaintainDualInfeasiblePositions(bool maintain)
const DenseColumn & GetDualValues()
void ClearAndRemoveCostShifts()
void UpdateDataOnBasisPermutation()
void SetParameters(const GlopParameters ¶meters)
bool NeedsBasisRefactorization() const
std::string StatString() const
const DenseRow & GetDualRayRowCombination() const
Fractional GetVariableValue(ColIndex col) const
void SetIntegralityScale(ColIndex col, Fractional scale)
const DenseRow & GetReducedCosts() const
int64 GetNumberOfIterations() const
const DenseRow & GetPrimalRay() const
Fractional GetConstraintActivity(RowIndex row) const
VariableStatus GetVariableStatus(ColIndex col) const
Fractional GetReducedCost(ColIndex col) const
const DenseColumn & GetDualRay() const
ABSL_MUST_USE_RESULT Status Solve(const LinearProgram &lp, TimeLimit *time_limit)
ProblemStatus GetProblemStatus() const
Fractional GetObjectiveValue() const
RowMajorSparseMatrix ComputeDictionary(const DenseRow *column_scales)
Fractional GetDualValue(RowIndex row) const
void NotifyThatMatrixIsUnchangedForNextSolve()
ConstraintStatus GetConstraintStatus(RowIndex row) const
void ComputeBasicVariablesForState(const LinearProgram &linear_program, const BasisState &state)
ColIndex GetProblemNumCols() const
void LoadStateForNextSolve(const BasisState &state)
RowIndex GetProblemNumRows() const
void ClearStateForNextSolve()
const BasisFactorization & GetBasisFactorization() const
const BasisState & GetState() const
ColIndex GetBasis(RowIndex row) const
void SetParameters(const GlopParameters ¶meters)
double DeterministicTime() const
typename Iterator::Entry Entry
void AssignToZero(IntType size)
void resize(IntType size)
const ScatteredRow & GetUnitRowLeftInverse() const
void RecomputeFullUpdateRow(RowIndex leaving_row)
void IgnoreUpdatePosition(ColIndex col)
const Fractional GetCoefficient(ColIndex col) const
void ComputeUpdateRow(RowIndex leaving_row)
void SetParameters(const GlopParameters ¶meters)
double DeterministicTime() const
const ColIndexVector & GetNonZeroPositions() const
std::string StatString() const
void Set(ColIndex col, Fractional value)
void SetNonBasicVariableValueFromStatus(ColIndex col)
const DenseColumn & GetPrimalSquaredInfeasibilities() const
Fractional ComputeMaximumPrimalInfeasibility() const
void UpdateGivenNonBasicVariables(const std::vector< ColIndex > &cols_to_update, bool update_basic_variables)
const DenseBitColumn & GetPrimalInfeasiblePositions() const
const DenseRow & GetDenseRow() const
void ResetPrimalInfeasibilityInformation()
void UpdateOnPivoting(const ScatteredColumn &direction, ColIndex entering_col, Fractional step)
const Fractional Get(ColIndex col) const
void UpdatePrimalInfeasibilityInformation(const std::vector< RowIndex > &rows)
void RecomputeBasicVariableValues()
Fractional ComputeMaximumPrimalResidual() const
bool UpdatePrimalPhaseICosts(const Rows &rows, DenseRow *objective)
void ResetAllNonBasicVariableValues()
std::string StatString() const
const DenseBitRow & GetIsBasicBitRow() const
const DenseBitRow & GetNonBasicBoxedVariables() const
Fractional GetBoundDifference(ColIndex col) const
const DenseBitRow & GetCanIncreaseBitRow() const
const DenseBitRow & GetCanDecreaseBitRow() const
const VariableTypeRow & GetTypeRow() const
void MakeBoxedVariableRelevant(bool value)
void UpdateToNonBasicStatus(ColIndex col, VariableStatus status)
void InitializeAndComputeType()
const DenseBitRow & GetNotBasicBitRow() const
const VariableStatusRow & GetStatusRow() const
void UpdateToBasicStatus(ColIndex col)
const DenseBitRow & GetIsRelevantBitRow() const
void Update(ColIndex col, VariableStatus status)
SharedTimeLimit * time_limit
std::string StringifyMonomial(const Fractional a, const std::string &x, bool fraction)
bool IsRightMostSquareMatrixIdentity(const SparseMatrix &matrix)
Fractional Square(Fractional f)
Fractional InfinityNorm(const DenseColumn &v)
const RowIndex kInvalidRow(-1)
std::string Stringify(const Fractional x, bool fraction)
StrictITIVector< ColIndex, VariableType > VariableTypeRow
Fractional PreciseScalarProduct(const DenseRowOrColumn &u, const DenseRowOrColumn2 &v)
StrictITIVector< ColIndex, Fractional > DenseRow
std::string GetProblemStatusString(ProblemStatus problem_status)
Index ColToIntIndex(ColIndex col)
Permutation< ColIndex > ColumnPermutation
StrictITIVector< ColIndex, VariableStatus > VariableStatusRow
constexpr const uint64 kDeterministicSeed
ColIndex RowToColIndex(RowIndex row)
bool IsFinite(Fractional value)
bool AreFirstColumnsAndRowsExactlyEquals(RowIndex num_rows, ColIndex num_cols, const SparseMatrix &matrix_a, const CompactSparseMatrix &matrix_b)
const DenseRow & Transpose(const DenseColumn &col)
Bitset64< ColIndex > DenseBitRow
ConstraintStatus VariableToConstraintStatus(VariableStatus status)
void ChangeSign(StrictITIVector< IndexType, Fractional > *data)
@ UPPER_AND_LOWER_BOUNDED
StrictITIVector< RowIndex, ColIndex > RowToColMapping
std::string GetVariableTypeString(VariableType variable_type)
void ApplyColumnPermutationToRowIndexedVector(const Permutation< ColIndex > &col_perm, RowIndexedVector *v)
StrictITIVector< RowIndex, Fractional > DenseColumn
StrictITIVector< RowIndex, bool > DenseBooleanColumn
std::string GetVariableStatusString(VariableStatus status)
const ColIndex kInvalidCol(-1)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
DisabledScopedTimeDistributionUpdater ScopedTimeDistributionUpdater
#define RETURN_IF_NULL(x)
Fractional coeff_magnitude
#define DCHECK_ROW_BOUNDS(row)
ABSL_FLAG(bool, simplex_display_numbers_as_fractions, false, "Display numbers as fractions.")
#define DCHECK_COL_BOUNDS(col)
#define IF_STATS_ENABLED(instructions)
#define SCOPED_TIME_STAT(stats)
#define GLOP_RETURN_IF_ERROR(function_call)
#define GLOP_RETURN_ERROR_IF_NULL(arg)
VariableStatusRow statuses
void ClearNonZerosIfTooDense(double ratio_for_using_dense_representation)
std::vector< Index > non_zeros
StrictITIVector< Index, Fractional > values
#define VLOG_IS_ON(verboselevel)