OR-Tools  8.2
gscip.cc
Go to the documentation of this file.
1 // Copyright 2010-2018 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
14 #include "ortools/gscip/gscip.h"
15 
16 #include <cstdint>
17 
18 #include "absl/container/flat_hash_set.h"
19 #include "absl/status/statusor.h"
20 #include "absl/strings/str_cat.h"
21 #include "ortools/base/logging.h"
28 #include "scip/cons_linear.h"
29 #include "scip/scip_general.h"
30 #include "scip/scip_param.h"
31 #include "scip/scip_solvingstats.h"
32 #include "scip/scipdefplugins.h"
33 #include "scip/type_cons.h"
34 
35 namespace operations_research {
36 
37 #define RETURN_ERROR_UNLESS(x) \
38  if (!(x)) \
39  return util::StatusBuilder(absl::InvalidArgumentError(absl::StrFormat( \
40  "Condition violated at %s:%d: %s", __FILE__, __LINE__, #x)))
41 
42 namespace {
43 
44 constexpr absl::string_view kLinearConstraintHandlerName = "linear";
45 
46 SCIP_VARTYPE ConvertVarType(const GScipVarType var_type) {
47  switch (var_type) {
49  return SCIP_VARTYPE_CONTINUOUS;
51  return SCIP_VARTYPE_IMPLINT;
53  return SCIP_VARTYPE_INTEGER;
54  }
55 }
56 
57 GScipVarType ConvertVarType(const SCIP_VARTYPE var_type) {
58  switch (var_type) {
59  case SCIP_VARTYPE_CONTINUOUS:
61  case SCIP_VARTYPE_IMPLINT:
63  case SCIP_VARTYPE_INTEGER:
64  case SCIP_VARTYPE_BINARY:
66  }
67 }
68 
69 GScipOutput::Status ConvertStatus(const SCIP_STATUS scip_status) {
70  switch (scip_status) {
71  case SCIP_STATUS_UNKNOWN:
72  return GScipOutput::UNKNOWN;
73  case SCIP_STATUS_USERINTERRUPT:
74  return GScipOutput::USER_INTERRUPT;
75  case SCIP_STATUS_BESTSOLLIMIT:
76  return GScipOutput::BEST_SOL_LIMIT;
77  case SCIP_STATUS_MEMLIMIT:
78  return GScipOutput::MEM_LIMIT;
79  case SCIP_STATUS_NODELIMIT:
80  return GScipOutput::NODE_LIMIT;
81  case SCIP_STATUS_RESTARTLIMIT:
82  return GScipOutput::RESTART_LIMIT;
83  case SCIP_STATUS_SOLLIMIT:
84  return GScipOutput::SOL_LIMIT;
85  case SCIP_STATUS_STALLNODELIMIT:
86  return GScipOutput::STALL_NODE_LIMIT;
87  case SCIP_STATUS_TIMELIMIT:
88  return GScipOutput::TIME_LIMIT;
89  case SCIP_STATUS_TOTALNODELIMIT:
90  return GScipOutput::TOTAL_NODE_LIMIT;
91  case SCIP_STATUS_OPTIMAL:
92  return GScipOutput::OPTIMAL;
93  case SCIP_STATUS_GAPLIMIT:
94  return GScipOutput::GAP_LIMIT;
95  case SCIP_STATUS_INFEASIBLE:
96  return GScipOutput::INFEASIBLE;
97  case SCIP_STATUS_UNBOUNDED:
98  return GScipOutput::UNBOUNDED;
99  case SCIP_STATUS_INFORUNBD:
100  return GScipOutput::INF_OR_UNBD;
101  case SCIP_STATUS_TERMINATE:
102  return GScipOutput::TERMINATE;
103  default:
104  LOG(FATAL) << "Unrecognized scip status: " << scip_status;
105  }
106 }
107 
108 SCIP_PARAMEMPHASIS ConvertEmphasis(
109  const GScipParameters::Emphasis gscip_emphasis) {
110  switch (gscip_emphasis) {
111  case GScipParameters::DEFAULT_EMPHASIS:
112  return SCIP_PARAMEMPHASIS_DEFAULT;
113  case GScipParameters::CP_SOLVER:
114  return SCIP_PARAMEMPHASIS_CPSOLVER;
115  case GScipParameters::EASY_CIP:
116  return SCIP_PARAMEMPHASIS_EASYCIP;
117  case GScipParameters::FEASIBILITY:
118  return SCIP_PARAMEMPHASIS_FEASIBILITY;
119  case GScipParameters::HARD_LP:
120  return SCIP_PARAMEMPHASIS_HARDLP;
121  case GScipParameters::OPTIMALITY:
122  return SCIP_PARAMEMPHASIS_OPTIMALITY;
124  return SCIP_PARAMEMPHASIS_COUNTER;
125  case GScipParameters::PHASE_FEAS:
126  return SCIP_PARAMEMPHASIS_PHASEFEAS;
127  case GScipParameters::PHASE_IMPROVE:
128  return SCIP_PARAMEMPHASIS_PHASEIMPROVE;
129  case GScipParameters::PHASE_PROOF:
130  return SCIP_PARAMEMPHASIS_PHASEPROOF;
131  default:
132  LOG(FATAL) << "Unrecognized gscip_emphasis: "
133  << ProtoEnumToString(gscip_emphasis);
134  }
135 }
136 
137 SCIP_PARAMSETTING ConvertMetaParamValue(
138  const GScipParameters::MetaParamValue gscip_meta_param_value) {
139  switch (gscip_meta_param_value) {
140  case GScipParameters::DEFAULT_META_PARAM_VALUE:
141  return SCIP_PARAMSETTING_DEFAULT;
142  case GScipParameters::AGGRESSIVE:
143  return SCIP_PARAMSETTING_AGGRESSIVE;
144  case GScipParameters::FAST:
145  return SCIP_PARAMSETTING_FAST;
146  case GScipParameters::OFF:
147  return SCIP_PARAMSETTING_OFF;
148  default:
149  LOG(FATAL) << "Unrecognized gscip_meta_param_value: "
150  << ProtoEnumToString(gscip_meta_param_value);
151  }
152 }
153 } // namespace
154 
156  static GScipVariableOptions var_options;
157  return var_options;
158 }
159 
161  static GScipConstraintOptions constraint_options;
162  return constraint_options;
163 }
164 
165 absl::Status GScip::SetParams(const GScipParameters& params,
166  const std::string& legacy_params) {
167  if (params.has_silence_output()) {
168  SCIPsetMessagehdlrQuiet(scip_, params.silence_output());
169  }
170  if (!params.search_logs_filename().empty()) {
171  SCIPsetMessagehdlrLogfile(scip_, params.search_logs_filename().c_str());
172  }
173  const SCIP_Bool set_param_quiet =
174  static_cast<SCIP_Bool>(!params.silence_output());
175 
176  RETURN_IF_SCIP_ERROR(SCIPsetEmphasis(
177  scip_, ConvertEmphasis(params.emphasis()), set_param_quiet));
178  if (params.has_heuristics()) {
179  RETURN_IF_SCIP_ERROR(SCIPsetHeuristics(
180  scip_, ConvertMetaParamValue(params.heuristics()), set_param_quiet));
181  }
182  if (params.has_presolve()) {
183  RETURN_IF_SCIP_ERROR(SCIPsetPresolving(
184  scip_, ConvertMetaParamValue(params.presolve()), set_param_quiet));
185  }
186  if (params.has_separating()) {
187  RETURN_IF_SCIP_ERROR(SCIPsetSeparating(
188  scip_, ConvertMetaParamValue(params.separating()), set_param_quiet));
189  }
190  for (const auto& bool_param : params.bool_params()) {
192  (SCIPsetBoolParam(scip_, bool_param.first.c_str(), bool_param.second)));
193  }
194  for (const auto& int_param : params.int_params()) {
196  (SCIPsetIntParam(scip_, int_param.first.c_str(), int_param.second)));
197  }
198  for (const auto& long_param : params.long_params()) {
199  RETURN_IF_SCIP_ERROR((SCIPsetLongintParam(scip_, long_param.first.c_str(),
200  long_param.second)));
201  }
202  for (const auto& char_param : params.char_params()) {
203  if (char_param.second.size() != 1) {
204  return absl::InvalidArgumentError(
205  absl::StrCat("Character parameters must be single character strings, "
206  "but parameter: ",
207  char_param.first, " was: ", char_param.second));
208  }
209  RETURN_IF_SCIP_ERROR((SCIPsetCharParam(scip_, char_param.first.c_str(),
210  char_param.second[0])));
211  }
212  for (const auto& string_param : params.string_params()) {
213  RETURN_IF_SCIP_ERROR((SCIPsetStringParam(scip_, string_param.first.c_str(),
214  string_param.second.c_str())));
215  }
216  for (const auto& real_param : params.real_params()) {
218  (SCIPsetRealParam(scip_, real_param.first.c_str(), real_param.second)));
219  }
220  if (!legacy_params.empty()) {
222  LegacyScipSetSolverSpecificParameters(legacy_params, scip_));
223  }
224  return absl::OkStatus();
225 }
226 
227 absl::StatusOr<std::unique_ptr<GScip>> GScip::Create(
228  const std::string& problem_name) {
229  SCIP* scip = nullptr;
230  RETURN_IF_SCIP_ERROR(SCIPcreate(&scip));
231  RETURN_IF_SCIP_ERROR(SCIPincludeDefaultPlugins(scip));
232  RETURN_IF_SCIP_ERROR(SCIPcreateProbBasic(scip, problem_name.c_str()));
233  // NOTE(user): the constructor is private, so we cannot call make_unique.
234  return absl::WrapUnique(new GScip(scip));
235 }
236 
237 GScip::GScip(SCIP* scip) : scip_(scip) {}
238 
239 double GScip::ScipInf() { return SCIPinfinity(scip_); }
240 
241 absl::Status GScip::FreeTransform() {
242  return SCIP_TO_STATUS(SCIPfreeTransform(scip_));
243 }
244 
245 std::string GScip::ScipVersion() {
246  return absl::StrFormat("SCIP %d.%d.%d [LP solver: %s]", SCIPmajorVersion(),
247  SCIPminorVersion(), SCIPtechVersion(),
248  SCIPlpiGetSolverName());
249 }
250 
252  if (scip_ == nullptr) {
253  return true;
254  }
255  return SCIPinterruptSolve(scip_) == SCIP_OKAY;
256 }
257 
258 absl::Status GScip::CleanUp() {
259  if (scip_ != nullptr) {
260  for (SCIP_VAR* variable : variables_) {
261  if (variable != nullptr) {
262  RETURN_IF_SCIP_ERROR(SCIPreleaseVar(scip_, &variable));
263  }
264  }
265  for (SCIP_CONS* constraint : constraints_) {
266  if (constraint != nullptr) {
267  RETURN_IF_SCIP_ERROR(SCIPreleaseCons(scip_, &constraint));
268  }
269  }
270  RETURN_IF_SCIP_ERROR(SCIPfree(&scip_));
271  }
272  return absl::OkStatus();
273 }
274 
276  const absl::Status clean_up_status = CleanUp();
277  LOG_IF(DFATAL, !clean_up_status.ok()) << clean_up_status;
278 }
279 
280 absl::StatusOr<SCIP_VAR*> GScip::AddVariable(
281  double lb, double ub, double obj_coef, GScipVarType var_type,
282  const std::string& var_name, const GScipVariableOptions& options) {
283  SCIP_VAR* var = nullptr;
284  lb = ScipInfClamp(lb);
285  ub = ScipInfClamp(ub);
286  RETURN_IF_SCIP_ERROR(SCIPcreateVarBasic(scip_, /*var=*/&var,
287  /*name=*/var_name.c_str(),
288  /*lb=*/lb, /*ub=*/ub,
289  /*obj=*/obj_coef,
290  ConvertVarType(var_type)));
291  RETURN_IF_SCIP_ERROR(SCIPvarSetInitial(var, options.initial));
292  RETURN_IF_SCIP_ERROR(SCIPvarSetRemovable(var, options.removable));
293  RETURN_IF_SCIP_ERROR(SCIPaddVar(scip_, var));
294  if (options.keep_alive) {
295  variables_.insert(var);
296  } else {
297  RETURN_IF_SCIP_ERROR(SCIPreleaseVar(scip_, &var));
298  }
299  return var;
300 }
301 
302 absl::Status GScip::MaybeKeepConstraintAlive(
303  SCIP_CONS* constraint, const GScipConstraintOptions& options) {
304  if (options.keep_alive) {
305  constraints_.insert(constraint);
306  } else {
307  RETURN_IF_SCIP_ERROR(SCIPreleaseCons(scip_, &constraint));
308  }
309  return absl::OkStatus();
310 }
311 
312 absl::StatusOr<SCIP_CONS*> GScip::AddLinearConstraint(
313  const GScipLinearRange& range, const std::string& name,
314  const GScipConstraintOptions& options) {
315  SCIP_CONS* constraint = nullptr;
316  RETURN_ERROR_UNLESS(range.variables.size() == range.coefficients.size())
317  << "Error adding constraint: " << name << ".";
318  RETURN_IF_SCIP_ERROR(SCIPcreateConsLinear(
319  scip_, &constraint, name.c_str(), range.variables.size(),
320  const_cast<SCIP_VAR**>(range.variables.data()),
321  const_cast<double*>(range.coefficients.data()),
322  ScipInfClamp(range.lower_bound), ScipInfClamp(range.upper_bound),
323  /*initial=*/options.initial,
324  /*separate=*/options.separate,
325  /*enforce=*/options.enforce,
326  /*check=*/options.check,
327  /*propagate=*/options.propagate,
328  /*local=*/options.local,
329  /*modifiable=*/options.modifiable,
330  /*dynamic=*/options.dynamic,
331  /*removable=*/options.removable,
332  /*stickingatnode=*/options.sticking_at_node));
333  RETURN_IF_SCIP_ERROR(SCIPaddCons(scip_, constraint));
334  RETURN_IF_ERROR(MaybeKeepConstraintAlive(constraint, options));
335  return constraint;
336 }
337 
338 absl::StatusOr<SCIP_CONS*> GScip::AddQuadraticConstraint(
339  const GScipQuadraticRange& range, const std::string& name,
340  const GScipConstraintOptions& options) {
341  SCIP_CONS* constraint = nullptr;
342  const int num_lin_vars = range.linear_variables.size();
343  RETURN_ERROR_UNLESS(num_lin_vars == range.linear_coefficients.size())
344  << "Error adding quadratic constraint: " << name << " in linear term.";
345  const int num_quad_vars = range.quadratic_variables1.size();
346  RETURN_ERROR_UNLESS(num_quad_vars == range.quadratic_variables2.size())
347  << "Error adding quadratic constraint: " << name << " in quadratic term.";
348  RETURN_ERROR_UNLESS(num_quad_vars == range.quadratic_coefficients.size())
349  << "Error adding quadratic constraint: " << name << " in quadratic term.";
350  RETURN_IF_SCIP_ERROR(SCIPcreateConsQuadratic(
351  scip_, &constraint, name.c_str(), num_lin_vars,
352  const_cast<SCIP_Var**>(range.linear_variables.data()),
353  const_cast<double*>(range.linear_coefficients.data()), num_quad_vars,
354  const_cast<SCIP_Var**>(range.quadratic_variables1.data()),
355  const_cast<SCIP_Var**>(range.quadratic_variables2.data()),
356  const_cast<double*>(range.quadratic_coefficients.data()),
357  ScipInfClamp(range.lower_bound), ScipInfClamp(range.upper_bound),
358  /*initial=*/options.initial,
359  /*separate=*/options.separate,
360  /*enforce=*/options.enforce,
361  /*check=*/options.check,
362  /*propagate=*/options.propagate,
363  /*local=*/options.local,
364  /*modifiable=*/options.modifiable,
365  /*dynamic=*/options.dynamic,
366  /*removable=*/options.removable));
367  RETURN_IF_SCIP_ERROR(SCIPaddCons(scip_, constraint));
368  RETURN_IF_ERROR(MaybeKeepConstraintAlive(constraint, options));
369  return constraint;
370 }
371 
372 absl::StatusOr<SCIP_CONS*> GScip::AddIndicatorConstraint(
373  const GScipIndicatorConstraint& indicator_constraint,
374  const std::string& name, const GScipConstraintOptions& options) {
375  SCIP_VAR* indicator = indicator_constraint.indicator_variable;
376  RETURN_ERROR_UNLESS(indicator != nullptr)
377  << "Error adding indicator constraint: " << name << ".";
378  if (indicator_constraint.negate_indicator) {
379  RETURN_IF_SCIP_ERROR(SCIPgetNegatedVar(scip_, indicator, &indicator));
380  }
381 
382  SCIP_CONS* constraint = nullptr;
383  RETURN_ERROR_UNLESS(indicator_constraint.variables.size() ==
384  indicator_constraint.coefficients.size())
385  << "Error adding indicator constraint: " << name << ".";
386  RETURN_IF_SCIP_ERROR(SCIPcreateConsIndicator(
387  scip_, &constraint, name.c_str(), indicator,
388  indicator_constraint.variables.size(),
389  const_cast<SCIP_Var**>(indicator_constraint.variables.data()),
390  const_cast<double*>(indicator_constraint.coefficients.data()),
391  ScipInfClamp(indicator_constraint.upper_bound),
392  /*initial=*/options.initial,
393  /*separate=*/options.separate,
394  /*enforce=*/options.enforce,
395  /*check=*/options.check,
396  /*propagate=*/options.propagate,
397  /*local=*/options.local,
398  /*dynamic=*/options.dynamic,
399  /*removable=*/options.removable,
400  /*stickingatnode=*/options.sticking_at_node));
401  RETURN_IF_SCIP_ERROR(SCIPaddCons(scip_, constraint));
402  RETURN_IF_ERROR(MaybeKeepConstraintAlive(constraint, options));
403  return constraint;
404 }
405 
406 absl::StatusOr<SCIP_CONS*> GScip::AddAndConstraint(
407  const GScipLogicalConstraintData& logical_data, const std::string& name,
408  const GScipConstraintOptions& options) {
409  RETURN_ERROR_UNLESS(logical_data.resultant != nullptr)
410  << "Error adding and constraint: " << name << ".";
411  SCIP_CONS* constraint = nullptr;
413  SCIPcreateConsAnd(scip_, &constraint, name.c_str(),
414  logical_data.resultant, logical_data.operators.size(),
415  const_cast<SCIP_VAR**>(logical_data.operators.data()),
416  /*initial=*/options.initial,
417  /*separate=*/options.separate,
418  /*enforce=*/options.enforce,
419  /*check=*/options.check,
420  /*propagate=*/options.propagate,
421  /*local=*/options.local,
422  /*modifiable=*/options.modifiable,
423  /*dynamic=*/options.dynamic,
424  /*removable=*/options.removable,
425  /*stickingatnode=*/options.sticking_at_node));
426  RETURN_IF_SCIP_ERROR(SCIPaddCons(scip_, constraint));
427  RETURN_IF_ERROR(MaybeKeepConstraintAlive(constraint, options));
428  return constraint;
429 }
430 
431 absl::StatusOr<SCIP_CONS*> GScip::AddOrConstraint(
432  const GScipLogicalConstraintData& logical_data, const std::string& name,
433  const GScipConstraintOptions& options) {
434  RETURN_ERROR_UNLESS(logical_data.resultant != nullptr)
435  << "Error adding or constraint: " << name << ".";
436  SCIP_CONS* constraint = nullptr;
438  SCIPcreateConsOr(scip_, &constraint, name.c_str(), logical_data.resultant,
439  logical_data.operators.size(),
440  const_cast<SCIP_Var**>(logical_data.operators.data()),
441  /*initial=*/options.initial,
442  /*separate=*/options.separate,
443  /*enforce=*/options.enforce,
444  /*check=*/options.check,
445  /*propagate=*/options.propagate,
446  /*local=*/options.local,
447  /*modifiable=*/options.modifiable,
448  /*dynamic=*/options.dynamic,
449  /*removable=*/options.removable,
450  /*stickingatnode=*/options.sticking_at_node));
451  RETURN_IF_SCIP_ERROR(SCIPaddCons(scip_, constraint));
452  RETURN_IF_ERROR(MaybeKeepConstraintAlive(constraint, options));
453  return constraint;
454 }
455 
456 namespace {
457 
458 absl::Status ValidateSOSData(const GScipSOSData& sos_data,
459  const std::string& name) {
460  RETURN_ERROR_UNLESS(!sos_data.variables.empty())
461  << "Error adding SOS constraint: " << name << ".";
462  if (!sos_data.weights.empty()) {
463  RETURN_ERROR_UNLESS(sos_data.variables.size() == sos_data.weights.size())
464  << " Error adding SOS constraint: " << name << ".";
465  }
466  absl::flat_hash_set<double> distinct_weights;
467  for (const double w : sos_data.weights) {
468  RETURN_ERROR_UNLESS(!distinct_weights.contains(w))
469  << "Error adding SOS constraint: " << name
470  << ", weights must be distinct, but found value " << w << " twice.";
471  distinct_weights.insert(w);
472  }
473  return absl::OkStatus();
474 }
475 
476 } // namespace
477 
478 absl::StatusOr<SCIP_CONS*> GScip::AddSOS1Constraint(
479  const GScipSOSData& sos_data, const std::string& name,
480  const GScipConstraintOptions& options) {
481  RETURN_IF_ERROR(ValidateSOSData(sos_data, name));
482  SCIP_CONS* constraint = nullptr;
483  double* weights = nullptr;
484  if (!sos_data.weights.empty()) {
485  weights = const_cast<double*>(sos_data.weights.data());
486  }
487 
488  RETURN_IF_SCIP_ERROR(SCIPcreateConsSOS1(
489  scip_, &constraint, name.c_str(), sos_data.variables.size(),
490  const_cast<SCIP_Var**>(sos_data.variables.data()), weights,
491  /*initial=*/options.initial,
492  /*separate=*/options.separate,
493  /*enforce=*/options.enforce,
494  /*check=*/options.check,
495  /*propagate=*/options.propagate,
496  /*local=*/options.local,
497  /*dynamic=*/options.dynamic,
498  /*removable=*/options.removable,
499  /*stickingatnode=*/options.sticking_at_node));
500  RETURN_IF_SCIP_ERROR(SCIPaddCons(scip_, constraint));
501  RETURN_IF_ERROR(MaybeKeepConstraintAlive(constraint, options));
502  return constraint;
503 }
504 
505 absl::StatusOr<SCIP_CONS*> GScip::AddSOS2Constraint(
506  const GScipSOSData& sos_data, const std::string& name,
507  const GScipConstraintOptions& options) {
508  RETURN_IF_ERROR(ValidateSOSData(sos_data, name));
509  SCIP_CONS* constraint = nullptr;
510  double* weights = nullptr;
511  if (!sos_data.weights.empty()) {
512  weights = const_cast<double*>(sos_data.weights.data());
513  }
514  RETURN_IF_SCIP_ERROR(SCIPcreateConsSOS2(
515  scip_, &constraint, name.c_str(), sos_data.variables.size(),
516  const_cast<SCIP_Var**>(sos_data.variables.data()), weights,
517  /*initial=*/options.initial,
518  /*separate=*/options.separate,
519  /*enforce=*/options.enforce,
520  /*check=*/options.check,
521  /*propagate=*/options.propagate,
522  /*local=*/options.local,
523  /*dynamic=*/options.dynamic,
524  /*removable=*/options.removable,
525  /*stickingatnode=*/options.sticking_at_node));
526  RETURN_IF_SCIP_ERROR(SCIPaddCons(scip_, constraint));
527  RETURN_IF_ERROR(MaybeKeepConstraintAlive(constraint, options));
528  return constraint;
529 }
530 
531 absl::Status GScip::SetMaximize(bool is_maximize) {
532  RETURN_IF_SCIP_ERROR(SCIPsetObjsense(
533  scip_, is_maximize ? SCIP_OBJSENSE_MAXIMIZE : SCIP_OBJSENSE_MINIMIZE));
534  return absl::OkStatus();
535 }
536 
537 absl::Status GScip::SetObjectiveOffset(double offset) {
538  double old_offset = SCIPgetOrigObjoffset(scip_);
539  double delta_offset = offset - old_offset;
540  RETURN_IF_SCIP_ERROR(SCIPaddOrigObjoffset(scip_, delta_offset));
541  return absl::OkStatus();
542 }
543 
545  return SCIPgetObjsense(scip_) == SCIP_OBJSENSE_MAXIMIZE;
546 }
547 
548 double GScip::ObjectiveOffset() { return SCIPgetOrigObjoffset(scip_); }
549 
550 absl::Status GScip::SetBranchingPriority(SCIP_VAR* var, int priority) {
551  RETURN_IF_SCIP_ERROR(SCIPchgVarBranchPriority(scip_, var, priority));
552  return absl::OkStatus();
553 }
554 
555 absl::Status GScip::SetLb(SCIP_VAR* var, double lb) {
556  lb = ScipInfClamp(lb);
557  RETURN_IF_SCIP_ERROR(SCIPchgVarLb(scip_, var, lb));
558  return absl::OkStatus();
559 }
560 
561 absl::Status GScip::SetUb(SCIP_VAR* var, double ub) {
562  ub = ScipInfClamp(ub);
563  RETURN_IF_SCIP_ERROR(SCIPchgVarUb(scip_, var, ub));
564  return absl::OkStatus();
565 }
566 
567 absl::Status GScip::SetObjCoef(SCIP_VAR* var, double obj_coef) {
568  RETURN_IF_SCIP_ERROR(SCIPchgVarObj(scip_, var, obj_coef));
569  return absl::OkStatus();
570 }
571 
572 absl::Status GScip::SetVarType(SCIP_VAR* var, GScipVarType var_type) {
573  SCIP_Bool infeasible;
575  SCIPchgVarType(scip_, var, ConvertVarType(var_type), &infeasible));
576  return absl::OkStatus();
577 }
578 
579 absl::Status GScip::DeleteVariable(SCIP_VAR* var) {
580  SCIP_Bool did_delete;
581  RETURN_IF_SCIP_ERROR(SCIPdelVar(scip_, var, &did_delete));
582  RETURN_ERROR_UNLESS(static_cast<bool>(did_delete))
583  << "Failed to delete variable named: " << Name(var);
584  variables_.erase(var);
585  RETURN_IF_SCIP_ERROR(SCIPreleaseVar(scip_, &var));
586  return absl::OkStatus();
587 }
588 
590  const absl::flat_hash_set<SCIP_VAR*>& vars) {
591  for (SCIP_CONS* constraint : constraints_) {
592  if (!IsConstraintLinear(constraint)) {
593  return absl::InvalidArgumentError(absl::StrCat(
594  "Model contains nonlinear constraint: ", Name(constraint)));
595  }
596  }
597  return absl::OkStatus();
598 }
599 
600 absl::Status GScip::SafeBulkDelete(const absl::flat_hash_set<SCIP_VAR*>& vars) {
602  // Now, we can assume that all constraints are linear.
603  for (SCIP_CONS* constraint : constraints_) {
604  const absl::Span<SCIP_VAR* const> nonzeros =
605  LinearConstraintVariables(constraint);
606  const std::vector<SCIP_VAR*> nonzeros_copy(nonzeros.begin(),
607  nonzeros.end());
608  for (SCIP_VAR* var : nonzeros_copy) {
609  if (vars.contains(var)) {
610  RETURN_IF_ERROR(SetLinearConstraintCoef(constraint, var, 0.0));
611  }
612  }
613  }
614  for (SCIP_VAR* const var : vars) {
616  }
617  return absl::OkStatus();
618 }
619 
620 double GScip::Lb(SCIP_VAR* var) {
621  return ScipInfUnclamp(SCIPvarGetLbOriginal(var));
622 }
623 
624 double GScip::Ub(SCIP_VAR* var) {
625  return ScipInfUnclamp(SCIPvarGetUbOriginal(var));
626 }
627 
628 double GScip::ObjCoef(SCIP_VAR* var) { return SCIPvarGetObj(var); }
629 
631  return ConvertVarType(SCIPvarGetType(var));
632 }
633 
634 absl::string_view GScip::Name(SCIP_VAR* var) { return SCIPvarGetName(var); }
635 
636 absl::string_view GScip::ConstraintType(SCIP_CONS* constraint) {
637  return absl::string_view(SCIPconshdlrGetName(SCIPconsGetHdlr(constraint)));
638 }
639 
640 bool GScip::IsConstraintLinear(SCIP_CONS* constraint) {
641  return ConstraintType(constraint) == kLinearConstraintHandlerName;
642 }
643 
644 absl::Span<const double> GScip::LinearConstraintCoefficients(
645  SCIP_CONS* constraint) {
646  int num_vars = SCIPgetNVarsLinear(scip_, constraint);
647  return absl::MakeConstSpan(SCIPgetValsLinear(scip_, constraint), num_vars);
648 }
649 
650 absl::Span<SCIP_VAR* const> GScip::LinearConstraintVariables(
651  SCIP_CONS* constraint) {
652  int num_vars = SCIPgetNVarsLinear(scip_, constraint);
653  return absl::MakeConstSpan(SCIPgetVarsLinear(scip_, constraint), num_vars);
654 }
655 
656 double GScip::LinearConstraintLb(SCIP_CONS* constraint) {
657  return ScipInfUnclamp(SCIPgetLhsLinear(scip_, constraint));
658 }
659 
660 double GScip::LinearConstraintUb(SCIP_CONS* constraint) {
661  return ScipInfUnclamp(SCIPgetRhsLinear(scip_, constraint));
662 }
663 
664 absl::string_view GScip::Name(SCIP_CONS* constraint) {
665  return SCIPconsGetName(constraint);
666 }
667 
668 absl::Status GScip::SetLinearConstraintLb(SCIP_CONS* constraint, double lb) {
669  lb = ScipInfClamp(lb);
670  RETURN_IF_SCIP_ERROR(SCIPchgLhsLinear(scip_, constraint, lb));
671  return absl::OkStatus();
672 }
673 
674 absl::Status GScip::SetLinearConstraintUb(SCIP_CONS* constraint, double ub) {
675  ub = ScipInfClamp(ub);
676  RETURN_IF_SCIP_ERROR(SCIPchgRhsLinear(scip_, constraint, ub));
677  return absl::OkStatus();
678 }
679 
680 absl::Status GScip::DeleteConstraint(SCIP_CONS* constraint) {
681  RETURN_IF_SCIP_ERROR(SCIPdelCons(scip_, constraint));
682  constraints_.erase(constraint);
683  RETURN_IF_SCIP_ERROR(SCIPreleaseCons(scip_, &constraint));
684  return absl::OkStatus();
685 }
686 
687 absl::Status GScip::SetLinearConstraintCoef(SCIP_CONS* constraint,
688  SCIP_VAR* var, double value) {
689  // TODO(user): this operation is slow (linear in the nnz in the constraint).
690  // It would be better to just use a bulk operation, but there doesn't appear
691  // to be any?
692  RETURN_IF_SCIP_ERROR(SCIPchgCoefLinear(scip_, constraint, var, value));
693  return absl::OkStatus();
694 }
695 
696 absl::StatusOr<GScipHintResult> GScip::SuggestHint(
697  const GScipSolution& partial_solution) {
698  SCIP_SOL* solution;
699  const int scip_num_vars = SCIPgetNOrigVars(scip_);
700  const bool is_solution_partial = partial_solution.size() < scip_num_vars;
701  if (is_solution_partial) {
702  RETURN_IF_SCIP_ERROR(SCIPcreatePartialSol(scip_, &solution, nullptr));
703  } else {
704  // This is actually a full solution
705  RETURN_ERROR_UNLESS(partial_solution.size() == scip_num_vars)
706  << "Error suggesting hint.";
707  RETURN_IF_SCIP_ERROR(SCIPcreateSol(scip_, &solution, nullptr));
708  }
709  for (const auto& var_value_pair : partial_solution) {
710  RETURN_IF_SCIP_ERROR(SCIPsetSolVal(scip_, solution, var_value_pair.first,
711  var_value_pair.second));
712  }
713  if (!is_solution_partial) {
714  SCIP_Bool is_feasible;
715  RETURN_IF_SCIP_ERROR(SCIPcheckSol(
716  scip_, solution, /*printreason=*/false, /*completely=*/true,
717  /*checkbounds=*/true, /*checkintegrality=*/true, /*checklprows=*/true,
718  &is_feasible));
719  if (!static_cast<bool>(is_feasible)) {
720  RETURN_IF_SCIP_ERROR(SCIPfreeSol(scip_, &solution));
722  }
723  }
724  SCIP_Bool is_stored;
725  RETURN_IF_SCIP_ERROR(SCIPaddSolFree(scip_, &solution, &is_stored));
726  if (static_cast<bool>(is_stored)) {
728  } else {
730  }
731 }
732 
733 absl::StatusOr<GScipResult> GScip::Solve(const GScipParameters& params,
734  const std::string& legacy_params) {
735  // A four step process:
736  // 1. Apply parameters.
737  // 2. Solve the problem.
738  // 3. Extract solution and solve statistics.
739  // 4. Prepare the solver for further modification/solves (reset parameters,
740  // free the solutions found).
741  GScipResult result;
742 
743  // Step 1: apply parameters.
744  const absl::Status param_status = SetParams(params, legacy_params);
745  if (!param_status.ok()) {
746  result.gscip_output.set_status(GScipOutput::INVALID_SOLVER_PARAMETERS);
747  // Conversion to std::string for open source build.
748  result.gscip_output.set_status_detail(
749  std::string(param_status.message())); // NOLINT
750  return result;
751  }
752  if (params.print_scip_model()) {
753  RETURN_IF_SCIP_ERROR(SCIPwriteOrigProblem(scip_, nullptr, "cip", FALSE));
754  }
755  if (!params.scip_model_filename().empty()) {
756  RETURN_IF_SCIP_ERROR(SCIPwriteOrigProblem(
757  scip_, params.scip_model_filename().c_str(), "cip", FALSE));
758  }
759 
760  // Step 2: Solve.
761  // NOTE(user): after solve, SCIP will either be in stage PRESOLVING,
762  // SOLVING, OR SOLVED.
763  if (GScipMaxNumThreads(params) > 1) {
764  RETURN_IF_SCIP_ERROR(SCIPsolveConcurrent(scip_));
765  } else {
766  RETURN_IF_SCIP_ERROR(SCIPsolve(scip_));
767  }
768  const SCIP_STAGE stage = SCIPgetStage(scip_);
769  if (stage != SCIP_STAGE_PRESOLVING && stage != SCIP_STAGE_SOLVING &&
770  stage != SCIP_STAGE_SOLVED) {
771  result.gscip_output.set_status(GScipOutput::UNKNOWN);
772  result.gscip_output.set_status_detail(
773  absl::StrCat("Unpexpected SCIP final stage= ", stage,
774  " was expected to be either SCIP_STAGE_PRESOLVING, "
775  "SCIP_STAGE_SOLVING, or SCIP_STAGE_SOLVED"));
776  return result;
777  }
778  if (params.print_detailed_solving_stats()) {
779  RETURN_IF_SCIP_ERROR(SCIPprintStatistics(scip_, nullptr));
780  }
781  if (!params.detailed_solving_stats_filename().empty()) {
782  FILE* file = fopen(params.detailed_solving_stats_filename().c_str(), "w");
783  if (file == nullptr) {
784  return absl::InvalidArgumentError(absl::StrCat(
785  "Could not open file: ", params.detailed_solving_stats_filename(),
786  " to write SCIP solve stats."));
787  }
788  RETURN_IF_SCIP_ERROR(SCIPprintStatistics(scip_, file));
789  int close_result = fclose(file);
790  if (close_result != 0) {
791  return absl::InvalidArgumentError(absl::StrCat(
792  "Error: ", close_result,
793  " closing file: ", params.detailed_solving_stats_filename(),
794  " when writing solve stats."));
795  }
796  }
797  // Step 3: Extract solution information.
798  // Some outputs are available unconditionally, and some are only ready if at
799  // least presolve succeeded.
800  GScipSolvingStats* stats = result.gscip_output.mutable_stats();
801  const int num_scip_solutions = SCIPgetNSols(scip_);
802  const int num_returned_solutions =
803  std::min(num_scip_solutions, std::max(1, params.num_solutions()));
804  SCIP_SOL** all_solutions = SCIPgetSols(scip_);
805  stats->set_best_objective(ScipInfUnclamp(SCIPgetPrimalbound(scip_)));
806  for (int i = 0; i < num_returned_solutions; ++i) {
807  SCIP_SOL* scip_sol = all_solutions[i];
808  const double obj_value = ScipInfUnclamp(SCIPgetSolOrigObj(scip_, scip_sol));
809  GScipSolution solution;
810  for (SCIP_VAR* v : variables_) {
811  solution[v] = SCIPgetSolVal(scip_, scip_sol, v);
812  }
813  result.solutions.push_back(solution);
814  result.objective_values.push_back(obj_value);
815  }
816  // Can only check for primal ray if we made it past presolve.
817  if (stage != SCIP_STAGE_PRESOLVING && SCIPhasPrimalRay(scip_)) {
818  for (SCIP_VAR* v : variables_) {
819  result.primal_ray[v] = SCIPgetPrimalRayVal(scip_, v);
820  }
821  }
822  // TODO(user): refactor this into a new method.
823  stats->set_best_bound(ScipInfUnclamp(SCIPgetDualbound(scip_)));
824  stats->set_node_count(SCIPgetNTotalNodes(scip_));
825  stats->set_first_lp_relaxation_bound(SCIPgetFirstLPDualboundRoot(scip_));
826  stats->set_root_node_bound(SCIPgetDualboundRoot(scip_));
827  if (stage != SCIP_STAGE_PRESOLVING) {
828  stats->set_total_lp_iterations(SCIPgetNLPIterations(scip_));
829  stats->set_primal_simplex_iterations(SCIPgetNPrimalLPIterations(scip_));
830  stats->set_dual_simplex_iterations(SCIPgetNDualLPIterations(scip_));
831  stats->set_deterministic_time(SCIPgetDeterministicTime(scip_));
832  }
833  result.gscip_output.set_status(ConvertStatus(SCIPgetStatus(scip_)));
834 
835  // Step 4: clean up.
836  RETURN_IF_ERROR(FreeTransform());
837  RETURN_IF_SCIP_ERROR(SCIPresetParams(scip_));
838  return result;
839 }
840 
841 absl::StatusOr<bool> GScip::DefaultBoolParamValue(
842  const std::string& parameter_name) {
843  SCIP_Bool default_value;
845  SCIPgetBoolParam(scip_, parameter_name.c_str(), &default_value));
846  return static_cast<bool>(default_value);
847 }
848 
849 absl::StatusOr<int> GScip::DefaultIntParamValue(
850  const std::string& parameter_name) {
851  int default_value;
853  SCIPgetIntParam(scip_, parameter_name.c_str(), &default_value));
854  return default_value;
855 }
856 
857 absl::StatusOr<int64_t> GScip::DefaultLongParamValue(
858  const std::string& parameter_name) {
859  SCIP_Longint result;
861  SCIPgetLongintParam(scip_, parameter_name.c_str(), &result));
862  return static_cast<int64_t>(result);
863 }
864 
865 absl::StatusOr<double> GScip::DefaultRealParamValue(
866  const std::string& parameter_name) {
867  double result;
869  SCIPgetRealParam(scip_, parameter_name.c_str(), &result));
870  return result;
871 }
872 
873 absl::StatusOr<char> GScip::DefaultCharParamValue(
874  const std::string& parameter_name) {
875  char result;
877  SCIPgetCharParam(scip_, parameter_name.c_str(), &result));
878  return result;
879 }
880 
881 absl::StatusOr<std::string> GScip::DefaultStringParamValue(
882  const std::string& parameter_name) {
883  char* result;
885  SCIPgetStringParam(scip_, parameter_name.c_str(), &result));
886  return std::string(result);
887 }
888 
889 double GScip::ScipInfClamp(double d) {
890  const double kScipInf = ScipInf();
891  if (d > kScipInf) return kScipInf;
892  if (d < -kScipInf) return -kScipInf;
893  return d;
894 }
895 
896 double GScip::ScipInfUnclamp(double d) {
897  const double kScipInf = ScipInf();
898  if (d >= kScipInf) return std::numeric_limits<double>::infinity();
899  if (d <= -kScipInf) return -std::numeric_limits<double>::infinity();
900  return d;
901 }
902 
903 #undef RETURN_ERROR_UNLESS
904 
905 } // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
#define LOG_IF(severity, condition)
Definition: base/logging.h:479
#define LOG(severity)
Definition: base/logging.h:420
double LinearConstraintUb(SCIP_CONS *constraint)
Definition: gscip.cc:660
absl::Status SetObjectiveOffset(double offset)
Definition: gscip.cc:537
absl::StatusOr< SCIP_VAR * > AddVariable(double lb, double ub, double obj_coef, GScipVarType var_type, const std::string &var_name="", const GScipVariableOptions &options=DefaultGScipVariableOptions())
Definition: gscip.cc:280
absl::Status DeleteVariable(SCIP_VAR *var)
Definition: gscip.cc:579
absl::StatusOr< SCIP_CONS * > AddOrConstraint(const GScipLogicalConstraintData &logical_data, const std::string &name="", const GScipConstraintOptions &options=DefaultGScipConstraintOptions())
Definition: gscip.cc:431
absl::StatusOr< double > DefaultRealParamValue(const std::string &parameter_name)
Definition: gscip.cc:865
absl::Status CanSafeBulkDelete(const absl::flat_hash_set< SCIP_VAR * > &vars)
Definition: gscip.cc:589
absl::StatusOr< SCIP_CONS * > AddAndConstraint(const GScipLogicalConstraintData &logical_data, const std::string &name="", const GScipConstraintOptions &options=DefaultGScipConstraintOptions())
Definition: gscip.cc:406
absl::StatusOr< SCIP_CONS * > AddLinearConstraint(const GScipLinearRange &range, const std::string &name="", const GScipConstraintOptions &options=DefaultGScipConstraintOptions())
Definition: gscip.cc:312
bool IsConstraintLinear(SCIP_CONS *constraint)
Definition: gscip.cc:640
absl::string_view ConstraintType(SCIP_CONS *constraint)
Definition: gscip.cc:636
absl::StatusOr< int64_t > DefaultLongParamValue(const std::string &parameter_name)
Definition: gscip.cc:857
absl::StatusOr< int > DefaultIntParamValue(const std::string &parameter_name)
Definition: gscip.cc:849
absl::Status DeleteConstraint(SCIP_CONS *constraint)
Definition: gscip.cc:680
absl::Status SetLinearConstraintUb(SCIP_CONS *constraint, double ub)
Definition: gscip.cc:674
absl::Status SafeBulkDelete(const absl::flat_hash_set< SCIP_VAR * > &vars)
Definition: gscip.cc:600
absl::StatusOr< GScipResult > Solve(const GScipParameters &params=GScipParameters(), const std::string &legacy_params="")
Definition: gscip.cc:733
static absl::StatusOr< std::unique_ptr< GScip > > Create(const std::string &problem_name)
Definition: gscip.cc:227
double Ub(SCIP_VAR *var)
Definition: gscip.cc:624
double ObjCoef(SCIP_VAR *var)
Definition: gscip.cc:628
absl::Status SetMaximize(bool is_maximize)
Definition: gscip.cc:531
absl::Span< SCIP_VAR *const > LinearConstraintVariables(SCIP_CONS *constraint)
Definition: gscip.cc:650
absl::StatusOr< std::string > DefaultStringParamValue(const std::string &parameter_name)
Definition: gscip.cc:881
absl::StatusOr< bool > DefaultBoolParamValue(const std::string &parameter_name)
Definition: gscip.cc:841
absl::StatusOr< SCIP_CONS * > AddIndicatorConstraint(const GScipIndicatorConstraint &indicator_constraint, const std::string &name="", const GScipConstraintOptions &options=DefaultGScipConstraintOptions())
Definition: gscip.cc:372
double Lb(SCIP_VAR *var)
Definition: gscip.cc:620
absl::Status SetLb(SCIP_VAR *var, double lb)
Definition: gscip.cc:555
double LinearConstraintLb(SCIP_CONS *constraint)
Definition: gscip.cc:656
absl::Status SetLinearConstraintCoef(SCIP_CONS *constraint, SCIP_VAR *var, double value)
Definition: gscip.cc:687
absl::Status SetLinearConstraintLb(SCIP_CONS *constraint, double lb)
Definition: gscip.cc:668
absl::StatusOr< GScipHintResult > SuggestHint(const GScipSolution &partial_solution)
Definition: gscip.cc:696
GScipVarType VarType(SCIP_VAR *var)
Definition: gscip.cc:630
absl::Status SetVarType(SCIP_VAR *var, GScipVarType var_type)
Definition: gscip.cc:572
absl::Status SetBranchingPriority(SCIP_VAR *var, int priority)
Definition: gscip.cc:550
absl::StatusOr< char > DefaultCharParamValue(const std::string &parameter_name)
Definition: gscip.cc:873
absl::Span< const double > LinearConstraintCoefficients(SCIP_CONS *constraint)
Definition: gscip.cc:644
absl::Status SetUb(SCIP_VAR *var, double ub)
Definition: gscip.cc:561
absl::Status SetObjCoef(SCIP_VAR *var, double obj_coef)
Definition: gscip.cc:567
absl::StatusOr< SCIP_CONS * > AddSOS2Constraint(const GScipSOSData &sos_data, const std::string &name="", const GScipConstraintOptions &options=DefaultGScipConstraintOptions())
Definition: gscip.cc:505
static std::string ScipVersion()
Definition: gscip.cc:245
absl::StatusOr< SCIP_CONS * > AddQuadraticConstraint(const GScipQuadraticRange &range, const std::string &name="", const GScipConstraintOptions &options=DefaultGScipConstraintOptions())
Definition: gscip.cc:338
absl::string_view Name(SCIP_VAR *var)
Definition: gscip.cc:634
absl::StatusOr< SCIP_CONS * > AddSOS1Constraint(const GScipSOSData &sos_data, const std::string &name="", const GScipConstraintOptions &options=DefaultGScipConstraintOptions())
Definition: gscip.cc:478
const std::string name
int64 value
IntVar * var
Definition: expr_array.cc:1858
#define RETURN_ERROR_UNLESS(x)
Definition: gscip.cc:37
const int FATAL
Definition: log_severity.h:32
Definition: file.cc:141
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
const GScipConstraintOptions & DefaultGScipConstraintOptions()
Definition: gscip.cc:160
int GScipMaxNumThreads(const GScipParameters &parameters)
absl::Status LegacyScipSetSolverSpecificParameters(const std::string &parameters, SCIP *scip)
std::string ProtoEnumToString(ProtoEnumType enum_value)
const GScipVariableOptions & DefaultGScipVariableOptions()
Definition: gscip.cc:155
absl::flat_hash_map< SCIP_VAR *, double > GScipSolution
Definition: gscip.h:69
#define SCIP_TO_STATUS(x)
#define RETURN_IF_SCIP_ERROR(x)
#define RETURN_IF_ERROR(expr)
Definition: status_macros.h:27
std::vector< SCIP_Var * > variables
Definition: gscip.h:428
std::vector< SCIP_VAR * > variables
Definition: gscip.h:95
std::vector< double > coefficients
Definition: gscip.h:96
std::vector< SCIP_VAR * > operators
Definition: gscip.h:441
std::vector< SCIP_Var * > quadratic_variables1
Definition: gscip.h:388
std::vector< SCIP_Var * > quadratic_variables2
Definition: gscip.h:389
std::vector< SCIP_Var * > linear_variables
Definition: gscip.h:375
std::vector< double > linear_coefficients
Definition: gscip.h:376
std::vector< double > quadratic_coefficients
Definition: gscip.h:390
absl::flat_hash_map< SCIP_VAR *, double > primal_ray
Definition: gscip.h:85
std::vector< double > objective_values
Definition: gscip.h:80
std::vector< GScipSolution > solutions
Definition: gscip.h:78
std::vector< SCIP_VAR * > variables
Definition: gscip.h:409
std::vector< double > weights
Definition: gscip.h:418