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"
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
35namespace 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
42namespace {
43
44constexpr absl::string_view kLinearConstraintHandlerName = "linear";
45
46SCIP_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
57GScipVarType 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
69GScipOutput::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
108SCIP_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
137SCIP_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
165absl::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
227absl::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
237GScip::GScip(SCIP* scip) : scip_(scip) {}
238
239double GScip::ScipInf() { return SCIPinfinity(scip_); }
240
241absl::Status GScip::FreeTransform() {
242 return SCIP_TO_STATUS(SCIPfreeTransform(scip_));
243}
244
245std::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
258absl::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
280absl::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
302absl::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
312absl::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
338absl::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
372absl::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
406absl::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
431absl::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
456namespace {
457
458absl::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
478absl::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
505absl::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
531absl::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
537absl::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
548double GScip::ObjectiveOffset() { return SCIPgetOrigObjoffset(scip_); }
549
550absl::Status GScip::SetBranchingPriority(SCIP_VAR* var, int priority) {
551 RETURN_IF_SCIP_ERROR(SCIPchgVarBranchPriority(scip_, var, priority));
552 return absl::OkStatus();
553}
554
555absl::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
561absl::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
567absl::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
572absl::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
579absl::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
600absl::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)) {
611 }
612 }
613 }
614 for (SCIP_VAR* const var : vars) {
616 }
617 return absl::OkStatus();
618}
619
620double GScip::Lb(SCIP_VAR* var) {
621 return ScipInfUnclamp(SCIPvarGetLbOriginal(var));
622}
623
624double GScip::Ub(SCIP_VAR* var) {
625 return ScipInfUnclamp(SCIPvarGetUbOriginal(var));
626}
627
628double GScip::ObjCoef(SCIP_VAR* var) { return SCIPvarGetObj(var); }
629
631 return ConvertVarType(SCIPvarGetType(var));
632}
633
634absl::string_view GScip::Name(SCIP_VAR* var) { return SCIPvarGetName(var); }
635
636absl::string_view GScip::ConstraintType(SCIP_CONS* constraint) {
637 return absl::string_view(SCIPconshdlrGetName(SCIPconsGetHdlr(constraint)));
638}
639
640bool GScip::IsConstraintLinear(SCIP_CONS* constraint) {
641 return ConstraintType(constraint) == kLinearConstraintHandlerName;
642}
643
644absl::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
650absl::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
656double GScip::LinearConstraintLb(SCIP_CONS* constraint) {
657 return ScipInfUnclamp(SCIPgetLhsLinear(scip_, constraint));
658}
659
660double GScip::LinearConstraintUb(SCIP_CONS* constraint) {
661 return ScipInfUnclamp(SCIPgetRhsLinear(scip_, constraint));
662}
663
664absl::string_view GScip::Name(SCIP_CONS* constraint) {
665 return SCIPconsGetName(constraint);
666}
667
668absl::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
674absl::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
680absl::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
687absl::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
696absl::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
733absl::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
841absl::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
849absl::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
857absl::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
865absl::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
873absl::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
881absl::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
889double 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
896double 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::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
absl::Span< SCIP_VAR *const > LinearConstraintVariables(SCIP_CONS *constraint)
Definition: gscip.cc:650
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
std::string ProtoEnumToString(ProtoEnumType enum_value)
int GScipMaxNumThreads(const GScipParameters &parameters)
absl::Status LegacyScipSetSolverSpecificParameters(const std::string &parameters, SCIP *scip)
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