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"
41#include "ortools/linear_solver/linear_solver.pb.h"
44#include "ortools/port/file.h"
46
47ABSL_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.");
51ABSL_FLAG(bool, log_verification_errors, true,
52 "If --verify_solution is set: LOG(ERROR) all errors detected"
53 " during the verification of the solution.");
54ABSL_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
58ABSL_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
63namespace operations_research {
64
65bool 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
90double 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
96void 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
127void 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
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
157bool 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
171double 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
177void 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
197namespace {
198void 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
219void 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;
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
245bool MPObjective::maximization() const { return interface_->maximize_; }
246
247bool MPObjective::minimization() const { return !interface_->maximize_; }
248
249double 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
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
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
299void 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
308void 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
325bool MPSolver::IsMIP() const { return interface_->IsMIP(); }
326
327std::string MPSolver::SolverVersion() const {
328 return interface_->SolverVersion();
329}
330
331void* MPSolver::underlying_solver() { return interface_->underlying_solver(); }
332
333// ---- Solver-specific parameters ----
334
335absl::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)
355extern MPSolverInterface* BuildCLPInterface(MPSolver* const solver);
356#endif
357#if defined(USE_CBC)
358extern MPSolverInterface* BuildCBCInterface(MPSolver* const solver);
359#endif
360#if defined(USE_GLPK)
361extern MPSolverInterface* BuildGLPKInterface(bool mip, MPSolver* const solver);
362#endif
363extern MPSolverInterface* BuildBopInterface(MPSolver* const solver);
364extern MPSolverInterface* BuildGLOPInterface(MPSolver* const solver);
365extern MPSolverInterface* BuildSatInterface(MPSolver* const solver);
366#if defined(USE_SCIP)
367extern MPSolverInterface* BuildSCIPInterface(MPSolver* const solver);
368#endif
370 MPSolver* const solver);
371#if defined(USE_CPLEX)
372extern MPSolverInterface* BuildCplexInterface(bool mip, MPSolver* const solver);
373
374extern MPSolverInterface* BuildGLOPInterface(MPSolver* const solver);
375#endif
376#if defined(USE_XPRESS)
377extern MPSolverInterface* BuildXpressInterface(bool mip,
378 MPSolver* const solver);
379#endif
380
381namespace {
382MPSolverInterface* 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
433namespace {
434int 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
445MPSolver::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
479#endif
480#ifdef USE_CBC
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.
501namespace {
502struct NamedOptimizationProblemType {
504 absl::string_view name;
505};
506} // namespace
507
508#if defined(_MSC_VER)
509const
510#else
511constexpr
512#endif
513 NamedOptimizationProblemType kOptimizationProblemTypeNames[] = {
529
530};
531// static
532bool 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
569const 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
581bool 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 */
602MPSolver* 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
616MPVariable* 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
636MPSolverResponseStatus 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
662MPSolverResponseStatus 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
787namespace {
788MPSolverResponseStatus ResultStatusToMPSolverResponseStatus(
789 MPSolver::ResultStatus status) {
790 switch (status) {
792 return MPSOLVER_OPTIMAL;
794 return MPSOLVER_FEASIBLE;
796 return MPSOLVER_INFEASIBLE;
798 return MPSOLVER_UNBOUNDED;
800 return MPSOLVER_ABNORMAL;
802 return MPSOLVER_MODEL_INVALID;
804 return MPSOLVER_NOT_SOLVED;
805 }
806 return MPSOLVER_UNKNOWN_STATUS;
807}
808} // namespace
809
810void 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
838void 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
906void 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
995absl::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
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
1080void MPSolver::Reset() { interface_->Reset(); }
1081
1082bool 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
1090MPVariable* 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
1104MPVariable* MPSolver::MakeNumVar(double lb, double ub,
1105 const std::string& name) {
1106 return MakeVar(lb, ub, false, name);
1107}
1108
1109MPVariable* MPSolver::MakeIntVar(double lb, double ub,
1110 const std::string& name) {
1111 return MakeVar(lb, ub, true, name);
1112}
1113
1115 return MakeVar(0.0, 1.0, true, name);
1116}
1117
1118void 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
1135void 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
1141void 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
1147void 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
1194int 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
1208bool 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
1222bool 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
1261void MPSolver::Write(const std::string& file_name) {
1262 interface_->Write(file_name);
1263}
1264
1265namespace {
1266std::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
1298std::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
1344std::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];
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.
1360bool 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
1504bool MPSolver::OutputIsEnabled() const { return !interface_->quiet(); }
1505
1506void MPSolver::EnableOutput() { interface_->set_quiet(false); }
1507
1508void MPSolver::SuppressOutput() { interface_->set_quiet(true); }
1509
1510int64 MPSolver::iterations() const { return interface_->iterations(); }
1511
1512int64 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
1539bool 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
1556void 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
1564void 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
1572void 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
1580bool MPSolver::NextSolution() { return interface_->NextSolution(); }
1581
1583 interface_->SetCallback(mp_callback);
1584}
1585
1587 return interface_->SupportsCallbacks();
1588}
1589
1590bool 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
1637void 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: {
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 }
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
1784absl::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
1803// For the primal and dual tolerances, choose the same default as CLP and GLPK.
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 << ".";
1963 }
1964 }
1965}
1966
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.
const std::string & name() const
Returns the name of the constraint.
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.
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.
void MakeBoolVarArray(int nb, const std::string &name, std::vector< MPVariable * > *vars)
Creates an array of boolean variables.
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...
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.
const std::string & Name() const
Returns the name of the model set at construction.
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.
const MPObjective & Objective() const
Returns the objective object.
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.
MPObjective * MutableObjective()
Returns the mutable objective object.
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.
const std::string & name() const
Returns the name of the variable.
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.
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 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
void STLDeleteElements(T *container)
Definition: stl_util.h:372
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 AreWithinAbsoluteOrRelativeTolerances(FloatType x, FloatType y, FloatType relative_tolerance, FloatType absolute_tolerance)
Definition: fp_utils.h:120
bool SolverTypeIsMip(MPModelRequest::SolverType solver_type)
MPSolverInterface * BuildCBCInterface(MPSolver *const solver)
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)
STL namespace.
const bool maximize_
Definition: search.cc:2499
bool obfuscate
Obfuscates variable and constraint names.