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