ortools.math_opt.python.callback

  1# Copyright 2010-2025 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"""Defines how to request a callback and the input and output of a callback."""
 15import dataclasses
 16import datetime
 17import enum
 18import math
 19from typing import Dict, List, Mapping, Optional, Set, Union
 20
 21from ortools.math_opt import callback_pb2
 22from ortools.math_opt.python import model
 23from ortools.math_opt.python import normalized_inequality
 24from ortools.math_opt.python import sparse_containers
 25from ortools.math_opt.python import variables
 26
 27
 28@enum.unique
 29class Event(enum.Enum):
 30    """The supported events during a solve for callbacks.
 31
 32    * UNSPECIFIED: The event is unknown (typically an internal error).
 33    * PRESOLVE: The solver is currently running presolve. Gurobi only.
 34    * SIMPLEX: The solver is currently running the simplex method. Gurobi only.
 35    * MIP: The solver is in the MIP loop (called periodically before starting a
 36        new node). Useful for early termination. Note that this event does not
 37        provide information on LP relaxations nor about new incumbent solutions.
 38        Gurobi only.
 39    * MIP_SOLUTION: Called every time a new MIP incumbent is found. Fully
 40        supported by Gurobi, partially supported by CP-SAT (you can observe new
 41        solutions, but not add lazy constraints).
 42    * MIP_NODE: Called inside a MIP node. Note that there is no guarantee that the
 43        callback function will be called on every node. That behavior is
 44        solver-dependent. Gurobi only.
 45
 46        Disabling cuts using SolveParameters may interfere with this event being
 47        called and/or adding cuts at this event, the behavior is solver specific.
 48    * BARRIER: Called in each iterate of an interior point/barrier method. Gurobi
 49        only.
 50    """
 51
 52    UNSPECIFIED = callback_pb2.CALLBACK_EVENT_UNSPECIFIED
 53    PRESOLVE = callback_pb2.CALLBACK_EVENT_PRESOLVE
 54    SIMPLEX = callback_pb2.CALLBACK_EVENT_SIMPLEX
 55    MIP = callback_pb2.CALLBACK_EVENT_MIP
 56    MIP_SOLUTION = callback_pb2.CALLBACK_EVENT_MIP_SOLUTION
 57    MIP_NODE = callback_pb2.CALLBACK_EVENT_MIP_NODE
 58    BARRIER = callback_pb2.CALLBACK_EVENT_BARRIER
 59
 60
 61PresolveStats = callback_pb2.CallbackDataProto.PresolveStats
 62SimplexStats = callback_pb2.CallbackDataProto.SimplexStats
 63BarrierStats = callback_pb2.CallbackDataProto.BarrierStats
 64MipStats = callback_pb2.CallbackDataProto.MipStats
 65
 66
 67@dataclasses.dataclass
 68class CallbackData:
 69    """Input to the solve callback (produced by the solver).
 70
 71    Attributes:
 72      event: The current state of the solver when the callback is run. The event
 73        (partially) determines what data is available and what the user is allowed
 74        to return.
 75      solution: A solution to the primal optimization problem, if available. For
 76        Event.MIP_SOLUTION, solution is always present, integral, and feasible.
 77        For Event.MIP_NODE, the primal_solution contains the current LP-node
 78        relaxation. In some cases, no solution will be available (e.g. because LP
 79        was infeasible or the solve was imprecise). Empty for other events.
 80      messages: Logs generated by the underlying solver, as a list of strings
 81        without new lines (each string is a line). Only filled on Event.MESSAGE.
 82      runtime: The time since Solve() was invoked.
 83      presolve_stats: Filled for Event.PRESOLVE only.
 84      simplex_stats: Filled for Event.SIMPLEX only.
 85      barrier_stats: Filled for Event.BARRIER only.
 86      mip_stats: Filled for the events MIP, MIP_SOLUTION and MIP_NODE only.
 87    """
 88
 89    event: Event = Event.UNSPECIFIED
 90    solution: Optional[Dict[variables.Variable, float]] = None
 91    messages: List[str] = dataclasses.field(default_factory=list)
 92    runtime: datetime.timedelta = datetime.timedelta()
 93    presolve_stats: PresolveStats = dataclasses.field(default_factory=PresolveStats)
 94    simplex_stats: SimplexStats = dataclasses.field(default_factory=SimplexStats)
 95    barrier_stats: BarrierStats = dataclasses.field(default_factory=BarrierStats)
 96    mip_stats: MipStats = dataclasses.field(default_factory=MipStats)
 97
 98
 99def parse_callback_data(
100    cb_data: callback_pb2.CallbackDataProto, mod: model.Model
101) -> CallbackData:
102    """Creates a CallbackData from an equivalent proto.
103
104    Args:
105      cb_data: A protocol buffer with the information the user needs for a
106        callback.
107      mod: The model being solved.
108
109    Returns:
110      An equivalent CallbackData.
111
112    Raises:
113      ValueError: if cb_data is invalid or inconsistent with mod, e.g. cb_data
114      refers to a variable id not in mod.
115    """
116    result = CallbackData()
117    result.event = Event(cb_data.event)
118    if cb_data.HasField("primal_solution_vector"):
119        primal_solution = cb_data.primal_solution_vector
120        result.solution = {
121            mod.get_variable(id): val
122            for (id, val) in zip(primal_solution.ids, primal_solution.values)
123        }
124    result.runtime = cb_data.runtime.ToTimedelta()
125    result.presolve_stats = cb_data.presolve_stats
126    result.simplex_stats = cb_data.simplex_stats
127    result.barrier_stats = cb_data.barrier_stats
128    result.mip_stats = cb_data.mip_stats
129    return result
130
131
132@dataclasses.dataclass
133class CallbackRegistration:
134    """Request the events and input data and reports output types for a callback.
135
136    Note that it is an error to add a constraint in a callback without setting
137    add_cuts and/or add_lazy_constraints to true.
138
139    Attributes:
140      events: When the callback should be invoked, by default, never. If an
141        unsupported event for a solver/model combination is selected, an
142        excecption is raised, see Event above for details.
143      mip_solution_filter: restricts the variable values returned in
144        CallbackData.solution (the callback argument) at each MIP_SOLUTION event.
145        By default, values are returned for all variables.
146      mip_node_filter: restricts the variable values returned in
147        CallbackData.solution (the callback argument) at each MIP_NODE event. By
148        default, values are returned for all variables.
149      add_cuts: The callback may add "user cuts" (linear constraints that
150        strengthen the LP without cutting of integer points) at MIP_NODE events.
151      add_lazy_constraints: The callback may add "lazy constraints" (linear
152        constraints that cut off integer solutions) at MIP_NODE or MIP_SOLUTION
153        events.
154    """
155
156    events: Set[Event] = dataclasses.field(default_factory=set)
157    mip_solution_filter: sparse_containers.VariableFilter = (
158        sparse_containers.VariableFilter()
159    )
160    mip_node_filter: sparse_containers.VariableFilter = (
161        sparse_containers.VariableFilter()
162    )
163    add_cuts: bool = False
164    add_lazy_constraints: bool = False
165
166    def to_proto(self) -> callback_pb2.CallbackRegistrationProto:
167        """Returns an equivalent proto to this CallbackRegistration."""
168        result = callback_pb2.CallbackRegistrationProto()
169        result.request_registration[:] = sorted([event.value for event in self.events])
170        result.mip_solution_filter.CopyFrom(self.mip_solution_filter.to_proto())
171        result.mip_node_filter.CopyFrom(self.mip_node_filter.to_proto())
172        result.add_cuts = self.add_cuts
173        result.add_lazy_constraints = self.add_lazy_constraints
174        return result
175
176
177@dataclasses.dataclass
178class GeneratedConstraint:
179    """A linear constraint to add inside a callback.
180
181    Models a constraint of the form:
182      lb <= sum_{i in I} a_i * x_i <= ub
183
184    Two types of generated linear constraints are supported based on is_lazy:
185      * The "lazy constraint" can remove integer points from the feasible
186        region and can be added at event Event.MIP_NODE or
187        Event.MIP_SOLUTION
188      * The "user cut" (on is_lazy=false) strengthens the LP without removing
189        integer points. It can only be added at Event.MIP_NODE.
190
191
192    Attributes:
193      terms: The variables and linear coefficients in the constraint, a_i and x_i
194        in the model above.
195      lower_bound: lb in the model above.
196      upper_bound: ub in the model above.
197      is_lazy: Indicates if the constraint should be interpreted as a "lazy
198        constraint" (cuts off integer solutions) or a "user cut" (strengthens the
199        LP relaxation without cutting of integer solutions).
200    """
201
202    terms: Mapping[variables.Variable, float] = dataclasses.field(default_factory=dict)
203    lower_bound: float = -math.inf
204    upper_bound: float = math.inf
205    is_lazy: bool = False
206
207    def to_proto(
208        self,
209    ) -> callback_pb2.CallbackResultProto.GeneratedLinearConstraint:
210        """Returns an equivalent proto for the constraint."""
211        result = callback_pb2.CallbackResultProto.GeneratedLinearConstraint()
212        result.is_lazy = self.is_lazy
213        result.lower_bound = self.lower_bound
214        result.upper_bound = self.upper_bound
215        result.linear_expression.CopyFrom(
216            sparse_containers.to_sparse_double_vector_proto(self.terms)
217        )
218        return result
219
220
221@dataclasses.dataclass
222class CallbackResult:
223    """The value returned by a solve callback (produced by the user).
224
225    Attributes:
226      terminate: When true it tells the solver to interrupt the solve as soon as
227        possible.
228
229        It can be set from any event. This is equivalent to using a
230        SolveInterrupter and triggering it from the callback.
231
232        Some solvers don't support interruption, in that case this is simply
233        ignored and the solve terminates as usual. On top of that solvers may not
234        immediately stop the solve. Thus the user should expect the callback to
235        still be called after they set `terminate` to true in a previous
236        call. Returning with `terminate` false after having previously returned
237        true won't cancel the interruption.
238      generated_constraints: Constraints to add to the model. For details, see
239        GeneratedConstraint documentation.
240      suggested_solutions: A list of solutions (or partially defined solutions) to
241        suggest to the solver. Some solvers (e.g. gurobi) will try and convert a
242        partial solution into a full solution by solving a MIP. Use only for
243        Event.MIP_NODE.
244    """
245
246    terminate: bool = False
247    generated_constraints: List[GeneratedConstraint] = dataclasses.field(
248        default_factory=list
249    )
250    suggested_solutions: List[Mapping[variables.Variable, float]] = dataclasses.field(
251        default_factory=list
252    )
253
254    def add_generated_constraint(
255        self,
256        bounded_expr: Optional[Union[bool, variables.BoundedLinearTypes]] = None,
257        *,
258        lb: Optional[float] = None,
259        ub: Optional[float] = None,
260        expr: Optional[variables.LinearTypes] = None,
261        is_lazy: bool,
262    ) -> None:
263        """Adds a linear constraint to the list of generated constraints.
264
265        The constraint can be of two exclusive types: a "lazy constraint" or a
266        "user cut. A "user cut" is a constraint that excludes the current LP
267        solution, but does not cut off any integer-feasible points that satisfy the
268        already added constraints (either in callbacks or through
269        Model.add_linear_constraint()). A "lazy constraint" is a constraint that
270        excludes such integer-feasible points and hence is needed for corrctness of
271        the forlumation.
272
273        The simplest way to specify the constraint is by passing a one-sided or
274        two-sided linear inequality as in:
275          * add_generated_constraint(x + y + 1.0 <= 2.0, is_lazy=True),
276          * add_generated_constraint(x + y >= 2.0, is_lazy=True), or
277          * add_generated_constraint((1.0 <= x + y) <= 2.0, is_lazy=True).
278
279        Note the extra parenthesis for two-sided linear inequalities, which is
280        required due to some language limitations (see
281        https://peps.python.org/pep-0335/ and https://peps.python.org/pep-0535/).
282        If the parenthesis are omitted, a TypeError will be raised explaining the
283        issue (if this error was not raised the first inequality would have been
284        silently ignored because of the noted language limitations).
285
286        The second way to specify the constraint is by setting lb, ub, and/o expr as
287        in:
288          * add_generated_constraint(expr=x + y + 1.0, ub=2.0, is_lazy=True),
289          * add_generated_constraint(expr=x + y, lb=2.0, is_lazy=True),
290          * add_generated_constraint(expr=x + y, lb=1.0, ub=2.0, is_lazy=True), or
291          * add_generated_constraint(lb=1.0, is_lazy=True).
292        Omitting lb is equivalent to setting it to -math.inf and omiting ub is
293        equivalent to setting it to math.inf.
294
295        These two alternatives are exclusive and a combined call like:
296          * add_generated_constraint(x + y <= 2.0, lb=1.0, is_lazy=True), or
297          * add_generated_constraint(x + y <= 2.0, ub=math.inf, is_lazy=True)
298        will raise a ValueError. A ValueError is also raised if expr's offset is
299        infinite.
300
301        Args:
302          bounded_expr: a linear inequality describing the constraint. Cannot be
303            specified together with lb, ub, or expr.
304          lb: The constraint's lower bound if bounded_expr is omitted (if both
305            bounder_expr and lb are omitted, the lower bound is -math.inf).
306          ub: The constraint's upper bound if bounded_expr is omitted (if both
307            bounder_expr and ub are omitted, the upper bound is math.inf).
308          expr: The constraint's linear expression if bounded_expr is omitted.
309          is_lazy: Whether the constraint is lazy or not.
310        """
311        norm_ineq = normalized_inequality.as_normalized_linear_inequality(
312            bounded_expr, lb=lb, ub=ub, expr=expr
313        )
314        self.generated_constraints.append(
315            GeneratedConstraint(
316                lower_bound=norm_ineq.lb,
317                terms=norm_ineq.coefficients,
318                upper_bound=norm_ineq.ub,
319                is_lazy=is_lazy,
320            )
321        )
322
323    def add_lazy_constraint(
324        self,
325        bounded_expr: Optional[Union[bool, variables.BoundedLinearTypes]] = None,
326        *,
327        lb: Optional[float] = None,
328        ub: Optional[float] = None,
329        expr: Optional[variables.LinearTypes] = None,
330    ) -> None:
331        """Shortcut for add_generated_constraint(..., is_lazy=True).."""
332        self.add_generated_constraint(
333            bounded_expr, lb=lb, ub=ub, expr=expr, is_lazy=True
334        )
335
336    def add_user_cut(
337        self,
338        bounded_expr: Optional[Union[bool, variables.BoundedLinearTypes]] = None,
339        *,
340        lb: Optional[float] = None,
341        ub: Optional[float] = None,
342        expr: Optional[variables.LinearTypes] = None,
343    ) -> None:
344        """Shortcut for add_generated_constraint(..., is_lazy=False)."""
345        self.add_generated_constraint(
346            bounded_expr, lb=lb, ub=ub, expr=expr, is_lazy=False
347        )
348
349    def to_proto(self) -> callback_pb2.CallbackResultProto:
350        """Returns a proto equivalent to this CallbackResult."""
351        result = callback_pb2.CallbackResultProto(terminate=self.terminate)
352        for generated_constraint in self.generated_constraints:
353            result.cuts.add().CopyFrom(generated_constraint.to_proto())
354        for suggested_solution in self.suggested_solutions:
355            result.suggested_solutions.add().CopyFrom(
356                sparse_containers.to_sparse_double_vector_proto(suggested_solution)
357            )
358        return result