OR-Tools  8.2
linear_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 //
15 
17 
18 #if !defined(_MSC_VER)
19 #include <unistd.h>
20 #endif
21 
22 #include <cmath>
23 #include <cstddef>
24 #include <utility>
25 
26 #include "absl/status/status.h"
27 #include "absl/status/statusor.h"
28 #include "absl/strings/ascii.h"
29 #include "absl/strings/match.h"
30 #include "absl/strings/str_cat.h"
31 #include "absl/strings/str_format.h"
32 #include "absl/strings/str_replace.h"
33 #include "absl/synchronization/mutex.h"
37 #include "ortools/base/logging.h"
38 #include "ortools/base/map_util.h"
40 #include "ortools/base/stl_util.h"
41 #include "ortools/linear_solver/linear_solver.pb.h"
44 #include "ortools/port/file.h"
45 #include "ortools/util/fp_utils.h"
46 
47 ABSL_FLAG(bool, verify_solution, false,
48  "Systematically verify the solution when calling Solve()"
49  ", and change the return value of Solve() to ABNORMAL if"
50  " an error was detected.");
51 ABSL_FLAG(bool, log_verification_errors, true,
52  "If --verify_solution is set: LOG(ERROR) all errors detected"
53  " during the verification of the solution.");
54 ABSL_FLAG(bool, linear_solver_enable_verbose_output, false,
55  "If set, enables verbose output for the solver. Setting this flag"
56  " is the same as calling MPSolver::EnableOutput().");
57 
58 ABSL_FLAG(bool, mpsolver_bypass_model_validation, false,
59  "If set, the user-provided Model won't be verified before Solve()."
60  " Invalid models will typically trigger various error responses"
61  " from the underlying solvers; sometimes crashes.");
62 
63 namespace operations_research {
64 
65 bool SolverTypeIsMip(MPModelRequest::SolverType solver_type) {
66  switch (solver_type) {
67  case MPModelRequest::GLOP_LINEAR_PROGRAMMING:
68  case MPModelRequest::CLP_LINEAR_PROGRAMMING:
69  case MPModelRequest::GLPK_LINEAR_PROGRAMMING:
70  case MPModelRequest::GUROBI_LINEAR_PROGRAMMING:
71  case MPModelRequest::XPRESS_LINEAR_PROGRAMMING:
72  case MPModelRequest::CPLEX_LINEAR_PROGRAMMING:
73  return false;
74 
75  case MPModelRequest::SCIP_MIXED_INTEGER_PROGRAMMING:
76  case MPModelRequest::GLPK_MIXED_INTEGER_PROGRAMMING:
77  case MPModelRequest::CBC_MIXED_INTEGER_PROGRAMMING:
78  case MPModelRequest::GUROBI_MIXED_INTEGER_PROGRAMMING:
79  case MPModelRequest::KNAPSACK_MIXED_INTEGER_PROGRAMMING:
80  case MPModelRequest::BOP_INTEGER_PROGRAMMING:
81  case MPModelRequest::SAT_INTEGER_PROGRAMMING:
82  case MPModelRequest::XPRESS_MIXED_INTEGER_PROGRAMMING:
83  case MPModelRequest::CPLEX_MIXED_INTEGER_PROGRAMMING:
84  return true;
85  }
86  LOG(DFATAL) << "Invalid SolverType: " << solver_type;
87  return false;
88 }
89 
90 double MPConstraint::GetCoefficient(const MPVariable* const var) const {
91  DLOG_IF(DFATAL, !interface_->solver_->OwnsVariable(var)) << var;
92  if (var == nullptr) return 0.0;
93  return gtl::FindWithDefault(coefficients_, var, 0.0);
94 }
95 
96 void MPConstraint::SetCoefficient(const MPVariable* const var, double coeff) {
97  DLOG_IF(DFATAL, !interface_->solver_->OwnsVariable(var)) << var;
98  if (var == nullptr) return;
99  if (coeff == 0.0) {
100  auto it = coefficients_.find(var);
101  // If setting a coefficient to 0 when this coefficient did not
102  // exist or was already 0, do nothing: skip
103  // interface_->SetCoefficient() and do not store a coefficient in
104  // the map. Note that if the coefficient being set to 0 did exist
105  // and was not 0, we do have to keep a 0 in the coefficients_ map,
106  // because the extraction of the constraint might rely on it,
107  // depending on the underlying solver.
108  if (it != coefficients_.end() && it->second != 0.0) {
109  const double old_value = it->second;
110  it->second = 0.0;
111  interface_->SetCoefficient(this, var, 0.0, old_value);
112  }
113  return;
114  }
115  auto insertion_result = coefficients_.insert(std::make_pair(var, coeff));
116  const double old_value =
117  insertion_result.second ? 0.0 : insertion_result.first->second;
118  insertion_result.first->second = coeff;
119  interface_->SetCoefficient(this, var, coeff, old_value);
120 }
121 
123  interface_->ClearConstraint(this);
124  coefficients_.clear();
125 }
126 
127 void MPConstraint::SetBounds(double lb, double ub) {
128  const bool change = lb != lb_ || ub != ub_;
129  lb_ = lb;
130  ub_ = ub;
131  if (change && interface_->constraint_is_extracted(index_)) {
132  interface_->SetConstraintBounds(index_, lb_, ub_);
133  }
134 }
135 
136 double MPConstraint::dual_value() const {
137  if (!interface_->IsContinuous()) {
138  LOG(DFATAL) << "Dual value only available for continuous problems";
139  return 0.0;
140  }
141  if (!interface_->CheckSolutionIsSynchronizedAndExists()) return 0.0;
142  return dual_value_;
143 }
144 
146  if (!interface_->IsContinuous()) {
147  LOG(DFATAL) << "Basis status only available for continuous problems";
148  return MPSolver::FREE;
149  }
150  if (!interface_->CheckSolutionIsSynchronizedAndExists()) {
151  return MPSolver::FREE;
152  }
153  // This is done lazily as this method is expected to be rarely used.
154  return interface_->row_status(index_);
155 }
156 
157 bool MPConstraint::ContainsNewVariables() {
158  const int last_variable_index = interface_->last_variable_index();
159  for (const auto& entry : coefficients_) {
160  const int variable_index = entry.first->index();
161  if (variable_index >= last_variable_index ||
162  !interface_->variable_is_extracted(variable_index)) {
163  return true;
164  }
165  }
166  return false;
167 }
168 
169 // ----- MPObjective -----
170 
171 double MPObjective::GetCoefficient(const MPVariable* const var) const {
172  DLOG_IF(DFATAL, !interface_->solver_->OwnsVariable(var)) << var;
173  if (var == nullptr) return 0.0;
174  return gtl::FindWithDefault(coefficients_, var, 0.0);
175 }
176 
177 void MPObjective::SetCoefficient(const MPVariable* const var, double coeff) {
178  DLOG_IF(DFATAL, !interface_->solver_->OwnsVariable(var)) << var;
179  if (var == nullptr) return;
180  if (coeff == 0.0) {
181  auto it = coefficients_.find(var);
182  // See the discussion on MPConstraint::SetCoefficient() for 0 coefficients,
183  // the same reasoning applies here.
184  if (it == coefficients_.end() || it->second == 0.0) return;
185  it->second = 0.0;
186  } else {
187  coefficients_[var] = coeff;
188  }
189  interface_->SetObjectiveCoefficient(var, coeff);
190 }
191 
193  offset_ = value;
194  interface_->SetObjectiveOffset(offset_);
195 }
196 
197 namespace {
198 void CheckLinearExpr(const MPSolver& solver, const LinearExpr& linear_expr) {
199  for (auto var_value_pair : linear_expr.terms()) {
200  CHECK(solver.OwnsVariable(var_value_pair.first))
201  << "Bad MPVariable* in LinearExpr, did you try adding an integer to an "
202  "MPVariable* directly?";
203  }
204 }
205 } // namespace
206 
208  bool is_maximization) {
209  CheckLinearExpr(*interface_->solver_, linear_expr);
210  interface_->ClearObjective();
211  coefficients_.clear();
212  SetOffset(linear_expr.offset());
213  for (const auto& kv : linear_expr.terms()) {
214  SetCoefficient(kv.first, kv.second);
215  }
216  SetOptimizationDirection(is_maximization);
217 }
218 
219 void MPObjective::AddLinearExpr(const LinearExpr& linear_expr) {
220  CheckLinearExpr(*interface_->solver_, linear_expr);
221  SetOffset(offset_ + linear_expr.offset());
222  for (const auto& kv : linear_expr.terms()) {
223  SetCoefficient(kv.first, GetCoefficient(kv.first) + kv.second);
224  }
225 }
226 
228  interface_->ClearObjective();
229  coefficients_.clear();
230  offset_ = 0.0;
231  SetMinimization();
232 }
233 
235  // Note(user): The maximize_ bool would more naturally belong to the
236  // MPObjective, but it actually has to be a member of MPSolverInterface,
237  // because some implementations (such as GLPK) need that bool for the
238  // MPSolverInterface constructor, i.e at a time when the MPObjective is not
239  // constructed yet (MPSolverInterface is always built before MPObjective
240  // when a new MPSolver is constructed).
241  interface_->maximize_ = maximize;
242  interface_->SetOptimizationDirection(maximize);
243 }
244 
245 bool MPObjective::maximization() const { return interface_->maximize_; }
246 
247 bool MPObjective::minimization() const { return !interface_->maximize_; }
248 
249 double MPObjective::Value() const {
250  // Note(user): implementation-wise, the objective value belongs more
251  // naturally to the MPSolverInterface, since all of its implementations write
252  // to it directly.
253  return interface_->objective_value();
254 }
255 
256 double MPObjective::BestBound() const {
257  // Note(user): the best objective bound belongs to the interface for the
258  // same reasons as the objective value does.
259  return interface_->best_objective_bound();
260 }
261 
262 // ----- MPVariable -----
263 
265  if (!interface_->CheckSolutionIsSynchronizedAndExists()) return 0.0;
266  // If the underlying solver supports integer variables, and this is an integer
267  // variable, we round the solution value (i.e., clients usually expect precise
268  // integer values for integer variables).
269  return (integer_ && interface_->IsMIP()) ? round(solution_value_)
270  : solution_value_;
271 }
272 
274  if (!interface_->CheckSolutionIsSynchronizedAndExists()) return 0.0;
275  return solution_value_;
276 }
277 
278 double MPVariable::reduced_cost() const {
279  if (!interface_->IsContinuous()) {
280  LOG(DFATAL) << "Reduced cost only available for continuous problems";
281  return 0.0;
282  }
283  if (!interface_->CheckSolutionIsSynchronizedAndExists()) return 0.0;
284  return reduced_cost_;
285 }
286 
288  if (!interface_->IsContinuous()) {
289  LOG(DFATAL) << "Basis status only available for continuous problems";
290  return MPSolver::FREE;
291  }
292  if (!interface_->CheckSolutionIsSynchronizedAndExists()) {
293  return MPSolver::FREE;
294  }
295  // This is done lazily as this method is expected to be rarely used.
296  return interface_->column_status(index_);
297 }
298 
299 void MPVariable::SetBounds(double lb, double ub) {
300  const bool change = lb != lb_ || ub != ub_;
301  lb_ = lb;
302  ub_ = ub;
303  if (change && interface_->variable_is_extracted(index_)) {
304  interface_->SetVariableBounds(index_, lb_, ub_);
305  }
306 }
307 
308 void MPVariable::SetInteger(bool integer) {
309  if (integer_ != integer) {
310  integer_ = integer;
311  if (interface_->variable_is_extracted(index_)) {
312  interface_->SetVariableInteger(index_, integer);
313  }
314  }
315 }
316 
318  if (priority == branching_priority_) return;
319  branching_priority_ = priority;
320  interface_->BranchingPriorityChangedForVariable(index_);
321 }
322 
323 // ----- Interface shortcuts -----
324 
325 bool MPSolver::IsMIP() const { return interface_->IsMIP(); }
326 
327 std::string MPSolver::SolverVersion() const {
328  return interface_->SolverVersion();
329 }
330 
331 void* MPSolver::underlying_solver() { return interface_->underlying_solver(); }
332 
333 // ---- Solver-specific parameters ----
334 
335 absl::Status MPSolver::SetNumThreads(int num_threads) {
336  if (num_threads < 1) {
337  return absl::InvalidArgumentError("num_threads must be a positive number.");
338  }
339  const absl::Status status = interface_->SetNumThreads(num_threads);
340  if (status.ok()) {
341  num_threads_ = num_threads;
342  }
343  return status;
344 }
345 
347  const std::string& parameters) {
348  solver_specific_parameter_string_ = parameters;
349  return interface_->SetSolverSpecificParametersAsString(parameters);
350 }
351 
352 // ----- Solver -----
353 
354 #if defined(USE_CLP) || defined(USE_CBC)
355 extern MPSolverInterface* BuildCLPInterface(MPSolver* const solver);
356 #endif
357 #if defined(USE_CBC)
358 extern MPSolverInterface* BuildCBCInterface(MPSolver* const solver);
359 #endif
360 #if defined(USE_GLPK)
361 extern MPSolverInterface* BuildGLPKInterface(bool mip, MPSolver* const solver);
362 #endif
363 extern MPSolverInterface* BuildBopInterface(MPSolver* const solver);
364 extern MPSolverInterface* BuildGLOPInterface(MPSolver* const solver);
365 extern MPSolverInterface* BuildSatInterface(MPSolver* const solver);
366 #if defined(USE_SCIP)
367 extern MPSolverInterface* BuildSCIPInterface(MPSolver* const solver);
368 #endif
369 extern MPSolverInterface* BuildGurobiInterface(bool mip,
370  MPSolver* const solver);
371 #if defined(USE_CPLEX)
372 extern MPSolverInterface* BuildCplexInterface(bool mip, MPSolver* const solver);
373 
374 extern MPSolverInterface* BuildGLOPInterface(MPSolver* const solver);
375 #endif
376 #if defined(USE_XPRESS)
377 extern MPSolverInterface* BuildXpressInterface(bool mip,
378  MPSolver* const solver);
379 #endif
380 
381 namespace {
382 MPSolverInterface* BuildSolverInterface(MPSolver* const solver) {
383  DCHECK(solver != nullptr);
384  switch (solver->ProblemType()) {
386  return BuildBopInterface(solver);
388  return BuildSatInterface(solver);
390  return BuildGLOPInterface(solver);
391 #if defined(USE_GLPK)
393  return BuildGLPKInterface(false, solver);
395  return BuildGLPKInterface(true, solver);
396 #endif
397 #if defined(USE_CLP) || defined(USE_CBC)
399  return BuildCLPInterface(solver);
400 #endif
401 #if defined(USE_CBC)
403  return BuildCBCInterface(solver);
404 #endif
405 #if defined(USE_SCIP)
407  return BuildSCIPInterface(solver);
408 #endif
410  return BuildGurobiInterface(false, solver);
412  return BuildGurobiInterface(true, solver);
413 #if defined(USE_CPLEX)
415  return BuildCplexInterface(false, solver);
417  return BuildCplexInterface(true, solver);
418 #endif
419 #if defined(USE_XPRESS)
421  return BuildXpressInterface(true, solver);
423  return BuildXpressInterface(false, solver);
424 #endif
425  default:
426  // TODO(user): Revert to the best *available* interface.
427  LOG(FATAL) << "Linear solver not recognized.";
428  }
429  return nullptr;
430 }
431 } // namespace
432 
433 namespace {
434 int NumDigits(int n) {
435 // Number of digits needed to write a non-negative integer in base 10.
436 // Note(user): max(1, log(0) + 1) == max(1, -inf) == 1.
437 #if defined(_MSC_VER)
438  return static_cast<int>(std::max(1.0L, log(1.0L * n) / log(10.0L) + 1.0));
439 #else
440  return static_cast<int>(std::max(1.0, log10(static_cast<double>(n)) + 1.0));
441 #endif
442 }
443 } // namespace
444 
445 MPSolver::MPSolver(const std::string& name,
447  : name_(name),
448  problem_type_(problem_type),
449  construction_time_(absl::Now()) {
450  interface_.reset(BuildSolverInterface(this));
451  if (absl::GetFlag(FLAGS_linear_solver_enable_verbose_output)) {
452  EnableOutput();
453  }
454  objective_.reset(new MPObjective(interface_.get()));
455 }
456 
458 
459 // static
461 #ifdef USE_CLP
462  if (problem_type == CLP_LINEAR_PROGRAMMING) return true;
463 #endif
464 #ifdef USE_GLPK
467  return true;
468  }
469 #endif
470  if (problem_type == BOP_INTEGER_PROGRAMMING) return true;
471  if (problem_type == SAT_INTEGER_PROGRAMMING) return true;
472  if (problem_type == GLOP_LINEAR_PROGRAMMING) return true;
475  return MPSolver::GurobiIsCorrectlyInstalled();
476  }
477 #ifdef USE_SCIP
478  if (problem_type == SCIP_MIXED_INTEGER_PROGRAMMING) return true;
479 #endif
480 #ifdef USE_CBC
481  if (problem_type == CBC_MIXED_INTEGER_PROGRAMMING) return true;
482 #endif
483 #ifdef USE_XPRESS
486  return true;
487  }
488 #endif
489 #ifdef USE_CPLEX
492  return true;
493  }
494 #endif
495  return false;
496 }
497 
498 // TODO(user): post c++ 14, instead use
499 // std::pair<MPSolver::OptimizationProblemType, const absl::string_view>
500 // once pair gets a constexpr constructor.
501 namespace {
502 struct NamedOptimizationProblemType {
504  absl::string_view name;
505 };
506 } // namespace
507 
508 #if defined(_MSC_VER)
509 const
510 #else
511 constexpr
512 #endif
513  NamedOptimizationProblemType kOptimizationProblemTypeNames[] = {
529 
530 };
531 // static
532 bool MPSolver::ParseSolverType(absl::string_view solver_id,
534  // Normalize the solver id.
535  const std::string id =
536  absl::StrReplaceAll(absl::AsciiStrToUpper(solver_id), {{"-", "_"}});
537 
538  // Support the full enum name
539  MPModelRequest::SolverType solver_type;
540  if (MPModelRequest::SolverType_Parse(id, &solver_type)) {
541  *type = static_cast<MPSolver::OptimizationProblemType>(solver_type);
542  return true;
543  }
544 
545  // Names are stored in lower case.
546  std::string lower_id = absl::AsciiStrToLower(id);
547 
548  // Remove any "_mip" suffix, since they are optional.
549  if (absl::EndsWith(lower_id, "_mip")) {
550  lower_id = lower_id.substr(0, lower_id.size() - 4);
551  }
552 
553  // Rewrite CP-SAT into SAT.
554  if (lower_id == "cp_sat") {
555  lower_id = "sat";
556  }
557 
558  // Reverse lookup in the kOptimizationProblemTypeNames[] array.
559  for (auto& named_solver : kOptimizationProblemTypeNames) {
560  if (named_solver.name == lower_id) {
561  *type = named_solver.problem_type;
562  return true;
563  }
564  }
565 
566  return false;
567 }
568 
569 const absl::string_view ToString(
570  MPSolver::OptimizationProblemType optimization_problem_type) {
571  for (const auto& named_solver : kOptimizationProblemTypeNames) {
572  if (named_solver.problem_type == optimization_problem_type) {
573  return named_solver.name;
574  }
575  }
576  LOG(FATAL) << "Unrecognized solver type: "
577  << static_cast<int>(optimization_problem_type);
578  return "";
579 }
580 
581 bool AbslParseFlag(const absl::string_view text,
583  std::string* error) {
584  DCHECK(solver_type != nullptr);
585  DCHECK(error != nullptr);
586  const bool result = MPSolver::ParseSolverType(text, solver_type);
587  if (!result) {
588  *error = absl::StrCat("Solver type: ", text, " does not exist.");
589  }
590  return result;
591 }
592 
593 /* static */
595  const std::string& solver_id) {
597  CHECK(MPSolver::ParseSolverType(solver_id, &problem_type)) << solver_id;
598  return problem_type;
599 }
600 
601 /* static */
602 MPSolver* MPSolver::CreateSolver(const std::string& solver_id) {
604  if (!MPSolver::ParseSolverType(solver_id, &problem_type)) {
605  LOG(WARNING) << "Unrecognized solver type: " << solver_id;
606  return nullptr;
607  }
609  LOG(WARNING) << "Support for " << solver_id
610  << " not linked in, or the license was not found.";
611  return nullptr;
612  }
613  return new MPSolver("", problem_type);
614 }
615 
616 MPVariable* MPSolver::LookupVariableOrNull(const std::string& var_name) const {
617  if (!variable_name_to_index_) GenerateVariableNameIndex();
618 
619  absl::flat_hash_map<std::string, int>::const_iterator it =
620  variable_name_to_index_->find(var_name);
621  if (it == variable_name_to_index_->end()) return nullptr;
622  return variables_[it->second];
623 }
624 
626  const std::string& constraint_name) const {
627  if (!constraint_name_to_index_) GenerateConstraintNameIndex();
628 
629  const auto it = constraint_name_to_index_->find(constraint_name);
630  if (it == constraint_name_to_index_->end()) return nullptr;
631  return constraints_[it->second];
632 }
633 
634 // ----- Methods using protocol buffers -----
635 
636 MPSolverResponseStatus MPSolver::LoadModelFromProto(
637  const MPModelProto& input_model, std::string* error_message) {
638  Clear();
639 
640  // The variable and constraint names are dropped, because we allow
641  // duplicate names in the proto (they're not considered as 'ids'),
642  // unlike the MPSolver C++ API which crashes if there are duplicate names.
643  // Clearing the names makes the MPSolver generate unique names.
644  return LoadModelFromProtoInternal(input_model, /*clear_names=*/true,
645  /*check_model_validity=*/true,
646  error_message);
647 }
648 
650  const MPModelProto& input_model, std::string* error_message) {
651  Clear();
652 
653  // Force variable and constraint name indexing (which CHECKs name uniqueness).
654  GenerateVariableNameIndex();
655  GenerateConstraintNameIndex();
656 
657  return LoadModelFromProtoInternal(input_model, /*clear_names=*/false,
658  /*check_model_validity=*/true,
659  error_message);
660 }
661 
662 MPSolverResponseStatus MPSolver::LoadModelFromProtoInternal(
663  const MPModelProto& input_model, bool clear_names,
664  bool check_model_validity, std::string* error_message) {
665  CHECK(error_message != nullptr);
666  if (check_model_validity) {
667  const std::string error = FindErrorInMPModelProto(input_model);
668  if (!error.empty()) {
669  *error_message = error;
671  << "Invalid model given to LoadModelFromProto(): " << error;
672  if (absl::GetFlag(FLAGS_mpsolver_bypass_model_validation)) {
674  << "Ignoring the model error(s) because of"
675  << " --mpsolver_bypass_model_validation.";
676  } else {
677  return absl::StrContains(error, "Infeasible") ? MPSOLVER_INFEASIBLE
678  : MPSOLVER_MODEL_INVALID;
679  }
680  }
681  }
682 
683  if (input_model.has_quadratic_objective()) {
684  *error_message =
685  "Optimizing a quadratic objective is only supported through direct "
686  "proto solves. Please use MPSolver::SolveWithProto, or the solver's "
687  "direct proto solve function.";
688  return MPSOLVER_MODEL_INVALID;
689  }
690 
691  MPObjective* const objective = MutableObjective();
692  // Passing empty names makes the MPSolver generate unique names.
693  const std::string empty;
694  for (int i = 0; i < input_model.variable_size(); ++i) {
695  const MPVariableProto& var_proto = input_model.variable(i);
696  MPVariable* variable =
697  MakeNumVar(var_proto.lower_bound(), var_proto.upper_bound(),
698  clear_names ? empty : var_proto.name());
699  variable->SetInteger(var_proto.is_integer());
700  if (var_proto.branching_priority() != 0) {
701  variable->SetBranchingPriority(var_proto.branching_priority());
702  }
703  objective->SetCoefficient(variable, var_proto.objective_coefficient());
704  }
705 
706  for (const MPConstraintProto& ct_proto : input_model.constraint()) {
707  if (ct_proto.lower_bound() == -infinity() &&
708  ct_proto.upper_bound() == infinity()) {
709  continue;
710  }
711 
712  MPConstraint* const ct =
713  MakeRowConstraint(ct_proto.lower_bound(), ct_proto.upper_bound(),
714  clear_names ? empty : ct_proto.name());
715  ct->set_is_lazy(ct_proto.is_lazy());
716  for (int j = 0; j < ct_proto.var_index_size(); ++j) {
717  ct->SetCoefficient(variables_[ct_proto.var_index(j)],
718  ct_proto.coefficient(j));
719  }
720  }
721 
722  for (const MPGeneralConstraintProto& general_constraint :
723  input_model.general_constraint()) {
724  switch (general_constraint.general_constraint_case()) {
725  case MPGeneralConstraintProto::kIndicatorConstraint: {
726  const auto& proto =
727  general_constraint.indicator_constraint().constraint();
728  if (proto.lower_bound() == -infinity() &&
729  proto.upper_bound() == infinity()) {
730  continue;
731  }
732 
733  const int constraint_index = NumConstraints();
734  MPConstraint* const constraint = new MPConstraint(
735  constraint_index, proto.lower_bound(), proto.upper_bound(),
736  clear_names ? "" : proto.name(), interface_.get());
737  if (constraint_name_to_index_) {
738  gtl::InsertOrDie(&*constraint_name_to_index_, constraint->name(),
739  constraint_index);
740  }
741  constraints_.push_back(constraint);
742  constraint_is_extracted_.push_back(false);
743 
744  constraint->set_is_lazy(proto.is_lazy());
745  for (int j = 0; j < proto.var_index_size(); ++j) {
746  constraint->SetCoefficient(variables_[proto.var_index(j)],
747  proto.coefficient(j));
748  }
749 
750  MPVariable* const variable =
751  variables_[general_constraint.indicator_constraint().var_index()];
752  constraint->indicator_variable_ = variable;
753  constraint->indicator_value_ =
754  general_constraint.indicator_constraint().var_value();
755 
756  if (!interface_->AddIndicatorConstraint(constraint)) {
757  *error_message = "Solver doesn't support indicator constraints";
758  return MPSOLVER_MODEL_INVALID;
759  }
760  break;
761  }
762  default:
763  *error_message = absl::StrFormat(
764  "Optimizing general constraints of type %i is only supported "
765  "through direct proto solves. Please use MPSolver::SolveWithProto, "
766  "or the solver's direct proto solve function.",
767  general_constraint.general_constraint_case());
768  return MPSOLVER_MODEL_INVALID;
769  }
770  }
771 
772  objective->SetOptimizationDirection(input_model.maximize());
773  if (input_model.has_objective_offset()) {
774  objective->SetOffset(input_model.objective_offset());
775  }
776 
777  // Stores any hints about where to start the solve.
778  solution_hint_.clear();
779  for (int i = 0; i < input_model.solution_hint().var_index_size(); ++i) {
780  solution_hint_.push_back(
781  std::make_pair(variables_[input_model.solution_hint().var_index(i)],
782  input_model.solution_hint().var_value(i)));
783  }
784  return MPSOLVER_MODEL_IS_VALID;
785 }
786 
787 namespace {
788 MPSolverResponseStatus ResultStatusToMPSolverResponseStatus(
789  MPSolver::ResultStatus status) {
790  switch (status) {
791  case MPSolver::OPTIMAL:
792  return MPSOLVER_OPTIMAL;
793  case MPSolver::FEASIBLE:
794  return MPSOLVER_FEASIBLE;
796  return MPSOLVER_INFEASIBLE;
797  case MPSolver::UNBOUNDED:
798  return MPSOLVER_UNBOUNDED;
799  case MPSolver::ABNORMAL:
800  return MPSOLVER_ABNORMAL;
802  return MPSOLVER_MODEL_INVALID;
804  return MPSOLVER_NOT_SOLVED;
805  }
806  return MPSOLVER_UNKNOWN_STATUS;
807 }
808 } // namespace
809 
810 void MPSolver::FillSolutionResponseProto(MPSolutionResponse* response) const {
811  CHECK(response != nullptr);
812  response->Clear();
813  response->set_status(
814  ResultStatusToMPSolverResponseStatus(interface_->result_status_));
815  if (interface_->result_status_ == MPSolver::OPTIMAL ||
816  interface_->result_status_ == MPSolver::FEASIBLE) {
817  response->set_objective_value(Objective().Value());
818  for (int i = 0; i < variables_.size(); ++i) {
819  response->add_variable_value(variables_[i]->solution_value());
820  }
821 
822  if (interface_->IsMIP()) {
823  response->set_best_objective_bound(interface_->best_objective_bound());
824  } else {
825  // Dual values have no meaning in MIP.
826  for (int j = 0; j < constraints_.size(); ++j) {
827  response->add_dual_value(constraints_[j]->dual_value());
828  }
829  // Reduced cost have no meaning in MIP.
830  for (int i = 0; i < variables_.size(); ++i) {
831  response->add_reduced_cost(variables_[i]->reduced_cost());
832  }
833  }
834  }
835 }
836 
837 // static
838 void MPSolver::SolveWithProto(const MPModelRequest& model_request,
839  MPSolutionResponse* response) {
840  CHECK(response != nullptr);
841  MPSolver solver(model_request.model().name(),
843  model_request.solver_type()));
844  if (model_request.enable_internal_solver_output()) {
845  solver.EnableOutput();
846  }
847 
848  auto optional_response = solver.interface_->DirectlySolveProto(model_request);
849  if (optional_response) {
850  *response = std::move(optional_response).value();
851  return;
852  }
853 
854  const absl::optional<LazyMutableCopy<MPModelProto>> optional_model =
856  if (!optional_model) {
857  LOG_IF(WARNING, model_request.enable_internal_solver_output())
858  << "Failed to extract a valid model from protocol buffer. Status: "
859  << ProtoEnumToString<MPSolverResponseStatus>(response->status()) << " ("
860  << response->status() << "): " << response->status_str();
861  return;
862  }
863  std::string error_message;
864  response->set_status(solver.LoadModelFromProtoInternal(
865  optional_model->get(), /*clear_names=*/true,
866  /*check_model_validity=*/false, &error_message));
867  // Even though we don't re-check model validity here, there can be some
868  // problems found by LoadModelFromProto, eg. unsupported features.
869  if (response->status() != MPSOLVER_MODEL_IS_VALID) {
870  response->set_status_str(error_message);
871  LOG_IF(WARNING, model_request.enable_internal_solver_output())
872  << "LoadModelFromProtoInternal() failed even though the model was "
873  << "valid! Status: "
874  << ProtoEnumToString<MPSolverResponseStatus>(response->status()) << " ("
875  << response->status() << "); Error: " << error_message;
876  return;
877  }
878  if (model_request.has_solver_time_limit_seconds()) {
879  solver.SetTimeLimit(
880  absl::Seconds(model_request.solver_time_limit_seconds()));
881  }
882  std::string warning_message;
883  if (model_request.has_solver_specific_parameters()) {
885  model_request.solver_specific_parameters())) {
886  if (model_request.ignore_solver_specific_parameters_failure()) {
887  // We'll add a warning message in status_str after the solve.
888  warning_message =
889  "Warning: the solver specific parameters were not successfully "
890  "applied";
891  } else {
892  response->set_status(MPSOLVER_MODEL_INVALID_SOLVER_PARAMETERS);
893  return;
894  }
895  }
896  }
897  solver.Solve();
899  if (!warning_message.empty()) {
900  response->set_status_str(absl::StrCat(
901  response->status_str(), (response->status_str().empty() ? "" : "\n"),
902  warning_message));
903  }
904 }
905 
906 void MPSolver::ExportModelToProto(MPModelProto* output_model) const {
907  DCHECK(output_model != nullptr);
908  output_model->Clear();
909  // Name
910  output_model->set_name(Name());
911  // Variables
912  for (int j = 0; j < variables_.size(); ++j) {
913  const MPVariable* const var = variables_[j];
914  MPVariableProto* const variable_proto = output_model->add_variable();
915  // TODO(user): Add option to avoid filling the var name to avoid overly
916  // large protocol buffers.
917  variable_proto->set_name(var->name());
918  variable_proto->set_lower_bound(var->lb());
919  variable_proto->set_upper_bound(var->ub());
920  variable_proto->set_is_integer(var->integer());
921  if (objective_->GetCoefficient(var) != 0.0) {
922  variable_proto->set_objective_coefficient(
923  objective_->GetCoefficient(var));
924  }
925  if (var->branching_priority() != 0) {
926  variable_proto->set_branching_priority(var->branching_priority());
927  }
928  }
929 
930  // Map the variables to their indices. This is needed to output the
931  // variables in the order they were created, which in turn is needed to have
932  // repeatable results with ExportModelAsLpFormat and ExportModelAsMpsFormat.
933  // This step is needed as long as the variable indices are given by the
934  // underlying solver at the time of model extraction.
935  // TODO(user): remove this step.
936  absl::flat_hash_map<const MPVariable*, int> var_to_index;
937  for (int j = 0; j < variables_.size(); ++j) {
938  var_to_index[variables_[j]] = j;
939  }
940 
941  // Constraints
942  for (int i = 0; i < constraints_.size(); ++i) {
943  MPConstraint* const constraint = constraints_[i];
944  MPConstraintProto* constraint_proto;
945  if (constraint->indicator_variable() != nullptr) {
946  MPGeneralConstraintProto* const general_constraint_proto =
947  output_model->add_general_constraint();
948  general_constraint_proto->set_name(constraint->name());
949  MPIndicatorConstraint* const indicator_constraint_proto =
950  general_constraint_proto->mutable_indicator_constraint();
951  indicator_constraint_proto->set_var_index(
952  constraint->indicator_variable()->index());
953  indicator_constraint_proto->set_var_value(constraint->indicator_value());
954  constraint_proto = indicator_constraint_proto->mutable_constraint();
955  } else {
956  constraint_proto = output_model->add_constraint();
957  }
958  constraint_proto->set_name(constraint->name());
959  constraint_proto->set_lower_bound(constraint->lb());
960  constraint_proto->set_upper_bound(constraint->ub());
961  constraint_proto->set_is_lazy(constraint->is_lazy());
962  // Vector linear_term will contain pairs (variable index, coeff), that will
963  // be sorted by variable index.
964  std::vector<std::pair<int, double>> linear_term;
965  for (const auto& entry : constraint->coefficients_) {
966  const MPVariable* const var = entry.first;
967  const int var_index = gtl::FindWithDefault(var_to_index, var, -1);
968  DCHECK_NE(-1, var_index);
969  const double coeff = entry.second;
970  linear_term.push_back(std::pair<int, double>(var_index, coeff));
971  }
972  // The cost of sort is expected to be low as constraints usually have very
973  // few terms.
974  std::sort(linear_term.begin(), linear_term.end());
975  // Now use linear term.
976  for (const std::pair<int, double>& var_and_coeff : linear_term) {
977  constraint_proto->add_var_index(var_and_coeff.first);
978  constraint_proto->add_coefficient(var_and_coeff.second);
979  }
980  }
981 
982  output_model->set_maximize(Objective().maximization());
983  output_model->set_objective_offset(Objective().offset());
984 
985  if (!solution_hint_.empty()) {
986  PartialVariableAssignment* const hint =
987  output_model->mutable_solution_hint();
988  for (const auto& var_value_pair : solution_hint_) {
989  hint->add_var_index(var_value_pair.first->index());
990  hint->add_var_value(var_value_pair.second);
991  }
992  }
993 }
994 
995 absl::Status MPSolver::LoadSolutionFromProto(const MPSolutionResponse& response,
996  double tolerance) {
997  interface_->result_status_ = static_cast<ResultStatus>(response.status());
998  if (response.status() != MPSOLVER_OPTIMAL &&
999  response.status() != MPSOLVER_FEASIBLE) {
1000  return absl::InvalidArgumentError(absl::StrCat(
1001  "Cannot load a solution unless its status is OPTIMAL or FEASIBLE"
1002  " (status was: ",
1003  ProtoEnumToString<MPSolverResponseStatus>(response.status()), ")"));
1004  }
1005  // Before touching the variables, verify that the solution looks legit:
1006  // each variable of the MPSolver must have its value listed exactly once, and
1007  // each listed solution should correspond to a known variable.
1008  if (response.variable_value_size() != variables_.size()) {
1009  return absl::InvalidArgumentError(absl::StrCat(
1010  "Trying to load a solution whose number of variables (",
1011  response.variable_value_size(),
1012  ") does not correspond to the Solver's (", variables_.size(), ")"));
1013  }
1014  interface_->ExtractModel();
1015 
1016  if (tolerance != infinity()) {
1017  // Look further: verify that the variable values are within the bounds.
1018  double largest_error = 0;
1019  int num_vars_out_of_bounds = 0;
1020  int last_offending_var = -1;
1021  for (int i = 0; i < response.variable_value_size(); ++i) {
1022  const double var_value = response.variable_value(i);
1023  MPVariable* var = variables_[i];
1024  // TODO(user): Use parameter when they become available in this class.
1025  const double lb_error = var->lb() - var_value;
1026  const double ub_error = var_value - var->ub();
1027  if (lb_error > tolerance || ub_error > tolerance) {
1028  ++num_vars_out_of_bounds;
1029  largest_error = std::max(largest_error, std::max(lb_error, ub_error));
1030  last_offending_var = i;
1031  }
1032  }
1033  if (num_vars_out_of_bounds > 0) {
1034  return absl::InvalidArgumentError(absl::StrCat(
1035  "Loaded a solution whose variables matched the solver's, but ",
1036  num_vars_out_of_bounds, " of ", variables_.size(),
1037  " variables were out of their bounds, by more than the primal"
1038  " tolerance which is: ",
1039  tolerance, ". Max error: ", largest_error, ", last offender var is #",
1040  last_offending_var, ": '", variables_[last_offending_var]->name(),
1041  "'"));
1042  }
1043  }
1044  // TODO(user): Load the reduced costs too, if available.
1045  for (int i = 0; i < response.variable_value_size(); ++i) {
1046  variables_[i]->set_solution_value(response.variable_value(i));
1047  }
1048  // Set the objective value, if is known.
1049  // NOTE(user): We do not verify the objective, even though we could!
1050  if (response.has_objective_value()) {
1051  interface_->objective_value_ = response.objective_value();
1052  }
1053  if (response.has_best_objective_bound()) {
1054  interface_->best_objective_bound_ = response.best_objective_bound();
1055  }
1056  // Mark the status as SOLUTION_SYNCHRONIZED, so that users may inspect the
1057  // solution normally.
1058  interface_->sync_status_ = MPSolverInterface::SOLUTION_SYNCHRONIZED;
1059  return absl::OkStatus();
1060 }
1061 
1063  MutableObjective()->Clear();
1064  gtl::STLDeleteElements(&variables_);
1065  gtl::STLDeleteElements(&constraints_);
1066  variables_.clear();
1067  if (variable_name_to_index_) {
1068  variable_name_to_index_->clear();
1069  }
1070  variable_is_extracted_.clear();
1071  constraints_.clear();
1072  if (constraint_name_to_index_) {
1073  constraint_name_to_index_->clear();
1074  }
1075  constraint_is_extracted_.clear();
1076  interface_->Reset();
1077  solution_hint_.clear();
1078 }
1079 
1080 void MPSolver::Reset() { interface_->Reset(); }
1081 
1082 bool MPSolver::InterruptSolve() { return interface_->InterruptSolve(); }
1083 
1085  const std::vector<BasisStatus>& variable_statuses,
1086  const std::vector<BasisStatus>& constraint_statuses) {
1087  interface_->SetStartingLpBasis(variable_statuses, constraint_statuses);
1088 }
1089 
1090 MPVariable* MPSolver::MakeVar(double lb, double ub, bool integer,
1091  const std::string& name) {
1092  const int var_index = NumVariables();
1093  MPVariable* v =
1094  new MPVariable(var_index, lb, ub, integer, name, interface_.get());
1095  if (variable_name_to_index_) {
1096  gtl::InsertOrDie(&*variable_name_to_index_, v->name(), var_index);
1097  }
1098  variables_.push_back(v);
1099  variable_is_extracted_.push_back(false);
1100  interface_->AddVariable(v);
1101  return v;
1102 }
1103 
1104 MPVariable* MPSolver::MakeNumVar(double lb, double ub,
1105  const std::string& name) {
1106  return MakeVar(lb, ub, false, name);
1107 }
1108 
1109 MPVariable* MPSolver::MakeIntVar(double lb, double ub,
1110  const std::string& name) {
1111  return MakeVar(lb, ub, true, name);
1112 }
1113 
1114 MPVariable* MPSolver::MakeBoolVar(const std::string& name) {
1115  return MakeVar(0.0, 1.0, true, name);
1116 }
1117 
1118 void MPSolver::MakeVarArray(int nb, double lb, double ub, bool integer,
1119  const std::string& name,
1120  std::vector<MPVariable*>* vars) {
1121  DCHECK_GE(nb, 0);
1122  if (nb <= 0) return;
1123  const int num_digits = NumDigits(nb);
1124  for (int i = 0; i < nb; ++i) {
1125  if (name.empty()) {
1126  vars->push_back(MakeVar(lb, ub, integer, name));
1127  } else {
1128  std::string vname =
1129  absl::StrFormat("%s%0*d", name.c_str(), num_digits, i);
1130  vars->push_back(MakeVar(lb, ub, integer, vname));
1131  }
1132  }
1133 }
1134 
1135 void MPSolver::MakeNumVarArray(int nb, double lb, double ub,
1136  const std::string& name,
1137  std::vector<MPVariable*>* vars) {
1138  MakeVarArray(nb, lb, ub, false, name, vars);
1139 }
1140 
1141 void MPSolver::MakeIntVarArray(int nb, double lb, double ub,
1142  const std::string& name,
1143  std::vector<MPVariable*>* vars) {
1144  MakeVarArray(nb, lb, ub, true, name, vars);
1145 }
1146 
1147 void MPSolver::MakeBoolVarArray(int nb, const std::string& name,
1148  std::vector<MPVariable*>* vars) {
1149  MakeVarArray(nb, 0.0, 1.0, true, name, vars);
1150 }
1151 
1153  return MakeRowConstraint(lb, ub, "");
1154 }
1155 
1157  return MakeRowConstraint(-infinity(), infinity(), "");
1158 }
1159 
1161  const std::string& name) {
1162  const int constraint_index = NumConstraints();
1163  MPConstraint* const constraint =
1164  new MPConstraint(constraint_index, lb, ub, name, interface_.get());
1165  if (constraint_name_to_index_) {
1166  gtl::InsertOrDie(&*constraint_name_to_index_, constraint->name(),
1167  constraint_index);
1168  }
1169  constraints_.push_back(constraint);
1170  constraint_is_extracted_.push_back(false);
1171  interface_->AddRowConstraint(constraint);
1172  return constraint;
1173 }
1174 
1176  return MakeRowConstraint(-infinity(), infinity(), name);
1177 }
1178 
1180  return MakeRowConstraint(range, "");
1181 }
1182 
1184  const std::string& name) {
1185  CheckLinearExpr(*this, range.linear_expr());
1186  MPConstraint* constraint =
1187  MakeRowConstraint(range.lower_bound(), range.upper_bound(), name);
1188  for (const auto& kv : range.linear_expr().terms()) {
1189  constraint->SetCoefficient(kv.first, kv.second);
1190  }
1191  return constraint;
1192 }
1193 
1194 int MPSolver::ComputeMaxConstraintSize(int min_constraint_index,
1195  int max_constraint_index) const {
1196  int max_constraint_size = 0;
1197  DCHECK_GE(min_constraint_index, 0);
1198  DCHECK_LE(max_constraint_index, constraints_.size());
1199  for (int i = min_constraint_index; i < max_constraint_index; ++i) {
1200  MPConstraint* const ct = constraints_[i];
1201  if (ct->coefficients_.size() > max_constraint_size) {
1202  max_constraint_size = ct->coefficients_.size();
1203  }
1204  }
1205  return max_constraint_size;
1206 }
1207 
1208 bool MPSolver::HasInfeasibleConstraints() const {
1209  bool hasInfeasibleConstraints = false;
1210  for (int i = 0; i < constraints_.size(); ++i) {
1211  if (constraints_[i]->lb() > constraints_[i]->ub()) {
1212  LOG(WARNING) << "Constraint " << constraints_[i]->name() << " (" << i
1213  << ") has contradictory bounds:"
1214  << " lower bound = " << constraints_[i]->lb()
1215  << " upper bound = " << constraints_[i]->ub();
1216  hasInfeasibleConstraints = true;
1217  }
1218  }
1219  return hasInfeasibleConstraints;
1220 }
1221 
1222 bool MPSolver::HasIntegerVariables() const {
1223  for (const MPVariable* const variable : variables_) {
1224  if (variable->integer()) return true;
1225  }
1226  return false;
1227 }
1228 
1230  MPSolverParameters default_param;
1231  return Solve(default_param);
1232 }
1233 
1235  // Special case for infeasible constraints so that all solvers have
1236  // the same behavior.
1237  // TODO(user): replace this by model extraction to proto + proto validation
1238  // (the proto has very low overhead compared to the wrapper, both in
1239  // performance and memory, so it's ok).
1240  if (HasInfeasibleConstraints()) {
1241  interface_->result_status_ = MPSolver::INFEASIBLE;
1242  return interface_->result_status_;
1243  }
1244 
1245  MPSolver::ResultStatus status = interface_->Solve(param);
1246  if (absl::GetFlag(FLAGS_verify_solution)) {
1247  if (status != MPSolver::OPTIMAL && status != MPSolver::FEASIBLE) {
1248  VLOG(1) << "--verify_solution enabled, but the solver did not find a"
1249  << " solution: skipping the verification.";
1250  } else if (!VerifySolution(
1252  absl::GetFlag(FLAGS_log_verification_errors))) {
1253  status = MPSolver::ABNORMAL;
1254  interface_->result_status_ = status;
1255  }
1256  }
1257  DCHECK_EQ(interface_->result_status_, status);
1258  return status;
1259 }
1260 
1261 void MPSolver::Write(const std::string& file_name) {
1262  interface_->Write(file_name);
1263 }
1264 
1265 namespace {
1266 std::string PrettyPrintVar(const MPVariable& var) {
1267  const std::string prefix = "Variable '" + var.name() + "': domain = ";
1268  if (var.lb() >= MPSolver::infinity() || var.ub() <= -MPSolver::infinity() ||
1269  var.lb() > var.ub()) {
1270  return prefix + "∅"; // Empty set.
1271  }
1272  // Special case: integer variable with at most two possible values
1273  // (and potentially none).
1274  if (var.integer() && var.ub() - var.lb() <= 1) {
1275  const int64 lb = static_cast<int64>(ceil(var.lb()));
1276  const int64 ub = static_cast<int64>(floor(var.ub()));
1277  if (lb > ub) {
1278  return prefix + "∅";
1279  } else if (lb == ub) {
1280  return absl::StrFormat("%s{ %d }", prefix.c_str(), lb);
1281  } else {
1282  return absl::StrFormat("%s{ %d, %d }", prefix.c_str(), lb, ub);
1283  }
1284  }
1285  // Special case: single (non-infinite) real value.
1286  if (var.lb() == var.ub()) {
1287  return absl::StrFormat("%s{ %f }", prefix.c_str(), var.lb());
1288  }
1289  return prefix + (var.integer() ? "Integer" : "Real") + " in " +
1290  (var.lb() <= -MPSolver::infinity()
1291  ? std::string("]-∞")
1292  : absl::StrFormat("[%f", var.lb())) +
1293  ", " +
1294  (var.ub() >= MPSolver::infinity() ? std::string("+∞[")
1295  : absl::StrFormat("%f]", var.ub()));
1296 }
1297 
1298 std::string PrettyPrintConstraint(const MPConstraint& constraint) {
1299  std::string prefix = "Constraint '" + constraint.name() + "': ";
1300  if (constraint.lb() >= MPSolver::infinity() ||
1301  constraint.ub() <= -MPSolver::infinity() ||
1302  constraint.lb() > constraint.ub()) {
1303  return prefix + "ALWAYS FALSE";
1304  }
1305  if (constraint.lb() <= -MPSolver::infinity() &&
1306  constraint.ub() >= MPSolver::infinity()) {
1307  return prefix + "ALWAYS TRUE";
1308  }
1309  prefix += "<linear expr>";
1310  // Equality.
1311  if (constraint.lb() == constraint.ub()) {
1312  return absl::StrFormat("%s = %f", prefix.c_str(), constraint.lb());
1313  }
1314  // Inequalities.
1315  if (constraint.lb() <= -MPSolver::infinity()) {
1316  return absl::StrFormat("%s ≤ %f", prefix.c_str(), constraint.ub());
1317  }
1318  if (constraint.ub() >= MPSolver::infinity()) {
1319  return absl::StrFormat("%s ≥ %f", prefix.c_str(), constraint.lb());
1320  }
1321  return absl::StrFormat("%s ∈ [%f, %f]", prefix.c_str(), constraint.lb(),
1322  constraint.ub());
1323 }
1324 } // namespace
1325 
1327  interface_->ExtractModel();
1328  for (MPVariable* const variable : variables_) {
1329  const double value = variable->solution_value();
1330  if (std::isnan(value)) {
1331  return absl::InvalidArgumentError(
1332  absl::StrCat("NaN value for ", PrettyPrintVar(*variable)));
1333  }
1334  if (value < variable->lb()) {
1335  variable->set_solution_value(variable->lb());
1336  } else if (value > variable->ub()) {
1337  variable->set_solution_value(variable->ub());
1338  }
1339  }
1340  interface_->sync_status_ = MPSolverInterface::SOLUTION_SYNCHRONIZED;
1341  return absl::OkStatus();
1342 }
1343 
1344 std::vector<double> MPSolver::ComputeConstraintActivities() const {
1345  // TODO(user): test this failure case.
1346  if (!interface_->CheckSolutionIsSynchronizedAndExists()) return {};
1347  std::vector<double> activities(constraints_.size(), 0.0);
1348  for (int i = 0; i < constraints_.size(); ++i) {
1349  const MPConstraint& constraint = *constraints_[i];
1350  AccurateSum<double> sum;
1351  for (const auto& entry : constraint.coefficients_) {
1352  sum.Add(entry.first->solution_value() * entry.second);
1353  }
1354  activities[i] = sum.Value();
1355  }
1356  return activities;
1357 }
1358 
1359 // TODO(user): split.
1360 bool MPSolver::VerifySolution(double tolerance, bool log_errors) const {
1361  double max_observed_error = 0;
1362  if (tolerance < 0) tolerance = infinity();
1363  int num_errors = 0;
1364 
1365  // Verify variables.
1366  for (int i = 0; i < variables_.size(); ++i) {
1367  const MPVariable& var = *variables_[i];
1368  const double value = var.solution_value();
1369  // Check for NaN.
1370  if (std::isnan(value)) {
1371  ++num_errors;
1372  max_observed_error = infinity();
1373  LOG_IF(ERROR, log_errors) << "NaN value for " << PrettyPrintVar(var);
1374  continue;
1375  }
1376  // Check lower bound.
1377  if (var.lb() != -infinity()) {
1378  if (value < var.lb() - tolerance) {
1379  ++num_errors;
1380  max_observed_error = std::max(max_observed_error, var.lb() - value);
1381  LOG_IF(ERROR, log_errors)
1382  << "Value " << value << " too low for " << PrettyPrintVar(var);
1383  }
1384  }
1385  // Check upper bound.
1386  if (var.ub() != infinity()) {
1387  if (value > var.ub() + tolerance) {
1388  ++num_errors;
1389  max_observed_error = std::max(max_observed_error, value - var.ub());
1390  LOG_IF(ERROR, log_errors)
1391  << "Value " << value << " too high for " << PrettyPrintVar(var);
1392  }
1393  }
1394  // Check integrality.
1395  if (IsMIP() && var.integer()) {
1396  if (fabs(value - round(value)) > tolerance) {
1397  ++num_errors;
1398  max_observed_error =
1399  std::max(max_observed_error, fabs(value - round(value)));
1400  LOG_IF(ERROR, log_errors)
1401  << "Non-integer value " << value << " for " << PrettyPrintVar(var);
1402  }
1403  }
1404  }
1405  if (!IsMIP() && HasIntegerVariables()) {
1406  LOG_IF(INFO, log_errors) << "Skipped variable integrality check, because "
1407  << "a continuous relaxation of the model was "
1408  << "solved (i.e., the selected solver does not "
1409  << "support integer variables).";
1410  }
1411 
1412  // Verify constraints.
1413  const std::vector<double> activities = ComputeConstraintActivities();
1414  for (int i = 0; i < constraints_.size(); ++i) {
1415  const MPConstraint& constraint = *constraints_[i];
1416  const double activity = activities[i];
1417  // Re-compute the activity with a inaccurate summing algorithm.
1418  double inaccurate_activity = 0.0;
1419  for (const auto& entry : constraint.coefficients_) {
1420  inaccurate_activity += entry.first->solution_value() * entry.second;
1421  }
1422  // Catch NaNs.
1423  if (std::isnan(activity) || std::isnan(inaccurate_activity)) {
1424  ++num_errors;
1425  max_observed_error = infinity();
1426  LOG_IF(ERROR, log_errors)
1427  << "NaN value for " << PrettyPrintConstraint(constraint);
1428  continue;
1429  }
1430  // Check bounds.
1431  if (constraint.indicator_variable() == nullptr ||
1432  std::round(constraint.indicator_variable()->solution_value()) ==
1433  constraint.indicator_value()) {
1434  if (constraint.lb() != -infinity()) {
1435  if (activity < constraint.lb() - tolerance) {
1436  ++num_errors;
1437  max_observed_error =
1438  std::max(max_observed_error, constraint.lb() - activity);
1439  LOG_IF(ERROR, log_errors)
1440  << "Activity " << activity << " too low for "
1441  << PrettyPrintConstraint(constraint);
1442  } else if (inaccurate_activity < constraint.lb() - tolerance) {
1443  LOG_IF(WARNING, log_errors)
1444  << "Activity " << activity << ", computed with the (inaccurate)"
1445  << " standard sum of its terms, is too low for "
1446  << PrettyPrintConstraint(constraint);
1447  }
1448  }
1449  if (constraint.ub() != infinity()) {
1450  if (activity > constraint.ub() + tolerance) {
1451  ++num_errors;
1452  max_observed_error =
1453  std::max(max_observed_error, activity - constraint.ub());
1454  LOG_IF(ERROR, log_errors)
1455  << "Activity " << activity << " too high for "
1456  << PrettyPrintConstraint(constraint);
1457  } else if (inaccurate_activity > constraint.ub() + tolerance) {
1458  LOG_IF(WARNING, log_errors)
1459  << "Activity " << activity << ", computed with the (inaccurate)"
1460  << " standard sum of its terms, is too high for "
1461  << PrettyPrintConstraint(constraint);
1462  }
1463  }
1464  }
1465  }
1466 
1467  // Verify that the objective value wasn't reported incorrectly.
1468  const MPObjective& objective = Objective();
1469  AccurateSum<double> objective_sum;
1470  objective_sum.Add(objective.offset());
1471  double inaccurate_objective_value = objective.offset();
1472  for (const auto& entry : objective.coefficients_) {
1473  const double term = entry.first->solution_value() * entry.second;
1474  objective_sum.Add(term);
1475  inaccurate_objective_value += term;
1476  }
1477  const double actual_objective_value = objective_sum.Value();
1479  objective.Value(), actual_objective_value, tolerance, tolerance)) {
1480  ++num_errors;
1481  max_observed_error = std::max(
1482  max_observed_error, fabs(actual_objective_value - objective.Value()));
1483  LOG_IF(ERROR, log_errors)
1484  << "Objective value " << objective.Value() << " isn't accurate"
1485  << ", it should be " << actual_objective_value
1486  << " (delta=" << actual_objective_value - objective.Value() << ").";
1487  } else if (!AreWithinAbsoluteOrRelativeTolerances(objective.Value(),
1488  inaccurate_objective_value,
1489  tolerance, tolerance)) {
1490  LOG_IF(WARNING, log_errors)
1491  << "Objective value " << objective.Value() << " doesn't correspond"
1492  << " to the value computed with the standard (and therefore inaccurate)"
1493  << " sum of its terms.";
1494  }
1495  if (num_errors > 0) {
1496  LOG_IF(ERROR, log_errors)
1497  << "There were " << num_errors << " errors above the tolerance ("
1498  << tolerance << "), the largest was " << max_observed_error;
1499  return false;
1500  }
1501  return true;
1502 }
1503 
1504 bool MPSolver::OutputIsEnabled() const { return !interface_->quiet(); }
1505 
1506 void MPSolver::EnableOutput() { interface_->set_quiet(false); }
1507 
1508 void MPSolver::SuppressOutput() { interface_->set_quiet(true); }
1509 
1510 int64 MPSolver::iterations() const { return interface_->iterations(); }
1511 
1512 int64 MPSolver::nodes() const { return interface_->nodes(); }
1513 
1515  return interface_->ComputeExactConditionNumber();
1516 }
1517 
1519  if (var == nullptr) return false;
1520  if (var->index() >= 0 && var->index() < variables_.size()) {
1521  // Then, verify that the variable with this index has the same address.
1522  return variables_[var->index()] == var;
1523  }
1524  return false;
1525 }
1526 
1528  std::string* model_str) const {
1529  MPModelProto proto;
1531  MPModelExportOptions options;
1532  options.obfuscate = obfuscate;
1533  const auto status_or =
1535  *model_str = status_or.value_or("");
1536  return status_or.ok();
1537 }
1538 
1539 bool MPSolver::ExportModelAsMpsFormat(bool fixed_format, bool obfuscate,
1540  std::string* model_str) const {
1541  // if (fixed_format) {
1542  // LOG_EVERY_N_SEC(WARNING, 10)
1543  // << "Fixed format is deprecated. Using free format instead.";
1544  //
1545 
1546  MPModelProto proto;
1548  MPModelExportOptions options;
1549  options.obfuscate = obfuscate;
1550  const auto status_or =
1552  *model_str = status_or.value_or("");
1553  return status_or.ok();
1554 }
1555 
1556 void MPSolver::SetHint(std::vector<std::pair<const MPVariable*, double>> hint) {
1557  for (const auto& var_value_pair : hint) {
1558  CHECK(OwnsVariable(var_value_pair.first))
1559  << "hint variable does not belong to this solver";
1560  }
1561  solution_hint_ = std::move(hint);
1562 }
1563 
1564 void MPSolver::GenerateVariableNameIndex() const {
1565  if (variable_name_to_index_) return;
1566  variable_name_to_index_ = absl::flat_hash_map<std::string, int>();
1567  for (const MPVariable* const var : variables_) {
1568  gtl::InsertOrDie(&*variable_name_to_index_, var->name(), var->index());
1569  }
1570 }
1571 
1572 void MPSolver::GenerateConstraintNameIndex() const {
1573  if (constraint_name_to_index_) return;
1574  constraint_name_to_index_ = absl::flat_hash_map<std::string, int>();
1575  for (const MPConstraint* const cst : constraints_) {
1576  gtl::InsertOrDie(&*constraint_name_to_index_, cst->name(), cst->index());
1577  }
1578 }
1579 
1580 bool MPSolver::NextSolution() { return interface_->NextSolution(); }
1581 
1582 void MPSolver::SetCallback(MPCallback* mp_callback) {
1583  interface_->SetCallback(mp_callback);
1584 }
1585 
1587  return interface_->SupportsCallbacks();
1588 }
1589 
1590 bool MPSolverResponseStatusIsRpcError(MPSolverResponseStatus status) {
1591  switch (status) {
1592  // Cases that don't yield an RPC error when they happen on the server.
1593  case MPSOLVER_OPTIMAL:
1594  case MPSOLVER_FEASIBLE:
1595  case MPSOLVER_INFEASIBLE:
1596  case MPSOLVER_NOT_SOLVED:
1597  case MPSOLVER_UNBOUNDED:
1598  case MPSOLVER_ABNORMAL:
1599  case MPSOLVER_UNKNOWN_STATUS:
1600  return false;
1601  // Cases that should never happen with the linear solver server. We prefer
1602  // to consider those as "not RPC errors".
1603  case MPSOLVER_MODEL_IS_VALID:
1604  return false;
1605  // Cases that yield an RPC error when they happen on the server.
1606  case MPSOLVER_MODEL_INVALID:
1607  case MPSOLVER_MODEL_INVALID_SOLUTION_HINT:
1608  case MPSOLVER_MODEL_INVALID_SOLVER_PARAMETERS:
1609  case MPSOLVER_SOLVER_TYPE_UNAVAILABLE:
1610  return true;
1611  }
1612  LOG(DFATAL)
1613  << "MPSolverResponseStatusIsRpcError() called with invalid status "
1614  << "(value: " << status << ")";
1615  return false;
1616 }
1617 
1618 // ---------- MPSolverInterface ----------
1619 
1621 
1622 // TODO(user): Initialize objective value and bound to +/- inf (depending on
1623 // optimization direction).
1625  : solver_(solver),
1626  sync_status_(MODEL_SYNCHRONIZED),
1627  result_status_(MPSolver::NOT_SOLVED),
1628  maximize_(false),
1629  last_constraint_index_(0),
1630  last_variable_index_(0),
1631  objective_value_(0.0),
1632  best_objective_bound_(0.0),
1633  quiet_(true) {}
1634 
1636 
1637 void MPSolverInterface::Write(const std::string& filename) {
1638  LOG(WARNING) << "Writing model not implemented in this solver interface.";
1639 }
1640 
1642  switch (sync_status_) {
1643  case MUST_RELOAD: {
1646  ExtractObjective();
1647 
1648  last_constraint_index_ = solver_->constraints_.size();
1649  last_variable_index_ = solver_->variables_.size();
1651  break;
1652  }
1653  case MODEL_SYNCHRONIZED: {
1654  // Everything has already been extracted.
1655  DCHECK_EQ(last_constraint_index_, solver_->constraints_.size());
1656  DCHECK_EQ(last_variable_index_, solver_->variables_.size());
1657  break;
1658  }
1659  case SOLUTION_SYNCHRONIZED: {
1660  // Nothing has changed since last solve.
1661  DCHECK_EQ(last_constraint_index_, solver_->constraints_.size());
1662  DCHECK_EQ(last_variable_index_, solver_->variables_.size());
1663  break;
1664  }
1665  }
1666 }
1667 
1668 // TODO(user): remove this method.
1673  solver_->variable_is_extracted_.assign(solver_->variables_.size(), false);
1674  solver_->constraint_is_extracted_.assign(solver_->constraints_.size(), false);
1675 }
1676 
1679  LOG(DFATAL)
1680  << "The model has been changed since the solution was last computed."
1681  << " MPSolverInterface::sync_status_ = " << sync_status_;
1682  return false;
1683  }
1684  return true;
1685 }
1686 
1687 // Default version that can be overwritten by a solver-specific
1688 // version to accommodate for the quirks of each solver.
1692  LOG(DFATAL) << "No solution exists. MPSolverInterface::result_status_ = "
1693  << result_status_;
1694  return false;
1695  }
1696  return true;
1697 }
1698 
1700  if (!CheckSolutionIsSynchronizedAndExists()) return 0;
1701  return objective_value_;
1702 }
1703 
1705  const double trivial_worst_bound =
1706  maximize_ ? -std::numeric_limits<double>::infinity()
1707  : std::numeric_limits<double>::infinity();
1708  if (!IsMIP()) {
1709  LOG(DFATAL) << "Best objective bound only available for discrete problems.";
1710  return trivial_worst_bound;
1711  }
1712  if (!CheckSolutionIsSynchronized()) {
1713  return trivial_worst_bound;
1714  }
1715  // Special case for empty model.
1716  if (solver_->variables_.empty() && solver_->constraints_.empty()) {
1717  return solver_->Objective().offset();
1718  }
1719  return best_objective_bound_;
1720 }
1721 
1725  }
1726 }
1727 
1729  // Override this method in interfaces that actually support it.
1730  LOG(DFATAL) << "ComputeExactConditionNumber not implemented for "
1731  << ProtoEnumToString<MPModelRequest::SolverType>(
1732  static_cast<MPModelRequest::SolverType>(
1733  solver_->ProblemType()));
1734  return 0.0;
1735 }
1736 
1738  // TODO(user): Overhaul the code that sets parameters to enable changing
1739  // GLOP parameters without issuing warnings.
1740  // By default, we let GLOP keep its own default tolerance, much more accurate
1741  // than for the rest of the solvers.
1742  //
1747  }
1749  // TODO(user): In the future, we could distinguish between the
1750  // algorithm to solve the root LP and the algorithm to solve node
1751  // LPs. Not sure if underlying solvers support it.
1755  }
1756 }
1757 
1762  }
1763 }
1764 
1767  LOG(WARNING) << "Trying to set an unsupported parameter: " << param << ".";
1768 }
1771  LOG(WARNING) << "Trying to set an unsupported parameter: " << param << ".";
1772 }
1774  MPSolverParameters::DoubleParam param, double value) {
1775  LOG(WARNING) << "Trying to set a supported parameter: " << param
1776  << " to an unsupported value: " << value;
1777 }
1780  LOG(WARNING) << "Trying to set a supported parameter: " << param
1781  << " to an unsupported value: " << value;
1782 }
1783 
1784 absl::Status MPSolverInterface::SetNumThreads(int num_threads) {
1785  return absl::UnimplementedError(
1786  absl::StrFormat("SetNumThreads() not supported by %s.", SolverVersion()));
1787 }
1788 
1790  const std::string& parameters) {
1791  if (parameters.empty()) {
1792  return true;
1793  }
1794 
1795  LOG(WARNING) << "SetSolverSpecificParametersAsString() not supported by "
1796  << SolverVersion();
1797  return false;
1798 }
1799 
1800 // ---------- MPSolverParameters ----------
1801 
1802 const double MPSolverParameters::kDefaultRelativeMipGap = 1e-4;
1803 // For the primal and dual tolerances, choose the same default as CLP and GLPK.
1806 const double MPSolverParameters::kDefaultDualTolerance = 1e-7;
1812 
1817 
1818 // The constructor sets all parameters to their default value.
1820  : relative_mip_gap_value_(kDefaultRelativeMipGap),
1821  primal_tolerance_value_(kDefaultPrimalTolerance),
1822  dual_tolerance_value_(kDefaultDualTolerance),
1823  presolve_value_(kDefaultPresolve),
1824  scaling_value_(kDefaultIntegerParamValue),
1825  lp_algorithm_value_(kDefaultIntegerParamValue),
1826  incrementality_value_(kDefaultIncrementality),
1827  lp_algorithm_is_default_(true) {}
1828 
1830  double value) {
1831  switch (param) {
1832  case RELATIVE_MIP_GAP: {
1833  relative_mip_gap_value_ = value;
1834  break;
1835  }
1836  case PRIMAL_TOLERANCE: {
1837  primal_tolerance_value_ = value;
1838  break;
1839  }
1840  case DUAL_TOLERANCE: {
1841  dual_tolerance_value_ = value;
1842  break;
1843  }
1844  default: {
1845  LOG(ERROR) << "Trying to set an unknown parameter: " << param << ".";
1846  }
1847  }
1848 }
1849 
1851  int value) {
1852  switch (param) {
1853  case PRESOLVE: {
1854  if (value != PRESOLVE_OFF && value != PRESOLVE_ON) {
1855  LOG(ERROR) << "Trying to set a supported parameter: " << param
1856  << " to an unknown value: " << value;
1857  }
1858  presolve_value_ = value;
1859  break;
1860  }
1861  case SCALING: {
1862  if (value != SCALING_OFF && value != SCALING_ON) {
1863  LOG(ERROR) << "Trying to set a supported parameter: " << param
1864  << " to an unknown value: " << value;
1865  }
1866  scaling_value_ = value;
1867  break;
1868  }
1869  case LP_ALGORITHM: {
1870  if (value != DUAL && value != PRIMAL && value != BARRIER) {
1871  LOG(ERROR) << "Trying to set a supported parameter: " << param
1872  << " to an unknown value: " << value;
1873  }
1874  lp_algorithm_value_ = value;
1875  lp_algorithm_is_default_ = false;
1876  break;
1877  }
1878  case INCREMENTALITY: {
1880  LOG(ERROR) << "Trying to set a supported parameter: " << param
1881  << " to an unknown value: " << value;
1882  }
1883  incrementality_value_ = value;
1884  break;
1885  }
1886  default: {
1887  LOG(ERROR) << "Trying to set an unknown parameter: " << param << ".";
1888  }
1889  }
1890 }
1891 
1894  switch (param) {
1895  case RELATIVE_MIP_GAP: {
1896  relative_mip_gap_value_ = kDefaultRelativeMipGap;
1897  break;
1898  }
1899  case PRIMAL_TOLERANCE: {
1900  primal_tolerance_value_ = kDefaultPrimalTolerance;
1901  break;
1902  }
1903  case DUAL_TOLERANCE: {
1904  dual_tolerance_value_ = kDefaultDualTolerance;
1905  break;
1906  }
1907  default: {
1908  LOG(ERROR) << "Trying to reset an unknown parameter: " << param << ".";
1909  }
1910  }
1911 }
1912 
1915  switch (param) {
1916  case PRESOLVE: {
1917  presolve_value_ = kDefaultPresolve;
1918  break;
1919  }
1920  case SCALING: {
1921  scaling_value_ = kDefaultIntegerParamValue;
1922  break;
1923  }
1924  case LP_ALGORITHM: {
1925  lp_algorithm_is_default_ = true;
1926  break;
1927  }
1928  case INCREMENTALITY: {
1929  incrementality_value_ = kDefaultIncrementality;
1930  break;
1931  }
1932  default: {
1933  LOG(ERROR) << "Trying to reset an unknown parameter: " << param << ".";
1934  }
1935  }
1936 }
1937 
1946 }
1947 
1949  MPSolverParameters::DoubleParam param) const {
1950  switch (param) {
1951  case RELATIVE_MIP_GAP: {
1952  return relative_mip_gap_value_;
1953  }
1954  case PRIMAL_TOLERANCE: {
1955  return primal_tolerance_value_;
1956  }
1957  case DUAL_TOLERANCE: {
1958  return dual_tolerance_value_;
1959  }
1960  default: {
1961  LOG(ERROR) << "Trying to get an unknown parameter: " << param << ".";
1962  return kUnknownDoubleParamValue;
1963  }
1964  }
1965 }
1966 
1968  MPSolverParameters::IntegerParam param) const {
1969  switch (param) {
1970  case PRESOLVE: {
1971  return presolve_value_;
1972  }
1973  case LP_ALGORITHM: {
1974  if (lp_algorithm_is_default_) return kDefaultIntegerParamValue;
1975  return lp_algorithm_value_;
1976  }
1977  case INCREMENTALITY: {
1978  return incrementality_value_;
1979  }
1980  case SCALING: {
1981  return scaling_value_;
1982  }
1983  default: {
1984  LOG(ERROR) << "Trying to get an unknown parameter: " << param << ".";
1986  }
1987  }
1988 }
1989 
1990 } // namespace operations_research
int64 max
Definition: alldiff_cst.cc:139
#define DLOG_IF(severity, condition)
Definition: base/logging.h:877
#define LOG_IF(severity, condition)
Definition: base/logging.h:479
#define CHECK(condition)
Definition: base/logging.h:495
#define DCHECK_LE(val1, val2)
Definition: base/logging.h:887
#define DCHECK_NE(val1, val2)
Definition: base/logging.h:886
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#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 Add(const FpNumber &value)
Definition: accurate_sum.h:29
LinearExpr models a quantity that is linear in the decision variables (MPVariable) of an optimization...
Definition: linear_expr.h:114
const absl::flat_hash_map< const MPVariable *, double > & terms() const
Definition: linear_expr.h:143
An expression of the form:
Definition: linear_expr.h:192
const LinearExpr & linear_expr() const
Definition: linear_expr.h:206
The class for constraints of a Mathematical Programming (MP) model.
void SetBounds(double lb, double ub)
Sets both the lower and upper bounds.
void SetCoefficient(const MPVariable *const var, double coeff)
Sets the coefficient of the variable on the constraint.
double GetCoefficient(const MPVariable *const var) const
Gets the coefficient of a given variable on the constraint (which is 0 if the variable does not appea...
double ub() const
Returns the upper bound.
const MPVariable * indicator_variable() const
void Clear()
Clears all variables and coefficients. Does not clear the bounds.
bool is_lazy() const
Advanced usage: returns true if the constraint is "lazy" (see below).
double lb() const
Returns the lower bound.
const std::string & name() const
Returns the name of the constraint.
MPSolver::BasisStatus basis_status() const
Advanced usage: returns the basis status of the constraint.
double dual_value() const
Advanced usage: returns the dual value of the constraint in the current solution (only available for ...
A class to express a linear objective.
void SetCoefficient(const MPVariable *const var, double coeff)
Sets the coefficient of the variable in the objective.
double GetCoefficient(const MPVariable *const var) const
Gets the coefficient of a given variable in the objective.
void SetOffset(double value)
Sets the constant term in the objective.
bool maximization() const
Is the optimization direction set to maximize?
void OptimizeLinearExpr(const LinearExpr &linear_expr, bool is_maximization)
Resets the current objective to take the value of linear_expr, and sets the objective direction to ma...
void AddLinearExpr(const LinearExpr &linear_expr)
Adds linear_expr to the current objective, does not change the direction.
double Value() const
Returns the objective value of the best solution found so far.
double offset() const
Gets the constant term in the objective.
double BestBound() const
Returns the best objective bound.
bool minimization() const
Is the optimization direction set to minimize?
void Clear()
Clears the offset, all variables and coefficients, and the optimization direction.
void SetMinimization()
Sets the optimization direction to minimize.
void SetOptimizationDirection(bool maximize)
Sets the optimization direction (maximize: true or minimize: false).
This mathematical programming (MP) solver class is the main class though which users build and solve ...
void FillSolutionResponseProto(MPSolutionResponse *response) const
Encodes the current solution in a solution response protocol buffer.
int NumConstraints() const
Returns the number of constraints.
static OptimizationProblemType ParseSolverTypeOrDie(const std::string &solver_id)
Parses the name of the solver and returns the correct optimization type or dies.
const std::string & Name() const
Returns the name of the model set at construction.
void MakeBoolVarArray(int nb, const std::string &name, std::vector< MPVariable * > *vars)
Creates an array of boolean variables.
MPObjective * MutableObjective()
Returns the mutable objective object.
bool VerifySolution(double tolerance, bool log_errors) const
Advanced usage: Verifies the correctness of the solution.
void Reset()
Advanced usage: resets extracted model to solve from scratch.
MPVariable * LookupVariableOrNull(const std::string &var_name) const
Looks up a variable by name, and returns nullptr if it does not exist.
void SetStartingLpBasis(const std::vector< MPSolver::BasisStatus > &variable_statuses, const std::vector< MPSolver::BasisStatus > &constraint_statuses)
Advanced usage: Incrementality.
static bool SupportsProblemType(OptimizationProblemType problem_type)
Whether the given problem type is supported (this will depend on the targets that you linked).
static MPSolver * CreateSolver(const std::string &solver_id)
Recommended factory method to create a MPSolver instance, especially in non C++ languages.
MPVariable * MakeBoolVar(const std::string &name)
Creates a boolean variable.
void SetHint(std::vector< std::pair< const MPVariable *, double > > hint)
Sets a hint for solution.
double ComputeExactConditionNumber() const
Advanced usage: computes the exact condition number of the current scaled basis: L1norm(B) * L1norm(i...
const MPObjective & Objective() const
Returns the objective object.
int64 nodes() const
Returns the number of branch-and-bound nodes evaluated during the solve.
ResultStatus
The status of solving the problem.
@ FEASIBLE
feasible, or stopped by limit.
@ NOT_SOLVED
not been solved yet.
@ INFEASIBLE
proven infeasible.
@ UNBOUNDED
proven unbounded.
@ ABNORMAL
abnormal, i.e., error of some kind.
@ MODEL_INVALID
the model is trivially invalid (NaN coefficients, etc).
static void SolveWithProto(const MPModelRequest &model_request, MPSolutionResponse *response)
Solves the model encoded by a MPModelRequest protocol buffer and fills the solution encoded as a MPSo...
void MakeNumVarArray(int nb, double lb, double ub, const std::string &name, std::vector< MPVariable * > *vars)
Creates an array of continuous variables.
void MakeVarArray(int nb, double lb, double ub, bool integer, const std::string &name_prefix, std::vector< MPVariable * > *vars)
Creates an array of variables.
void * underlying_solver()
Advanced usage: returns the underlying solver.
OptimizationProblemType
The type of problems (LP or MIP) that will be solved and the underlying solver (GLOP,...
bool SetSolverSpecificParametersAsString(const std::string &parameters)
Advanced usage: pass solver specific parameters in text format.
absl::Status SetNumThreads(int num_threads)
Sets the number of threads to use by the underlying solver.
std::string SolverVersion() const
Returns a string describing the underlying solver and its version.
void ExportModelToProto(MPModelProto *output_model) const
Exports model to protocol buffer.
int64 iterations() const
Returns the number of simplex iterations.
void MakeIntVarArray(int nb, double lb, double ub, const std::string &name, std::vector< MPVariable * > *vars)
Creates an array of integer variables.
std::vector< double > ComputeConstraintActivities() const
Advanced usage: compute the "activities" of all constraints, which are the sums of their linear terms...
static double infinity()
Infinity.
static bool ParseSolverType(absl::string_view solver_id, OptimizationProblemType *type)
Parses the name of the solver.
int NumVariables() const
Returns the number of variables.
absl::Status ClampSolutionWithinBounds()
Resets values of out of bound variables to the corresponding bound and returns an error if any of the...
bool OwnsVariable(const MPVariable *var) const
void Clear()
Clears the objective (including the optimization direction), all variables and constraints.
bool ExportModelAsLpFormat(bool obfuscate, std::string *model_str) const
Shortcuts to the homonymous MPModelProtoExporter methods, via exporting to a MPModelProto with Export...
void Write(const std::string &file_name)
Writes the model using the solver internal write function.
MPConstraint * MakeRowConstraint()
Creates a constraint with -infinity and +infinity bounds.
void SetCallback(MPCallback *mp_callback)
MPSolverResponseStatus LoadModelFromProto(const MPModelProto &input_model, std::string *error_message)
Loads model from protocol buffer.
bool OutputIsEnabled() const
Controls (or queries) the amount of output produced by the underlying solver.
bool ExportModelAsMpsFormat(bool fixed_format, bool obfuscate, std::string *model_str) const
ABSL_MUST_USE_RESULT bool NextSolution()
Some solvers (MIP only, not LP) can produce multiple solutions to the problem.
MPVariable * MakeVar(double lb, double ub, bool integer, const std::string &name)
Creates a variable with the given bounds, integrality requirement and name.
MPConstraint * LookupConstraintOrNull(const std::string &constraint_name) const
Looks up a constraint by name, and returns nullptr if it does not exist.
MPVariable * MakeNumVar(double lb, double ub, const std::string &name)
Creates a continuous variable.
bool InterruptSolve()
Interrupts the Solve() execution to terminate processing if possible.
MPVariable * MakeIntVar(double lb, double ub, const std::string &name)
Creates an integer variable.
MPSolver(const std::string &name, OptimizationProblemType problem_type)
Create a solver with the given name and underlying solver backend.
ResultStatus Solve()
Solves the problem using the default parameter values.
void EnableOutput()
Enables solver logging.
void SuppressOutput()
Suppresses solver logging.
absl::Status LoadSolutionFromProto(const MPSolutionResponse &response, double tolerance=kDefaultPrimalTolerance)
Load a solution encoded in a protocol buffer onto this solver for easy access via the MPSolver interf...
MPSolverResponseStatus LoadModelFromProtoWithUniqueNamesOrDie(const MPModelProto &input_model, std::string *error_message)
Loads model from protocol buffer.
virtual OptimizationProblemType ProblemType() const
Returns the optimization problem type set at construction.
BasisStatus
Advanced usage: possible basis status values for a variable and the slack variable of a linear constr...
void SetTimeLimit(absl::Duration time_limit)
virtual void SetLpAlgorithm(int value)=0
virtual void SetIntegerParamToUnsupportedValue(MPSolverParameters::IntegerParam param, int value)
void SetUnsupportedDoubleParam(MPSolverParameters::DoubleParam param)
void SetMIPParameters(const MPSolverParameters &param)
virtual bool IsContinuous() const =0
virtual double ComputeExactConditionNumber() const
virtual void Write(const std::string &filename)
MPSolverInterface(MPSolver *const solver)
bool constraint_is_extracted(int ct_index) const
virtual void SetVariableBounds(int index, double lb, double ub)=0
virtual void SetPrimalTolerance(double value)=0
virtual void BranchingPriorityChangedForVariable(int var_index)
virtual void SetRelativeMipGap(double value)=0
virtual void SetOptimizationDirection(bool maximize)=0
virtual bool SetSolverSpecificParametersAsString(const std::string &parameters)
virtual MPSolver::BasisStatus column_status(int variable_index) const =0
virtual MPSolver::BasisStatus row_status(int constraint_index) const =0
virtual std::string SolverVersion() const =0
virtual absl::Status SetNumThreads(int num_threads)
virtual void ClearConstraint(MPConstraint *const constraint)=0
virtual void SetObjectiveOffset(double value)=0
virtual void SetVariableInteger(int index, bool integer)=0
bool variable_is_extracted(int var_index) const
virtual void SetDualTolerance(double value)=0
virtual void SetPresolveMode(int value)=0
virtual void SetUnsupportedIntegerParam(MPSolverParameters::IntegerParam param)
virtual void SetCoefficient(MPConstraint *const constraint, const MPVariable *const variable, double new_value, double old_value)=0
virtual void SetObjectiveCoefficient(const MPVariable *const variable, double coefficient)=0
void SetDoubleParamToUnsupportedValue(MPSolverParameters::DoubleParam param, double value)
virtual void SetConstraintBounds(int index, double lb, double ub)=0
void SetCommonParameters(const MPSolverParameters &param)
This class stores parameter settings for LP and MIP solvers.
void ResetIntegerParam(MPSolverParameters::IntegerParam param)
Sets an integer parameter to its default value (default value defined in MPSolverParameters if it exi...
void SetDoubleParam(MPSolverParameters::DoubleParam param, double value)
Sets a double parameter to a specific value.
IncrementalityValues
Advanced usage: Incrementality options.
@ INCREMENTALITY_OFF
Start solve from scratch.
@ INCREMENTALITY_ON
Reuse results from previous solve as much as the underlying solver allows.
static const IncrementalityValues kDefaultIncrementality
void Reset()
Sets all parameters to their default value.
DoubleParam
Enumeration of parameters that take continuous values.
@ DUAL_TOLERANCE
Advanced usage: tolerance for dual feasibility of basic solutions.
@ PRIMAL_TOLERANCE
Advanced usage: tolerance for primal feasibility of basic solutions.
@ RELATIVE_MIP_GAP
Limit for relative MIP gap.
static const PresolveValues kDefaultPresolve
double GetDoubleParam(MPSolverParameters::DoubleParam param) const
Returns the value of a double parameter.
IntegerParam
Enumeration of parameters that take integer or categorical values.
@ LP_ALGORITHM
Algorithm to solve linear programs.
@ SCALING
Advanced usage: enable or disable matrix scaling.
@ PRESOLVE
Advanced usage: presolve mode.
@ INCREMENTALITY
Advanced usage: incrementality from one solve to the next.
PresolveValues
For each categorical parameter, enumeration of possible values.
void SetIntegerParam(MPSolverParameters::IntegerParam param, int value)
Sets a integer parameter to a specific value.
int GetIntegerParam(MPSolverParameters::IntegerParam param) const
Returns the value of an integer parameter.
MPSolverParameters()
The constructor sets all parameters to their default value.
void ResetDoubleParam(MPSolverParameters::DoubleParam param)
Sets a double parameter to its default value (default value defined in MPSolverParameters if it exist...
The class for variables of a Mathematical Programming (MP) model.
void SetBounds(double lb, double ub)
Sets both the lower and upper bounds.
double unrounded_solution_value() const
Advanced usage: unrounded solution value.
void SetBranchingPriority(int priority)
double ub() const
Returns the upper bound.
double reduced_cost() const
Advanced usage: returns the reduced cost of the variable in the current solution (only available for ...
void SetInteger(bool integer)
Sets the integrality requirement of the variable.
bool integer() const
Returns the integrality requirement of the variable.
int index() const
Returns the index of the variable in the MPSolver::variables_.
double lb() const
Returns the lower bound.
const std::string & name() const
Returns the name of the variable.
double solution_value() const
Returns the value of the variable in the current solution.
MPSolver::BasisStatus basis_status() const
Advanced usage: returns the basis status of the variable in the current solution (only available for ...
virtual std::string name() const
Object naming.
SatParameters parameters
CpModelProto proto
SharedResponseManager * response
const Constraint * ct
int64 value
IntVar * var
Definition: expr_array.cc:1858
int64_t int64
absl::string_view name
ABSL_FLAG(bool, verify_solution, false, "Systematically verify the solution when calling Solve()" ", and change the return value of Solve() to ABNORMAL if" " an error was detected.")
MPSolver::OptimizationProblemType problem_type
A C++ wrapper that provides a simple and unified interface to several linear programming and mixed in...
const int WARNING
Definition: log_severity.h:31
const int INFO
Definition: log_severity.h:31
const int ERROR
Definition: log_severity.h:32
const int FATAL
Definition: log_severity.h:32
Definition: cleanup.h:22
void STLDeleteElements(T *container)
Definition: stl_util.h:372
void InsertOrDie(Collection *const collection, const typename Collection::value_type &value)
Definition: map_util.h:135
const Collection::value_type::second_type & FindWithDefault(const Collection &collection, const typename Collection::value_type::first_type &key, const typename Collection::value_type::second_type &value)
Definition: map_util.h:26
std::function< int64(const Model &)> Value(IntegerVariable v)
Definition: integer.h:1487
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
MPSolverInterface * BuildGurobiInterface(bool mip, MPSolver *const solver)
MPSolverInterface * BuildSCIPInterface(MPSolver *const solver)
MPSolverInterface * BuildBopInterface(MPSolver *const solver)
constexpr double kDefaultPrimalTolerance
const absl::string_view ToString(MPSolver::OptimizationProblemType optimization_problem_type)
bool SolverTypeIsMip(MPModelRequest::SolverType solver_type)
MPSolverInterface * BuildCBCInterface(MPSolver *const solver)
bool AreWithinAbsoluteOrRelativeTolerances(FloatType x, FloatType y, FloatType relative_tolerance, FloatType absolute_tolerance)
Definition: fp_utils.h:120
absl::StatusOr< std::string > ExportModelAsMpsFormat(const MPModelProto &model, const MPModelExportOptions &options)
Outputs the current model (variables, constraints, objective) as a string encoded in MPS file format,...
bool AbslParseFlag(const absl::string_view text, MPSolver::OptimizationProblemType *solver_type, std::string *error)
absl::optional< LazyMutableCopy< MPModelProto > > ExtractValidMPModelOrPopulateResponseStatus(const MPModelRequest &request, MPSolutionResponse *response)
If the model is valid and non-empty, returns it (possibly after extracting the model_delta).
MPSolverInterface * BuildSatInterface(MPSolver *const solver)
MPSolverInterface * BuildCLPInterface(MPSolver *const solver)
constexpr NamedOptimizationProblemType kOptimizationProblemTypeNames[]
MPSolverInterface * BuildGLOPInterface(MPSolver *const solver)
std::string FindErrorInMPModelProto(const MPModelProto &model, double abs_value_threshold)
Returns an empty string iff the model is valid and not trivially infeasible.
absl::StatusOr< std::string > ExportModelAsLpFormat(const MPModelProto &model, const MPModelExportOptions &options)
Outputs the current model (variables, constraints, objective) as a string encoded in the so-called "C...
bool MPSolverResponseStatusIsRpcError(MPSolverResponseStatus status)
const bool maximize_
Definition: search.cc:2499
bool obfuscate
Obfuscates variable and constraint names.