ortools.math_opt.python.solve

  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"""Solve optimization problems, as defined by Model in model.py."""
 16import types
 17from typing import Callable, Optional
 18
 19from ortools.math_opt import parameters_pb2
 20from ortools.math_opt import rpc_pb2
 21from ortools.math_opt.core.python import solver
 22from ortools.math_opt.python import callback
 23from ortools.math_opt.python import compute_infeasible_subsystem_result
 24from ortools.math_opt.python import errors
 25from ortools.math_opt.python import init_arguments
 26from ortools.math_opt.python import message_callback
 27from ortools.math_opt.python import model
 28from ortools.math_opt.python import model_parameters
 29from ortools.math_opt.python import parameters
 30from ortools.math_opt.python import result
 31from ortools.util.python import solve_interrupter
 32from pybind11_abseil.status import StatusNotOk
 33
 34SolveCallback = Callable[[callback.CallbackData], callback.CallbackResult]
 35
 36
 37def solve(
 38    opt_model: model.Model,
 39    solver_type: parameters.SolverType,
 40    *,
 41    params: Optional[parameters.SolveParameters] = None,
 42    model_params: Optional[model_parameters.ModelSolveParameters] = None,
 43    msg_cb: Optional[message_callback.SolveMessageCallback] = None,
 44    callback_reg: Optional[callback.CallbackRegistration] = None,
 45    cb: Optional[SolveCallback] = None,
 46    streamable_init_args: Optional[init_arguments.StreamableSolverInitArguments] = None,
 47    remove_names: bool = False,
 48    interrupter: Optional[solve_interrupter.SolveInterrupter] = None,
 49) -> result.SolveResult:
 50    """Solves an optimization model.
 51
 52    Thread-safety: this function must not be called while modifying the Model
 53    (adding variables...). Some solvers may add more restriction regarding
 54    threading. Please see SolverType::XXX documentation for details.
 55
 56    Args:
 57      opt_model: The optimization model.
 58      solver_type: The underlying solver to use.
 59      params: Configuration of the underlying solver.
 60      model_params: Configuration of the solver that is model specific.
 61      msg_cb: A callback that gives back the underlying solver's logs by the line.
 62      callback_reg: Configures when the callback will be invoked (if provided) and
 63        what data will be collected to access in the callback.
 64      cb: A callback that will be called periodically as the solver runs.
 65      streamable_init_args: Configuration for initializing the underlying solver.
 66      remove_names: When true, remove all names for the ModelProto.
 67      interrupter: An optional interrupter that the solver can use to interrupt
 68        the solve early.
 69
 70    Returns:
 71      A SolveResult containing the termination reason, solution(s) and stats.
 72
 73    Raises:
 74      RuntimeError: On a solve error.
 75    """
 76    # First, initialize optional arguments that were not set to default values.
 77    # Note that in python, default arguments must be immutable, and these are not.
 78    params = params or parameters.SolveParameters()
 79    model_params = model_params or model_parameters.ModelSolveParameters()
 80    callback_reg = callback_reg or callback.CallbackRegistration()
 81    streamable_init_args = (
 82        streamable_init_args or init_arguments.StreamableSolverInitArguments()
 83    )
 84    model_proto = opt_model.export_model(remove_names=remove_names)
 85    proto_cb = None
 86    if cb is not None:
 87        proto_cb = lambda x: cb(  # pylint: disable=g-long-lambda
 88            callback.parse_callback_data(x, opt_model)
 89        ).to_proto()
 90    # Solve
 91    try:
 92        proto_result = solver.solve(
 93            model_proto,
 94            solver_type.value,
 95            streamable_init_args.to_proto(),
 96            params.to_proto(),
 97            model_params.to_proto(),
 98            msg_cb,
 99            callback_reg.to_proto(),
100            proto_cb,
101            interrupter.pybind_interrupter if interrupter is not None else None,
102        )
103    except StatusNotOk as e:
104        raise _status_not_ok_to_exception(e) from None
105    return result.parse_solve_result(proto_result, opt_model, validate=False)
106
107
108def compute_infeasible_subsystem(
109    opt_model: model.Model,
110    solver_type: parameters.SolverType,
111    *,
112    params: Optional[parameters.SolveParameters] = None,
113    msg_cb: Optional[message_callback.SolveMessageCallback] = None,
114    streamable_init_args: Optional[init_arguments.StreamableSolverInitArguments] = None,
115    remove_names: bool = False,
116    interrupter: Optional[solve_interrupter.SolveInterrupter] = None,
117) -> compute_infeasible_subsystem_result.ComputeInfeasibleSubsystemResult:
118    """Computes an infeasible subsystem of the input model.
119
120    Args:
121      opt_model: The optimization model to check for infeasibility.
122      solver_type: Which solver to use to compute the infeasible subsystem. As of
123        August 2023, the only supported solver is Gurobi.
124      params: Configuration of the underlying solver.
125      msg_cb: A callback that gives back the underlying solver's logs by the line.
126      streamable_init_args: Configuration for initializing the underlying solver.
127      remove_names: When true, remove all names for the ModelProto.
128      interrupter: An optional interrupter that the solver can use to interrupt
129        the solve early.
130
131    Returns:
132      An `ComputeInfeasibleSubsystemResult` where `feasibility` indicates if the
133      problem was proven infeasible.
134
135    Throws:
136      RuntimeError: on invalid inputs or an internal solver error.
137    """
138    params = params or parameters.SolveParameters()
139    streamable_init_args = (
140        streamable_init_args or init_arguments.StreamableSolverInitArguments()
141    )
142    model_proto = opt_model.export_model(remove_names=remove_names)
143    # Solve
144    try:
145        proto_result = solver.compute_infeasible_subsystem(
146            model_proto,
147            solver_type.value,
148            streamable_init_args.to_proto(),
149            params.to_proto(),
150            msg_cb,
151            interrupter.pybind_interrupter if interrupter is not None else None,
152        )
153    except StatusNotOk as e:
154        raise _status_not_ok_to_exception(e) from None
155    return (
156        compute_infeasible_subsystem_result.parse_compute_infeasible_subsystem_result(
157            proto_result, opt_model
158        )
159    )
160
161
162class IncrementalSolver:
163    """Solve an optimization multiple times, with modifications between solves.
164
165    Prefer calling simply solve() above in most cases when incrementalism is not
166    needed.
167
168    Thread-safety: The __init__(), solve() methods must not be called while
169    modifying the Model (adding variables...). The user is expected to use proper
170    synchronization primitives to serialize changes to the model and the use of
171    this object. Note though that it is safe to call methods from different
172    IncrementalSolver instances on the same Model concurrently. The solve() method
173    must not be called concurrently on different threads for the same
174    IncrementalSolver. Some solvers may add more restriction regarding
175    threading. Please see to SolverType::XXX documentation for details.
176
177    This class references some resources that are freed when it is garbage
178    collected (which should usually happen when the last reference is lost). In
179    particular, it references some C++ objects. Although it is not mandatory, it
180    is recommended to free those as soon as possible. To do so it is possible to
181    use this class in the `with` statement:
182
183    with IncrementalSolver(model, SolverType.GLOP) as solver:
184      ...
185
186    When it is not possible to use `with`, the close() method can be called.
187    """
188
189    def __init__(
190        self,
191        opt_model: model.Model,
192        solver_type: parameters.SolverType,
193        *,
194        streamable_init_args: Optional[
195            init_arguments.StreamableSolverInitArguments
196        ] = None,
197        remove_names: bool = False,
198    ):
199        streamable_init_args = (
200            streamable_init_args or init_arguments.StreamableSolverInitArguments()
201        )
202        self._model = opt_model
203        self._solver_type = solver_type
204        self._update_tracker = self._model.add_update_tracker()
205        try:
206            self._proto_solver = solver.new(
207                solver_type.value,
208                self._model.export_model(remove_names=remove_names),
209                streamable_init_args.to_proto(),
210            )
211        except StatusNotOk as e:
212            raise _status_not_ok_to_exception(e) from None
213        self._closed = False
214
215    def solve(
216        self,
217        *,
218        params: Optional[parameters.SolveParameters] = None,
219        model_params: Optional[model_parameters.ModelSolveParameters] = None,
220        msg_cb: Optional[message_callback.SolveMessageCallback] = None,
221        callback_reg: Optional[callback.CallbackRegistration] = None,
222        cb: Optional[SolveCallback] = None,
223        interrupter: Optional[solve_interrupter.SolveInterrupter] = None,
224    ) -> result.SolveResult:
225        """Solves the current optimization model.
226
227        Args:
228          params: The non-model specific solve parameters.
229          model_params: The model specific solve parameters.
230          msg_cb: An optional callback for solver messages.
231          callback_reg: The parameters controlling when cb is called.
232          cb: An optional callback for LP/MIP events.
233          interrupter: An optional interrupter that the solver can use to interrupt
234            the solve early.
235
236        Returns:
237          The result of the solve.
238
239        Raises:
240          RuntimeError: If called after being closed, or on a solve error.
241        """
242        if self._closed:
243            raise RuntimeError("the solver is closed")
244
245        update = self._update_tracker.export_update()
246        if update is not None:
247            try:
248                if not self._proto_solver.update(update):
249                    self._proto_solver = solver.new(
250                        self._solver_type.value,
251                        self._model.export_model(),
252                        parameters_pb2.SolverInitializerProto(),
253                    )
254            except StatusNotOk as e:
255                raise _status_not_ok_to_exception(e) from None
256            self._update_tracker.advance_checkpoint()
257        params = params or parameters.SolveParameters()
258        model_params = model_params or model_parameters.ModelSolveParameters()
259        callback_reg = callback_reg or callback.CallbackRegistration()
260        proto_cb = None
261        if cb is not None:
262            proto_cb = lambda x: cb(  # pylint: disable=g-long-lambda
263                callback.parse_callback_data(x, self._model)
264            ).to_proto()
265        try:
266            result_proto = self._proto_solver.solve(
267                params.to_proto(),
268                model_params.to_proto(),
269                msg_cb,
270                callback_reg.to_proto(),
271                proto_cb,
272                interrupter.pybind_interrupter if interrupter is not None else None,
273            )
274        except StatusNotOk as e:
275            raise _status_not_ok_to_exception(e) from None
276        return result.parse_solve_result(result_proto, self._model, validate=False)
277
278    def close(self) -> None:
279        """Closes this solver, freeing all its resources.
280
281        This is optional, the code is correct without calling this function. See the
282        class documentation for details.
283
284        After a solver has been closed, it can't be used anymore. Prefer using the
285        context manager API when possible instead of calling close() directly:
286
287        with IncrementalSolver(model, SolverType.GLOP) as solver:
288          ...
289        """
290        if self._closed:
291            return
292        self._closed = True
293
294        del self._model
295        del self._solver_type
296        del self._update_tracker
297        del self._proto_solver
298
299    def __enter__(self) -> "IncrementalSolver":
300        """Returns the solver itself."""
301        return self
302
303    def __exit__(
304        self,
305        exc_type: Optional[type[BaseException]],
306        exc_val: Optional[BaseException],
307        exc_tb: Optional[types.TracebackType],
308    ) -> None:
309        """Closes the solver."""
310        self.close()
311
312
313def _status_not_ok_to_exception(err: StatusNotOk) -> Exception:
314    """Converts a StatusNotOk to the best matching Python exception.
315
316    Args:
317      err: The input errors.
318
319    Returns:
320      The corresponding exception.
321    """
322    ret = errors.status_proto_to_exception(
323        rpc_pb2.StatusProto(code=err.canonical_code, message=err.message)
324    )
325    # We never expect StatusNotOk to be OK.
326    assert ret is not None, err
327    return ret