22 #include "absl/status/status.h"
23 #include "absl/status/statusor.h"
24 #include "absl/strings/str_cat.h"
25 #include "absl/strings/str_format.h"
26 #include "absl/strings/str_join.h"
27 #include "absl/strings/str_split.h"
28 #include "absl/types/optional.h"
32 #include "ortools/linear_solver/linear_solver.pb.h"
39 constexpr
int GRB_OK = 0;
41 inline absl::Status GurobiCodeToUtilStatus(
int error_code,
42 const char* source_file,
44 const char* statement,
46 if (error_code == GRB_OK)
return absl::OkStatus();
47 return absl::InvalidArgumentError(absl::StrFormat(
48 "Gurobi error code %d (file '%s', line %d) on '%s': %s", error_code,
52 int AddIndicatorConstraint(
const MPGeneralConstraintProto& gen_cst,
54 std::vector<int>* tmp_variables,
55 std::vector<double>* tmp_coefficients) {
56 CHECK(gurobi_model !=
nullptr);
57 CHECK(tmp_variables !=
nullptr);
58 CHECK(tmp_coefficients !=
nullptr);
60 const auto& ind_cst = gen_cst.indicator_constraint();
61 MPConstraintProto cst = ind_cst.constraint();
62 if (cst.lower_bound() > -std::numeric_limits<double>::infinity()) {
64 gurobi_model, gen_cst.name().c_str(), ind_cst.var_index(),
65 ind_cst.var_value(), cst.var_index_size(),
66 cst.mutable_var_index()->mutable_data(),
67 cst.mutable_coefficient()->mutable_data(),
70 if (status != GRB_OK)
return status;
72 if (cst.upper_bound() < std::numeric_limits<double>::infinity() &&
73 cst.lower_bound() != cst.upper_bound()) {
75 ind_cst.var_index(), ind_cst.var_value(),
77 cst.mutable_var_index()->mutable_data(),
78 cst.mutable_coefficient()->mutable_data(),
85 int AddSosConstraint(
const MPSosConstraint& sos_cst,
GRBmodel* gurobi_model,
86 std::vector<int>* tmp_variables,
87 std::vector<double>* tmp_weights) {
88 CHECK(gurobi_model !=
nullptr);
89 CHECK(tmp_variables !=
nullptr);
90 CHECK(tmp_weights !=
nullptr);
92 tmp_variables->resize(sos_cst.var_index_size(), 0);
93 for (
int v = 0; v < sos_cst.var_index_size(); ++v) {
94 (*tmp_variables)[v] = sos_cst.var_index(v);
96 tmp_weights->resize(sos_cst.var_index_size(), 0);
97 if (sos_cst.weight_size() == sos_cst.var_index_size()) {
98 for (
int w = 0; w < sos_cst.weight_size(); ++w) {
99 (*tmp_weights)[w] = sos_cst.weight(w);
104 std::iota(tmp_weights->begin(), tmp_weights->end(), 1);
107 std::vector<int> types = {sos_cst.type() == MPSosConstraint::SOS1_DEFAULT
110 std::vector<int> begins = {0};
112 sos_cst.var_index_size(),
114 begins.data(), tmp_variables->data(),
115 tmp_weights->data());
118 int AddQuadraticConstraint(
const MPGeneralConstraintProto& gen_cst,
120 CHECK(gurobi_model !=
nullptr);
121 constexpr
double kInfinity = std::numeric_limits<double>::infinity();
123 CHECK(gen_cst.has_quadratic_constraint());
124 const MPQuadraticConstraint& quad_cst = gen_cst.quadratic_constraint();
126 auto addqconstr = [](
GRBmodel* gurobi_model, MPQuadraticConstraint quad_cst,
127 char sense,
double rhs,
const std::string&
name) {
130 quad_cst.var_index_size(),
131 quad_cst.mutable_var_index()->mutable_data(),
132 quad_cst.mutable_coefficient()->mutable_data(),
133 quad_cst.qvar1_index_size(),
134 quad_cst.mutable_qvar1_index()->mutable_data(),
135 quad_cst.mutable_qvar2_index()->mutable_data(),
136 quad_cst.mutable_qcoefficient()->mutable_data(),
142 if (quad_cst.has_lower_bound() && quad_cst.lower_bound() > -
kInfinity) {
143 const int grb_status =
144 addqconstr(gurobi_model, gen_cst.quadratic_constraint(),
146 gen_cst.has_name() ? gen_cst.name() +
"_lb" :
"");
147 if (grb_status != GRB_OK)
return grb_status;
149 if (quad_cst.has_upper_bound() && quad_cst.upper_bound() <
kInfinity) {
150 const int grb_status =
151 addqconstr(gurobi_model, gen_cst.quadratic_constraint(),
GRB_LESS_EQUAL,
152 quad_cst.upper_bound(),
153 gen_cst.has_name() ? gen_cst.name() +
"_ub" :
"");
154 if (grb_status != GRB_OK)
return grb_status;
160 int AddAndConstraint(
const MPGeneralConstraintProto& gen_cst,
161 GRBmodel* gurobi_model, std::vector<int>* tmp_variables) {
162 CHECK(gurobi_model !=
nullptr);
163 CHECK(tmp_variables !=
nullptr);
165 auto and_cst = gen_cst.and_constraint();
168 gen_cst.name().c_str(),
169 and_cst.resultant_var_index(),
170 and_cst.var_index_size(),
171 and_cst.mutable_var_index()->mutable_data());
174 int AddOrConstraint(
const MPGeneralConstraintProto& gen_cst,
175 GRBmodel* gurobi_model, std::vector<int>* tmp_variables) {
176 CHECK(gurobi_model !=
nullptr);
177 CHECK(tmp_variables !=
nullptr);
179 auto or_cst = gen_cst.or_constraint();
181 gen_cst.name().c_str(),
182 or_cst.resultant_var_index(),
183 or_cst.var_index_size(),
184 or_cst.mutable_var_index()->mutable_data());
187 int AddMinConstraint(
const MPGeneralConstraintProto& gen_cst,
188 GRBmodel* gurobi_model, std::vector<int>* tmp_variables) {
189 CHECK(gurobi_model !=
nullptr);
190 CHECK(tmp_variables !=
nullptr);
192 auto min_cst = gen_cst.min_constraint();
195 gen_cst.name().c_str(),
196 min_cst.resultant_var_index(),
197 min_cst.var_index_size(),
198 min_cst.mutable_var_index()->mutable_data(),
199 min_cst.has_constant()
201 : std::numeric_limits<double>::infinity());
204 int AddMaxConstraint(
const MPGeneralConstraintProto& gen_cst,
205 GRBmodel* gurobi_model, std::vector<int>* tmp_variables) {
206 CHECK(gurobi_model !=
nullptr);
207 CHECK(tmp_variables !=
nullptr);
209 auto max_cst = gen_cst.max_constraint();
212 gen_cst.name().c_str(),
213 max_cst.resultant_var_index(),
214 max_cst.var_index_size(),
215 max_cst.mutable_var_index()->mutable_data(),
216 max_cst.has_constant()
218 : -std::numeric_limits<double>::infinity());
224 if (
parameters.empty())
return absl::OkStatus();
225 std::vector<std::string> error_messages;
226 for (absl::string_view line : absl::StrSplit(
parameters,
'\n')) {
229 if (line[0] ==
'#')
continue;
230 for (absl::string_view token :
231 absl::StrSplit(line,
',', absl::SkipWhitespace())) {
232 if (token.empty())
continue;
233 std::vector<std::string> key_value =
234 absl::StrSplit(token, absl::ByAnyChar(
" ="), absl::SkipWhitespace());
236 if (key_value.size() != 2) {
237 const std::string current_message =
238 absl::StrCat(
"Cannot parse parameter '", token,
239 "'. Expected format is 'ParameterName value' or "
240 "'ParameterName=value'");
241 error_messages.push_back(current_message);
244 const int gurobi_code =
245 GRBsetparam(gurobi, key_value[0].c_str(), key_value[1].c_str());
246 if (gurobi_code != GRB_OK) {
247 const std::string current_message = absl::StrCat(
248 "Error setting parameter '", key_value[0],
"' to value '",
250 error_messages.push_back(current_message);
253 VLOG(2) << absl::StrCat(
"Set parameter '", key_value[0],
"' to value '",
258 if (error_messages.empty())
return absl::OkStatus();
259 return absl::InvalidArgumentError(absl::StrJoin(error_messages,
"\n"));
263 const MPModelRequest& request,
GRBenv* gurobi_env) {
265 const absl::optional<LazyMutableCopy<MPModelProto>> optional_model =
267 if (!optional_model)
return response;
268 const MPModelProto&
model = optional_model->get();
273 bool gurobi_env_was_created =
false;
275 if (gurobi_env_was_created && gurobi_env !=
nullptr) {
279 if (gurobi_env ==
nullptr) {
283 gurobi_env_was_created =
true;
290 LOG_IF(DFATAL, error_code != GRB_OK)
291 <<
"GRBfreemodel failed with error " << error_code <<
": "
296 #define RETURN_IF_GUROBI_ERROR(x) \
298 GurobiCodeToUtilStatus(x, __FILE__, __LINE__, #x, gurobi_env));
301 model.name().c_str(),
309 if (request.has_solver_specific_parameters()) {
311 request.solver_specific_parameters(),
GRBgetenv(gurobi_model));
312 if (!parameters_status.ok()) {
313 response.set_status(MPSOLVER_MODEL_INVALID_SOLVER_PARAMETERS);
315 std::string(parameters_status.message()));
319 if (request.solver_time_limit_seconds() > 0) {
322 request.solver_time_limit_seconds()));
326 request.enable_internal_solver_output()));
328 const int variable_size =
model.variable_size();
329 bool has_integer_variables =
false;
331 std::vector<double> obj_coeffs(variable_size, 0);
332 std::vector<double> lb(variable_size);
333 std::vector<double> ub(variable_size);
334 std::vector<char> ctype(variable_size);
335 std::vector<const char*> varnames(variable_size);
336 for (
int v = 0; v < variable_size; ++v) {
337 const MPVariableProto& variable =
model.variable(v);
338 obj_coeffs[v] = variable.objective_coefficient();
339 lb[v] = variable.lower_bound();
340 ub[v] = variable.upper_bound();
342 if (variable.is_integer()) has_integer_variables =
true;
343 if (!variable.name().empty()) varnames[v] = variable.name().c_str();
347 GRBaddvars(gurobi_model, variable_size, 0,
nullptr,
nullptr,
nullptr,
349 lb.data(), ub.data(), ctype.data(),
350 const_cast<char**
>(varnames.data())));
353 for (
int i = 0; i <
model.solution_hint().var_index_size(); ++i) {
356 model.solution_hint().var_value(i)));
361 std::vector<int> ct_variables;
362 std::vector<double> ct_coefficients;
363 for (
int c = 0; c <
model.constraint_size(); ++c) {
364 const MPConstraintProto& constraint =
model.constraint(c);
365 const int size = constraint.var_index_size();
366 ct_variables.resize(size, 0);
367 ct_coefficients.resize(size, 0);
368 for (
int i = 0; i < size; ++i) {
369 ct_variables[i] = constraint.var_index(i);
370 ct_coefficients[i] = constraint.coefficient(i);
374 if (constraint.lower_bound() == constraint.upper_bound()) {
376 gurobi_model, size, ct_variables.data(),
377 ct_coefficients.data(),
379 constraint.name().c_str()));
380 }
else if (constraint.lower_bound() ==
381 -std::numeric_limits<double>::infinity()) {
383 gurobi_model, size, ct_variables.data(),
384 ct_coefficients.data(),
386 constraint.name().c_str()));
387 }
else if (constraint.upper_bound() ==
388 std::numeric_limits<double>::infinity()) {
390 gurobi_model, size, ct_variables.data(),
391 ct_coefficients.data(),
393 constraint.name().c_str()));
396 gurobi_model, size, ct_variables.data(),
397 ct_coefficients.data(),
398 constraint.lower_bound(),
399 constraint.upper_bound(),
400 constraint.name().c_str()));
404 for (
const auto& gen_cst :
model.general_constraint()) {
405 switch (gen_cst.general_constraint_case()) {
406 case MPGeneralConstraintProto::kIndicatorConstraint: {
408 gen_cst, gurobi_model, &ct_variables, &ct_coefficients));
411 case MPGeneralConstraintProto::kSosConstraint: {
413 gurobi_model, &ct_variables,
417 case MPGeneralConstraintProto::kQuadraticConstraint: {
421 case MPGeneralConstraintProto::kAbsConstraint: {
424 gen_cst.name().c_str(),
425 gen_cst.abs_constraint().resultant_var_index(),
426 gen_cst.abs_constraint().var_index()));
429 case MPGeneralConstraintProto::kAndConstraint: {
431 AddAndConstraint(gen_cst, gurobi_model, &ct_variables));
434 case MPGeneralConstraintProto::kOrConstraint: {
436 AddOrConstraint(gen_cst, gurobi_model, &ct_variables));
439 case MPGeneralConstraintProto::kMinConstraint: {
441 AddMinConstraint(gen_cst, gurobi_model, &ct_variables));
444 case MPGeneralConstraintProto::kMaxConstraint: {
446 AddMaxConstraint(gen_cst, gurobi_model, &ct_variables));
450 return absl::UnimplementedError(
451 absl::StrFormat(
"General constraints of type %i not supported.",
452 gen_cst.general_constraint_case()));
458 model.maximize() ? -1 : 1));
460 model.objective_offset()));
461 if (
model.has_quadratic_objective()) {
462 MPQuadraticObjective qobj =
model.quadratic_objective();
463 if (qobj.coefficient_size() > 0) {
466 qobj.mutable_qvar1_index()->mutable_data(),
467 qobj.mutable_qvar2_index()->mutable_data(),
468 qobj.mutable_coefficient()->mutable_data()));
475 int optimization_status = 0;
478 int solution_count = 0;
481 switch (optimization_status) {
483 response.set_status(MPSOLVER_OPTIMAL);
486 DLOG(
INFO) <<
"Gurobi solve returned GRB_INF_OR_UNBD, which we treat as "
487 "INFEASIBLE even though it may mean UNBOUNDED.";
489 "The model may actually be unbounded: Gurobi returned "
491 ABSL_FALLTHROUGH_INTENDED;
493 response.set_status(MPSOLVER_INFEASIBLE);
496 response.set_status(MPSOLVER_UNBOUNDED);
499 if (solution_count > 0) {
500 response.set_status(MPSOLVER_FEASIBLE);
502 response.set_status(MPSOLVER_NOT_SOLVED);
504 absl::StrFormat(
"Gurobi status code %d", optimization_status));
510 if (solution_count > 0 && (
response.status() == MPSOLVER_FEASIBLE ||
511 response.status() == MPSOLVER_OPTIMAL)) {
512 double objective_value = 0;
515 response.set_objective_value(objective_value);
516 double best_objective_bound = 0;
518 &best_objective_bound);
519 if (
response.status() == MPSOLVER_OPTIMAL &&
522 response.set_best_objective_bound(objective_value);
525 response.set_best_objective_bound(best_objective_bound);
528 response.mutable_variable_value()->Resize(variable_size, 0);
531 response.mutable_variable_value()->mutable_data()));
535 for (
int v = 0; v < variable_size; ++v) {
536 if (
model.variable(v).is_integer()) {
537 (*
response.mutable_variable_value())[v] =
538 std::round(
response.variable_value(v));
541 if (!has_integer_variables &&
model.general_constraint_size() == 0) {
542 response.mutable_dual_value()->Resize(
model.constraint_size(), 0);
545 response.mutable_dual_value()->mutable_data()));
548 #undef RETURN_IF_GUROBI_ERROR
#define LOG_IF(severity, condition)
#define DCHECK_EQ(val1, val2)
#define VLOG(verboselevel)
SharedResponseManager * response
#define GRB_DBL_ATTR_START
#define GRB_ERROR_DATA_NOT_AVAILABLE
#define GRB_INT_ATTR_MODELSENSE
#define GRB_GREATER_EQUAL
#define GRB_DBL_ATTR_OBJVAL
struct _GRBmodel GRBmodel
#define GRB_DBL_ATTR_OBJCON
#define GRB_INT_ATTR_STATUS
#define GRB_INT_ATTR_SOLCOUNT
#define GRB_INT_PAR_OUTPUTFLAG
#define GRB_DBL_PAR_TIMELIMIT
#define GRB_DBL_ATTR_OBJBOUND
#define RETURN_IF_GUROBI_ERROR(x)
absl::Cleanup< absl::decay_t< Callback > > MakeCleanup(Callback &&callback)
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< int(GRBmodel *model, const char *name, int resvar, int nvars, const int *vars, double constant)> GRBaddgenconstrMin
std::function< int(GRBmodel *model, int numnz, int *cind, double *cval, char sense, double rhs, const char *constrname)> GRBaddconstr
std::function< int(GRBmodel *model, int numlnz, int *lind, double *lval, int numqnz, int *qrow, int *qcol, double *qval, char sense, double rhs, const char *QCname)> GRBaddqconstr
std::function< void(GRBenv *)> GRBfreeenv
std::function< char *(GRBenv *)> GRBgeterrormsg
std::function< int(GRBmodel *, const char *, int)> GRBsetintattr
std::function< int(GRBenv *env, const char *paramname, const char *value)> GRBsetparam
std::function< int(GRBmodel *model, const char *name, int resvar, int argvar)> GRBaddgenconstrAbs
std::function< int(GRBmodel *, const char *, int *)> GRBgetintattr
std::function< int(GRBenv *, const char *, double)> GRBsetdblparam
std::function< int(GRBmodel *, const char *, double)> GRBsetdblattr
std::function< int(GRBmodel *)> GRBoptimize
std::function< int(GRBmodel *)> GRBupdatemodel
std::function< int(GRBmodel *model, int numqnz, int *qrow, int *qcol, double *qval)> GRBaddqpterms
std::function< int(GRBmodel *model, const char *name, int resvar, int nvars, const int *vars, double constant)> GRBaddgenconstrMax
std::function< int(GRBmodel *)> GRBfreemodel
std::function< int(GRBmodel *, const char *, int, int, double *)> GRBgetdblattrarray
std::function< int(GRBmodel *, int, int, int *, int *, double *, double *, double *, double *, char *, char **)> GRBaddvars
std::function< int(GRBmodel *model, const char *name, int resvar, int nvars, const int *vars)> GRBaddgenconstrAnd
absl::Status SetSolverSpecificParameters(const std::string ¶meters, GRBenv *gurobi)
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).
absl::StatusOr< MPSolutionResponse > GurobiSolveProto(const MPModelRequest &request, GRBenv *gurobi_env)
std::function< int(GRBmodel *model, const char *name, int resvar, int nvars, const int *vars)> GRBaddgenconstrOr
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 *model, int numsos, int nummembers, int *types, int *beg, int *ind, double *weight)> GRBaddsos
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
#define RETURN_IF_ERROR(expr)