OR-Tools  8.2
gurobi_interface.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 // Gurobi backend to MPSolver.
15 //
16 // Implementation Notes:
17 //
18 // Incrementalism (last updated June 29, 2020): For solving both LPs and MIPs,
19 // Gurobi attempts to reuse information from previous solves, potentially
20 // giving a faster solve time. MPSolver supports this for the following problem
21 // modification types:
22 // * Adding a variable,
23 // * Adding a linear constraint,
24 // * Updating a variable bound,
25 // * Updating an objective coefficient or the objective offset (note that in
26 // Gurobi 7.5 LP solver, there is a bug if you update only the objective
27 // offset and nothing else).
28 // * Updating a coefficient in the constraint matrix.
29 // * Updating the type of variable (integer, continuous)
30 // * Changing the optimization direction.
31 // Updates of the following types will force a resolve from scratch:
32 // * Updating the upper or lower bounds of a linear constraint. Note that in
33 // MPSolver's model, this includes updating the sense (le, ge, eq, range) of
34 // a linear constraint.
35 // * Clearing a constraint
36 // Any model containing indicator constraints is considered "non-incremental"
37 // and will always solve from scratch.
38 //
39 // The above limitations are largely due MPSolver and this file, not Gurobi.
40 //
41 // Warning(rander): the interactions between callbacks and incrementalism are
42 // poorly tested, proceed with caution.
43 //
44 
45 #include <cmath>
46 #include <cstddef>
47 #include <limits>
48 #include <memory>
49 #include <stdexcept>
50 #include <string>
51 #include <utility>
52 #include <vector>
53 
54 #include "absl/status/status.h"
55 #include "absl/strings/match.h"
56 #include "absl/strings/str_format.h"
59 #include "ortools/base/logging.h"
60 #include "ortools/base/map_util.h"
61 #include "ortools/base/timer.h"
66 
67 ABSL_FLAG(int, num_gurobi_threads, 4,
68  "Number of threads available for Gurobi.");
69 
70 namespace operations_research {
71 
73  public:
74  // Constructor that takes a name for the underlying GRB solver.
75  explicit GurobiInterface(MPSolver* const solver, bool mip);
76  ~GurobiInterface() override;
77 
78  // Sets the optimization direction (min/max).
79  void SetOptimizationDirection(bool maximize) override;
80 
81  // ----- Solve -----
82  // Solves the problem using the parameter values specified.
83  MPSolver::ResultStatus Solve(const MPSolverParameters& param) override;
84  absl::optional<MPSolutionResponse> DirectlySolveProto(
85  const MPModelRequest& request) override;
86 
87  // Writes the model.
88  void Write(const std::string& filename) override;
89 
90  // ----- Model modifications and extraction -----
91  // Resets extracted model
92  void Reset() override;
93 
94  // Modifies bounds.
95  void SetVariableBounds(int var_index, double lb, double ub) override;
96  void SetVariableInteger(int var_index, bool integer) override;
97  void SetConstraintBounds(int row_index, double lb, double ub) override;
98 
99  // Adds Constraint incrementally.
100  void AddRowConstraint(MPConstraint* const ct) override;
101  bool AddIndicatorConstraint(MPConstraint* const ct) override;
102  // Adds variable incrementally.
103  void AddVariable(MPVariable* const var) override;
104  // Changes a coefficient in a constraint.
105  void SetCoefficient(MPConstraint* const constraint,
106  const MPVariable* const variable, double new_value,
107  double old_value) override;
108  // Clears a constraint from all its terms.
109  void ClearConstraint(MPConstraint* const constraint) override;
110  // Changes a coefficient in the linear objective
111  void SetObjectiveCoefficient(const MPVariable* const variable,
112  double coefficient) override;
113  // Changes the constant term in the linear objective.
114  void SetObjectiveOffset(double value) override;
115  // Clears the objective from all its terms.
116  void ClearObjective() override;
117  void BranchingPriorityChangedForVariable(int var_index) override;
118 
119  // ------ Query statistics on the solution and the solve ------
120  // Number of simplex or interior-point iterations
121  int64 iterations() const override;
122  // Number of branch-and-bound nodes. Only available for discrete problems.
123  int64 nodes() const override;
124 
125  // Returns the basis status of a row.
126  MPSolver::BasisStatus row_status(int constraint_index) const override;
127  // Returns the basis status of a column.
128  MPSolver::BasisStatus column_status(int variable_index) const override;
129 
130  // ----- Misc -----
131  // Queries problem type.
132  bool IsContinuous() const override { return IsLP(); }
133  bool IsLP() const override { return !mip_; }
134  bool IsMIP() const override { return mip_; }
135 
136  void ExtractNewVariables() override;
137  void ExtractNewConstraints() override;
138  void ExtractObjective() override;
139 
140  std::string SolverVersion() const override {
141  int major, minor, technical;
142  GRBversion(&major, &minor, &technical);
143  return absl::StrFormat("Gurobi library version %d.%d.%d\n", major, minor,
144  technical);
145  }
146 
147  bool InterruptSolve() override {
148  const absl::MutexLock lock(&hold_interruptions_mutex_);
149  if (model_ != nullptr) GRBterminate(model_);
150  return true;
151  }
152 
153  void* underlying_solver() override { return reinterpret_cast<void*>(model_); }
154 
155  double ComputeExactConditionNumber() const override {
156  if (!IsContinuous()) {
157  LOG(DFATAL) << "ComputeExactConditionNumber not implemented for"
158  << " GUROBI_MIXED_INTEGER_PROGRAMMING";
159  return 0.0;
160  }
161 
162  // TODO(user,user): Not yet working.
163  LOG(DFATAL) << "ComputeExactConditionNumber not implemented for"
164  << " GUROBI_LINEAR_PROGRAMMING";
165  return 0.0;
166 
167  // double cond = 0.0;
168  // const int status = GRBgetdblattr(model_, GRB_DBL_ATTR_KAPPA, &cond);
169  // if (0 == status) {
170  // return cond;
171  // } else {
172  // LOG(DFATAL) << "Condition number only available for "
173  // << "continuous problems";
174  // return 0.0;
175  // }
176  }
177 
178  // Iterates through the solutions in Gurobi's solution pool.
179  bool NextSolution() override;
180 
181  void SetCallback(MPCallback* mp_callback) override;
182  bool SupportsCallbacks() const override { return true; }
183 
184  private:
185  // Sets all parameters in the underlying solver.
186  void SetParameters(const MPSolverParameters& param) override;
187  // Sets solver-specific parameters (avoiding using files). The previous
188  // implementations supported multi-line strings of the form:
189  // parameter_i value_i\n
190  // We extend support for strings of the form:
191  // parameter1=value1,....,parametern=valuen
192  // or for strings of the form:
193  // parameter1 value1, ... ,parametern valuen
194  // which are easier to set in the command line.
195  // This implementations relies on SetSolverSpecificParameters, which has the
196  // extra benefit of unifying the way we handle specific parameters for both
197  // proto-based solves and for MPModel solves.
198  bool SetSolverSpecificParametersAsString(
199  const std::string& parameters) override;
200  // Sets each parameter in the underlying solver.
201  void SetRelativeMipGap(double value) override;
202  void SetPrimalTolerance(double value) override;
203  void SetDualTolerance(double value) override;
204  void SetPresolveMode(int value) override;
205  void SetScalingMode(int value) override;
206  void SetLpAlgorithm(int value) override;
207 
208  MPSolver::BasisStatus TransformGRBVarBasisStatus(
209  int gurobi_basis_status) const;
210  MPSolver::BasisStatus TransformGRBConstraintBasisStatus(
211  int gurobi_basis_status, int constraint_index) const;
212 
213  // See the implementation note at the top of file on incrementalism.
214  bool ModelIsNonincremental() const;
215 
216  void SetIntAttr(const char* name, int value);
217  int GetIntAttr(const char* name) const;
218  void SetDoubleAttr(const char* name, double value);
219  double GetDoubleAttr(const char* name) const;
220  void SetIntAttrElement(const char* name, int index, int value);
221  int GetIntAttrElement(const char* name, int index) const;
222  void SetDoubleAttrElement(const char* name, int index, double value);
223  double GetDoubleAttrElement(const char* name, int index) const;
224  std::vector<double> GetDoubleAttrArray(const char* name, int elements);
225  void SetCharAttrElement(const char* name, int index, char value);
226  char GetCharAttrElement(const char* name, int index) const;
227 
228  void CheckedGurobiCall(int err) const;
229 
230  int SolutionCount() const;
231 
232  GRBmodel* model_;
233  GRBenv* env_;
234  bool mip_;
235  int current_solution_index_;
236  MPCallback* callback_ = nullptr;
237  bool update_branching_priorities_ = false;
238  // Has length equal to the number of MPVariables in
239  // MPSolverInterface::solver_. Values are the index of the corresponding
240  // Gurobi variable. Note that Gurobi may have additional auxiliary variables
241  // not represented by MPVariables, such as those created by two-sided range
242  // constraints.
243  std::vector<int> mp_var_to_gurobi_var_;
244  // Has length equal to the number of MPConstraints in
245  // MPSolverInterface::solver_. Values are the index of the corresponding
246  // linear (or range) constraint in Gurobi, or -1 if no such constraint exists
247  // (e.g. for indicator constraints).
248  std::vector<int> mp_cons_to_gurobi_linear_cons_;
249  // Should match the Gurobi model after it is updated.
250  int num_gurobi_vars_ = 0;
251  // Should match the Gurobi model after it is updated.
252  // NOTE(user): indicator constraints are not counted below.
253  int num_gurobi_linear_cons_ = 0;
254  // See the implementation note at the top of file on incrementalism.
255  bool had_nonincremental_change_ = false;
256 
257  // Mutex is held to prevent InterruptSolve() to call GRBterminate() when
258  // model_ is not completely built. It also prevents model_ to be changed
259  // during the execution of GRBterminate().
260  mutable absl::Mutex hold_interruptions_mutex_;
261 };
262 
263 namespace {
264 
265 void CheckedGurobiCall(int err, GRBenv* const env) {
266  CHECK_EQ(0, err) << "Fatal error with code " << err << ", due to "
267  << GRBgeterrormsg(env);
268 }
269 
270 // For interacting directly with the Gurobi C API for callbacks.
271 struct GurobiInternalCallbackContext {
274  int where;
275 };
276 
277 class GurobiMPCallbackContext : public MPCallbackContext {
278  public:
279  GurobiMPCallbackContext(GRBenv* env,
280  const std::vector<int>* mp_var_to_gurobi_var,
281  int num_gurobi_vars, bool might_add_cuts,
282  bool might_add_lazy_constraints);
283 
284  // Implementation of the interface.
285  MPCallbackEvent Event() override;
286  bool CanQueryVariableValues() override;
287  double VariableValue(const MPVariable* variable) override;
288  void AddCut(const LinearRange& cutting_plane) override;
289  void AddLazyConstraint(const LinearRange& lazy_constraint) override;
290  double SuggestSolution(
291  const absl::flat_hash_map<const MPVariable*, double>& solution) override;
292  int64 NumExploredNodes() override;
293 
294  // Call this method to update the internal state of the callback context
295  // before passing it to MPCallback::RunCallback().
296  void UpdateFromGurobiState(
297  const GurobiInternalCallbackContext& gurobi_internal_context);
298 
299  private:
300  // Wraps GRBcbget(), used to query the state of the solver. See
301  // http://www.gurobi.com/documentation/8.0/refman/callback_codes.html#sec:CallbackCodes
302  // for callback_code values.
303  template <typename T>
304  T GurobiCallbackGet(
305  const GurobiInternalCallbackContext& gurobi_internal_context,
306  int callback_code);
307  void CheckedGurobiCall(int gurobi_error_code) const;
308 
309  template <typename GRBConstraintFunction>
310  void AddGeneratedConstraint(const LinearRange& linear_range,
311  GRBConstraintFunction grb_constraint_function);
312 
313  GRBenv* const env_;
314  const std::vector<int>* const mp_var_to_gurobi_var_;
315  const int num_gurobi_vars_;
316 
317  const bool might_add_cuts_;
318  const bool might_add_lazy_constraints_;
319 
320  // Stateful, updated before each call to the callback.
321  GurobiInternalCallbackContext current_gurobi_internal_callback_context_;
322  bool variable_values_extracted_ = false;
323  std::vector<double> gurobi_variable_values_;
324 };
325 
326 void GurobiMPCallbackContext::CheckedGurobiCall(int gurobi_error_code) const {
327  ::operations_research::CheckedGurobiCall(gurobi_error_code, env_);
328 }
329 
330 GurobiMPCallbackContext::GurobiMPCallbackContext(
331  GRBenv* env, const std::vector<int>* mp_var_to_gurobi_var,
332  int num_gurobi_vars, bool might_add_cuts, bool might_add_lazy_constraints)
333  : env_(ABSL_DIE_IF_NULL(env)),
334  mp_var_to_gurobi_var_(ABSL_DIE_IF_NULL(mp_var_to_gurobi_var)),
335  num_gurobi_vars_(num_gurobi_vars),
336  might_add_cuts_(might_add_cuts),
337  might_add_lazy_constraints_(might_add_lazy_constraints) {}
338 
339 void GurobiMPCallbackContext::UpdateFromGurobiState(
340  const GurobiInternalCallbackContext& gurobi_internal_context) {
341  current_gurobi_internal_callback_context_ = gurobi_internal_context;
342  variable_values_extracted_ = false;
343 }
344 
345 int64 GurobiMPCallbackContext::NumExploredNodes() {
346  switch (Event()) {
347  case MPCallbackEvent::kMipNode:
348  return static_cast<int64>(GurobiCallbackGet<double>(
349  current_gurobi_internal_callback_context_, GRB_CB_MIPNODE_NODCNT));
350  case MPCallbackEvent::kMipSolution:
351  return static_cast<int64>(GurobiCallbackGet<double>(
352  current_gurobi_internal_callback_context_, GRB_CB_MIPSOL_NODCNT));
353  default:
354  LOG(FATAL) << "Node count is supported only for callback events MIP_NODE "
355  "and MIP_SOL, but was requested at: "
356  << ToString(Event());
357  }
358 }
359 
360 template <typename T>
361 T GurobiMPCallbackContext::GurobiCallbackGet(
362  const GurobiInternalCallbackContext& gurobi_internal_context,
363  const int callback_code) {
364  T result = 0;
365  CheckedGurobiCall(
366  GRBcbget(gurobi_internal_context.gurobi_internal_callback_data,
367  gurobi_internal_context.where, callback_code,
368  static_cast<void*>(&result)));
369  return result;
370 }
371 
372 MPCallbackEvent GurobiMPCallbackContext::Event() {
373  switch (current_gurobi_internal_callback_context_.where) {
374  case GRB_CB_POLLING:
375  return MPCallbackEvent::kPolling;
376  case GRB_CB_PRESOLVE:
377  return MPCallbackEvent::kPresolve;
378  case GRB_CB_SIMPLEX:
379  return MPCallbackEvent::kSimplex;
380  case GRB_CB_MIP:
381  return MPCallbackEvent::kMip;
382  case GRB_CB_MIPSOL:
383  return MPCallbackEvent::kMipSolution;
384  case GRB_CB_MIPNODE:
385  return MPCallbackEvent::kMipNode;
386  case GRB_CB_MESSAGE:
387  return MPCallbackEvent::kMessage;
388  case GRB_CB_BARRIER:
389  return MPCallbackEvent::kBarrier;
390  // TODO(b/112427356): in Gurobi 8.0, there is a new callback location.
391  // case GRB_CB_MULTIOBJ:
392  // return MPCallbackEvent::kMultiObj;
393  default:
394  LOG_FIRST_N(ERROR, 1) << "Gurobi callback at unknown where="
395  << current_gurobi_internal_callback_context_.where;
396  return MPCallbackEvent::kUnknown;
397  }
398 }
399 
400 bool GurobiMPCallbackContext::CanQueryVariableValues() {
401  const MPCallbackEvent where = Event();
402  if (where == MPCallbackEvent::kMipSolution) {
403  return true;
404  }
405  if (where == MPCallbackEvent::kMipNode) {
406  const int gurobi_node_status = GurobiCallbackGet<int>(
407  current_gurobi_internal_callback_context_, GRB_CB_MIPNODE_STATUS);
408  return gurobi_node_status == GRB_OPTIMAL;
409  }
410  return false;
411 }
412 
413 double GurobiMPCallbackContext::VariableValue(const MPVariable* variable) {
414  CHECK(variable != nullptr);
415  if (!variable_values_extracted_) {
416  const MPCallbackEvent where = Event();
417  CHECK(where == MPCallbackEvent::kMipSolution ||
418  where == MPCallbackEvent::kMipNode)
419  << "You can only call VariableValue at "
420  << ToString(MPCallbackEvent::kMipSolution) << " or "
421  << ToString(MPCallbackEvent::kMipNode)
422  << " but called from: " << ToString(where);
423  const int gurobi_get_var_param = where == MPCallbackEvent::kMipNode
426 
427  gurobi_variable_values_.resize(num_gurobi_vars_);
428  CheckedGurobiCall(GRBcbget(
429  current_gurobi_internal_callback_context_.gurobi_internal_callback_data,
430  current_gurobi_internal_callback_context_.where, gurobi_get_var_param,
431  static_cast<void*>(gurobi_variable_values_.data())));
432  variable_values_extracted_ = true;
433  }
434  return gurobi_variable_values_[mp_var_to_gurobi_var_->at(variable->index())];
435 }
436 
437 template <typename GRBConstraintFunction>
438 void GurobiMPCallbackContext::AddGeneratedConstraint(
439  const LinearRange& linear_range,
440  GRBConstraintFunction grb_constraint_function) {
441  std::vector<int> variable_indices;
442  std::vector<double> variable_coefficients;
443  const int num_terms = linear_range.linear_expr().terms().size();
444  variable_indices.reserve(num_terms);
445  variable_coefficients.reserve(num_terms);
446  for (const auto& var_coef_pair : linear_range.linear_expr().terms()) {
447  variable_indices.push_back(
448  mp_var_to_gurobi_var_->at(var_coef_pair.first->index()));
449  variable_coefficients.push_back(var_coef_pair.second);
450  }
451  if (std::isfinite(linear_range.upper_bound())) {
452  CheckedGurobiCall(grb_constraint_function(
453  current_gurobi_internal_callback_context_.gurobi_internal_callback_data,
454  variable_indices.size(), variable_indices.data(),
455  variable_coefficients.data(), GRB_LESS_EQUAL,
456  linear_range.upper_bound()));
457  }
458  if (std::isfinite(linear_range.lower_bound())) {
459  CheckedGurobiCall(grb_constraint_function(
460  current_gurobi_internal_callback_context_.gurobi_internal_callback_data,
461  variable_indices.size(), variable_indices.data(),
462  variable_coefficients.data(), GRB_GREATER_EQUAL,
463  linear_range.lower_bound()));
464  }
465 }
466 
467 void GurobiMPCallbackContext::AddCut(const LinearRange& cutting_plane) {
468  CHECK(might_add_cuts_);
469  const MPCallbackEvent where = Event();
470  CHECK(where == MPCallbackEvent::kMipNode)
471  << "Cuts can only be added at MIP_NODE, tried to add cut at: "
472  << ToString(where);
473  AddGeneratedConstraint(cutting_plane, GRBcbcut);
474 }
475 
476 void GurobiMPCallbackContext::AddLazyConstraint(
477  const LinearRange& lazy_constraint) {
478  CHECK(might_add_lazy_constraints_);
479  const MPCallbackEvent where = Event();
480  CHECK(where == MPCallbackEvent::kMipNode ||
481  where == MPCallbackEvent::kMipSolution)
482  << "Lazy constraints can only be added at MIP_NODE or MIP_SOL, tried to "
483  "add lazy constraint at: "
484  << ToString(where);
485  AddGeneratedConstraint(lazy_constraint, GRBcblazy);
486 }
487 
488 double GurobiMPCallbackContext::SuggestSolution(
489  const absl::flat_hash_map<const MPVariable*, double>& solution) {
490  const MPCallbackEvent where = Event();
491  CHECK(where == MPCallbackEvent::kMipNode)
492  << "Feasible solutions can only be added at MIP_NODE, tried to add "
493  "solution at: "
494  << ToString(where);
495 
496  std::vector<double> full_solution(num_gurobi_vars_, GRB_UNDEFINED);
497  for (const auto& variable_value : solution) {
498  const MPVariable* var = variable_value.first;
499  full_solution[mp_var_to_gurobi_var_->at(var->index())] =
500  variable_value.second;
501  }
502 
503  double objval;
504  CheckedGurobiCall(GRBcbsolution(
505  current_gurobi_internal_callback_context_.gurobi_internal_callback_data,
506  full_solution.data(), &objval));
507 
508  return objval;
509 }
510 
511 struct MPCallbackWithGurobiContext {
512  GurobiMPCallbackContext* context;
513  MPCallback* callback;
514 };
515 
516 // NOTE(user): This function must have this exact API, because we are passing
517 // it to Gurobi as a callback.
518 int STDCALL CallbackImpl(GRBmodel* model, void* gurobi_internal_callback_data,
519  int where, void* raw_model_and_callback) {
520  MPCallbackWithGurobiContext* const callback_with_context =
521  static_cast<MPCallbackWithGurobiContext*>(raw_model_and_callback);
522  CHECK(callback_with_context != nullptr);
523  CHECK(callback_with_context->context != nullptr);
524  CHECK(callback_with_context->callback != nullptr);
525  GurobiInternalCallbackContext gurobi_internal_context{
527  callback_with_context->context->UpdateFromGurobiState(
528  gurobi_internal_context);
529  callback_with_context->callback->RunCallback(callback_with_context->context);
530  return 0;
531 }
532 
533 } // namespace
534 
535 void GurobiInterface::CheckedGurobiCall(int err) const {
536  ::operations_research::CheckedGurobiCall(err, env_);
537 }
538 
539 void GurobiInterface::SetIntAttr(const char* name, int value) {
540  CheckedGurobiCall(GRBsetintattr(model_, name, value));
541 }
542 
543 int GurobiInterface::GetIntAttr(const char* name) const {
544  int value;
545  CheckedGurobiCall(GRBgetintattr(model_, name, &value));
546  return value;
547 }
548 
549 void GurobiInterface::SetDoubleAttr(const char* name, double value) {
550  CheckedGurobiCall(GRBsetdblattr(model_, name, value));
551 }
552 
553 double GurobiInterface::GetDoubleAttr(const char* name) const {
554  double value;
555  CheckedGurobiCall(GRBgetdblattr(model_, name, &value));
556  return value;
557 }
558 
559 void GurobiInterface::SetIntAttrElement(const char* name, int index,
560  int value) {
561  CheckedGurobiCall(GRBsetintattrelement(model_, name, index, value));
562 }
563 
564 int GurobiInterface::GetIntAttrElement(const char* name, int index) const {
565  int value;
566  CheckedGurobiCall(GRBgetintattrelement(model_, name, index, &value));
567  return value;
568 }
569 
570 void GurobiInterface::SetDoubleAttrElement(const char* name, int index,
571  double value) {
572  CheckedGurobiCall(GRBsetdblattrelement(model_, name, index, value));
573 }
574 double GurobiInterface::GetDoubleAttrElement(const char* name,
575  int index) const {
576  double value;
577  CheckedGurobiCall(GRBgetdblattrelement(model_, name, index, &value));
578  return value;
579 }
580 
581 std::vector<double> GurobiInterface::GetDoubleAttrArray(const char* name,
582  int elements) {
583  std::vector<double> results(elements);
584  CheckedGurobiCall(
585  GRBgetdblattrarray(model_, name, 0, elements, results.data()));
586  return results;
587 }
588 
589 void GurobiInterface::SetCharAttrElement(const char* name, int index,
590  char value) {
591  CheckedGurobiCall(GRBsetcharattrelement(model_, name, index, value));
592 }
593 char GurobiInterface::GetCharAttrElement(const char* name, int index) const {
594  char value;
595  CheckedGurobiCall(GRBgetcharattrelement(model_, name, index, &value));
596  return value;
597 }
598 
599 // Creates a LP/MIP instance with the specified name and minimization objective.
600 GurobiInterface::GurobiInterface(MPSolver* const solver, bool mip)
601  : MPSolverInterface(solver),
602  model_(nullptr),
603  env_(nullptr),
604  mip_(mip),
605  current_solution_index_(0) {
607  CheckedGurobiCall(GRBnewmodel(env_, &model_, solver_->name_.c_str(),
608  0, // numvars
609  nullptr, // obj
610  nullptr, // lb
611  nullptr, // ub
612  nullptr, // vtype
613  nullptr)); // varnanes
615  CheckedGurobiCall(GRBsetintparam(env_, GRB_INT_PAR_THREADS,
616  absl::GetFlag(FLAGS_num_gurobi_threads)));
617 }
618 
620  CheckedGurobiCall(GRBfreemodel(model_));
621  GRBfreeenv(env_);
622 }
623 
624 // ------ Model modifications and extraction -----
625 
627  // We hold calls to GRBterminate() until the new model_ is ready.
628  const absl::MutexLock lock(&hold_interruptions_mutex_);
629 
630  GRBmodel* old_model = model_;
631  CheckedGurobiCall(GRBnewmodel(env_, &model_, solver_->name_.c_str(),
632  0, // numvars
633  nullptr, // obj
634  nullptr, // lb
635  nullptr, // ub
636  nullptr, // vtype
637  nullptr)); // varnames
638 
639  // Copy all existing parameters from the previous model to the new one. This
640  // ensures that if a user calls multiple times
641  // SetSolverSpecificParametersAsString() and then Reset() is called, we still
642  // take into account all parameters.
643  //
644  // The current code only reapplies the parameters stored in
645  // solver_specific_parameter_string_ at the start of the solve; other
646  // parameters set by previous calls are only kept in the Gurobi model.
647  CheckedGurobiCall(GRBcopyparams(GRBgetenv(model_), GRBgetenv(old_model)));
648 
649  CheckedGurobiCall(GRBfreemodel(old_model));
650  old_model = nullptr;
651 
653  mp_var_to_gurobi_var_.clear();
654  mp_cons_to_gurobi_linear_cons_.clear();
655  num_gurobi_vars_ = 0;
656  num_gurobi_linear_cons_ = 0;
657  had_nonincremental_change_ = false;
658 }
659 
663 }
664 
665 void GurobiInterface::SetVariableBounds(int var_index, double lb, double ub) {
667  if (!had_nonincremental_change_ && variable_is_extracted(var_index)) {
668  SetDoubleAttrElement(GRB_DBL_ATTR_LB, mp_var_to_gurobi_var_.at(var_index),
669  lb);
670  SetDoubleAttrElement(GRB_DBL_ATTR_UB, mp_var_to_gurobi_var_.at(var_index),
671  ub);
672  } else {
674  }
675 }
676 
679  if (!had_nonincremental_change_ && variable_is_extracted(index)) {
680  char type_var;
681  if (integer) {
682  type_var = GRB_INTEGER;
683  } else {
684  type_var = GRB_CONTINUOUS;
685  }
686  SetCharAttrElement(GRB_CHAR_ATTR_VTYPE, mp_var_to_gurobi_var_.at(index),
687  type_var);
688  } else {
690  }
691 }
692 
693 void GurobiInterface::SetConstraintBounds(int index, double lb, double ub) {
696  had_nonincremental_change_ = true;
697  }
698  // TODO(user): this is nontrivial to make incremental:
699  // 1. Make sure it is a linear constraint (not an indicator or indicator
700  // range constraint).
701  // 2. Check if the sense of the constraint changes. If it was previously a
702  // range constraint, we can do nothing, and if it becomes a range
703  // constraint, we can do nothing. We could support range constraints if
704  // we tracked the auxiliary variable that is added with range
705  // constraints.
706 }
707 
710 }
711 
713  had_nonincremental_change_ = true;
715  return !IsContinuous();
716 }
717 
720 }
721 
723  const MPVariable* const variable,
724  double new_value, double old_value) {
726  if (!had_nonincremental_change_ && variable_is_extracted(variable->index()) &&
727  constraint_is_extracted(constraint->index())) {
728  // Cannot be const, GRBchgcoeffs needs non-const pointer.
729  int grb_var = mp_var_to_gurobi_var_.at(variable->index());
730  int grb_cons = mp_cons_to_gurobi_linear_cons_.at(constraint->index());
731  if (grb_cons < 0) {
732  had_nonincremental_change_ = true;
734  } else {
735  // TODO(user): investigate if this has bad performance.
736  CheckedGurobiCall(
737  GRBchgcoeffs(model_, 1, &grb_cons, &grb_var, &new_value));
738  }
739  } else {
741  }
742 }
743 
745  had_nonincremental_change_ = true;
747  // TODO(user): this is difficult to make incremental, like
748  // SetConstraintBounds(), because of the auxiliary Gurobi variables that
749  // range constraints introduce.
750 }
751 
753  double coefficient) {
755  if (!had_nonincremental_change_ && variable_is_extracted(variable->index())) {
756  SetDoubleAttrElement(GRB_DBL_ATTR_OBJ,
757  mp_var_to_gurobi_var_.at(variable->index()),
758  coefficient);
759  } else {
761  }
762 }
763 
766  if (!had_nonincremental_change_) {
767  SetDoubleAttr(GRB_DBL_ATTR_OBJCON, value);
768  } else {
770  }
771 }
772 
775  if (!had_nonincremental_change_) {
776  SetObjectiveOffset(0.0);
777  for (const auto& entry : solver_->objective_->coefficients_) {
778  SetObjectiveCoefficient(entry.first, 0.0);
779  }
780  } else {
782  }
783 }
784 
786  update_branching_priorities_ = true;
787 }
788 
789 // ------ Query statistics on the solution and the solve ------
790 
792  double iter;
794  CheckedGurobiCall(GRBgetdblattr(model_, GRB_DBL_ATTR_ITERCOUNT, &iter));
795  return static_cast<int64>(iter);
796 }
797 
799  if (mip_) {
801  return static_cast<int64>(GetDoubleAttr(GRB_DBL_ATTR_NODECOUNT));
802  } else {
803  LOG(DFATAL) << "Number of nodes only available for discrete problems.";
804  return kUnknownNumberOfNodes;
805  }
806 }
807 
808 MPSolver::BasisStatus GurobiInterface::TransformGRBVarBasisStatus(
809  int gurobi_basis_status) const {
810  switch (gurobi_basis_status) {
811  case GRB_BASIC:
812  return MPSolver::BASIC;
813  case GRB_NONBASIC_LOWER:
815  case GRB_NONBASIC_UPPER:
817  case GRB_SUPERBASIC:
818  return MPSolver::FREE;
819  default:
820  LOG(DFATAL) << "Unknown GRB basis status.";
821  return MPSolver::FREE;
822  }
823 }
824 
825 MPSolver::BasisStatus GurobiInterface::TransformGRBConstraintBasisStatus(
826  int gurobi_basis_status, int constraint_index) const {
827  const int grb_index = mp_cons_to_gurobi_linear_cons_.at(constraint_index);
828  if (grb_index < 0) {
829  LOG(DFATAL) << "Basis status not available for nonlinear constraints.";
830  return MPSolver::FREE;
831  }
832  switch (gurobi_basis_status) {
833  case GRB_BASIC:
834  return MPSolver::BASIC;
835  default: {
836  // Non basic.
837  double tolerance = 0.0;
838  CheckedGurobiCall(GRBgetdblparam(GRBgetenv(model_),
839  GRB_DBL_PAR_FEASIBILITYTOL, &tolerance));
840  const double slack = GetDoubleAttrElement(GRB_DBL_ATTR_SLACK, grb_index);
841  const char sense = GetCharAttrElement(GRB_CHAR_ATTR_SENSE, grb_index);
842  VLOG(4) << "constraint " << constraint_index << " , slack = " << slack
843  << " , sense = " << sense;
844  if (fabs(slack) <= tolerance) {
845  switch (sense) {
846  case GRB_EQUAL:
847  case GRB_LESS_EQUAL:
849  case GRB_GREATER_EQUAL:
851  default:
852  return MPSolver::FREE;
853  }
854  } else {
855  return MPSolver::FREE;
856  }
857  }
858  }
859 }
860 
861 // Returns the basis status of a row.
863  const int optim_status = GetIntAttr(GRB_INT_ATTR_STATUS);
864  if (optim_status != GRB_OPTIMAL && optim_status != GRB_SUBOPTIMAL) {
865  LOG(DFATAL) << "Basis status only available after a solution has "
866  << "been found.";
867  return MPSolver::FREE;
868  }
869  if (mip_) {
870  LOG(DFATAL) << "Basis status only available for continuous problems.";
871  return MPSolver::FREE;
872  }
873  const int grb_index = mp_cons_to_gurobi_linear_cons_.at(constraint_index);
874  if (grb_index < 0) {
875  LOG(DFATAL) << "Basis status not available for nonlinear constraints.";
876  return MPSolver::FREE;
877  }
878  const int gurobi_basis_status =
879  GetIntAttrElement(GRB_INT_ATTR_CBASIS, grb_index);
880  return TransformGRBConstraintBasisStatus(gurobi_basis_status,
881  constraint_index);
882 }
883 
884 // Returns the basis status of a column.
886  const int optim_status = GetIntAttr(GRB_INT_ATTR_STATUS);
887  if (optim_status != GRB_OPTIMAL && optim_status != GRB_SUBOPTIMAL) {
888  LOG(DFATAL) << "Basis status only available after a solution has "
889  << "been found.";
890  return MPSolver::FREE;
891  }
892  if (mip_) {
893  LOG(DFATAL) << "Basis status only available for continuous problems.";
894  return MPSolver::FREE;
895  }
896  const int grb_index = mp_var_to_gurobi_var_.at(variable_index);
897  const int gurobi_basis_status =
898  GetIntAttrElement(GRB_INT_ATTR_VBASIS, grb_index);
899  return TransformGRBVarBasisStatus(gurobi_basis_status);
900 }
901 
902 // Extracts new variables.
904  const int total_num_vars = solver_->variables_.size();
905  if (total_num_vars > last_variable_index_) {
906  // Define new variables.
907  for (int j = last_variable_index_; j < total_num_vars; ++j) {
908  const MPVariable* const var = solver_->variables_.at(j);
909  set_variable_as_extracted(var->index(), true);
910  CheckedGurobiCall(GRBaddvar(
911  model_, 0, // numnz
912  nullptr, // vind
913  nullptr, // vval
914  solver_->objective_->GetCoefficient(var), var->lb(), var->ub(),
915  var->integer() && mip_ ? GRB_INTEGER : GRB_CONTINUOUS,
916  var->name().empty() ? nullptr : var->name().c_str()));
917  mp_var_to_gurobi_var_.push_back(num_gurobi_vars_++);
918  }
919  CheckedGurobiCall(GRBupdatemodel(model_));
920  // Add new variables to existing constraints.
921  std::vector<int> grb_cons_ind;
922  std::vector<int> grb_var_ind;
923  std::vector<double> coef;
924  for (int i = 0; i < last_constraint_index_; ++i) {
925  // If there was a nonincremental change/the model is not incremental (e.g.
926  // there is an indicator constraint), we should never enter this loop, as
927  // last_variable_index_ will be reset to zero before ExtractNewVariables()
928  // is called.
929  MPConstraint* const ct = solver_->constraints_[i];
930  const int grb_ct_idx = mp_cons_to_gurobi_linear_cons_.at(ct->index());
931  DCHECK_GE(grb_ct_idx, 0);
932  DCHECK(ct->indicator_variable() == nullptr);
933  for (const auto& entry : ct->coefficients_) {
934  const int var_index = entry.first->index();
935  DCHECK(variable_is_extracted(var_index));
936 
937  if (var_index >= last_variable_index_) {
938  grb_cons_ind.push_back(grb_ct_idx);
939  grb_var_ind.push_back(mp_var_to_gurobi_var_.at(var_index));
940  coef.push_back(entry.second);
941  }
942  }
943  }
944  if (!grb_cons_ind.empty()) {
945  CheckedGurobiCall(GRBchgcoeffs(model_, grb_cons_ind.size(),
946  grb_cons_ind.data(), grb_var_ind.data(),
947  coef.data()));
948  }
949  }
950  CheckedGurobiCall(GRBupdatemodel(model_));
951  DCHECK_EQ(GetIntAttr(GRB_INT_ATTR_NUMVARS), num_gurobi_vars_);
952 }
953 
955  int total_num_rows = solver_->constraints_.size();
956  if (last_constraint_index_ < total_num_rows) {
957  // Add each new constraint.
958  for (int row = last_constraint_index_; row < total_num_rows; ++row) {
959  MPConstraint* const ct = solver_->constraints_[row];
961  const int size = ct->coefficients_.size();
962  std::vector<int> grb_vars;
963  std::vector<double> coefs;
964  grb_vars.reserve(size);
965  coefs.reserve(size);
966  for (const auto& entry : ct->coefficients_) {
967  const int var_index = entry.first->index();
968  CHECK(variable_is_extracted(var_index));
969  grb_vars.push_back(mp_var_to_gurobi_var_.at(var_index));
970  coefs.push_back(entry.second);
971  }
972  char* const name =
973  ct->name().empty() ? nullptr : const_cast<char*>(ct->name().c_str());
974  if (ct->indicator_variable() != nullptr) {
975  const int grb_ind_var =
976  mp_var_to_gurobi_var_.at(ct->indicator_variable()->index());
977  if (ct->lb() > -std::numeric_limits<double>::infinity()) {
978  CheckedGurobiCall(GRBaddgenconstrIndicator(
979  model_, name, grb_ind_var, ct->indicator_value(), size,
980  grb_vars.data(), coefs.data(),
981  ct->ub() == ct->lb() ? GRB_EQUAL : GRB_GREATER_EQUAL, ct->lb()));
982  }
983  if (ct->ub() < std::numeric_limits<double>::infinity() &&
984  ct->lb() != ct->ub()) {
985  CheckedGurobiCall(GRBaddgenconstrIndicator(
986  model_, name, grb_ind_var, ct->indicator_value(), size,
987  grb_vars.data(), coefs.data(), GRB_LESS_EQUAL, ct->ub()));
988  }
989  mp_cons_to_gurobi_linear_cons_.push_back(-1);
990  } else {
991  // Using GRBaddrangeconstr for constraints that don't require it adds
992  // a slack which is not always removed by presolve.
993  if (ct->lb() == ct->ub()) {
994  CheckedGurobiCall(GRBaddconstr(model_, size, grb_vars.data(),
995  coefs.data(), GRB_EQUAL, ct->lb(),
996  name));
997  } else if (ct->lb() == -std::numeric_limits<double>::infinity()) {
998  CheckedGurobiCall(GRBaddconstr(model_, size, grb_vars.data(),
999  coefs.data(), GRB_LESS_EQUAL, ct->ub(),
1000  name));
1001  } else if (ct->ub() == std::numeric_limits<double>::infinity()) {
1002  CheckedGurobiCall(GRBaddconstr(model_, size, grb_vars.data(),
1003  coefs.data(), GRB_GREATER_EQUAL,
1004  ct->lb(), name));
1005  } else {
1006  CheckedGurobiCall(GRBaddrangeconstr(model_, size, grb_vars.data(),
1007  coefs.data(), ct->lb(), ct->ub(),
1008  name));
1009  // NOTE(user): range constraints implicitly add an extra variable
1010  // to the model.
1011  num_gurobi_vars_++;
1012  }
1013  mp_cons_to_gurobi_linear_cons_.push_back(num_gurobi_linear_cons_++);
1014  }
1015  }
1016  }
1017  CheckedGurobiCall(GRBupdatemodel(model_));
1018  DCHECK_EQ(GetIntAttr(GRB_INT_ATTR_NUMCONSTRS), num_gurobi_linear_cons_);
1019 }
1020 
1023  SetDoubleAttr(GRB_DBL_ATTR_OBJCON, solver_->Objective().offset());
1024 }
1025 
1026 // ------ Parameters -----
1027 
1028 void GurobiInterface::SetParameters(const MPSolverParameters& param) {
1029  SetCommonParameters(param);
1030  if (mip_) {
1031  SetMIPParameters(param);
1032  }
1033 }
1034 
1035 bool GurobiInterface::SetSolverSpecificParametersAsString(
1036  const std::string& parameters) {
1037  return SetSolverSpecificParameters(parameters, GRBgetenv(model_)).ok();
1038 }
1039 
1040 void GurobiInterface::SetRelativeMipGap(double value) {
1041  if (mip_) {
1042  CheckedGurobiCall(
1044  } else {
1045  LOG(WARNING) << "The relative MIP gap is only available "
1046  << "for discrete problems.";
1047  }
1048 }
1049 
1050 // Gurobi has two different types of primal tolerance (feasibility tolerance):
1051 // constraint and integrality. We need to set them both.
1052 // See:
1053 // http://www.gurobi.com/documentation/6.0/refman/feasibilitytol.html
1054 // and
1055 // http://www.gurobi.com/documentation/6.0/refman/intfeastol.html
1056 void GurobiInterface::SetPrimalTolerance(double value) {
1057  CheckedGurobiCall(
1059  CheckedGurobiCall(
1061 }
1062 
1063 // As opposed to primal (feasibility) tolerance, the dual (optimality) tolerance
1064 // applies only to the reduced costs in the improving direction.
1065 // See:
1066 // http://www.gurobi.com/documentation/6.0/refman/optimalitytol.html
1067 void GurobiInterface::SetDualTolerance(double value) {
1068  CheckedGurobiCall(
1070 }
1071 
1072 void GurobiInterface::SetPresolveMode(int value) {
1073  switch (value) {
1075  CheckedGurobiCall(
1076  GRBsetintparam(GRBgetenv(model_), GRB_INT_PAR_PRESOLVE, false));
1077  break;
1078  }
1080  CheckedGurobiCall(
1082  break;
1083  }
1084  default: {
1086  }
1087  }
1088 }
1089 
1090 // Sets the scaling mode.
1091 void GurobiInterface::SetScalingMode(int value) {
1092  switch (value) {
1094  CheckedGurobiCall(
1096  break;
1098  CheckedGurobiCall(
1100  CheckedGurobiCall(
1102  break;
1103  default:
1104  // Leave the parameters untouched.
1105  break;
1106  }
1107 }
1108 
1109 // Sets the LP algorithm : primal, dual or barrier. Note that GRB
1110 // offers automatic selection
1111 void GurobiInterface::SetLpAlgorithm(int value) {
1112  switch (value) {
1114  CheckedGurobiCall(GRBsetintparam(GRBgetenv(model_), GRB_INT_PAR_METHOD,
1115  GRB_METHOD_DUAL));
1116  break;
1118  CheckedGurobiCall(GRBsetintparam(GRBgetenv(model_), GRB_INT_PAR_METHOD,
1120  break;
1122  CheckedGurobiCall(GRBsetintparam(GRBgetenv(model_), GRB_INT_PAR_METHOD,
1124  break;
1125  default:
1127  value);
1128  }
1129 }
1130 
1131 int GurobiInterface::SolutionCount() const {
1132  return GetIntAttr(GRB_INT_ATTR_SOLCOUNT);
1133 }
1134 
1135 bool GurobiInterface::ModelIsNonincremental() const {
1136  for (const MPConstraint* c : solver_->constraints()) {
1137  if (c->indicator_variable() != nullptr) {
1138  return true;
1139  }
1140  }
1141  return false;
1142 }
1143 
1145  WallTimer timer;
1146  timer.Start();
1147 
1150  ModelIsNonincremental() || had_nonincremental_change_) {
1151  Reset();
1152  }
1153 
1154  // Set log level.
1155  CheckedGurobiCall(
1157 
1158  ExtractModel();
1159  // Sync solver.
1160  CheckedGurobiCall(GRBupdatemodel(model_));
1161  VLOG(1) << absl::StrFormat("Model built in %s.",
1162  absl::FormatDuration(timer.GetDuration()));
1163 
1164  // Set solution hints if any.
1165  for (const std::pair<const MPVariable*, double>& p :
1166  solver_->solution_hint_) {
1167  SetDoubleAttrElement(GRB_DBL_ATTR_START,
1168  mp_var_to_gurobi_var_.at(p.first->index()), p.second);
1169  }
1170 
1171  // Pass branching priority annotations if at least one has been updated.
1172  if (update_branching_priorities_) {
1173  for (const MPVariable* var : solver_->variables_) {
1174  SetIntAttrElement(GRB_INT_ATTR_BRANCHPRIORITY,
1175  mp_var_to_gurobi_var_.at(var->index()),
1176  var->branching_priority());
1177  }
1178  update_branching_priorities_ = false;
1179  }
1180 
1181  // Time limit.
1182  if (solver_->time_limit() != 0) {
1183  VLOG(1) << "Setting time limit = " << solver_->time_limit() << " ms.";
1184  CheckedGurobiCall(GRBsetdblparam(GRBgetenv(model_), GRB_DBL_PAR_TIMELIMIT,
1186  }
1187 
1188  // We first set our internal MPSolverParameters from 'param' and then set
1189  // any user-specified internal solver parameters via
1190  // solver_specific_parameter_string_.
1191  // Default MPSolverParameters can override custom parameters (for example for
1192  // presolving) and therefore we apply MPSolverParameters first.
1193  SetParameters(param);
1195  solver_->solver_specific_parameter_string_);
1196 
1197  std::unique_ptr<GurobiMPCallbackContext> gurobi_context;
1198  MPCallbackWithGurobiContext mp_callback_with_context;
1199  int gurobi_precrush = 0;
1200  int gurobi_lazy_constraint = 0;
1201  if (callback_ == nullptr) {
1202  CheckedGurobiCall(GRBsetcallbackfunc(model_, nullptr, nullptr));
1203  } else {
1204  gurobi_context = absl::make_unique<GurobiMPCallbackContext>(
1205  env_, &mp_var_to_gurobi_var_, num_gurobi_vars_,
1206  callback_->might_add_cuts(), callback_->might_add_lazy_constraints());
1207  mp_callback_with_context.context = gurobi_context.get();
1208  mp_callback_with_context.callback = callback_;
1209  CheckedGurobiCall(GRBsetcallbackfunc(
1210  model_, CallbackImpl, static_cast<void*>(&mp_callback_with_context)));
1211  gurobi_precrush = callback_->might_add_cuts();
1212  gurobi_lazy_constraint = callback_->might_add_lazy_constraints();
1213  }
1214  CheckedGurobiCall(
1215  GRBsetintparam(GRBgetenv(model_), GRB_INT_PAR_PRECRUSH, gurobi_precrush));
1216  CheckedGurobiCall(GRBsetintparam(
1217  GRBgetenv(model_), GRB_INT_PAR_LAZYCONSTRAINTS, gurobi_lazy_constraint));
1218 
1219  // Solve
1220  timer.Restart();
1221  const int status = GRBoptimize(model_);
1222 
1223  if (status) {
1224  VLOG(1) << "Failed to optimize MIP." << GRBgeterrormsg(env_);
1225  } else {
1226  VLOG(1) << absl::StrFormat("Solved in %s.",
1227  absl::FormatDuration(timer.GetDuration()));
1228  }
1229 
1230  // Get the status.
1231  const int optimization_status = GetIntAttr(GRB_INT_ATTR_STATUS);
1232  VLOG(1) << absl::StrFormat("Solution status %d.\n", optimization_status);
1233  const int solution_count = SolutionCount();
1234 
1235  switch (optimization_status) {
1236  case GRB_OPTIMAL:
1238  break;
1239  case GRB_INFEASIBLE:
1241  break;
1242  case GRB_UNBOUNDED:
1244  break;
1245  case GRB_INF_OR_UNBD:
1246  // TODO(user,user): We could introduce our own "infeasible or
1247  // unbounded" status.
1249  break;
1250  default: {
1251  if (solution_count > 0) {
1253  } else {
1255  }
1256  break;
1257  }
1258  }
1259 
1260  if (IsMIP() && (result_status_ != MPSolver::UNBOUNDED &&
1262  const int error =
1264  LOG_IF(WARNING, error != 0)
1265  << "Best objective bound is not available, error=" << error
1266  << ", message=" << GRBgeterrormsg(env_);
1267  VLOG(1) << "best bound = " << best_objective_bound_;
1268  }
1269 
1270  if (solution_count > 0 && (result_status_ == MPSolver::FEASIBLE ||
1272  current_solution_index_ = 0;
1273  // Get the results.
1274  objective_value_ = GetDoubleAttr(GRB_DBL_ATTR_OBJVAL);
1275  VLOG(1) << "objective = " << objective_value_;
1276 
1277  {
1278  const std::vector<double> grb_variable_values =
1279  GetDoubleAttrArray(GRB_DBL_ATTR_X, num_gurobi_vars_);
1280  for (int i = 0; i < solver_->variables_.size(); ++i) {
1281  MPVariable* const var = solver_->variables_[i];
1282  const double val = grb_variable_values.at(mp_var_to_gurobi_var_.at(i));
1283  var->set_solution_value(val);
1284  VLOG(3) << var->name() << ", value = " << val;
1285  }
1286  }
1287  if (!mip_) {
1288  {
1289  const std::vector<double> grb_reduced_costs =
1290  GetDoubleAttrArray(GRB_DBL_ATTR_RC, num_gurobi_vars_);
1291  for (int i = 0; i < solver_->variables_.size(); ++i) {
1292  MPVariable* const var = solver_->variables_[i];
1293  const double rc = grb_reduced_costs.at(mp_var_to_gurobi_var_.at(i));
1294  var->set_reduced_cost(rc);
1295  VLOG(4) << var->name() << ", reduced cost = " << rc;
1296  }
1297  }
1298 
1299  {
1300  std::vector<double> grb_dual_values =
1301  GetDoubleAttrArray(GRB_DBL_ATTR_PI, num_gurobi_linear_cons_);
1302  for (int i = 0; i < solver_->constraints_.size(); ++i) {
1303  MPConstraint* const ct = solver_->constraints_[i];
1304  const double dual_value =
1305  grb_dual_values.at(mp_cons_to_gurobi_linear_cons_.at(i));
1306  ct->set_dual_value(dual_value);
1307  VLOG(4) << "row " << ct->index() << ", dual value = " << dual_value;
1308  }
1309  }
1310  }
1311  }
1312 
1314  GRBresetparams(GRBgetenv(model_));
1315  return result_status_;
1316 }
1317 
1318 absl::optional<MPSolutionResponse> GurobiInterface::DirectlySolveProto(
1319  const MPModelRequest& request) {
1320  // Here we reuse the Gurobi environment to support single-use license that
1321  // forbids creating a second environment if one already exists.
1322  const auto status_or = GurobiSolveProto(request, env_);
1323  if (status_or.ok()) return status_or.value();
1324  // Special case: if something is not implemented yet, fall back to solving
1325  // through MPSolver.
1326  if (absl::IsUnimplemented(status_or.status())) return absl::nullopt;
1327 
1328  if (request.enable_internal_solver_output()) {
1329  LOG(INFO) << "Invalid Gurobi status: " << status_or.status();
1330  }
1331  MPSolutionResponse response;
1332  response.set_status(MPSOLVER_NOT_SOLVED);
1333  response.set_status_str(status_or.status().ToString());
1334  return response;
1335 }
1336 
1338  // Next solution only supported for MIP
1339  if (!mip_) return false;
1340 
1341  // Make sure we have successfully solved the problem and not modified it.
1343  return false;
1344  }
1345  // Check if we are out of solutions.
1346  if (current_solution_index_ + 1 >= SolutionCount()) {
1347  return false;
1348  }
1349  current_solution_index_++;
1350 
1351  CheckedGurobiCall(GRBsetintparam(
1352  GRBgetenv(model_), GRB_INT_PAR_SOLUTIONNUMBER, current_solution_index_));
1353 
1354  objective_value_ = GetDoubleAttr(GRB_DBL_ATTR_POOLOBJVAL);
1355  const std::vector<double> grb_variable_values =
1356  GetDoubleAttrArray(GRB_DBL_ATTR_XN, num_gurobi_vars_);
1357 
1358  for (int i = 0; i < solver_->variables_.size(); ++i) {
1359  MPVariable* const var = solver_->variables_[i];
1360  var->set_solution_value(
1361  grb_variable_values.at(mp_var_to_gurobi_var_.at(i)));
1362  }
1363  // TODO(user,user): This reset may not be necessary, investigate.
1364  GRBresetparams(GRBgetenv(model_));
1365  return true;
1366 }
1367 
1368 void GurobiInterface::Write(const std::string& filename) {
1369  if (sync_status_ == MUST_RELOAD) {
1370  Reset();
1371  }
1372  ExtractModel();
1373  // Sync solver.
1374  CheckedGurobiCall(GRBupdatemodel(model_));
1375  VLOG(1) << "Writing Gurobi model file \"" << filename << "\".";
1376  const int status = GRBwrite(model_, filename.c_str());
1377  if (status) {
1378  LOG(WARNING) << "Failed to write MIP." << GRBgeterrormsg(env_);
1379  }
1380 }
1381 
1383  return new GurobiInterface(solver, mip);
1384 }
1385 
1387  callback_ = mp_callback;
1388 }
1389 
1390 } // namespace operations_research
#define LOG_IF(severity, condition)
Definition: base/logging.h:479
#define LOG_FIRST_N(severity, n)
Definition: base/logging.h:849
#define CHECK(condition)
Definition: base/logging.h:495
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define CHECK_OK(x)
Definition: base/logging.h:40
#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 ABSL_DIE_IF_NULL
Definition: base/logging.h:39
#define VLOG(verboselevel)
Definition: base/logging.h:978
void Start()
Definition: timer.h:31
absl::Duration GetDuration() const
Definition: timer.h:48
void Restart()
Definition: timer.h:35
void BranchingPriorityChangedForVariable(int var_index) override
void AddRowConstraint(MPConstraint *const ct) override
GurobiInterface(MPSolver *const solver, bool mip)
void Write(const std::string &filename) override
void SetConstraintBounds(int row_index, double lb, double ub) override
MPSolver::ResultStatus Solve(const MPSolverParameters &param) override
void ClearConstraint(MPConstraint *const constraint) override
void SetObjectiveCoefficient(const MPVariable *const variable, double coefficient) override
void SetCoefficient(MPConstraint *const constraint, const MPVariable *const variable, double new_value, double old_value) override
MPSolver::BasisStatus row_status(int constraint_index) const override
double ComputeExactConditionNumber() const override
void SetVariableInteger(int var_index, bool integer) override
void SetCallback(MPCallback *mp_callback) override
void SetObjectiveOffset(double value) override
std::string SolverVersion() const override
void AddVariable(MPVariable *const var) override
void SetVariableBounds(int var_index, double lb, double ub) override
absl::optional< MPSolutionResponse > DirectlySolveProto(const MPModelRequest &request) override
bool AddIndicatorConstraint(MPConstraint *const ct) override
void SetOptimizationDirection(bool maximize) override
MPSolver::BasisStatus column_status(int variable_index) const override
The class for constraints of a Mathematical Programming (MP) model.
int index() const
Returns the index of the constraint in the MPSolver::constraints_.
double offset() const
Gets the constant term in the objective.
This mathematical programming (MP) solver class is the main class though which users build and solve ...
const MPObjective & Objective() const
Returns the objective object.
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.
const std::vector< MPConstraint * > & constraints() const
Returns the array of constraints handled by the MPSolver.
bool SetSolverSpecificParametersAsString(const std::string &parameters)
Advanced usage: pass solver specific parameters in text format.
BasisStatus
Advanced usage: possible basis status values for a variable and the slack variable of a linear constr...
static constexpr int64 kUnknownNumberOfNodes
virtual void SetIntegerParamToUnsupportedValue(MPSolverParameters::IntegerParam param, int value)
static constexpr int64 kUnknownNumberOfIterations
void set_constraint_as_extracted(int ct_index, bool extracted)
void SetMIPParameters(const MPSolverParameters &param)
bool constraint_is_extracted(int ct_index) const
bool variable_is_extracted(int var_index) const
void set_variable_as_extracted(int var_index, bool extracted)
void SetCommonParameters(const MPSolverParameters &param)
This class stores parameter settings for LP and MIP solvers.
@ INCREMENTALITY_OFF
Start solve from scratch.
@ LP_ALGORITHM
Algorithm to solve linear programs.
@ PRESOLVE
Advanced usage: presolve mode.
@ INCREMENTALITY
Advanced usage: incrementality from one solve to the next.
int GetIntegerParam(MPSolverParameters::IntegerParam param) const
Returns the value of an integer parameter.
The class for variables of a Mathematical Programming (MP) model.
int index() const
Returns the index of the variable in the MPSolver::variables_.
SatParameters parameters
SharedResponseManager * response
const std::string name
const Constraint * ct
int64 value
IntVar * var
Definition: expr_array.cc:1858
int64 coef
Definition: expr_array.cc:1859
#define GRB_SUPERBASIC
#define GRB_CB_MIPSOL
#define GRB_DBL_ATTR_UB
#define GRB_INT_ATTR_BRANCHPRIORITY
#define GRB_DBL_ATTR_START
#define GRB_DBL_PAR_MIPGAP
#define GRB_CB_BARRIER
#define GRB_DBL_PAR_FEASIBILITYTOL
#define GRB_MAXIMIZE
#define GRB_NONBASIC_LOWER
#define GRB_INT_ATTR_MODELSENSE
struct _GRBenv GRBenv
#define GRB_INT_ATTR_VBASIS
#define GRB_GREATER_EQUAL
#define GRB_DBL_ATTR_NODECOUNT
#define GRB_INT_PAR_PRESOLVE
#define GRB_DBL_ATTR_ITERCOUNT
#define GRB_INT_PAR_THREADS
#define GRB_OPTIMAL
#define STDCALL
#define GRB_CB_MIPNODE_REL
#define GRB_CB_SIMPLEX
#define GRB_INTEGER
#define GRB_INT_PAR_METHOD
#define GRB_DBL_ATTR_PI
#define GRB_DBL_ATTR_OBJVAL
#define GRB_DBL_ATTR_SLACK
#define GRB_INT_PAR_LAZYCONSTRAINTS
#define GRB_DBL_ATTR_XN
#define GRB_DBL_PAR_OPTIMALITYTOL
#define GRB_CONTINUOUS
#define GRB_CB_MIPSOL_NODCNT
#define GRB_CB_MIPNODE_STATUS
#define GRB_INT_PAR_SCALEFLAG
#define GRB_DBL_ATTR_OBJ
#define GRB_METHOD_BARRIER
struct _GRBmodel GRBmodel
#define GRB_CHAR_ATTR_VTYPE
#define GRB_CB_PRESOLVE
#define GRB_NONBASIC_UPPER
#define GRB_DBL_ATTR_OBJCON
#define GRB_DBL_ATTR_RC
#define GRB_INF_OR_UNBD
#define GRB_DBL_ATTR_X
#define GRB_SUBOPTIMAL
#define GRB_INFEASIBLE
#define GRB_CB_MIP
#define GRB_EQUAL
#define GRB_DBL_PAR_INTFEASTOL
#define GRB_CB_MIPNODE
#define GRB_CHAR_ATTR_SENSE
#define GRB_CB_POLLING
#define GRB_INT_ATTR_NUMVARS
#define GRB_UNBOUNDED
#define GRB_INT_ATTR_NUMCONSTRS
#define GRB_CB_MESSAGE
#define GRB_INT_ATTR_CBASIS
#define GRB_METHOD_DUAL
#define GRB_BASIC
#define GRB_MINIMIZE
#define GRB_INT_ATTR_STATUS
#define GRB_LESS_EQUAL
#define GRB_DBL_ATTR_POOLOBJVAL
#define GRB_DBL_ATTR_LB
#define GRB_INT_PAR_SOLUTIONNUMBER
#define GRB_INT_ATTR_SOLCOUNT
#define GRB_METHOD_PRIMAL
#define GRB_INT_PAR_OUTPUTFLAG
#define GRB_DBL_PAR_TIMELIMIT
#define GRB_UNDEFINED
#define GRB_CB_MIPSOL_SOL
#define GRB_DBL_ATTR_OBJBOUND
#define GRB_INT_PAR_PRECRUSH
#define GRB_DBL_PAR_OBJSCALE
#define GRB_CB_MIPNODE_NODCNT
GRBmodel * model
void * gurobi_internal_callback_data
GurobiMPCallbackContext * context
MPCallback * callback
int where
ABSL_FLAG(int, num_gurobi_threads, 4, "Number of threads available for Gurobi.")
int64_t int64
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
RowIndex row
Definition: markowitz.cc:175
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
std::function< int(GRBenv *, GRBmodel **, const char *, int numvars, double *, double *, double *, char *, char **)> GRBnewmodel
std::function< void(int *, int *, int *)> GRBversion
std::function< int(GRBmodel *model, int numnz, int *cind, double *cval, char sense, double rhs, const char *constrname)> GRBaddconstr
MPSolverInterface * BuildGurobiInterface(bool mip, MPSolver *const solver)
std::function< int(GRBmodel *model, int numnz, int *vind, double *vval, double obj, double lb, double ub, char vtype, const char *varname)> GRBaddvar
std::function< void(GRBenv *)> GRBfreeenv
std::function< int(GRBmodel *, const char *, int, char)> GRBsetcharattrelement
const absl::string_view ToString(MPSolver::OptimizationProblemType optimization_problem_type)
std::function< char *(GRBenv *)> GRBgeterrormsg
std::function< int(GRBmodel *, const char *, int)> GRBsetintattr
std::function< int(GRBmodel *, const char *)> GRBwrite
std::function< int(GRBmodel *model, int(STDCALL *cb)(CB_ARGS), void *usrdata)> GRBsetcallbackfunc
std::function< int(void *cbdata, int lazylen, const int *lazyind, const double *lazyval, char lazysense, double lazyrhs)> GRBcblazy
std::function< int(void *cbdata, int where, int what, void *resultP)> GRBcbget
std::function< int(GRBmodel *, const char *, int *)> GRBgetintattr
std::function< int(GRBmodel *, const char *, int, int *)> GRBgetintattrelement
std::function< int(GRBenv *, const char *, double)> GRBsetdblparam
std::function< void(GRBmodel *)> GRBterminate
std::function< int(GRBenv *dest, GRBenv *src)> GRBcopyparams
std::function< int(GRBmodel *, const char *, double)> GRBsetdblattr
std::function< int(GRBmodel *)> GRBoptimize
std::function< int(GRBmodel *)> GRBupdatemodel
std::function< int(GRBmodel *)> GRBfreemodel
std::function< int(GRBmodel *, const char *, int, int, double *)> GRBgetdblattrarray
std::function< int(GRBmodel *, const char *, int, char *)> GRBgetcharattrelement
std::function< int(GRBenv *)> GRBresetparams
absl::Status SetSolverSpecificParameters(const std::string &parameters, GRBenv *gurobi)
absl::StatusOr< MPSolutionResponse > GurobiSolveProto(const MPModelRequest &request, GRBenv *gurobi_env)
std::function< int(GRBmodel *model, const char *attrname, int element, int newvalue)> GRBsetintattrelement
std::function< int(GRBmodel *model, int numchgs, int *cind, int *vind, double *val)> GRBchgcoeffs
std::function< int(void *cbdata, const double *solution, double *objvalP)> GRBcbsolution
std::function< int(GRBenv *, const char *, double *)> GRBgetdblparam
std::function< int(GRBmodel *, const char *, double *)> GRBgetdblattr
absl::Status LoadGurobiEnvironment(GRBenv **env)
std::function< int(GRBmodel *, const char *, int, double)> GRBsetdblattrelement
std::function< int(GRBmodel *, const char *, int, double *)> GRBgetdblattrelement
std::function< int(void *cbdata, int cutlen, const int *cutind, const double *cutval, char cutsense, double cutrhs)> GRBcbcut
std::function< GRBenv *(GRBmodel *)> GRBgetenv
std::function< int(GRBmodel *model, const char *name, int binvar, int binval, int nvars, const int *vars, const double *vals, char sense, double rhs)> GRBaddgenconstrIndicator
std::function< int(GRBmodel *, int, int *, double *, double, double, const char *)> GRBaddrangeconstr
std::function< int(GRBenv *, const char *, int)> GRBsetintparam
int index
Definition: pack.cc:508
int64 coefficient