ortools.math_opt.python.callback

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