OR-Tools  8.2
scip_callback.h
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 // See go/scip-callbacks for documentation.
15 //
16 // This file provides a simplified C++ API for using callbacks with SCIP and
17 // MPSolver. It can be used directly by users, although in most cases, the
18 // mp_callback.h should be sufficient (in fact, SCIP's mp_callback.h
19 // implementation is built on top of this). See also go/mpsolver-callbacks.
20 
21 #ifndef OR_TOOLS_LINEAR_SOLVER_SCIP_CALLBACK_H_
22 #define OR_TOOLS_LINEAR_SOLVER_SCIP_CALLBACK_H_
23 
24 #include <string>
25 #include <vector>
26 
27 #include "absl/memory/memory.h"
30 #include "scip/scip_sol.h"
31 #include "scip/type_cons.h"
32 #include "scip/type_scip.h"
33 #include "scip/type_sol.h"
34 #include "scip/type_var.h"
35 
36 namespace operations_research {
37 
38 // See https://scip.zib.de/doc-6.0.2/html/CONS.php#CONS_PROPERTIES for details.
39 // For member below, the corresponding SCIP constraint handler property name is
40 // provided.
41 //
42 // TODO(user): no effort has been made to optimize the default values of
43 // enforcement_priority, feasibility_check_priority, eager_frequency, or
44 // separation_priority.
46  // See CONSHDLR_NAME in SCIP documentation above.
47  std::string name;
48 
49  // See CONSHDLR_DESC in SCIP documentation above.
50  std::string description;
51 
52  // See CONSHDLR_ENFOPRIORITY in the SCIP documentation above. Determines the
53  // order this constraint class is checked at each LP node.
54  //
55  // WARNING(rander): Assumed that enforcement_priority < 0. (This enforcement
56  // runs after integrality enforcement, so CONSENFOLP always runs on integral
57  // solutions.)
59 
60  // See CONSHDLR_CHECKPRIORITY: in the SCIP documentation above. Determines the
61  // order this constraint class runs in when testing solution feasibility.
62  //
63  // WARNING(rander): Assumed that feasibility_check_priority < 0. (This check
64  // runs after the integrality check, so CONSCHECK always runs on integral
65  // solutions.)
67 
68  // See CONSHDLR_EAGERFREQ in SCIP documentation above.
69  int eager_frequency = 10;
70 
71  // See CONSHDLR_NEEDSCONS in SCIP documentation above.
72  bool needs_constraints = false;
73 
74  // See CONSHDLR_SEPAPRIORITY in SCIP documentation above. Determines the
75  // order this constraint class runs in the cut loop.
77 
78  // See CONSHDLR_SEPAFREQ in the SCIP documentation above.
80 };
81 
83  public:
84  // A value of nullptr for solution means to use the current LP solution.
85  ScipConstraintHandlerContext(SCIP* scip, SCIP_SOL* solution,
86  bool is_pseudo_solution);
87  double VariableValue(const MPVariable* variable) const;
88 
89  int64 CurrentNodeId() const;
90  int64 NumNodesProcessed() const;
91 
92  SCIP* scip() const { return scip_; }
93 
94  // Pseudo solutions may not be LP feasible. Duals/reduced costs are not
95  // available (the LP solver failed at this node).
96  //
97  // Do not add "user cuts" here (that strengthen LP solution but don't change
98  // feasible region), add only "lazy constraints" (cut off integer solutions).
99  //
100  // TODO(user): maybe this can be abstracted away.
101  bool is_pseudo_solution() const { return is_pseudo_solution_; }
102 
103  private:
104  SCIP* scip_;
105  SCIP_SOL* solution_;
106  bool is_pseudo_solution_;
107 };
108 
111  bool is_cut = false; // Does not remove any integer points.
112  std::string name; // can be empty
113  bool local = false;
114 };
115 
116 // See go/scip-callbacks for additional documentation.
117 template <typename Constraint>
119  public:
122  : description_(description) {}
125  return description_;
126  }
127 
128  // Unless SeparateIntegerSolution() below is overridden, this must find a
129  // violated lazy constraint if one exists when given an integral solution.
130  virtual std::vector<CallbackRangeConstraint> SeparateFractionalSolution(
132  const Constraint& constraint) = 0;
133 
134  // This MUST find a violated lazy constraint if one exists.
135  // All constraints returned must have is_cut as false.
136  virtual std::vector<CallbackRangeConstraint> SeparateIntegerSolution(
138  const Constraint& constraint) {
139  return SeparateFractionalSolution(context, constraint);
140  }
141 
142  // Returns true if no constraints are violated.
145  const Constraint& constraint) {
146  return SeparateFractionalSolution(context, constraint).empty();
147  }
148 
149  // This MUST find a violated constraint if one exists.
152  const Constraint& constraint) {
153  return SeparateIntegerSolution(context, constraint).empty();
154  }
155 
156  private:
158 };
159 
160 // handler is not owned but held.
161 template <typename Constraint>
163  SCIP* scip);
164 
166  bool initial = true;
167  bool separate = true;
168  bool enforce = true;
169  bool check = true;
170  bool propagate = true;
171  bool local = false;
172  bool modifiable = false;
173  bool dynamic = false;
174  bool removable = true;
175  bool stickingatnodes = false;
176 };
177 
178 // constraint_data is not owned but held.
179 template <typename ConstraintData>
180 void AddCallbackConstraint(SCIP* scip,
182  const std::string& constraint_name,
183  const ConstraintData* constraint_data,
184  const ScipCallbackConstraintOptions& options);
185 
186 // Implementation details, here and below.
187 
188 namespace internal {
189 
191  public:
192  virtual ~ScipCallbackRunner() {}
193  virtual std::vector<CallbackRangeConstraint> SeparateFractionalSolution(
194  const ScipConstraintHandlerContext& context, void* constraint) = 0;
195 
196  virtual std::vector<CallbackRangeConstraint> SeparateIntegerSolution(
197  const ScipConstraintHandlerContext& context, void* constraint) = 0;
198 
200  const ScipConstraintHandlerContext& context, void* constraint) = 0;
201 
203  const ScipConstraintHandlerContext& context, void* constraint) = 0;
204 };
205 
206 template <typename ConstraintData>
208  public:
211  : handler_(handler) {}
212 
213  std::vector<CallbackRangeConstraint> SeparateFractionalSolution(
215  void* constraint_data) override {
216  return handler_->SeparateFractionalSolution(
217  context, *static_cast<ConstraintData*>(constraint_data));
218  }
219 
220  std::vector<CallbackRangeConstraint> SeparateIntegerSolution(
222  void* constraint_data) override {
223  return handler_->SeparateIntegerSolution(
224  context, *static_cast<ConstraintData*>(constraint_data));
225  }
226 
228  void* constraint_data) override {
229  return handler_->FractionalSolutionFeasible(
230  context, *static_cast<ConstraintData*>(constraint_data));
231  }
232 
234  void* constraint_data) override {
235  return handler_->IntegerSolutionFeasible(
236  context, *static_cast<ConstraintData*>(constraint_data));
237  }
238 
239  private:
241 };
242 
244  const ScipConstraintHandlerDescription& description,
245  std::unique_ptr<ScipCallbackRunner> runner, SCIP* scip);
246 
247 void AddCallbackConstraintImpl(SCIP* scip, const std::string& handler_name,
248  const std::string& constraint_name,
249  void* constraint_data,
250  const ScipCallbackConstraintOptions& options);
251 
252 } // namespace internal
253 
254 template <typename ConstraintData>
256  SCIP* scip) {
258  handler->description(),
260  handler),
261  scip);
262 }
263 
264 template <typename ConstraintData>
265 void AddCallbackConstraint(SCIP* scip,
267  const std::string& constraint_name,
268  const ConstraintData* constraint_data,
269  const ScipCallbackConstraintOptions& options) {
271  scip, handler->description().name, constraint_name,
272  static_cast<void*>(const_cast<ConstraintData*>(constraint_data)),
273  options);
274 }
275 
276 } // namespace operations_research
277 
278 #endif // OR_TOOLS_LINEAR_SOLVER_SCIP_CALLBACK_H_
A constraint is the main modeling object.
An expression of the form:
Definition: linear_expr.h:192
The class for variables of a Mathematical Programming (MP) model.
double VariableValue(const MPVariable *variable) const
ScipConstraintHandlerContext(SCIP *scip, SCIP_SOL *solution, bool is_pseudo_solution)
virtual bool IntegerSolutionFeasible(const ScipConstraintHandlerContext &context, const Constraint &constraint)
virtual bool FractionalSolutionFeasible(const ScipConstraintHandlerContext &context, const Constraint &constraint)
virtual std::vector< CallbackRangeConstraint > SeparateFractionalSolution(const ScipConstraintHandlerContext &context, const Constraint &constraint)=0
ScipConstraintHandler(const ScipConstraintHandlerDescription &description)
virtual std::vector< CallbackRangeConstraint > SeparateIntegerSolution(const ScipConstraintHandlerContext &context, const Constraint &constraint)
const ScipConstraintHandlerDescription & description() const
virtual bool IntegerSolutionFeasible(const ScipConstraintHandlerContext &context, void *constraint)=0
virtual bool FractionalSolutionFeasible(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
std::vector< CallbackRangeConstraint > SeparateFractionalSolution(const ScipConstraintHandlerContext &context, void *constraint_data) override
std::vector< CallbackRangeConstraint > SeparateIntegerSolution(const ScipConstraintHandlerContext &context, void *constraint_data) override
ScipCallbackRunnerImpl(ScipConstraintHandler< ConstraintData > *handler)
bool FractionalSolutionFeasible(const ScipConstraintHandlerContext &context, void *constraint_data) override
bool IntegerSolutionFeasible(const ScipConstraintHandlerContext &context, void *constraint_data) override
GurobiMPCallbackContext * context
int64_t int64
This file allows you to write natural code (like a mathematical equation) to model optimization probl...
A C++ wrapper that provides a simple and unified interface to several linear programming and mixed in...
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...
void RegisterConstraintHandler(ScipConstraintHandler< Constraint > *handler, SCIP *scip)
void AddCallbackConstraint(SCIP *scip, ScipConstraintHandler< ConstraintData > *handler, const std::string &constraint_name, const ConstraintData *constraint_data, const ScipCallbackConstraintOptions &options)