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 
14 #include "ortools/glop/lp_solver.h"
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"
31 #include "ortools/util/fp_utils.h"
32 
33 // TODO(user): abstract this in some way to the port directory.
34 #ifndef __PORTABLE_PLATFORM__
35 #include "ortools/util/file_util.h"
36 #endif
37 
38 ABSL_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.");
42 ABSL_FLAG(bool, lp_dump_to_proto_file, false,
43  "Tells whether do dump the problem to a protobuf file.");
44 ABSL_FLAG(bool, lp_dump_compressed_file, true,
45  "Whether the proto dump file is compressed.");
46 ABSL_FLAG(bool, lp_dump_binary_file, false,
47  "Whether the proto dump file is binary.");
48 ABSL_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().");
52 ABSL_FLAG(std::string, lp_dump_dir, "/tmp",
53  "Directory where dump files are written.");
54 ABSL_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 
59 namespace operations_research {
60 namespace glop {
61 namespace {
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).
70 void 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 
111 LPSolver::LPSolver() : num_solves_(0) {}
112 
113 void LPSolver::SetParameters(const GlopParameters& parameters) {
114  parameters_ = parameters;
115 }
116 
117 const GlopParameters& LPSolver::GetParameters() const { return parameters_; }
118 
119 GlopParameters* 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.
152  DLOG(WARNING)
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;
235  state.statuses = variable_statuses;
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 
268 namespace {
269 // Computes the "real" problem objective from the one without offset nor
270 // scaling.
271 Fractional 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.
277 Fractional 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 !!";
397  status = ProblemStatus::IMPRECISE;
398  }
399  if (cost_perturbation_is_too_large) {
400  if (log_info) LOG(INFO) << "The needed cost perturbation is too large !!";
401  status = ProblemStatus::IMPRECISE;
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  }
414  status = ProblemStatus::IMPRECISE;
415  }
416  }
417  if ((status == ProblemStatus::OPTIMAL ||
418  status == ProblemStatus::PRIMAL_FEASIBLE) &&
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  }
424  status = ProblemStatus::IMPRECISE;
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  }
432  status = ProblemStatus::IMPRECISE;
433  }
434 
435  may_have_multiple_solutions_ =
436  (status == ProblemStatus::OPTIMAL) ? IsOptimalSolutionOnFacet(lp) : false;
437  return status;
438 }
439 
440 bool 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 
501 void 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 
519 void 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 
544 void 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 
554 void 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 
590 namespace {
591 
592 void 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 
600 void 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 
609 bool 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.
740 Fractional 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.
769 Fractional 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 
798 void 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 
809 void 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 
820 double 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.
846 double 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 
909 double 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 
924 double 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 
954 double 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 
1005 double 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 
1029 double 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
const ConstraintStatusColumn & constraint_statuses() const
Definition: lp_solver.h:116
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
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
const DenseRow & variable_lower_bounds() const
Definition: lp_data.h:228
const DenseColumn & constraint_lower_bounds() const
Definition: lp_data.h:214
std::string GetBoundsStatsString() const
Definition: lp_data.cc:463
const DenseColumn & constraint_upper_bounds() const
Definition: lp_data.h:217
const DenseRow & variable_upper_bounds() const
Definition: lp_data.h:231
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
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
bool IsFinite(Fractional value)
Definition: lp_types.h:90
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 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
bool AreWithinAbsoluteTolerance(FloatType x, FloatType y, FloatType absolute_tolerance)
Definition: fp_utils.h:141
ConstraintStatusColumn constraint_statuses
Definition: lp_data.h:676
#define VLOG_IS_ON(verboselevel)
Definition: vlog_is_on.h:41