ortools.math_opt.python.solve

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