ortools.math_opt.python.solve

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