OR-Tools  8.2
lp_solver.cc
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
15
16#include <cmath>
17#include <stack>
18#include <vector>
19
20#include "absl/memory/memory.h"
21#include "absl/strings/match.h"
22#include "absl/strings/str_format.h"
25#include "ortools/base/timer.h"
27#include "ortools/glop/status.h"
32
33// TODO(user): abstract this in some way to the port directory.
34#ifndef __PORTABLE_PLATFORM__
36#endif
37
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.");
42ABSL_FLAG(bool, lp_dump_to_proto_file, false,
43 "Tells whether do dump the problem to a protobuf file.");
44ABSL_FLAG(bool, lp_dump_compressed_file, true,
45 "Whether the proto dump file is compressed.");
46ABSL_FLAG(bool, lp_dump_binary_file, false,
47 "Whether the proto dump file is binary.");
48ABSL_FLAG(int, lp_dump_file_number, -1,
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().");
52ABSL_FLAG(std::string, lp_dump_dir, "/tmp",
53 "Directory where dump files are written.");
54ABSL_FLAG(std::string, lp_dump_file_basename, "",
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.");
58
59namespace operations_research {
60namespace glop {
61namespace {
62
63// Writes a LinearProgram to a file if FLAGS_lp_dump_to_proto_file is true. The
64// integer num is appended to the base name of the file. When this function is
65// called from LPSolver::Solve(), num is usually the number of times Solve() was
66// called. For a LinearProgram whose name is "LinPro", and num = 48, the default
67// output file will be /tmp/LinPro-000048.pb.gz.
68//
69// Warning: is a no-op on portable platforms (android, ios, etc).
70void DumpLinearProgramIfRequiredByFlags(const LinearProgram& linear_program,
71 int num) {
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.";
78#else
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";
83 } else {
84 filename = linear_program.name();
85 }
86 }
87 const int file_num = absl::GetFlag(FLAGS_lp_dump_file_number) >= 0
88 ? absl::GetFlag(FLAGS_lp_dump_file_number)
89 : num;
90 absl::StrAppendFormat(&filename, "-%06d.pb", file_num);
91 const std::string filespec =
92 absl::StrCat(absl::GetFlag(FLAGS_lp_dump_dir), "/", filename);
93 MPModelProto proto;
94 LinearProgramToMPModelProto(linear_program, &proto);
95 const ProtoWriteFormat write_format = absl::GetFlag(FLAGS_lp_dump_binary_file)
98 if (!WriteProtoToFile(filespec, proto, write_format,
99 absl::GetFlag(FLAGS_lp_dump_compressed_file))) {
100 LOG(DFATAL) << "Could not write " << filespec;
101 }
102#endif
103}
104
105} // anonymous namespace
106
107// --------------------------------------------------------
108// LPSolver
109// --------------------------------------------------------
110
111LPSolver::LPSolver() : num_solves_(0) {}
112
113void LPSolver::SetParameters(const GlopParameters& parameters) {
114 parameters_ = parameters;
115}
116
117const GlopParameters& LPSolver::GetParameters() const { return parameters_; }
118
119GlopParameters* LPSolver::GetMutableParameters() { return &parameters_; }
120
122 std::unique_ptr<TimeLimit> time_limit =
123 TimeLimit::FromParameters(parameters_);
124 return SolveWithTimeLimit(lp, time_limit.get());
125}
126
129 if (time_limit == nullptr) {
130 LOG(DFATAL) << "SolveWithTimeLimit() called with a nullptr time_limit.";
132 }
133 ++num_solves_;
134 num_revised_simplex_iterations_ = 0;
135 DumpLinearProgramIfRequiredByFlags(lp, num_solves_);
136 // Check some preconditions.
137 if (!lp.IsCleanedUp()) {
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().";
141 ResizeSolution(lp.num_constraints(), lp.num_variables());
143 }
144 if (!lp.IsValid()) {
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.";
148 ResizeSolution(lp.num_constraints(), lp.num_variables());
150 }
151 // Display a warning if running in non-opt, unless we're inside a unit test.
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******************************************************************";
159
160 // Note that we only activate the floating-point exceptions after we are sure
161 // that the program is valid. This way, if we have input NaNs, we will not
162 // crash.
163 ScopedFloatingPointEnv scoped_fenv;
164 if (absl::GetFlag(FLAGS_lp_solver_enable_fp_exceptions)) {
165#ifdef _MSC_VER
166 scoped_fenv.EnableExceptions(_EM_INVALID | EM_ZERODIVIDE);
167#else
168 scoped_fenv.EnableExceptions(FE_DIVBYZERO | FE_INVALID);
169#endif
170 }
171
172 // Make an internal copy of the problem for the preprocessing.
173 const bool log_info = parameters_.log_search_progress() || VLOG_IS_ON(1);
174 if (log_info) {
175 LOG(INFO) << "Initial problem: " << lp.GetDimensionString();
176 LOG(INFO) << "Objective stats: " << lp.GetObjectiveStatsString();
177 LOG(INFO) << "Bounds stats: " << lp.GetBoundsStatsString();
178 }
179 current_linear_program_.PopulateFromLinearProgram(lp);
180
181 // Preprocess.
182 MainLpPreprocessor preprocessor(&parameters_);
183 preprocessor.SetTimeLimit(time_limit);
184
185 const bool postsolve_is_needed = preprocessor.Run(&current_linear_program_);
186
187 if (log_info) {
188 LOG(INFO) << "Presolved problem: "
189 << current_linear_program_.GetDimensionString();
190 LOG(INFO) << "Objective stats: "
191 << current_linear_program_.GetObjectiveStatsString();
192 LOG(INFO) << "Bounds stats: "
193 << current_linear_program_.GetBoundsStatsString();
194 }
195
196 // At this point, we need to initialize a ProblemSolution with the correct
197 // size and status.
198 ProblemSolution solution(current_linear_program_.num_constraints(),
199 current_linear_program_.num_variables());
200 solution.status = preprocessor.status();
201
202 // Do not launch the solver if the time limit was already reached. This might
203 // mean that the pre-processors were not all run, and current_linear_program_
204 // might not be in a completely safe state.
205 if (!time_limit->LimitReached()) {
206 RunRevisedSimplexIfNeeded(&solution, time_limit);
207 }
208
209 if (postsolve_is_needed) preprocessor.RecoverSolution(&solution);
210 const ProblemStatus status = LoadAndVerifySolution(lp, solution);
211
212 // LOG some statistics that can be parsed by our benchmark script.
213 if (log_info) {
214 LOG(INFO) << "status: " << status;
215 LOG(INFO) << "objective: " << GetObjectiveValue();
216 LOG(INFO) << "iterations: " << GetNumberOfSimplexIterations();
217 LOG(INFO) << "time: " << time_limit->GetElapsedTime();
218 LOG(INFO) << "deterministic_time: "
219 << time_limit->GetElapsedDeterministicTime();
220 }
221
222 return status;
223}
224
226 ResizeSolution(RowIndex(0), ColIndex(0));
227 revised_simplex_.reset(nullptr);
228}
229
231 const VariableStatusRow& variable_statuses,
232 const ConstraintStatusColumn& constraint_statuses) {
233 // Create the associated basis state.
234 BasisState state;
236 for (const ConstraintStatus status : constraint_statuses) {
237 // Note the change of upper/lower bound between the status of a constraint
238 // and the status of its associated slack variable.
239 switch (status) {
242 break;
245 break;
248 break;
251 break;
254 break;
255 }
256 }
257 if (revised_simplex_ == nullptr) {
258 revised_simplex_ = absl::make_unique<RevisedSimplex>();
259 }
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 "
264 "what you want.";
265 }
266}
267
268namespace {
269// Computes the "real" problem objective from the one without offset nor
270// scaling.
271Fractional ProblemObjectiveValue(const LinearProgram& lp, Fractional value) {
272 return lp.objective_scaling_factor() * (value + lp.objective_offset());
273}
274
275// Returns the allowed error magnitude for something that should evaluate to
276// value under the given tolerance.
277Fractional AllowedError(Fractional tolerance, Fractional value) {
278 return tolerance * std::max(1.0, std::abs(value));
279}
280} // namespace
281
282// TODO(user): Try to also check the precision of an INFEASIBLE or UNBOUNDED
283// return status.
285 const ProblemSolution& solution) {
286 const bool log_info = parameters_.log_search_progress() || VLOG_IS_ON(1);
287
288 if (!IsProblemSolutionConsistent(lp, solution)) {
289 if (log_info) LOG(INFO) << "Inconsistency detected in the solution.";
290 ResizeSolution(lp.num_constraints(), lp.num_variables());
292 }
293
294 // Load the solution.
295 primal_values_ = solution.primal_values;
296 dual_values_ = solution.dual_values;
297 variable_statuses_ = solution.variable_statuses;
298 constraint_statuses_ = solution.constraint_statuses;
299 ProblemStatus status = solution.status;
300
301 // Objective before eventually moving the primal/dual values inside their
302 // bounds.
303 ComputeReducedCosts(lp);
304 const Fractional primal_objective_value = ComputeObjective(lp);
305 const Fractional dual_objective_value = ComputeDualObjective(lp);
306 if (log_info) {
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) = "
311 << absl::StrFormat(
312 "%.15E", ProblemObjectiveValue(lp, dual_objective_value));
313 }
314
315 // Eventually move the primal/dual values inside their bounds.
316 if (status == ProblemStatus::OPTIMAL &&
317 parameters_.provide_strong_optimal_guarantee()) {
318 MovePrimalValuesWithinBounds(lp);
319 MoveDualValuesWithinBounds(lp);
320 }
321
322 // The reported objective to the user.
323 problem_objective_value_ = ProblemObjectiveValue(lp, ComputeObjective(lp));
324 if (log_info) {
325 LOG(INFO) << "Primal objective (after moving primal/dual values) = "
326 << absl::StrFormat("%.15E", problem_objective_value_);
327 }
328
329 ComputeReducedCosts(lp);
330 ComputeConstraintActivities(lp);
331
332 // These will be set to true if the associated "infeasibility" is too large.
333 //
334 // The tolerance used is the parameter solution_feasibility_tolerance. To be
335 // somewhat independent of the original problem scaling, the thresholds used
336 // depend of the quantity involved and of its coordinates:
337 // - tolerance * max(1.0, abs(cost[col])) when a reduced cost is infeasible.
338 // - tolerance * max(1.0, abs(bound)) when a bound is crossed.
339 // - tolerance for an infeasible dual value (because the limit is always 0.0).
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;
346
347 // Computes all the infeasiblities and update the Booleans above.
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);
360
361 // TODO(user): the name is not really consistent since in practice those are
362 // the "residual" since the primal/dual infeasibility are zero when
363 // parameters_.provide_strong_optimal_guarantee() is true.
364 max_absolute_primal_infeasibility_ =
365 std::max(primal_infeasibility, primal_residual);
366 max_absolute_dual_infeasibility_ =
367 std::max(dual_infeasibility, dual_residual);
368 if (log_info) {
369 LOG(INFO) << "Max. primal infeasibility = "
370 << max_absolute_primal_infeasibility_;
371 LOG(INFO) << "Max. dual infeasibility = "
372 << max_absolute_dual_infeasibility_;
373 }
374
375 // Now that all the relevant quantities are computed, we check the precision
376 // and optimality of the result. See Chvatal pp. 61-62. If any of the tests
377 // fail, we return the IMPRECISE status.
378 const double objective_error_ub = ComputeMaxExpectedObjectiveError(lp);
379 if (log_info) {
380 LOG(INFO) << "Objective error <= " << objective_error_ub;
381 }
382
383 if (status == ProblemStatus::OPTIMAL &&
384 parameters_.provide_strong_optimal_guarantee()) {
385 // If the primal/dual values were moved to the bounds, then the primal/dual
386 // infeasibilities should be exactly zero (but not the residuals).
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().";
394 }
395 if (rhs_perturbation_is_too_large) {
396 if (log_info) LOG(INFO) << "The needed rhs perturbation is too large !!";
398 }
399 if (cost_perturbation_is_too_large) {
400 if (log_info) LOG(INFO) << "The needed cost perturbation is too large !!";
402 }
403 }
404
405 // Note that we compare the values without offset nor scaling. We also need to
406 // compare them before we move the primal/dual values, otherwise we lose some
407 // precision since the values are modified independently of each other.
408 if (status == ProblemStatus::OPTIMAL) {
409 if (std::abs(primal_objective_value - dual_objective_value) >
410 objective_error_ub) {
411 if (log_info) {
412 LOG(INFO) << "The objective gap of the final solution is too large.";
413 }
415 }
416 }
417 if ((status == ProblemStatus::OPTIMAL ||
419 (primal_residual_is_too_large || primal_infeasibility_is_too_large)) {
420 if (log_info) {
421 LOG(INFO)
422 << "The primal infeasibility of the final solution is too large.";
423 }
425 }
426 if ((status == ProblemStatus::OPTIMAL ||
427 status == ProblemStatus::DUAL_FEASIBLE) &&
428 (dual_residual_is_too_large || dual_infeasibility_is_too_large)) {
429 if (log_info) {
430 LOG(INFO) << "The dual infeasibility of the final solution is too large.";
431 }
433 }
434
435 may_have_multiple_solutions_ =
436 (status == ProblemStatus::OPTIMAL) ? IsOptimalSolutionOnFacet(lp) : false;
437 return status;
438}
439
440bool LPSolver::IsOptimalSolutionOnFacet(const LinearProgram& lp) {
441 // Note(user): We use the following same two tolerances for the dual and
442 // primal values.
443 // TODO(user): investigate whether to use the tolerances defined in
444 // parameters.proto.
445 const double kReducedCostTolerance = 1e-9;
446 const double kBoundTolerance = 1e-7;
447 const ColIndex num_cols = lp.num_variables();
448 for (ColIndex col(0); col < num_cols; ++col) {
449 if (variable_statuses_[col] == VariableStatus::FIXED_VALUE) continue;
450 const Fractional lower_bound = lp.variable_lower_bounds()[col];
451 const Fractional upper_bound = lp.variable_upper_bounds()[col];
452 const Fractional value = primal_values_[col];
453 if (AreWithinAbsoluteTolerance(reduced_costs_[col], 0.0,
454 kReducedCostTolerance) &&
455 (AreWithinAbsoluteTolerance(value, lower_bound, kBoundTolerance) ||
456 AreWithinAbsoluteTolerance(value, upper_bound, kBoundTolerance))) {
457 return true;
458 }
459 }
460 const RowIndex num_rows = lp.num_constraints();
461 for (RowIndex row(0); row < num_rows; ++row) {
462 if (constraint_statuses_[row] == ConstraintStatus::FIXED_VALUE) continue;
463 const Fractional lower_bound = lp.constraint_lower_bounds()[row];
464 const Fractional upper_bound = lp.constraint_upper_bounds()[row];
465 const Fractional activity = constraint_activities_[row];
466 if (AreWithinAbsoluteTolerance(dual_values_[row], 0.0,
467 kReducedCostTolerance) &&
468 (AreWithinAbsoluteTolerance(activity, lower_bound, kBoundTolerance) ||
469 AreWithinAbsoluteTolerance(activity, upper_bound, kBoundTolerance))) {
470 return true;
471 }
472 }
473 return false;
474}
475
477 return problem_objective_value_;
478}
479
481 return max_absolute_primal_infeasibility_;
482}
483
485 return max_absolute_dual_infeasibility_;
486}
487
489 return may_have_multiple_solutions_;
490}
491
493 return num_revised_simplex_iterations_;
494}
495
497 return revised_simplex_ == nullptr ? 0.0
498 : revised_simplex_->DeterministicTime();
499}
500
501void LPSolver::MovePrimalValuesWithinBounds(const LinearProgram& lp) {
502 const ColIndex num_cols = lp.num_variables();
503 DCHECK_EQ(num_cols, primal_values_.size());
504 Fractional error = 0.0;
505 for (ColIndex col(0); col < num_cols; ++col) {
506 const Fractional lower_bound = lp.variable_lower_bounds()[col];
507 const Fractional upper_bound = lp.variable_upper_bounds()[col];
508 DCHECK_LE(lower_bound, upper_bound);
509
510 error = std::max(error, primal_values_[col] - upper_bound);
511 error = std::max(error, lower_bound - primal_values_[col]);
512 primal_values_[col] = std::min(primal_values_[col], upper_bound);
513 primal_values_[col] = std::max(primal_values_[col], lower_bound);
514 }
515 const bool log_info = parameters_.log_search_progress() || VLOG_IS_ON(1);
516 if (log_info) LOG(INFO) << "Max. primal values move = " << error;
517}
518
519void LPSolver::MoveDualValuesWithinBounds(const LinearProgram& lp) {
520 const RowIndex num_rows = lp.num_constraints();
521 DCHECK_EQ(num_rows, dual_values_.size());
522 const Fractional optimization_sign = lp.IsMaximizationProblem() ? -1.0 : 1.0;
523 Fractional error = 0.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];
527
528 // For a minimization problem, we want a lower bound.
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;
533 }
534 if (upper_bound == kInfinity && minimization_dual_value < 0.0) {
535 error = std::max(error, -minimization_dual_value);
536 minimization_dual_value = 0.0;
537 }
538 dual_values_[row] = optimization_sign * minimization_dual_value;
539 }
540 const bool log_info = parameters_.log_search_progress() || VLOG_IS_ON(1);
541 if (log_info) LOG(INFO) << "Max. dual values move = " << error;
542}
543
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);
547 variable_statuses_.resize(num_cols, VariableStatus::FREE);
548
549 dual_values_.resize(num_rows, 0.0);
550 constraint_activities_.resize(num_rows, 0.0);
551 constraint_statuses_.resize(num_rows, ConstraintStatus::FREE);
552}
553
554void LPSolver::RunRevisedSimplexIfNeeded(ProblemSolution* solution,
555 TimeLimit* time_limit) {
556 // Note that the transpose matrix is no longer needed at this point.
557 // This helps reduce the peak memory usage of the solver.
558 current_linear_program_.ClearTransposeMatrix();
559 if (solution->status != ProblemStatus::INIT) return;
560 if (revised_simplex_ == nullptr) {
561 revised_simplex_ = absl::make_unique<RevisedSimplex>();
562 }
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();
567
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);
574 }
575
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);
582 }
583 } else {
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.";
586 solution->status = ProblemStatus::ABNORMAL;
587 }
588}
589
590namespace {
591
592void LogVariableStatusError(ColIndex col, Fractional value,
593 VariableStatus status, Fractional lb,
594 Fractional ub) {
595 VLOG(1) << "Variable " << col << " status is "
596 << GetVariableStatusString(status) << " but its value is " << value
597 << " and its bounds are [" << lb << ", " << ub << "].";
598}
599
600void LogConstraintStatusError(RowIndex row, ConstraintStatus status,
601 Fractional lb, Fractional ub) {
602 VLOG(1) << "Constraint " << row << " status is "
603 << GetConstraintStatusString(status) << " but its bounds are [" << lb
604 << ", " << ub << "].";
605}
606
607} // namespace
608
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;
617 if (solution.status != ProblemStatus::OPTIMAL &&
618 solution.status != ProblemStatus::PRIMAL_FEASIBLE &&
619 solution.status != ProblemStatus::DUAL_FEASIBLE) {
620 return true;
621 }
622
623 // This checks that the variable statuses verify the properties described
624 // in the VariableStatus declaration.
625 RowIndex num_basic_variables(0);
626 for (ColIndex col(0); col < num_cols; ++col) {
627 const Fractional value = solution.primal_values[col];
628 const Fractional lb = lp.variable_lower_bounds()[col];
629 const Fractional ub = lp.variable_upper_bounds()[col];
630 const VariableStatus status = solution.variable_statuses[col];
631 switch (solution.variable_statuses[col]) {
633 // TODO(user): Check that the reduced cost of this column is epsilon
634 // close to zero.
635 ++num_basic_variables;
636 break;
638 // TODO(user): Because of scaling, it is possible that a FIXED_VALUE
639 // status (only reserved for the exact lb == ub case) is now set for a
640 // variable where (ub == lb + epsilon). So we do not check here that the
641 // two bounds are exactly equal. The best is probably to remove the
642 // FIXED status from the API completely and report one of AT_LOWER_BOUND
643 // or AT_UPPER_BOUND instead. This also allows to indicate if at
644 // optimality, the objective is limited because of this variable lower
645 // bound or its upper bound. Note that there are other TODOs in the
646 // codebase about removing this FIXED_VALUE status.
647 if (value != ub && value != lb) {
648 LogVariableStatusError(col, value, status, lb, ub);
649 return false;
650 }
651 break;
653 if (value != lb || lb == ub) {
654 LogVariableStatusError(col, value, status, lb, ub);
655 return false;
656 }
657 break;
659 // TODO(user): revert to an exact comparison once the bug causing this
660 // to fail has been fixed.
661 if (!AreWithinAbsoluteTolerance(value, ub, 1e-7) || lb == ub) {
662 LogVariableStatusError(col, value, status, lb, ub);
663 return false;
664 }
665 break;
667 if (lb != -kInfinity || ub != kInfinity || value != 0.0) {
668 LogVariableStatusError(col, value, status, lb, ub);
669 return false;
670 }
671 break;
672 }
673 }
674 for (RowIndex row(0); row < num_rows; ++row) {
675 const Fractional dual_value = solution.dual_values[row];
676 const Fractional lb = lp.constraint_lower_bounds()[row];
677 const Fractional ub = lp.constraint_upper_bounds()[row];
678 const ConstraintStatus status = solution.constraint_statuses[row];
679
680 // The activity value is not checked since it is imprecise.
681 // TODO(user): Check that the activity is epsilon close to the expected
682 // value.
683 switch (status) {
685 if (dual_value != 0.0) {
686 VLOG(1) << "Constraint " << row << " is BASIC, but its dual value is "
687 << dual_value << " instead of 0.";
688 return false;
689 }
690 ++num_basic_variables;
691 break;
693 // Exactly the same remark as for the VariableStatus::FIXED_VALUE case
694 // above. Because of precision error, this can happen when the
695 // difference between the two bounds is small and not just exactly zero.
696 if (ub - lb > 1e-12) {
697 LogConstraintStatusError(row, status, lb, ub);
698 return false;
699 }
700 break;
702 if (lb == -kInfinity) {
703 LogConstraintStatusError(row, status, lb, ub);
704 return false;
705 }
706 break;
708 if (ub == kInfinity) {
709 LogConstraintStatusError(row, status, lb, ub);
710 return false;
711 }
712 break;
714 if (dual_value != 0.0) {
715 VLOG(1) << "Constraint " << row << " is FREE, but its dual value is "
716 << dual_value << " instead of 0.";
717 return false;
718 }
719 if (lb != -kInfinity || ub != kInfinity) {
720 LogConstraintStatusError(row, status, lb, ub);
721 return false;
722 }
723 break;
724 }
725 }
726
727 // TODO(user): We could check in debug mode (because it will be costly) that
728 // the basis is actually factorizable.
729 if (num_basic_variables != num_rows) {
730 VLOG(1) << "Wrong number of basic variables: " << num_basic_variables;
731 return false;
732 }
733 return true;
734}
735
736// This computes by how much the objective must be perturbed to enforce the
737// following complementary slackness conditions:
738// - Reduced cost is exactly zero for FREE and BASIC variables.
739// - Reduced cost is of the correct sign for variables at their bounds.
740Fractional LPSolver::ComputeMaxCostPerturbationToEnforceOptimality(
741 const LinearProgram& lp, bool* is_too_large) {
742 Fractional max_cost_correction = 0.0;
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) {
747 // We correct the reduced cost, so we have a minimization problem and
748 // thus the dual objective value will be a lower bound of the primal
749 // objective.
750 const Fractional reduced_cost = optimization_sign * reduced_costs_[col];
751 const VariableStatus status = variable_statuses_[col];
752 if (status == VariableStatus::BASIC || status == VariableStatus::FREE ||
753 (status == VariableStatus::AT_UPPER_BOUND && reduced_cost > 0.0) ||
754 (status == VariableStatus::AT_LOWER_BOUND && reduced_cost < 0.0)) {
755 max_cost_correction =
756 std::max(max_cost_correction, std::abs(reduced_cost));
757 *is_too_large |=
758 std::abs(reduced_cost) >
759 AllowedError(tolerance, lp.objective_coefficients()[col]);
760 }
761 }
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;
765}
766
767// This computes by how much the rhs must be perturbed to enforce the fact that
768// the constraint activities exactly reflect their status.
769Fractional LPSolver::ComputeMaxRhsPerturbationToEnforceOptimality(
770 const LinearProgram& lp, bool* is_too_large) {
771 Fractional max_rhs_correction = 0.0;
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];
777 const Fractional activity = constraint_activities_[row];
778 const ConstraintStatus status = constraint_statuses_[row];
779
780 Fractional rhs_error = 0.0;
781 Fractional allowed_error = 0.0;
782 if (status == ConstraintStatus::AT_LOWER_BOUND || activity < lower_bound) {
783 rhs_error = std::abs(activity - lower_bound);
784 allowed_error = AllowedError(tolerance, lower_bound);
785 } else if (status == ConstraintStatus::AT_UPPER_BOUND ||
786 activity > upper_bound) {
787 rhs_error = std::abs(activity - upper_bound);
788 allowed_error = AllowedError(tolerance, upper_bound);
789 }
790 max_rhs_correction = std::max(max_rhs_correction, rhs_error);
791 *is_too_large |= rhs_error > allowed_error;
792 }
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;
796}
797
798void LPSolver::ComputeConstraintActivities(const LinearProgram& lp) {
799 const RowIndex num_rows = lp.num_constraints();
800 const ColIndex num_cols = lp.num_variables();
801 DCHECK_EQ(num_cols, primal_values_.size());
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_);
806 }
807}
808
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] -
816 ScalarProduct(dual_values_, lp.GetSparseColumn(col));
817 }
818}
819
820double LPSolver::ComputeObjective(const LinearProgram& lp) {
821 const ColIndex num_cols = lp.num_variables();
822 DCHECK_EQ(num_cols, primal_values_.size());
823 KahanSum sum;
824 for (ColIndex col(0); col < num_cols; ++col) {
825 sum.Add(lp.objective_coefficients()[col] * primal_values_[col]);
826 }
827 return sum.Value();
828}
829
830// By the duality theorem, the dual "objective" is a bound on the primal
831// objective obtained by taking the linear combinaison of the constraints
832// given by dual_values_.
833//
834// As it is written now, this has no real precise meaning since we ignore
835// infeasible reduced costs. This is almost the same as computing the objective
836// to the perturbed problem, but then we don't use the pertubed rhs. It is just
837// here as an extra "consistency" check.
838//
839// Note(user): We could actually compute an EXACT lower bound for the cost of
840// the non-cost perturbed problem. The idea comes from "Safe bounds in linear
841// and mixed-integer linear programming", Arnold Neumaier , Oleg Shcherbina,
842// Math Prog, 2003. Note that this requires having some variable bounds that may
843// not be in the original problem so that the current dual solution is always
844// feasible. It also involves changing the rounding mode to obtain exact
845// confidence intervals on the reduced costs.
846double LPSolver::ComputeDualObjective(const LinearProgram& lp) {
847 KahanSum dual_objective;
848
849 // Compute the part coming from the row constraints.
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];
855
856 // We correct the optimization_sign so we have to compute a lower bound.
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);
860 }
861 if (corrected_value < 0.0 && upper_bound != kInfinity) {
862 dual_objective.Add(dual_values_[row] * upper_bound);
863 }
864 }
865
866 // For a given column associated to a variable x, we want to find a lower
867 // bound for c.x (where c is the objective coefficient for this column). If we
868 // write a.x the linear combination of the constraints at this column we have:
869 // (c + a - c) * x = a * x, and so
870 // c * x = a * x + (c - a) * x
871 // Now, if we suppose for example that the reduced cost 'c - a' is positive
872 // and that x is lower-bounded by 'lb' then the best bound we can get is
873 // c * x >= a * x + (c - a) * lb.
874 //
875 // Note: when summing over all variables, the left side is the primal
876 // objective and the right side is a lower bound to the objective. In
877 // particular, a necessary and sufficient condition for both objectives to be
878 // the same is that all the single variable inequalities above be equalities.
879 // This is possible only if c == a or if x is at its bound (modulo the
880 // optimization_sign of the reduced cost), or both (this is one side of the
881 // complementary slackness conditions, see Chvatal p. 62).
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];
886
887 // Correct the reduced cost, so as to have a minimization problem and
888 // thus a dual objective that is a lower bound of the primal objective.
889 const Fractional reduced_cost = optimization_sign * reduced_costs_[col];
890
891 // We do not do any correction if the reduced cost is 'infeasible', which is
892 // the same as computing the objective of the perturbed problem.
893 Fractional correction = 0.0;
894 if (variable_statuses_[col] == VariableStatus::AT_LOWER_BOUND &&
895 reduced_cost > 0.0) {
896 correction = reduced_cost * lower_bound;
897 } else if (variable_statuses_[col] == VariableStatus::AT_UPPER_BOUND &&
898 reduced_cost < 0.0) {
899 correction = reduced_cost * upper_bound;
900 } else if (variable_statuses_[col] == VariableStatus::FIXED_VALUE) {
901 correction = reduced_cost * upper_bound;
902 }
903 // Now apply the correction in the right direction!
904 dual_objective.Add(optimization_sign * correction);
905 }
906 return dual_objective.Value();
907}
908
909double LPSolver::ComputeMaxExpectedObjectiveError(const LinearProgram& lp) {
910 const ColIndex num_cols = lp.num_variables();
911 DCHECK_EQ(num_cols, primal_values_.size());
912 const Fractional tolerance = parameters_.solution_feasibility_tolerance();
913 Fractional primal_objective_error = 0.0;
914 for (ColIndex col(0); col < num_cols; ++col) {
915 // TODO(user): Be more precise since the non-BASIC variables are exactly at
916 // their bounds, so for them the error bound is just the term magnitude
917 // times std::numeric_limits<double>::epsilon() with KahanSum.
918 primal_objective_error += std::abs(lp.objective_coefficients()[col]) *
919 AllowedError(tolerance, primal_values_[col]);
920 }
921 return primal_objective_error;
922}
923
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];
932 DCHECK(IsFinite(primal_values_[col]));
933
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);
938 continue;
939 }
940 if (primal_values_[col] > upper_bound) {
941 const Fractional error = primal_values_[col] - upper_bound;
942 infeasibility = std::max(infeasibility, error);
943 *is_too_large |= error > AllowedError(tolerance, upper_bound);
944 }
945 if (primal_values_[col] < lower_bound) {
946 const Fractional error = lower_bound - primal_values_[col];
947 infeasibility = std::max(infeasibility, error);
948 *is_too_large |= error > AllowedError(tolerance, lower_bound);
949 }
950 }
951 return infeasibility;
952}
953
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) {
961 const Fractional activity = constraint_activities_[row];
962 const Fractional lower_bound = lp.constraint_lower_bounds()[row];
963 const Fractional upper_bound = lp.constraint_upper_bounds()[row];
964 DCHECK(IsFinite(activity));
965
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;
973 }
974 infeasibility = std::max(infeasibility, std::abs(activity - upper_bound));
975 continue;
976 }
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 "
982 << row_excess;
983 ++num_problematic_rows;
984 }
985 infeasibility = std::max(infeasibility, row_excess);
986 }
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 "
992 << row_deficit;
993 ++num_problematic_rows;
994 }
995 infeasibility = std::max(infeasibility, row_deficit);
996 }
997 }
998 if (num_problematic_rows > 0) {
999 *is_too_large = true;
1000 VLOG(1) << "Number of infeasible rows = " << num_problematic_rows;
1001 }
1002 return infeasibility;
1003}
1004
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) {
1012 const Fractional dual_value = dual_values_[row];
1013 const Fractional lower_bound = lp.constraint_lower_bounds()[row];
1014 const Fractional upper_bound = lp.constraint_upper_bounds()[row];
1015 DCHECK(IsFinite(dual_value));
1016 const Fractional minimization_dual_value = optimization_sign * dual_value;
1017 if (lower_bound == -kInfinity) {
1018 *is_too_large |= minimization_dual_value > allowed_error;
1019 infeasibility = std::max(infeasibility, minimization_dual_value);
1020 }
1021 if (upper_bound == kInfinity) {
1022 *is_too_large |= -minimization_dual_value > allowed_error;
1023 infeasibility = std::max(infeasibility, -minimization_dual_value);
1024 }
1025 }
1026 return infeasibility;
1027}
1028
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) {
1036 const Fractional reduced_cost = reduced_costs_[col];
1037 const Fractional lower_bound = lp.variable_lower_bounds()[col];
1038 const Fractional upper_bound = lp.variable_upper_bounds()[col];
1039 DCHECK(IsFinite(reduced_cost));
1040 const Fractional minimization_reduced_cost =
1041 optimization_sign * reduced_cost;
1042 const Fractional allowed_error =
1043 AllowedError(tolerance, lp.objective_coefficients()[col]);
1044 if (lower_bound == -kInfinity) {
1045 *is_too_large |= minimization_reduced_cost > allowed_error;
1046 infeasibility = std::max(infeasibility, minimization_reduced_cost);
1047 }
1048 if (upper_bound == kInfinity) {
1049 *is_too_large |= -minimization_reduced_cost > allowed_error;
1050 infeasibility = std::max(infeasibility, -minimization_reduced_cost);
1051 }
1052 }
1053 return infeasibility;
1054}
1055
1056} // namespace glop
1057} // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
#define DLOG(severity)
Definition: base/logging.h:875
#define DCHECK_LE(val1, val2)
Definition: base/logging.h:887
#define LOG(severity)
Definition: base/logging.h:420
#define DCHECK(condition)
Definition: base/logging.h:884
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
#define VLOG(verboselevel)
Definition: base/logging.h:978
void push_back(const value_type &x)
void Add(const FpNumber &value)
Definition: accurate_sum.h:29
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
Definition: time_limit.h:105
static std::unique_ptr< TimeLimit > FromParameters(const Parameters &parameters)
Creates a time limit object initialized from an object that provides methods max_time_in_seconds() an...
Definition: time_limit.h:159
const GlopParameters & GetParameters() const
Definition: lp_solver.cc:117
void SetInitialBasis(const VariableStatusRow &variable_statuses, const ConstraintStatusColumn &constraint_statuses)
Definition: lp_solver.cc:230
bool MayHaveMultipleOptimalSolutions() const
Definition: lp_solver.cc:488
const VariableStatusRow & variable_statuses() const
Definition: lp_solver.h:102
GlopParameters * GetMutableParameters()
Definition: lp_solver.cc:119
Fractional GetMaximumDualInfeasibility() const
Definition: lp_solver.cc:484
const ConstraintStatusColumn & constraint_statuses() const
Definition: lp_solver.h:116
Fractional GetMaximumPrimalInfeasibility() const
Definition: lp_solver.cc:480
Fractional GetObjectiveValue() const
Definition: lp_solver.cc:476
ProblemStatus LoadAndVerifySolution(const LinearProgram &lp, const ProblemSolution &solution)
Definition: lp_solver.cc:284
ABSL_MUST_USE_RESULT ProblemStatus Solve(const LinearProgram &lp)
Definition: lp_solver.cc:121
ABSL_MUST_USE_RESULT ProblemStatus SolveWithTimeLimit(const LinearProgram &lp, TimeLimit *time_limit)
Definition: lp_solver.cc:127
void SetParameters(const GlopParameters &parameters)
Definition: lp_solver.cc:113
std::string GetObjectiveStatsString() const
Definition: lp_data.cc:450
void PopulateFromLinearProgram(const LinearProgram &linear_program)
Definition: lp_data.cc:860
std::string GetBoundsStatsString() const
Definition: lp_data.cc:463
const DenseColumn & constraint_lower_bounds() const
Definition: lp_data.h:214
const DenseRow & variable_upper_bounds() const
Definition: lp_data.h:231
const DenseColumn & constraint_upper_bounds() const
Definition: lp_data.h:217
const DenseRow & variable_lower_bounds() const
Definition: lp_data.h:228
std::string GetDimensionString() const
Definition: lp_data.cc:424
Fractional objective_scaling_factor() const
Definition: lp_data.h:260
void RecoverSolution(ProblemSolution *solution) const override
void SetTimeLimit(TimeLimit *time_limit)
Definition: preprocessor.h:75
void assign(IntType size, const T &v)
Definition: lp_types.h:274
SatParameters parameters
CpModelProto proto
SharedTimeLimit * time_limit
int64 value
const int WARNING
Definition: log_severity.h:31
const int INFO
Definition: log_severity.h:31
const int ERROR
Definition: log_severity.h:32
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.")
ColIndex col
Definition: markowitz.cc:176
RowIndex row
Definition: markowitz.cc:175
bool IsFinite(Fractional value)
Definition: lp_types.h:90
AccurateSum< Fractional > KahanSum
Fractional ScalarProduct(const DenseRowOrColumn1 &u, const DenseRowOrColumn2 &v)
std::string GetConstraintStatusString(ConstraintStatus status)
Definition: lp_types.cc:90
void LinearProgramToMPModelProto(const LinearProgram &input, MPModelProto *output)
Definition: proto_utils.cc:20
std::string GetVariableStatusString(VariableStatus status)
Definition: lp_types.cc:71
const double kInfinity
Definition: lp_types.h:83
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)
Definition: fp_utils.h:141
bool WriteProtoToFile(absl::string_view filename, const google::protobuf::Message &proto, ProtoWriteFormat proto_write_format, bool gzipped, bool append_extension_to_file_name)
Definition: file_util.cc:102
ConstraintStatusColumn constraint_statuses
Definition: lp_data.h:676
#define VLOG_IS_ON(verboselevel)
Definition: vlog_is_on.h:41