ortools.math_opt.python.model_storage

  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"""An interface for in memory storage of optimization problems."""
 15
 16import abc
 17import dataclasses
 18from typing import Iterator, Optional, Type, TypeVar
 19
 20from ortools.math_opt import model_pb2
 21from ortools.math_opt import model_update_pb2
 22
 23
 24# TODO(b/231426528): remove __slots__ and set slots=True when Python 3.10 is
 25# available.
 26@dataclasses.dataclass(frozen=True)
 27class LinearConstraintMatrixIdEntry:
 28    __slots__ = "linear_constraint_id", "variable_id", "coefficient"
 29    linear_constraint_id: int
 30    variable_id: int
 31    coefficient: float
 32
 33
 34# TODO(b/231426528): remove __slots__ and set slots=True when Python 3.10 is
 35# available.
 36@dataclasses.dataclass(frozen=True)
 37class LinearObjectiveEntry:
 38    __slots__ = "variable_id", "coefficient"
 39    variable_id: int
 40    coefficient: float
 41
 42
 43# TODO(b/231426528): remove __slots__ and set slots=True when Python 3.10 is
 44# available.
 45@dataclasses.dataclass(frozen=True)
 46class QuadraticTermIdKey:
 47    """An ordered pair of ints used as a key for quadratic terms.
 48
 49    QuadraticTermIdKey.id1 <= QuadraticTermIdKey.id2.
 50    """
 51
 52    __slots__ = "id1", "id2"
 53    id1: int
 54    id2: int
 55
 56    def __init__(self, a: int, b: int):
 57        """Ints a and b will be ordered internally."""
 58        id1 = a
 59        id2 = b
 60        if id1 > id2:
 61            id1, id2 = id2, id1
 62        object.__setattr__(self, "id1", id1)
 63        object.__setattr__(self, "id2", id2)
 64
 65
 66# TODO(b/231426528): remove __slots__ and set slots=True when Python 3.10 is
 67# available.
 68@dataclasses.dataclass(frozen=True)
 69class QuadraticEntry:
 70    """Represents an id-indexed quadratic term."""
 71
 72    __slots__ = "id_key", "coefficient"
 73    id_key: QuadraticTermIdKey
 74    coefficient: float
 75
 76
 77class StorageUpdateTracker(abc.ABC):
 78    """Tracks updates to an optimization model from a ModelStorage.
 79
 80    Do not instantiate directly, instead create through
 81    ModelStorage.add_update_tracker().
 82
 83    Interacting with an update tracker after it has been removed from the model
 84    will result in an UsedUpdateTrackerAfterRemovalError error.
 85
 86    Example:
 87      mod = model_storage.ModelStorage()
 88      x = mod.add_variable(0.0, 1.0, True, 'x')
 89      y = mod.add_variable(0.0, 1.0, True, 'y')
 90      tracker = mod.add_update_tracker()
 91      mod.set_variable_ub(x, 3.0)
 92      tracker.export_update()
 93        => "variable_updates: {upper_bounds: {ids: [0], values[3.0] }"
 94      mod.set_variable_ub(y, 2.0)
 95      tracker.export_update()
 96        => "variable_updates: {upper_bounds: {ids: [0, 1], values[3.0, 2.0] }"
 97      tracker.advance_checkpoint()
 98      tracker.export_update()
 99        => ""
100      mod.set_variable_ub(y, 4.0)
101      tracker.export_update()
102        => "variable_updates: {upper_bounds: {ids: [1], values[4.0] }"
103      tracker.advance_checkpoint()
104      mod.remove_update_tracker(tracker)
105        => ""
106    """
107
108    @abc.abstractmethod
109    def export_update(self) -> Optional[model_update_pb2.ModelUpdateProto]:
110        """Returns changes to the model since last call to checkpoint/creation, or None if no changes occurred."""
111        pass
112
113    @abc.abstractmethod
114    def advance_checkpoint(self) -> None:
115        """Track changes to the model only after this function call."""
116        pass
117
118
119class UsedUpdateTrackerAfterRemovalError(RuntimeError):
120
121    def __init__(self):
122        super().__init__(
123            "Attempted to use update tracker after removing it from model storage."
124        )
125
126
127class BadVariableIdError(LookupError):
128    """Raised by ModelStorage when a bad variable id is given."""
129
130    def __init__(self, variable_id):
131        super().__init__(f"Unexpected variable id: {variable_id}")
132        self.id = variable_id
133
134
135class BadLinearConstraintIdError(LookupError):
136    """Raised by ModelStorage when a bad linear constraint id is given."""
137
138    def __init__(self, linear_constraint_id):
139        super().__init__(f"Unexpected linear constraint id: {linear_constraint_id}")
140        self.id = linear_constraint_id
141
142
143class ModelStorage(abc.ABC):
144    """An interface for in memory storage of an optimization model.
145
146    Most users should not use this class directly and use Model defined in
147    model.py.
148
149    Stores an mixed integer programming problem of the form:
150
151    {max/min} c*x + d
152    s.t.  lb_c <= A * x <= ub_c
153          lb_v <=     x <= ub_v
154                      x_i integer for i in I
155
156    where x is a vector of n decision variables, d is a number, lb_v, ub_v, and c
157    are vectors of n numbers, lb_c and ub_c are vectors of m numbers, A is a
158    m by n matrix, and I is a subset of {1,..., n}.
159
160    Each of the n variables and m constraints have an integer id that you use to
161    get/set the problem data (c, A, lb_c etc.). Ids begin at zero and increase
162    sequentially. They are not reused after deletion. Note that if a variable is
163    deleted, your model has nonconsecutive variable ids.
164
165    For all methods taking an id (e.g. set_variable_lb), providing a bad id
166    (including the id of a deleted variable) will raise a BadVariableIdError or
167    BadLinearConstraintIdError. Further, the ModelStorage instance is assumed to
168    be in a bad state after any such error and there are no guarantees on further
169    interactions.
170
171    All implementations must have a constructor taking a str argument for the
172    model name with a default value of the empty string.
173
174    Any ModelStorage can be exported to model_pb2.ModelProto, the format consumed
175    by MathOpt solvers. Changes to a model can be exported to a
176    model_update_pb2.ModelUpdateProto with an UpdateTracker, see the UpdateTracker
177    documentation for details.
178
179    When solving this optimization problem we will additionally require that:
180      * No numbers are NaN,
181      * c, d, and A are all finite,
182      * lb_c and lb_v are not +inf,
183      * ub_c and ub_v are not -inf,
184    but those assumptions are not checked or enforced here (NaNs and infinite
185    values can be used anywhere).
186    """
187
188    @property
189    @abc.abstractmethod
190    def name(self) -> str:
191        pass
192
193    @abc.abstractmethod
194    def add_variable(self, lb: float, ub: float, is_integer: bool, name: str) -> int:
195        pass
196
197    @abc.abstractmethod
198    def delete_variable(self, variable_id: int) -> None:
199        pass
200
201    @abc.abstractmethod
202    def variable_exists(self, variable_id: int) -> bool:
203        pass
204
205    @abc.abstractmethod
206    def next_variable_id(self) -> int:
207        pass
208
209    @abc.abstractmethod
210    def set_variable_lb(self, variable_id: int, lb: float) -> None:
211        pass
212
213    @abc.abstractmethod
214    def set_variable_ub(self, variable_id: int, ub: float) -> None:
215        pass
216
217    @abc.abstractmethod
218    def set_variable_is_integer(self, variable_id: int, is_integer: bool) -> None:
219        pass
220
221    @abc.abstractmethod
222    def get_variable_lb(self, variable_id: int) -> float:
223        pass
224
225    @abc.abstractmethod
226    def get_variable_ub(self, variable_id: int) -> float:
227        pass
228
229    @abc.abstractmethod
230    def get_variable_is_integer(self, variable_id: int) -> bool:
231        pass
232
233    @abc.abstractmethod
234    def get_variable_name(self, variable_id: int) -> str:
235        pass
236
237    @abc.abstractmethod
238    def get_variables(self) -> Iterator[int]:
239        """Yields the variable ids in order of creation."""
240        pass
241
242    @abc.abstractmethod
243    def add_linear_constraint(self, lb: float, ub: float, name: str) -> int:
244        pass
245
246    @abc.abstractmethod
247    def delete_linear_constraint(self, linear_constraint_id: int) -> None:
248        pass
249
250    @abc.abstractmethod
251    def linear_constraint_exists(self, linear_constraint_id: int) -> bool:
252        pass
253
254    @abc.abstractmethod
255    def next_linear_constraint_id(self) -> int:
256        pass
257
258    @abc.abstractmethod
259    def set_linear_constraint_lb(self, linear_constraint_id: int, lb: float) -> None:
260        pass
261
262    @abc.abstractmethod
263    def set_linear_constraint_ub(self, linear_constraint_id: int, ub: float) -> None:
264        pass
265
266    @abc.abstractmethod
267    def get_linear_constraint_lb(self, linear_constraint_id: int) -> float:
268        pass
269
270    @abc.abstractmethod
271    def get_linear_constraint_ub(self, linear_constraint_id: int) -> float:
272        pass
273
274    @abc.abstractmethod
275    def get_linear_constraint_name(self, linear_constraint_id: int) -> str:
276        pass
277
278    @abc.abstractmethod
279    def get_linear_constraints(self) -> Iterator[int]:
280        """Yields the linear constraint ids in order of creation."""
281        pass
282
283    @abc.abstractmethod
284    def set_linear_constraint_coefficient(
285        self, linear_constraint_id: int, variable_id: int, lb: float
286    ) -> None:
287        pass
288
289    @abc.abstractmethod
290    def get_linear_constraint_coefficient(
291        self, linear_constraint_id: int, variable_id: int
292    ) -> float:
293        pass
294
295    @abc.abstractmethod
296    def get_linear_constraints_with_variable(self, variable_id: int) -> Iterator[int]:
297        """Yields the linear constraints with nonzero coefficient for a variable in undefined order."""
298        pass
299
300    @abc.abstractmethod
301    def get_variables_for_linear_constraint(
302        self, linear_constraint_id: int
303    ) -> Iterator[int]:
304        """Yields the variables with nonzero coefficient in a linear constraint in undefined order."""
305        pass
306
307    @abc.abstractmethod
308    def get_linear_constraint_matrix_entries(
309        self,
310    ) -> Iterator[LinearConstraintMatrixIdEntry]:
311        """Yields the nonzero elements of the linear constraint matrix in undefined order."""
312        pass
313
314    @abc.abstractmethod
315    def clear_objective(self) -> None:
316        """Clears objective coefficients and offset. Does not change direction."""
317
318    @abc.abstractmethod
319    def set_linear_objective_coefficient(self, variable_id: int, value: float) -> None:
320        pass
321
322    @abc.abstractmethod
323    def get_linear_objective_coefficient(self, variable_id: int) -> float:
324        pass
325
326    @abc.abstractmethod
327    def get_linear_objective_coefficients(self) -> Iterator[LinearObjectiveEntry]:
328        """Yields the nonzero linear objective terms in undefined order."""
329        pass
330
331    @abc.abstractmethod
332    def set_quadratic_objective_coefficient(
333        self, first_variable_id: int, second_variable_id: int, value: float
334    ) -> None:
335        """Sets the objective coefficient for the product of two variables.
336
337        The ordering of the input variables does not matter.
338
339        Args:
340          first_variable_id: The first variable in the product.
341          second_variable_id: The second variable in the product.
342          value: The value of the coefficient.
343
344        Raises:
345          BadVariableIdError if first_variable_id or second_variable_id are not in
346          the model.
347        """
348
349    @abc.abstractmethod
350    def get_quadratic_objective_coefficient(
351        self, first_variable_id: int, second_variable_id: int
352    ) -> float:
353        """Gets the objective coefficient for the product of two variables.
354
355        The ordering of the input variables does not matter.
356
357        Args:
358          first_variable_id: The first variable in the product.
359          second_variable_id: The second variable in the product.
360
361        Raises:
362          BadVariableIdError if first_variable_id or second_variable_id are not in
363          the model.
364
365        Returns:
366          The value of the coefficient.
367        """
368
369    @abc.abstractmethod
370    def get_quadratic_objective_coefficients(self) -> Iterator[QuadraticEntry]:
371        """Yields the nonzero quadratic objective terms in undefined order."""
372
373    @abc.abstractmethod
374    def get_quadratic_objective_adjacent_variables(
375        self, variable_id: int
376    ) -> Iterator[int]:
377        """Yields the variables multiplying a variable in the objective function.
378
379        Variables are returned in an unspecified order.
380
381        For example, if variables x and y have ids 0 and 1 respectively, and the
382        quadratic portion of the objective is x^2 + 2 x*y, then
383        get_quadratic_objective_adjacent_variables(0) = (0, 1).
384
385        Args:
386          variable_id: Function yields the variables multiplying variable_id in the
387            objective function.
388
389        Yields:
390          The variables multiplying variable_id in the objective function.
391
392        Raises:
393          BadVariableIdError if variable_id is not in the model.
394        """
395
396    @abc.abstractmethod
397    def set_is_maximize(self, is_maximize: bool) -> None:
398        pass
399
400    @abc.abstractmethod
401    def get_is_maximize(self) -> bool:
402        pass
403
404    @abc.abstractmethod
405    def set_objective_offset(self, offset: float) -> None:
406        pass
407
408    @abc.abstractmethod
409    def get_objective_offset(self) -> float:
410        pass
411
412    @abc.abstractmethod
413    def export_model(self) -> model_pb2.ModelProto:
414        pass
415
416    @abc.abstractmethod
417    def add_update_tracker(self) -> StorageUpdateTracker:
418        """Creates a StorageUpdateTracker registered with self to view model changes."""
419        pass
420
421    @abc.abstractmethod
422    def remove_update_tracker(self, tracker: StorageUpdateTracker):
423        """Stops tracker from getting updates on model changes in self.
424
425        An error will be raised if tracker is not a StorageUpdateTracker created by
426        this Model that has not previously been removed.
427
428        Using an UpdateTracker (via checkpoint or export_update) after it has been
429        removed will result in an error.
430
431        Args:
432          tracker: The StorageUpdateTracker to unregister.
433
434        Raises:
435          KeyError: The tracker was created by another model or was already removed.
436        """
437        pass
438
439
440ModelStorageImpl = TypeVar("ModelStorageImpl", bound=ModelStorage)
441ModelStorageImplClass = Type[ModelStorageImpl]