OR-Tools  8.2
scip_callback.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#if defined(USE_SCIP)
15
17
18#include "absl/strings/str_cat.h"
19#include "absl/types/span.h"
22#include "scip/cons_linear.h"
23#include "scip/def.h"
24#include "scip/pub_cons.h"
25#include "scip/scip.h"
26#include "scip/scip_cons.h"
27#include "scip/scip_cut.h"
28#include "scip/scip_general.h"
29#include "scip/scip_lp.h"
30#include "scip/scip_param.h"
31#include "scip/scip_prob.h"
32#include "scip/scip_sol.h"
33#include "scip/scip_solvingstats.h"
34#include "scip/scip_tree.h"
35#include "scip/scipdefplugins.h"
36#include "scip/struct_cons.h"
37#include "scip/struct_tree.h"
38#include "scip/struct_var.h"
39#include "scip/type_cons.h"
40#include "scip/type_lp.h"
41#include "scip/type_result.h"
42#include "scip/type_retcode.h"
43#include "scip/type_scip.h"
44#include "scip/type_sol.h"
45#include "scip/type_tree.h"
46#include "scip/type_var.h"
47
49 std::unique_ptr<operations_research::internal::ScipCallbackRunner> runner;
50};
51
53 void* data;
54};
55
56namespace operations_research {
57
58namespace {
59int ScipNumVars(SCIP* scip) { return SCIPgetNOrigVars(scip); }
60
61SCIP_VAR* ScipGetVar(SCIP* scip, int var_index) {
62 DCHECK_GE(var_index, 0);
63 DCHECK_LT(var_index, ScipNumVars(scip));
64 return SCIPgetOrigVars(scip)[var_index];
65}
66
67} // namespace
68
70 SCIP* scip, SCIP_SOL* solution, bool is_pseudo_solution)
71 : scip_(scip),
72 solution_(solution),
73 is_pseudo_solution_(is_pseudo_solution) {}
74
76 const MPVariable* variable) const {
77 return SCIPgetSolVal(scip_, solution_, ScipGetVar(scip_, variable->index()));
78}
79
81 return SCIPgetNNodes(scip_);
82}
83
85 return SCIPgetCurrentNode(scip_)->number;
86}
87
92};
93
95 const LinearRange& constraint) {
96 double a_times_x = 0;
97 for (const auto& coef_pair : constraint.linear_expr().terms()) {
98 a_times_x += coef_pair.second * context.VariableValue(coef_pair.first);
99 }
100 double violation = std::max(a_times_x - constraint.upper_bound(),
101 constraint.lower_bound() - a_times_x);
102 return violation > 0;
103}
104
105// If any violated lazy constraint is found:
106// returns kLazyConstraintAdded,
107// else if any violated cutting plane is found:
108// returns kCuttingPlaneAdded,
109// else:
110// returns kDidNotFind
113 absl::Span<SCIP_CONS*> constraints,
114 bool is_integral) {
116 SCIP* scip = context.scip();
117 for (SCIP_CONS* constraint : constraints) {
118 SCIP_CONSDATA* consdata = SCIPconsGetData(constraint);
119 CHECK(consdata != nullptr);
120 std::vector<CallbackRangeConstraint> user_suggested_constraints;
121 if (is_integral) {
122 user_suggested_constraints =
123 runner->SeparateIntegerSolution(context, consdata->data);
124 } else {
125 user_suggested_constraints =
126 runner->SeparateFractionalSolution(context, consdata->data);
127 }
128 int num_constraints_added = 0;
129 for (const CallbackRangeConstraint& user_suggested_constraint :
130 user_suggested_constraints) {
132 user_suggested_constraint.range)) {
133 continue;
134 }
135 num_constraints_added++;
136 // Two code paths, one for cuts, one for lazy constraints. Cuts first:
137 if (user_suggested_constraint.is_cut) {
138 SCIP_ROW* row = nullptr;
139 constexpr bool kModifiable = false;
140 constexpr bool kRemovable = true;
141 CHECK_OK(SCIP_TO_STATUS(SCIPcreateEmptyRowCons(
142 scip, &row, constraint, user_suggested_constraint.name.c_str(),
143 user_suggested_constraint.range.lower_bound(),
144 user_suggested_constraint.range.upper_bound(),
145 user_suggested_constraint.local, kModifiable, kRemovable)));
146 CHECK_OK(SCIP_TO_STATUS(SCIPcacheRowExtensions(scip, row)));
147 for (const auto& coef_pair :
148 user_suggested_constraint.range.linear_expr().terms()) {
149 // NOTE(user): the coefficients don't come out sorted. I don't
150 // think this matters.
151 SCIP_VAR* var = ScipGetVar(scip, coef_pair.first->index());
152 const double coef = coef_pair.second;
153 CHECK_OK(SCIP_TO_STATUS(SCIPaddVarToRow(scip, row, var, coef)));
154 }
155 CHECK_OK(SCIP_TO_STATUS(SCIPflushRowExtensions(scip, row)));
156 SCIP_Bool infeasible;
157 constexpr bool kForceCut = false;
158 CHECK_OK(SCIP_TO_STATUS(SCIPaddRow(scip, row, kForceCut, &infeasible)));
159 CHECK_OK(SCIP_TO_STATUS(SCIPreleaseRow(scip, &row)));
160 // TODO(user): when infeasible is true, it better to have the scip
161 // return status be cutoff instead of cutting plane added (e.g. see
162 // cs/scip/cons_knapsack.c). However, as we use
163 // SCIPaddRow(), it isn't clear this will even happen.
165 // NOTE(user): if we have already found a violated lazy constraint,
166 // we want to return kLazyConstraintAdded, not kCuttingPlaneAdded,
167 // see function contract.
169 }
170 } else {
171 // Lazy constraint path:
172 std::vector<SCIP_VAR*> vars;
173 std::vector<double> coefs;
174 for (const auto& coef_pair :
175 user_suggested_constraint.range.linear_expr().terms()) {
176 // NOTE(user): the coefficients don't come out sorted. I don't
177 // think this matters.
178 vars.push_back(ScipGetVar(scip, coef_pair.first->index()));
179 coefs.push_back(coef_pair.second);
180 }
181
182 const int num_vars = vars.size();
183 SCIP_CONS* scip_cons;
184 // TODO(user): Maybe it is better to expose more of these options,
185 // potentially through user_suggested_constraint.
186 CHECK_OK(SCIP_TO_STATUS(SCIPcreateConsLinear(
187 scip, &scip_cons, user_suggested_constraint.name.c_str(), num_vars,
188 vars.data(), coefs.data(),
189 user_suggested_constraint.range.lower_bound(),
190 user_suggested_constraint.range.upper_bound(), /*initial=*/true,
191 /*separate=*/true, /*enforce=*/true, /*check=*/true,
192 /*propagate=*/true, /*local=*/user_suggested_constraint.local,
193 /*modifiable=*/false, /*dynamic=*/false, /*removable=*/true,
194 /*stickingatnode=*/false)));
195 if (user_suggested_constraint.local) {
196 CHECK_OK(SCIP_TO_STATUS(SCIPaddConsLocal(scip, scip_cons, nullptr)));
197 } else {
198 CHECK_OK(SCIP_TO_STATUS(SCIPaddCons(scip, scip_cons)));
199 }
200 CHECK_OK(SCIP_TO_STATUS(SCIPreleaseCons(scip, &scip_cons)));
202 }
203 }
204 }
205 return result;
206}
207
209 SCIP_CONSHDLRDATA* scip_handler_data;
212 absl::Span<SCIP_CONS*> useful_constraints;
213 absl::Span<SCIP_CONS*> unlikely_useful_constraints;
214
215 CallbackSetup(SCIP* scip, SCIP_CONSHDLR* scip_handler, SCIP_CONS** conss,
216 int nconss, int nusefulconss, SCIP_SOL* sol,
217 bool is_pseudo_solution)
218 : scip_handler_data(SCIPconshdlrGetData(scip_handler)),
219 callback_runner(scip_handler_data->runner.get()),
220 context(scip, sol, is_pseudo_solution),
221 useful_constraints(absl::MakeSpan(conss, nusefulconss)),
223 absl::MakeSpan(conss, nconss).subspan(nusefulconss)) {
224 CHECK(scip_handler_data != nullptr);
225 CHECK(callback_runner != nullptr);
226 }
227};
228
229} // namespace operations_research
230
231extern "C" {
234static SCIP_DECL_CONSFREE(ConstraintHandlerFreeC) {
235 VLOG(3) << "FreeC";
236 CHECK(scip != nullptr);
237 SCIP_CONSHDLRDATA* scip_handler_data = SCIPconshdlrGetData(conshdlr);
238 CHECK(scip_handler_data != nullptr);
239 delete scip_handler_data;
240 SCIPconshdlrSetData(conshdlr, nullptr);
241 return SCIP_OKAY;
242}
243
244static SCIP_DECL_CONSDELETE(ConstraintHandlerDeleteC) {
245 VLOG(3) << "DeleteC";
246 CHECK(consdata != nullptr);
247 CHECK(*consdata != nullptr);
248 delete *consdata;
249 cons->consdata = nullptr;
250 return SCIP_OKAY;
251}
252
253static SCIP_DECL_CONSENFOLP(EnforceLpC) {
254 VLOG(3) << "EnforceC";
255 operations_research::CallbackSetup setup(scip, conshdlr, conss, nconss,
256 nusefulconss, nullptr, false);
259 setup.useful_constraints,
260 /*is_integral=*/true);
261 if (separation_result ==
263 separation_result = operations_research::RunSeparation(
265 /*is_integral=*/true);
266 }
267 switch (separation_result) {
269 *result = SCIP_CONSADDED;
270 break;
272 *result = SCIP_SEPARATED;
273 break;
275 *result = SCIP_FEASIBLE;
276 break;
277 }
278 return SCIP_OKAY;
279}
280
281static SCIP_DECL_CONSSEPALP(SeparateLpC) {
282 VLOG(3) << "SeparateLpC";
283 operations_research::CallbackSetup setup(scip, conshdlr, conss, nconss,
284 nusefulconss, nullptr, false);
287 setup.useful_constraints,
288 /*is_integral=*/false);
289 if (separation_result ==
291 separation_result = operations_research::RunSeparation(
293 /*is_integral=*/false);
294 }
295 switch (separation_result) {
297 *result = SCIP_CONSADDED;
298 break;
300 *result = SCIP_SEPARATED;
301 break;
303 *result = SCIP_DIDNOTFIND;
304 break;
305 }
306 return SCIP_OKAY;
307}
308
309static SCIP_DECL_CONSSEPASOL(SeparatePrimalSolutionC) {
310 VLOG(3) << "SeparatePrimalC";
311 operations_research::CallbackSetup setup(scip, conshdlr, conss, nconss,
312 nusefulconss, sol, false);
315 setup.useful_constraints,
316 /*is_integral=*/true);
317 if (separation_result ==
319 separation_result = operations_research::RunSeparation(
321 /*is_integral=*/true);
322 }
323 switch (separation_result) {
325 *result = SCIP_CONSADDED;
326 break;
328 LOG(ERROR) << "Cutting planes cannot be added on integer solutions, "
329 "treating as a constraint.";
330 *result = SCIP_CONSADDED;
331 break;
333 *result = SCIP_DIDNOTFIND;
334 break;
335 }
336 return SCIP_OKAY;
337}
338
339static SCIP_DECL_CONSCHECK(CheckFeasibilityC) {
340 VLOG(3) << "CheckFeasibilityC";
341 operations_research::CallbackSetup setup(scip, conshdlr, conss, nconss,
342 nconss, sol, false);
343 // All constraints are "useful" for this callback.
344 for (SCIP_CONS* constraint : setup.useful_constraints) {
345 SCIP_CONSDATA* consdata = SCIPconsGetData(constraint);
346 CHECK(consdata != nullptr);
348 consdata->data)) {
349 *result = SCIP_INFEASIBLE;
350 return SCIP_OKAY;
351 }
352 }
353 *result = SCIP_FEASIBLE;
354 return SCIP_OKAY;
355}
356static SCIP_DECL_CONSENFOPS(EnforcePseudoSolutionC) {
357 VLOG(3) << "EnforcePseudoSolutionC";
358 // TODO(user): are we sure the pseudo solution is LP feasible? It seems like
359 // it doesn't need to be. The code in RunSeparation might assume this?
360 operations_research::CallbackSetup setup(scip, conshdlr, conss, nconss,
361 nusefulconss, nullptr, true);
364 setup.useful_constraints,
365 /*is_integral=*/false);
366 if (separation_result ==
368 separation_result = operations_research::RunSeparation(
370 /*is_integral=*/false);
371 }
372 switch (separation_result) {
374 *result = SCIP_CONSADDED;
375 break;
377 LOG(ERROR) << "Cutting planes cannot be added on pseudo solutions, "
378 "treating as a constraint.";
379 *result = SCIP_CONSADDED;
380 break;
382 *result = SCIP_FEASIBLE;
383 break;
384 }
385 return SCIP_OKAY;
386}
387static SCIP_DECL_CONSLOCK(VariableRoundingLockC) {
388 // In this callback, we need to say, for a constraint class and an instance of
389 // the constraint, for which variables could an {increase,decrease,either}
390 // affect feasibility. As a conservative overestimate, we say that any
391 // change in any variable could cause an infeasibility for any instance of
392 // any callback constraint.
393 // TODO(user): this could be a little better, but we would need to add
394 // another method to override on ScipConstraintHandler<ConstraintData>.
395
396 const int num_vars = operations_research::ScipNumVars(scip);
397 for (int i = 0; i < num_vars; ++i) {
398 SCIP_VAR* var = operations_research::ScipGetVar(scip, i);
399 SCIP_CALL(SCIPaddVarLocksType(scip, var, locktype, nlockspos + nlocksneg,
400 nlockspos + nlocksneg));
401 }
402 return SCIP_OKAY;
403}
404}
405
406namespace operations_research {
407namespace internal {
408
410 const ScipConstraintHandlerDescription& description,
411 std::unique_ptr<ScipCallbackRunner> runner, SCIP* scip) {
412 SCIP_CONSHDLR* c_scip_handler;
413 SCIP_CONSHDLRDATA* scip_handler_data = new SCIP_CONSHDLRDATA;
414 scip_handler_data->runner = std::move(runner);
415
416 CHECK_OK(SCIP_TO_STATUS(SCIPincludeConshdlrBasic(
417 scip, &c_scip_handler, description.name.c_str(),
418 description.description.c_str(), description.enforcement_priority,
419 description.feasibility_check_priority, description.eager_frequency,
420 description.needs_constraints, EnforceLpC, EnforcePseudoSolutionC,
421 CheckFeasibilityC, VariableRoundingLockC, scip_handler_data)));
422 CHECK(c_scip_handler != nullptr);
423 CHECK_OK(SCIP_TO_STATUS(SCIPsetConshdlrSepa(
424 scip, c_scip_handler, SeparateLpC, SeparatePrimalSolutionC,
425 description.separation_frequency, description.separation_priority,
426 /*delaysepa=*/false)));
428 SCIPsetConshdlrFree(scip, c_scip_handler, ConstraintHandlerFreeC)));
430 SCIPsetConshdlrDelete(scip, c_scip_handler, ConstraintHandlerDeleteC)));
431}
432
433void AddCallbackConstraintImpl(SCIP* scip, const std::string& handler_name,
434 const std::string& constraint_name,
435 void* constraint_data,
436 const ScipCallbackConstraintOptions& options) {
437 SCIP_CONSHDLR* conshdlr = SCIPfindConshdlr(scip, handler_name.c_str());
438 CHECK(conshdlr != nullptr)
439 << "Constraint handler " << handler_name << " not registered with scip.";
440 SCIP_ConsData* consdata = new SCIP_ConsData;
441 consdata->data = constraint_data;
442 SCIP_CONS* constraint = nullptr;
443 CHECK_OK(SCIP_TO_STATUS(SCIPcreateCons(
444 scip, &constraint, constraint_name.c_str(), conshdlr, consdata,
445 options.initial, options.separate, options.enforce, options.check,
446 options.propagate, options.local, options.modifiable, options.dynamic,
447 options.removable, options.stickingatnodes)));
448 CHECK(constraint != nullptr);
449 CHECK_OK(SCIP_TO_STATUS(SCIPaddCons(scip, constraint)));
450 CHECK_OK(SCIP_TO_STATUS(SCIPreleaseCons(scip, &constraint)));
451}
452
453} // namespace internal
454} // namespace operations_research
455#endif // #if defined(USE_SCIP)
int64 max
Definition: alldiff_cst.cc:139
#define CHECK(condition)
Definition: base/logging.h:495
#define CHECK_OK(x)
Definition: base/logging.h:40
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
#define LOG(severity)
Definition: base/logging.h:420
#define VLOG(verboselevel)
Definition: base/logging.h:978
const absl::flat_hash_map< const MPVariable *, double > & terms() const
Definition: linear_expr.h:143
An expression of the form:
Definition: linear_expr.h:192
const LinearExpr & linear_expr() const
Definition: linear_expr.h:206
The class for variables of a Mathematical Programming (MP) model.
int index() const
Returns the index of the variable in the MPSolver::variables_.
double VariableValue(const MPVariable *variable) const
ScipConstraintHandlerContext(SCIP *scip, SCIP_SOL *solution, bool is_pseudo_solution)
virtual bool IntegerSolutionFeasible(const ScipConstraintHandlerContext &context, void *constraint)=0
virtual std::vector< CallbackRangeConstraint > SeparateIntegerSolution(const ScipConstraintHandlerContext &context, void *constraint)=0
virtual std::vector< CallbackRangeConstraint > SeparateFractionalSolution(const ScipConstraintHandlerContext &context, void *constraint)=0
IntVar * var
Definition: expr_array.cc:1858
int64 coef
Definition: expr_array.cc:1859
GurobiMPCallbackContext * context
int64_t int64
const int ERROR
Definition: log_severity.h:32
RowIndex row
Definition: markowitz.cc:175
Definition: cleanup.h:22
void AddConstraintHandlerImpl(const ScipConstraintHandlerDescription &description, std::unique_ptr< ScipCallbackRunner > runner, SCIP *scip)
void AddCallbackConstraintImpl(SCIP *scip, const std::string &handler_name, const std::string &constraint_name, void *constraint_data, const ScipCallbackConstraintOptions &options)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
ScipSeparationResult RunSeparation(internal::ScipCallbackRunner *runner, const ScipConstraintHandlerContext &context, absl::Span< SCIP_CONS * > constraints, bool is_integral)
bool LinearConstraintIsViolated(const ScipConstraintHandlerContext &context, const LinearRange &constraint)
static SCIP_DECL_CONSLOCK(VariableRoundingLockC)
static SCIP_DECL_CONSFREE(ConstraintHandlerFreeC)
destructor of constraint handler to free user data (called when SCIP is exiting)
static SCIP_DECL_CONSSEPASOL(SeparatePrimalSolutionC)
static SCIP_DECL_CONSENFOPS(EnforcePseudoSolutionC)
static SCIP_DECL_CONSSEPALP(SeparateLpC)
static SCIP_DECL_CONSENFOLP(EnforceLpC)
static SCIP_DECL_CONSDELETE(ConstraintHandlerDeleteC)
static SCIP_DECL_CONSCHECK(CheckFeasibilityC)
#define SCIP_TO_STATUS(x)
std::unique_ptr< operations_research::internal::ScipCallbackRunner > runner
internal::ScipCallbackRunner * callback_runner
absl::Span< SCIP_CONS * > unlikely_useful_constraints
CallbackSetup(SCIP *scip, SCIP_CONSHDLR *scip_handler, SCIP_CONS **conss, int nconss, int nusefulconss, SCIP_SOL *sol, bool is_pseudo_solution)
absl::Span< SCIP_CONS * > useful_constraints
SCIP_CONSHDLRDATA * scip_handler_data
ScipConstraintHandlerContext context