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"
20 #include "ortools/base/logging.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 
52 struct SCIP_ConsData {
53  void* data;
54 };
55 
56 namespace operations_research {
57 
58 namespace {
59 int ScipNumVars(SCIP* scip) { return SCIPgetNOrigVars(scip); }
60 
61 SCIP_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 
231 extern "C" {
234 static 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 
244 static 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 
253 static 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 
281 static 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 
309 static 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 
339 static 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 }
356 static 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 }
387 static 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 
406 namespace operations_research {
407 namespace 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 
433 void 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 > SeparateFractionalSolution(const ScipConstraintHandlerContext &context, void *constraint)=0
virtual std::vector< CallbackRangeConstraint > SeparateIntegerSolution(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...
bool LinearConstraintIsViolated(const ScipConstraintHandlerContext &context, const LinearRange &constraint)
ScipSeparationResult RunSeparation(internal::ScipCallbackRunner *runner, const ScipConstraintHandlerContext &context, absl::Span< SCIP_CONS * > constraints, bool is_integral)
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