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
25namespace operations_research {
26
27class LinearExpr;
28class LinearRange;
29class 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.
36enum class MPCallbackEvent {
38 // For regaining control of the main thread in single threaded applications,
39 // not for interacting with the solver.
41 // The solver is currently running presolve.
43 // The solver is currently running the simplex method.
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.
52 // Called in each iterate of IPM/barrier method.
54 // The solver is about to log out a message, use this callback to capture it.
56 // The solver is in multi-objective optimization.
58};
59
60std::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.
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.
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)