20#include "absl/memory/memory.h"
21#include "absl/strings/match.h"
22#include "absl/strings/str_format.h"
34#ifndef __PORTABLE_PLATFORM__
38ABSL_FLAG(
bool, lp_solver_enable_fp_exceptions,
false,
39 "When true, NaNs and division / zero produce errors. "
40 "This is very useful for debugging, but incompatible with LLVM. "
41 "It is recommended to set this to false for production usage.");
43 "Tells whether do dump the problem to a protobuf file.");
45 "Whether the proto dump file is compressed.");
47 "Whether the proto dump file is binary.");
49 "Number for the dump file, in the form name-000048.pb. "
50 "If < 0, the file is automatically numbered from the number of "
51 "calls to LPSolver::Solve().");
53 "Directory where dump files are written.");
55 "Base name for dump files. LinearProgram::name_ is used if "
56 "lp_dump_file_basename is empty. If LinearProgram::name_ is "
57 "empty, \"linear_program_dump_file\" is used.");
70void DumpLinearProgramIfRequiredByFlags(
const LinearProgram& linear_program,
72 if (!absl::GetFlag(FLAGS_lp_dump_to_proto_file))
return;
73#ifdef __PORTABLE_PLATFORM__
74 LOG(
WARNING) <<
"DumpLinearProgramIfRequiredByFlags(linear_program, num) "
75 "requested for linear_program.name()='"
76 << linear_program.name() <<
"', num=" << num
77 <<
" but is not implemented for this platform.";
79 std::string filename = absl::GetFlag(FLAGS_lp_dump_file_basename);
80 if (filename.empty()) {
81 if (linear_program.name().empty()) {
82 filename =
"linear_program_dump";
84 filename = linear_program.name();
87 const int file_num = absl::GetFlag(FLAGS_lp_dump_file_number) >= 0
88 ? absl::GetFlag(FLAGS_lp_dump_file_number)
90 absl::StrAppendFormat(&filename,
"-%06d.pb", file_num);
91 const std::string filespec =
92 absl::StrCat(absl::GetFlag(FLAGS_lp_dump_dir),
"/", filename);
95 const ProtoWriteFormat write_format = absl::GetFlag(FLAGS_lp_dump_binary_file)
99 absl::GetFlag(FLAGS_lp_dump_compressed_file))) {
100 LOG(DFATAL) <<
"Could not write " << filespec;
130 LOG(DFATAL) <<
"SolveWithTimeLimit() called with a nullptr time_limit.";
134 num_revised_simplex_iterations_ = 0;
135 DumpLinearProgramIfRequiredByFlags(lp, num_solves_);
138 LOG(DFATAL) <<
"The columns of the given linear program should be ordered "
139 <<
"by row and contain no zero coefficients. Call CleanUp() "
140 <<
"on it before calling Solve().";
145 LOG(DFATAL) <<
"The given linear program is invalid. It contains NaNs, "
146 <<
"infinite coefficients or invalid bounds specification. "
147 <<
"You can construct it in debug mode to get the exact cause.";
153 <<
"\n******************************************************************"
154 "\n* WARNING: Glop will be very slow because it will use DCHECKs *"
155 "\n* to verify the results and the precision of the solver. *"
156 "\n* You can gain at least an order of magnitude speedup by *"
157 "\n* compiling with optimizations enabled and by defining NDEBUG. *"
158 "\n******************************************************************";
164 if (absl::GetFlag(FLAGS_lp_solver_enable_fp_exceptions)) {
173 const bool log_info = parameters_.log_search_progress() ||
VLOG_IS_ON(1);
185 const bool postsolve_is_needed = preprocessor.
Run(¤t_linear_program_);
188 LOG(
INFO) <<
"Presolved problem: "
190 LOG(
INFO) <<
"Objective stats: "
206 RunRevisedSimplexIfNeeded(&solution,
time_limit);
214 LOG(
INFO) <<
"status: " << status;
218 LOG(
INFO) <<
"deterministic_time: "
226 ResizeSolution(RowIndex(0), ColIndex(0));
227 revised_simplex_.reset(
nullptr);
257 if (revised_simplex_ ==
nullptr) {
258 revised_simplex_ = absl::make_unique<RevisedSimplex>();
260 revised_simplex_->LoadStateForNextSolve(state);
261 if (parameters_.use_preprocessing()) {
262 LOG(
WARNING) <<
"In GLOP, SetInitialBasis() was called but the parameter "
263 "use_preprocessing is true, this will likely not result in "
286 const bool log_info = parameters_.log_search_progress() ||
VLOG_IS_ON(1);
288 if (!IsProblemSolutionConsistent(lp, solution)) {
289 if (log_info)
LOG(
INFO) <<
"Inconsistency detected in the solution.";
303 ComputeReducedCosts(lp);
304 const Fractional primal_objective_value = ComputeObjective(lp);
305 const Fractional dual_objective_value = ComputeDualObjective(lp);
307 LOG(
INFO) <<
"Primal objective (before moving primal/dual values) = "
308 << absl::StrFormat(
"%.15E", ProblemObjectiveValue(
309 lp, primal_objective_value));
310 LOG(
INFO) <<
"Dual objective (before moving primal/dual values) = "
312 "%.15E", ProblemObjectiveValue(lp, dual_objective_value));
317 parameters_.provide_strong_optimal_guarantee()) {
318 MovePrimalValuesWithinBounds(lp);
319 MoveDualValuesWithinBounds(lp);
323 problem_objective_value_ = ProblemObjectiveValue(lp, ComputeObjective(lp));
325 LOG(
INFO) <<
"Primal objective (after moving primal/dual values) = "
326 << absl::StrFormat(
"%.15E", problem_objective_value_);
329 ComputeReducedCosts(lp);
330 ComputeConstraintActivities(lp);
340 bool rhs_perturbation_is_too_large =
false;
341 bool cost_perturbation_is_too_large =
false;
342 bool primal_infeasibility_is_too_large =
false;
343 bool dual_infeasibility_is_too_large =
false;
344 bool primal_residual_is_too_large =
false;
345 bool dual_residual_is_too_large =
false;
348 ComputeMaxRhsPerturbationToEnforceOptimality(lp,
349 &rhs_perturbation_is_too_large);
350 ComputeMaxCostPerturbationToEnforceOptimality(
351 lp, &cost_perturbation_is_too_large);
352 const double primal_infeasibility =
353 ComputePrimalValueInfeasibility(lp, &primal_infeasibility_is_too_large);
354 const double dual_infeasibility =
355 ComputeDualValueInfeasibility(lp, &dual_infeasibility_is_too_large);
356 const double primal_residual =
357 ComputeActivityInfeasibility(lp, &primal_residual_is_too_large);
358 const double dual_residual =
359 ComputeReducedCostInfeasibility(lp, &dual_residual_is_too_large);
364 max_absolute_primal_infeasibility_ =
365 std::max(primal_infeasibility, primal_residual);
366 max_absolute_dual_infeasibility_ =
367 std::max(dual_infeasibility, dual_residual);
369 LOG(
INFO) <<
"Max. primal infeasibility = "
370 << max_absolute_primal_infeasibility_;
371 LOG(
INFO) <<
"Max. dual infeasibility = "
372 << max_absolute_dual_infeasibility_;
378 const double objective_error_ub = ComputeMaxExpectedObjectiveError(lp);
380 LOG(
INFO) <<
"Objective error <= " << objective_error_ub;
384 parameters_.provide_strong_optimal_guarantee()) {
387 if (primal_infeasibility != 0.0 || dual_infeasibility != 0.0) {
388 LOG(
ERROR) <<
"Primal/dual values have been moved to their bounds. "
389 <<
"Therefore the primal/dual infeasibilities should be "
390 <<
"exactly zero (but not the residuals). If this message "
391 <<
"appears, there is probably a bug in "
392 <<
"MovePrimalValuesWithinBounds() or in "
393 <<
"MoveDualValuesWithinBounds().";
395 if (rhs_perturbation_is_too_large) {
396 if (log_info)
LOG(
INFO) <<
"The needed rhs perturbation is too large !!";
399 if (cost_perturbation_is_too_large) {
400 if (log_info)
LOG(
INFO) <<
"The needed cost perturbation is too large !!";
409 if (std::abs(primal_objective_value - dual_objective_value) >
410 objective_error_ub) {
412 LOG(
INFO) <<
"The objective gap of the final solution is too large.";
419 (primal_residual_is_too_large || primal_infeasibility_is_too_large)) {
422 <<
"The primal infeasibility of the final solution is too large.";
428 (dual_residual_is_too_large || dual_infeasibility_is_too_large)) {
430 LOG(
INFO) <<
"The dual infeasibility of the final solution is too large.";
435 may_have_multiple_solutions_ =
440bool LPSolver::IsOptimalSolutionOnFacet(
const LinearProgram& lp) {
445 const double kReducedCostTolerance = 1e-9;
446 const double kBoundTolerance = 1e-7;
448 for (ColIndex
col(0);
col < num_cols; ++
col) {
454 kReducedCostTolerance) &&
461 for (RowIndex
row(0);
row < num_rows; ++
row) {
467 kReducedCostTolerance) &&
477 return problem_objective_value_;
481 return max_absolute_primal_infeasibility_;
485 return max_absolute_dual_infeasibility_;
489 return may_have_multiple_solutions_;
493 return num_revised_simplex_iterations_;
497 return revised_simplex_ ==
nullptr ? 0.0
498 : revised_simplex_->DeterministicTime();
501void LPSolver::MovePrimalValuesWithinBounds(
const LinearProgram& lp) {
505 for (ColIndex
col(0);
col < num_cols; ++
col) {
510 error =
std::max(error, primal_values_[
col] - upper_bound);
511 error =
std::max(error, lower_bound - primal_values_[
col]);
515 const bool log_info = parameters_.log_search_progress() ||
VLOG_IS_ON(1);
516 if (log_info)
LOG(
INFO) <<
"Max. primal values move = " << error;
519void LPSolver::MoveDualValuesWithinBounds(
const LinearProgram& lp) {
520 const RowIndex num_rows = lp.num_constraints();
522 const Fractional optimization_sign = lp.IsMaximizationProblem() ? -1.0 : 1.0;
524 for (RowIndex
row(0);
row < num_rows; ++
row) {
525 const Fractional lower_bound = lp.constraint_lower_bounds()[
row];
526 const Fractional upper_bound = lp.constraint_upper_bounds()[
row];
529 Fractional minimization_dual_value = optimization_sign * dual_values_[
row];
530 if (lower_bound == -
kInfinity && minimization_dual_value > 0.0) {
531 error =
std::max(error, minimization_dual_value);
532 minimization_dual_value = 0.0;
534 if (upper_bound ==
kInfinity && minimization_dual_value < 0.0) {
535 error =
std::max(error, -minimization_dual_value);
536 minimization_dual_value = 0.0;
538 dual_values_[
row] = optimization_sign * minimization_dual_value;
540 const bool log_info = parameters_.log_search_progress() ||
VLOG_IS_ON(1);
541 if (log_info)
LOG(
INFO) <<
"Max. dual values move = " << error;
544void LPSolver::ResizeSolution(RowIndex num_rows, ColIndex num_cols) {
545 primal_values_.
resize(num_cols, 0.0);
546 reduced_costs_.
resize(num_cols, 0.0);
549 dual_values_.resize(num_rows, 0.0);
550 constraint_activities_.
resize(num_rows, 0.0);
554void LPSolver::RunRevisedSimplexIfNeeded(ProblemSolution* solution,
560 if (revised_simplex_ ==
nullptr) {
561 revised_simplex_ = absl::make_unique<RevisedSimplex>();
563 revised_simplex_->SetParameters(parameters_);
564 if (revised_simplex_->Solve(current_linear_program_,
time_limit).ok()) {
565 num_revised_simplex_iterations_ = revised_simplex_->GetNumberOfIterations();
566 solution->status = revised_simplex_->GetProblemStatus();
568 const ColIndex num_cols = revised_simplex_->GetProblemNumCols();
569 DCHECK_EQ(solution->primal_values.size(), num_cols);
570 for (ColIndex
col(0);
col < num_cols; ++
col) {
571 solution->primal_values[
col] = revised_simplex_->GetVariableValue(
col);
572 solution->variable_statuses[
col] =
573 revised_simplex_->GetVariableStatus(
col);
576 const RowIndex num_rows = revised_simplex_->GetProblemNumRows();
577 DCHECK_EQ(solution->dual_values.size(), num_rows);
578 for (RowIndex
row(0);
row < num_rows; ++
row) {
579 solution->dual_values[
row] = revised_simplex_->GetDualValue(
row);
580 solution->constraint_statuses[
row] =
581 revised_simplex_->GetConstraintStatus(
row);
584 const bool log_info = parameters_.log_search_progress() ||
VLOG_IS_ON(1);
585 if (log_info)
LOG(
INFO) <<
"Error during the revised simplex algorithm.";
595 VLOG(1) <<
"Variable " <<
col <<
" status is "
597 <<
" and its bounds are [" << lb <<
", " << ub <<
"].";
602 VLOG(1) <<
"Constraint " <<
row <<
" status is "
604 <<
", " << ub <<
"].";
609bool LPSolver::IsProblemSolutionConsistent(
610 const LinearProgram& lp,
const ProblemSolution& solution)
const {
611 const RowIndex num_rows = lp.num_constraints();
612 const ColIndex num_cols = lp.num_variables();
613 if (solution.variable_statuses.size() != num_cols)
return false;
614 if (solution.constraint_statuses.size() != num_rows)
return false;
615 if (solution.primal_values.size() != num_cols)
return false;
616 if (solution.dual_values.size() != num_rows)
return false;
625 RowIndex num_basic_variables(0);
626 for (ColIndex
col(0);
col < num_cols; ++
col) {
631 switch (solution.variable_statuses[
col]) {
635 ++num_basic_variables;
648 LogVariableStatusError(
col,
value, status, lb, ub);
653 if (
value != lb || lb == ub) {
654 LogVariableStatusError(
col,
value, status, lb, ub);
662 LogVariableStatusError(
col,
value, status, lb, ub);
668 LogVariableStatusError(
col,
value, status, lb, ub);
674 for (RowIndex
row(0);
row < num_rows; ++
row) {
685 if (dual_value != 0.0) {
686 VLOG(1) <<
"Constraint " <<
row <<
" is BASIC, but its dual value is "
687 << dual_value <<
" instead of 0.";
690 ++num_basic_variables;
696 if (ub - lb > 1e-12) {
697 LogConstraintStatusError(
row, status, lb, ub);
703 LogConstraintStatusError(
row, status, lb, ub);
709 LogConstraintStatusError(
row, status, lb, ub);
714 if (dual_value != 0.0) {
715 VLOG(1) <<
"Constraint " <<
row <<
" is FREE, but its dual value is "
716 << dual_value <<
" instead of 0.";
720 LogConstraintStatusError(
row, status, lb, ub);
729 if (num_basic_variables != num_rows) {
730 VLOG(1) <<
"Wrong number of basic variables: " << num_basic_variables;
740Fractional LPSolver::ComputeMaxCostPerturbationToEnforceOptimality(
741 const LinearProgram& lp,
bool* is_too_large) {
743 const ColIndex num_cols = lp.num_variables();
744 const Fractional optimization_sign = lp.IsMaximizationProblem() ? -1.0 : 1.0;
745 const Fractional tolerance = parameters_.solution_feasibility_tolerance();
746 for (ColIndex
col(0);
col < num_cols; ++
col) {
750 const Fractional reduced_cost = optimization_sign * reduced_costs_[
col];
755 max_cost_correction =
756 std::max(max_cost_correction, std::abs(reduced_cost));
758 std::abs(reduced_cost) >
759 AllowedError(tolerance, lp.objective_coefficients()[
col]);
762 const bool log_info = parameters_.log_search_progress() ||
VLOG_IS_ON(1);
763 if (log_info)
LOG(
INFO) <<
"Max. cost perturbation = " << max_cost_correction;
764 return max_cost_correction;
769Fractional LPSolver::ComputeMaxRhsPerturbationToEnforceOptimality(
770 const LinearProgram& lp,
bool* is_too_large) {
772 const RowIndex num_rows = lp.num_constraints();
773 const Fractional tolerance = parameters_.solution_feasibility_tolerance();
774 for (RowIndex
row(0);
row < num_rows; ++
row) {
775 const Fractional lower_bound = lp.constraint_lower_bounds()[
row];
776 const Fractional upper_bound = lp.constraint_upper_bounds()[
row];
783 rhs_error = std::abs(activity - lower_bound);
784 allowed_error = AllowedError(tolerance, lower_bound);
786 activity > upper_bound) {
787 rhs_error = std::abs(activity - upper_bound);
788 allowed_error = AllowedError(tolerance, upper_bound);
790 max_rhs_correction =
std::max(max_rhs_correction, rhs_error);
791 *is_too_large |= rhs_error > allowed_error;
793 const bool log_info = parameters_.log_search_progress() ||
VLOG_IS_ON(1);
794 if (log_info)
LOG(
INFO) <<
"Max. rhs perturbation = " << max_rhs_correction;
795 return max_rhs_correction;
798void LPSolver::ComputeConstraintActivities(
const LinearProgram& lp) {
799 const RowIndex num_rows = lp.num_constraints();
800 const ColIndex num_cols = lp.num_variables();
802 constraint_activities_.
assign(num_rows, 0.0);
803 for (ColIndex
col(0);
col < num_cols; ++
col) {
804 lp.GetSparseColumn(
col).AddMultipleToDenseVector(primal_values_[
col],
805 &constraint_activities_);
809void LPSolver::ComputeReducedCosts(
const LinearProgram& lp) {
810 const RowIndex num_rows = lp.num_constraints();
811 const ColIndex num_cols = lp.num_variables();
812 DCHECK_EQ(num_rows, dual_values_.size());
813 reduced_costs_.resize(num_cols, 0.0);
814 for (ColIndex
col(0);
col < num_cols; ++
col) {
815 reduced_costs_[
col] = lp.objective_coefficients()[
col] -
820double LPSolver::ComputeObjective(
const LinearProgram& lp) {
821 const ColIndex num_cols = lp.num_variables();
824 for (ColIndex
col(0);
col < num_cols; ++
col) {
825 sum.
Add(lp.objective_coefficients()[
col] * primal_values_[
col]);
846double LPSolver::ComputeDualObjective(
const LinearProgram& lp) {
850 const RowIndex num_rows = lp.num_constraints();
851 const Fractional optimization_sign = lp.IsMaximizationProblem() ? -1.0 : 1.0;
852 for (RowIndex
row(0);
row < num_rows; ++
row) {
853 const Fractional lower_bound = lp.constraint_lower_bounds()[
row];
854 const Fractional upper_bound = lp.constraint_upper_bounds()[
row];
857 const Fractional corrected_value = optimization_sign * dual_values_[
row];
858 if (corrected_value > 0.0 && lower_bound != -
kInfinity) {
859 dual_objective.Add(dual_values_[
row] * lower_bound);
861 if (corrected_value < 0.0 && upper_bound !=
kInfinity) {
862 dual_objective.Add(dual_values_[
row] * upper_bound);
882 const ColIndex num_cols = lp.num_variables();
883 for (ColIndex
col(0);
col < num_cols; ++
col) {
884 const Fractional lower_bound = lp.variable_lower_bounds()[
col];
885 const Fractional upper_bound = lp.variable_upper_bounds()[
col];
889 const Fractional reduced_cost = optimization_sign * reduced_costs_[
col];
895 reduced_cost > 0.0) {
896 correction = reduced_cost * lower_bound;
898 reduced_cost < 0.0) {
899 correction = reduced_cost * upper_bound;
901 correction = reduced_cost * upper_bound;
904 dual_objective.Add(optimization_sign * correction);
906 return dual_objective.Value();
909double LPSolver::ComputeMaxExpectedObjectiveError(
const LinearProgram& lp) {
910 const ColIndex num_cols = lp.num_variables();
912 const Fractional tolerance = parameters_.solution_feasibility_tolerance();
914 for (ColIndex
col(0);
col < num_cols; ++
col) {
918 primal_objective_error += std::abs(lp.objective_coefficients()[
col]) *
919 AllowedError(tolerance, primal_values_[
col]);
921 return primal_objective_error;
924double LPSolver::ComputePrimalValueInfeasibility(
const LinearProgram& lp,
925 bool* is_too_large) {
926 double infeasibility = 0.0;
927 const Fractional tolerance = parameters_.solution_feasibility_tolerance();
928 const ColIndex num_cols = lp.num_variables();
929 for (ColIndex
col(0);
col < num_cols; ++
col) {
930 const Fractional lower_bound = lp.variable_lower_bounds()[
col];
931 const Fractional upper_bound = lp.variable_upper_bounds()[
col];
934 if (lower_bound == upper_bound) {
935 const Fractional error = std::abs(primal_values_[
col] - upper_bound);
936 infeasibility =
std::max(infeasibility, error);
937 *is_too_large |= error > AllowedError(tolerance, upper_bound);
940 if (primal_values_[
col] > upper_bound) {
942 infeasibility =
std::max(infeasibility, error);
943 *is_too_large |= error > AllowedError(tolerance, upper_bound);
945 if (primal_values_[
col] < lower_bound) {
947 infeasibility =
std::max(infeasibility, error);
948 *is_too_large |= error > AllowedError(tolerance, lower_bound);
951 return infeasibility;
954double LPSolver::ComputeActivityInfeasibility(
const LinearProgram& lp,
955 bool* is_too_large) {
956 double infeasibility = 0.0;
957 int num_problematic_rows(0);
958 const RowIndex num_rows = lp.num_constraints();
959 const Fractional tolerance = parameters_.solution_feasibility_tolerance();
960 for (RowIndex
row(0);
row < num_rows; ++
row) {
962 const Fractional lower_bound = lp.constraint_lower_bounds()[
row];
963 const Fractional upper_bound = lp.constraint_upper_bounds()[
row];
966 if (lower_bound == upper_bound) {
967 if (std::abs(activity - upper_bound) >
968 AllowedError(tolerance, upper_bound)) {
969 VLOG(2) <<
"Row " <<
row.value() <<
" has activity " << activity
970 <<
" which is different from " << upper_bound <<
" by "
971 << activity - upper_bound;
972 ++num_problematic_rows;
974 infeasibility =
std::max(infeasibility, std::abs(activity - upper_bound));
977 if (activity > upper_bound) {
978 const Fractional row_excess = activity - upper_bound;
979 if (row_excess > AllowedError(tolerance, upper_bound)) {
980 VLOG(2) <<
"Row " <<
row.value() <<
" has activity " << activity
981 <<
", exceeding its upper bound " << upper_bound <<
" by "
983 ++num_problematic_rows;
985 infeasibility =
std::max(infeasibility, row_excess);
987 if (activity < lower_bound) {
988 const Fractional row_deficit = lower_bound - activity;
989 if (row_deficit > AllowedError(tolerance, lower_bound)) {
990 VLOG(2) <<
"Row " <<
row.value() <<
" has activity " << activity
991 <<
", below its lower bound " << lower_bound <<
" by "
993 ++num_problematic_rows;
995 infeasibility =
std::max(infeasibility, row_deficit);
998 if (num_problematic_rows > 0) {
999 *is_too_large =
true;
1000 VLOG(1) <<
"Number of infeasible rows = " << num_problematic_rows;
1002 return infeasibility;
1005double LPSolver::ComputeDualValueInfeasibility(
const LinearProgram& lp,
1006 bool* is_too_large) {
1007 const Fractional allowed_error = parameters_.solution_feasibility_tolerance();
1008 const Fractional optimization_sign = lp.IsMaximizationProblem() ? -1.0 : 1.0;
1009 double infeasibility = 0.0;
1010 const RowIndex num_rows = lp.num_constraints();
1011 for (RowIndex
row(0);
row < num_rows; ++
row) {
1013 const Fractional lower_bound = lp.constraint_lower_bounds()[
row];
1014 const Fractional upper_bound = lp.constraint_upper_bounds()[
row];
1016 const Fractional minimization_dual_value = optimization_sign * dual_value;
1018 *is_too_large |= minimization_dual_value > allowed_error;
1019 infeasibility =
std::max(infeasibility, minimization_dual_value);
1022 *is_too_large |= -minimization_dual_value > allowed_error;
1023 infeasibility =
std::max(infeasibility, -minimization_dual_value);
1026 return infeasibility;
1029double LPSolver::ComputeReducedCostInfeasibility(
const LinearProgram& lp,
1030 bool* is_too_large) {
1031 const Fractional optimization_sign = lp.IsMaximizationProblem() ? -1.0 : 1.0;
1032 double infeasibility = 0.0;
1033 const ColIndex num_cols = lp.num_variables();
1034 const Fractional tolerance = parameters_.solution_feasibility_tolerance();
1035 for (ColIndex
col(0);
col < num_cols; ++
col) {
1037 const Fractional lower_bound = lp.variable_lower_bounds()[
col];
1038 const Fractional upper_bound = lp.variable_upper_bounds()[
col];
1041 optimization_sign * reduced_cost;
1043 AllowedError(tolerance, lp.objective_coefficients()[
col]);
1045 *is_too_large |= minimization_reduced_cost > allowed_error;
1046 infeasibility =
std::max(infeasibility, minimization_reduced_cost);
1049 *is_too_large |= -minimization_reduced_cost > allowed_error;
1050 infeasibility =
std::max(infeasibility, -minimization_reduced_cost);
1053 return infeasibility;
#define DCHECK_LE(val1, val2)
#define DCHECK(condition)
#define DCHECK_EQ(val1, val2)
#define VLOG(verboselevel)
void push_back(const value_type &x)
void Add(const FpNumber &value)
void EnableExceptions(int excepts)
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
static std::unique_ptr< TimeLimit > FromParameters(const Parameters ¶meters)
Creates a time limit object initialized from an object that provides methods max_time_in_seconds() an...
const GlopParameters & GetParameters() const
void SetInitialBasis(const VariableStatusRow &variable_statuses, const ConstraintStatusColumn &constraint_statuses)
bool MayHaveMultipleOptimalSolutions() const
const VariableStatusRow & variable_statuses() const
GlopParameters * GetMutableParameters()
Fractional GetMaximumDualInfeasibility() const
const ConstraintStatusColumn & constraint_statuses() const
Fractional GetMaximumPrimalInfeasibility() const
Fractional GetObjectiveValue() const
ProblemStatus LoadAndVerifySolution(const LinearProgram &lp, const ProblemSolution &solution)
ABSL_MUST_USE_RESULT ProblemStatus Solve(const LinearProgram &lp)
ABSL_MUST_USE_RESULT ProblemStatus SolveWithTimeLimit(const LinearProgram &lp, TimeLimit *time_limit)
void SetParameters(const GlopParameters ¶meters)
double DeterministicTime() const
int GetNumberOfSimplexIterations() const
std::string GetObjectiveStatsString() const
void PopulateFromLinearProgram(const LinearProgram &linear_program)
void ClearTransposeMatrix()
std::string GetBoundsStatsString() const
const DenseColumn & constraint_lower_bounds() const
const DenseRow & variable_upper_bounds() const
Fractional objective_offset() const
const DenseColumn & constraint_upper_bounds() const
ColIndex num_variables() const
const DenseRow & variable_lower_bounds() const
std::string GetDimensionString() const
Fractional objective_scaling_factor() const
RowIndex num_constraints() const
void RecoverSolution(ProblemSolution *solution) const override
bool Run(LinearProgram *lp) final
ProblemStatus status() const
void SetTimeLimit(TimeLimit *time_limit)
void resize(IntType size)
void assign(IntType size, const T &v)
SharedTimeLimit * time_limit
ABSL_FLAG(bool, lp_solver_enable_fp_exceptions, false, "When true, NaNs and division / zero produce errors. " "This is very useful for debugging, but incompatible with LLVM. " "It is recommended to set this to false for production usage.")
bool IsFinite(Fractional value)
AccurateSum< Fractional > KahanSum
Fractional ScalarProduct(const DenseRowOrColumn1 &u, const DenseRowOrColumn2 &v)
std::string GetConstraintStatusString(ConstraintStatus status)
void LinearProgramToMPModelProto(const LinearProgram &input, MPModelProto *output)
std::string GetVariableStatusString(VariableStatus status)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
bool AreWithinAbsoluteTolerance(FloatType x, FloatType y, FloatType absolute_tolerance)
bool WriteProtoToFile(absl::string_view filename, const google::protobuf::Message &proto, ProtoWriteFormat proto_write_format, bool gzipped, bool append_extension_to_file_name)
VariableStatusRow statuses
VariableStatusRow variable_statuses
ConstraintStatusColumn constraint_statuses
#define VLOG_IS_ON(verboselevel)