OR-Tools  8.2
linear_solver_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/mpsolver-callbacks for documentation on how to use this file.
15 
16 #ifndef OR_TOOLS_LINEAR_SOLVER_LINEAR_SOLVER_CALLBACK_H_
17 #define OR_TOOLS_LINEAR_SOLVER_LINEAR_SOLVER_CALLBACK_H_
18 
19 #include <string>
20 #include <vector>
21 
22 #include "absl/container/flat_hash_map.h"
24 
25 namespace operations_research {
26 
27 class LinearExpr;
28 class LinearRange;
29 class MPVariable;
30 
31 // The current state of the solver when the callback is invoked.
32 //
33 // For Gurobi, similar to the int 'where' in the Gurobi callback API.
34 // See http://www.gurobi.com/documentation/8.0/refman/callback_codes.html
35 // for details.
36 enum class MPCallbackEvent {
37  kUnknown,
38  // For regaining control of the main thread in single threaded applications,
39  // not for interacting with the solver.
40  kPolling,
41  // The solver is currently running presolve.
42  kPresolve,
43  // The solver is currently running the simplex method.
44  kSimplex,
45  // The solver is in the MIP loop (called periodically before starting a new
46  // node). Useful to early termination.
47  kMip,
48  // Called every time a new MIP incumbent is found.
50  // Called once per pass of the cut loop inside each MIP node.
51  kMipNode,
52  // Called in each iterate of IPM/barrier method.
53  kBarrier,
54  // The solver is about to log out a message, use this callback to capture it.
55  kMessage,
56  // The solver is in multi-objective optimization.
57  kMultiObj,
58 };
59 
60 std::string ToString(MPCallbackEvent event);
61 
62 // When querying solution values or modifying the model during a callback, use
63 // this API, rather than manipulating MPSolver directly. You should only
64 // interact with this object from within MPCallback::RunCallback().
66  public:
67  virtual ~MPCallbackContext() {}
68 
69  // What the solver is currently doing. How you can interact with the solver
70  // from the callback depends on this value.
71  virtual MPCallbackEvent Event() = 0;
72 
73  // Always false if event is not kMipSolution or kMipNode, otherwise behavior
74  // may be solver dependent.
75  //
76  // For Gurobi, under kMipNode, may be false if the node was not solved to
77  // optimality, see MIPNODE_REL here for details:
78  // http://www.gurobi.com/documentation/8.0/refman/callback_codes.html
79  virtual bool CanQueryVariableValues() = 0;
80 
81  // Returns the value of variable from the solver's current state.
82  //
83  // Call only when CanQueryVariableValues() is true.
84  //
85  // At kMipSolution, the solution is integer feasible, while at kMipNode, the
86  // solution solves the current node's LP relaxation (so integer variables may
87  // be fractional).
88  virtual double VariableValue(const MPVariable* variable) = 0;
89 
90  // Adds a constraint to the model that strengths the LP relaxation.
91  //
92  // Call only when the event is kMipNode.
93  //
94  // Requires that MPCallback::might_add_cuts() is true.
95  //
96  // This constraint must not cut off integer solutions, it should only
97  // strengthen the LP (behavior is undefined otherwise). Use
98  // MPCallbackContext::AddLazyConstriant() if you are cutting off integer
99  // solutions.
100  virtual void AddCut(const LinearRange& cutting_plane) = 0;
101 
102  // Adds a constraint to the model that cuts off an undesired integer solution.
103  //
104  // Call only when the event is kMipSolution or kMipNode.
105  //
106  // Requires that MPCallback::might_add_lazy_constraints() is true.
107  //
108  // Use this to avoid adding a large number of constraints to the model where
109  // most are expected to not be needed.
110  //
111  // Given an integral solution, AddLazyConstraint() MUST be able to detect if
112  // there is a violated constraint, and it is guaranteed that every integer
113  // solution will be checked by AddLazyConstraint().
114  //
115  // Warning(rander): in some solvers, e.g. Gurobi, an integer solution may not
116  // respect a previously added lazy constraint, so you may need to add a
117  // constraint more than once (e.g. due to threading issues).
118  virtual void AddLazyConstraint(const LinearRange& lazy_constraint) = 0;
119 
120  // Suggests a (potentially partial) variable assignment to the solver, to be
121  // used as a feasible solution (or part of one). If the assignment is partial,
122  // certain solvers (e.g. Gurobi) will try to compute a feasible solution from
123  // the partial assignment. Returns the objective value of the solution if the
124  // solver supports it.
125  //
126  // Call only when the event is kMipNode.
127  virtual double SuggestSolution(
128  const absl::flat_hash_map<const MPVariable*, double>& solution) = 0;
129 
130  // Returns the number of nodes explored so far in the branch and bound tree,
131  // which 0 at the root node and > 0 otherwise.
132  //
133  // Call only when the event is kMipSolution or kMipNode.
134  virtual int64 NumExploredNodes() = 0;
135 };
136 
137 // Extend this class with model specific logic, and register through
138 // MPSolver::SetCallback, passing a pointer to this object.
139 //
140 // See go/mpsolver-callbacks for additional documentation.
141 class MPCallback {
142  public:
143  // If you intend to call call MPCallbackContext::AddCut(), you must set
144  // might_add_cuts below to be true. Likewise for
145  // MPCallbackContext::AddLazyConstraint() and might_add_lazy_constraints.
147  : might_add_cuts_(might_add_cuts),
148  might_add_lazy_constraints_(might_add_lazy_constraints) {}
149  virtual ~MPCallback() {}
150 
151  // Threading behavior may be solver dependent:
152  // * Gurobi: RunCallback always runs on the same thread that you called
153  // MPSolver::Solve() on, even when Gurobi uses multiple threads.
154  virtual void RunCallback(MPCallbackContext* callback_context) = 0;
155 
156  bool might_add_cuts() const { return might_add_cuts_; }
158  return might_add_lazy_constraints_;
159  }
160 
161  private:
162  bool might_add_cuts_;
163  bool might_add_lazy_constraints_;
164 };
165 
166 // Single callback that runs the list of callbacks given at construction, in
167 // sequence.
168 class MPCallbackList : public MPCallback {
169  public:
170  explicit MPCallbackList(const std::vector<MPCallback*>& callbacks);
171 
172  // Runs all callbacks from the list given at construction, in sequence.
173  void RunCallback(MPCallbackContext* context) override;
174 
175  private:
176  const std::vector<MPCallback*> callbacks_;
177 };
178 
179 } // namespace operations_research
180 
181 #endif // OR_TOOLS_LINEAR_SOLVER_LINEAR_SOLVER_CALLBACK_H_
An expression of the form:
Definition: linear_expr.h:192
virtual MPCallbackEvent Event()=0
virtual double VariableValue(const MPVariable *variable)=0
virtual void AddLazyConstraint(const LinearRange &lazy_constraint)=0
virtual void AddCut(const LinearRange &cutting_plane)=0
virtual double SuggestSolution(const absl::flat_hash_map< const MPVariable *, double > &solution)=0
MPCallback(bool might_add_cuts, bool might_add_lazy_constraints)
virtual void RunCallback(MPCallbackContext *callback_context)=0
void RunCallback(MPCallbackContext *context) override
MPCallbackList(const std::vector< MPCallback * > &callbacks)
The class for variables of a Mathematical Programming (MP) model.
GurobiMPCallbackContext * context
int64_t int64
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
const absl::string_view ToString(MPSolver::OptimizationProblemType optimization_problem_type)