ortools.math_opt.python.objectives

  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"""An Objective for a MathOpt optimization model."""
 15
 16import abc
 17from typing import Any, Iterator
 18
 19from ortools.math_opt.elemental.python import enums
 20from ortools.math_opt.python import from_model
 21from ortools.math_opt.python import variables
 22from ortools.math_opt.python.elemental import elemental
 23
 24
 25class Objective(from_model.FromModel, metaclass=abc.ABCMeta):
 26    """The objective for an optimization model.
 27
 28    An objective is either of the form:
 29      min o + sum_{i in I} c_i * x_i + sum_{i, j in I, i <= j} q_i,j * x_i * x_j
 30    or
 31      max o + sum_{i in I} c_i * x_i + sum_{(i, j) in Q} q_i,j * x_i * x_j
 32    where x_i are the decision variables of the problem and where all pairs (i, j)
 33    in Q satisfy i <= j. The values of o, c_i and q_i,j should be finite and not
 34    NaN.
 35
 36    The objective can be configured as follows:
 37      * offset: a float property, o above. Should be finite and not NaN.
 38      * is_maximize: a bool property, if the objective is to maximize or minimize.
 39      * set_linear_coefficient and get_linear_coefficient control the c_i * x_i
 40        terms. The variables must be from the same model as this objective, and
 41        the c_i must be finite and not NaN. The coefficient for any variable not
 42        set is 0.0, and setting a coefficient to 0.0 removes it from I above.
 43      * set_quadratic_coefficient and get_quadratic_coefficient control the
 44        q_i,j * x_i * x_j terms. The variables must be from the same model as this
 45        objective, and the q_i,j must be finite and not NaN. The coefficient for
 46        any pair of variables not set is 0.0, and setting a coefficient to 0.0
 47        removes the associated (i,j) from Q above.
 48
 49    Do not create an Objective directly, use Model.objective to access the
 50    objective instead (or Model.add_auxiliary_objective()). Two Objective objects
 51    can represent the same objective (for the same model). They will have the same
 52    underlying Objective.elemental for storing the data. The Objective class is
 53    simply a reference to an Elemental.
 54
 55    The objective is linear if only linear coefficients are set. This can be
 56    useful to avoid solve-time errors with solvers that do not accept quadratic
 57    objectives. To facilitate this linear objective guarantee we provide three
 58    functions to add to the objective:
 59      * add(), which accepts linear or quadratic expressions,
 60      * add_quadratic(), which also accepts linear or quadratic expressions and
 61        can be used to signal a quadratic objective is possible, and
 62      * add_linear(), which only accepts linear expressions and can be used to
 63        guarantee the objective remains linear.
 64
 65    For quadratic terms, the order that variables are provided does not matter,
 66    we always canonicalize to first_var <= second_var. So if you set (x1, x2) to 7
 67    then:
 68      * getting (x2, x1) returns 7
 69      * setting (x2, x1) to 10 overwrites the value of 7.
 70    Likewise, when we return nonzero quadratic coefficients, we always use the
 71    form first_var <= second_var.
 72
 73    Most problems have only a single objective, but hierarchical objectives are
 74    supported (see Model.add_auxiliary_objective()). Note that quadratic Auxiliary
 75    objectives are not supported.
 76    """
 77
 78    __slots__ = ("_elemental",)
 79
 80    def __init__(self, elem: elemental.Elemental) -> None:
 81        """Do not invoke directly, prefer Model.objective."""
 82        self._elemental: elemental.Elemental = elem
 83
 84    @property
 85    def elemental(self) -> elemental.Elemental:
 86        """The underlying data structure for the model, for internal use only."""
 87        return self._elemental
 88
 89    @property
 90    @abc.abstractmethod
 91    def name(self) -> str:
 92        """The immutable name of this objective, for display only."""
 93
 94    @property
 95    @abc.abstractmethod
 96    def is_maximize(self) -> bool:
 97        """If true, the direction is maximization, otherwise minimization."""
 98
 99    @is_maximize.setter
100    @abc.abstractmethod
101    def is_maximize(self, is_maximize: bool) -> None: ...
102
103    @property
104    @abc.abstractmethod
105    def offset(self) -> float:
106        """A constant added to the objective."""
107
108    @offset.setter
109    @abc.abstractmethod
110    def offset(self, value: float) -> None: ...
111
112    @property
113    @abc.abstractmethod
114    def priority(self) -> int:
115        """For hierarchical problems, determines the order to apply objectives.
116
117        The objectives are applied from lowest priority to highest.
118
119        The default priority for the primary objective is zero, and auxiliary
120        objectives must specific a priority at creation time.
121
122        Priority has no effect for problems with only one objective.
123        """
124
125    @priority.setter
126    @abc.abstractmethod
127    def priority(self, value: int) -> None: ...
128
129    @abc.abstractmethod
130    def set_linear_coefficient(self, var: variables.Variable, coef: float) -> None:
131        """Sets the coefficient of `var` to `coef` in the objective."""
132
133    @abc.abstractmethod
134    def get_linear_coefficient(self, var: variables.Variable) -> float:
135        """Returns the coefficinet of `var` (or zero if unset)."""
136
137    @abc.abstractmethod
138    def linear_terms(self) -> Iterator[variables.LinearTerm]:
139        """Yields variable coefficient pairs for variables with nonzero objective coefficient in undefined order."""
140
141    @abc.abstractmethod
142    def set_quadratic_coefficient(
143        self,
144        first_variable: variables.Variable,
145        second_variable: variables.Variable,
146        coef: float,
147    ) -> None:
148        """Sets the coefficient for product of variables (see class description)."""
149
150    @abc.abstractmethod
151    def get_quadratic_coefficient(
152        self,
153        first_variable: variables.Variable,
154        second_variable: variables.Variable,
155    ) -> float:
156        """Gets the coefficient for product of variables (see class description)."""
157
158    @abc.abstractmethod
159    def quadratic_terms(self) -> Iterator[variables.QuadraticTerm]:
160        """Yields quadratic terms with nonzero objective coefficient in undefined order."""
161
162    @abc.abstractmethod
163    def clear(self) -> None:
164        """Clears objective coefficients and offset. Does not change direction."""
165
166    def as_linear_expression(self) -> variables.LinearExpression:
167        """Returns an equivalent LinearExpression, or errors if quadratic."""
168        if any(self.quadratic_terms()):
169            raise TypeError("Cannot get a quadratic objective as a linear expression")
170        return variables.as_flat_linear_expression(
171            self.offset + variables.LinearSum(self.linear_terms())
172        )
173
174    def as_quadratic_expression(self) -> variables.QuadraticExpression:
175        """Returns an equivalent QuadraticExpression to this objetive."""
176        return variables.as_flat_quadratic_expression(
177            self.offset
178            + variables.LinearSum(self.linear_terms())
179            + variables.QuadraticSum(self.quadratic_terms())
180        )
181
182    def add(self, objective: variables.QuadraticTypes) -> None:
183        """Adds the provided expression `objective` to the objective function.
184
185        For a compile time guarantee that the objective remains linear, use
186        add_linear() instead.
187
188        Args:
189          objective: the expression to add to the objective function.
190        """
191        if isinstance(objective, (variables.LinearBase, int, float)):
192            self.add_linear(objective)
193        elif isinstance(objective, variables.QuadraticBase):
194            self.add_quadratic(objective)
195        else:
196            raise TypeError(
197                "unsupported type in objective argument for "
198                f"Objective.add(): {type(objective).__name__!r}"
199            )
200
201    def add_linear(self, objective: variables.LinearTypes) -> None:
202        """Adds the provided linear expression `objective` to the objective function."""
203        if not isinstance(objective, (variables.LinearBase, int, float)):
204            raise TypeError(
205                "unsupported type in objective argument for "
206                f"Objective.add_linear(): {type(objective).__name__!r}"
207            )
208        objective_expr = variables.as_flat_linear_expression(objective)
209        self.offset += objective_expr.offset
210        for var, coefficient in objective_expr.terms.items():
211            self.set_linear_coefficient(
212                var, self.get_linear_coefficient(var) + coefficient
213            )
214
215    def add_quadratic(self, objective: variables.QuadraticTypes) -> None:
216        """Adds the provided quadratic expression `objective` to the objective function."""
217        if not isinstance(
218            objective, (variables.QuadraticBase, variables.LinearBase, int, float)
219        ):
220            raise TypeError(
221                "unsupported type in objective argument for "
222                f"Objective.add(): {type(objective).__name__!r}"
223            )
224        objective_expr = variables.as_flat_quadratic_expression(objective)
225        self.offset += objective_expr.offset
226        for var, coefficient in objective_expr.linear_terms.items():
227            self.set_linear_coefficient(
228                var, self.get_linear_coefficient(var) + coefficient
229            )
230        for key, coefficient in objective_expr.quadratic_terms.items():
231            self.set_quadratic_coefficient(
232                key.first_var,
233                key.second_var,
234                self.get_quadratic_coefficient(key.first_var, key.second_var)
235                + coefficient,
236            )
237
238    def set_to_linear_expression(self, linear_expr: variables.LinearTypes) -> None:
239        """Sets the objective to optimize to `linear_expr`."""
240        if not isinstance(linear_expr, (variables.LinearBase, int, float)):
241            raise TypeError(
242                "unsupported type in objective argument for "
243                f"set_to_linear_expression: {type(linear_expr).__name__!r}"
244            )
245        self.clear()
246        objective_expr = variables.as_flat_linear_expression(linear_expr)
247        self.offset = objective_expr.offset
248        for var, coefficient in objective_expr.terms.items():
249            self.set_linear_coefficient(var, coefficient)
250
251    def set_to_quadratic_expression(
252        self, quadratic_expr: variables.QuadraticTypes
253    ) -> None:
254        """Sets the objective to optimize the `quadratic_expr`."""
255        if not isinstance(
256            quadratic_expr,
257            (variables.QuadraticBase, variables.LinearBase, int, float),
258        ):
259            raise TypeError(
260                "unsupported type in objective argument for "
261                f"set_to_quadratic_expression: {type(quadratic_expr).__name__!r}"
262            )
263        self.clear()
264        objective_expr = variables.as_flat_quadratic_expression(quadratic_expr)
265        self.offset = objective_expr.offset
266        for var, coefficient in objective_expr.linear_terms.items():
267            self.set_linear_coefficient(var, coefficient)
268        for quad_key, coefficient in objective_expr.quadratic_terms.items():
269            self.set_quadratic_coefficient(
270                quad_key.first_var, quad_key.second_var, coefficient
271            )
272
273    def set_to_expression(self, expr: variables.QuadraticTypes) -> None:
274        """Sets the objective to optimize the `expr`."""
275        if isinstance(expr, (variables.LinearBase, int, float)):
276            self.set_to_linear_expression(expr)
277        elif isinstance(expr, variables.QuadraticBase):
278            self.set_to_quadratic_expression(expr)
279        else:
280            raise TypeError(
281                "unsupported type in objective argument for "
282                f"set_to_expression: {type(expr).__name__!r}"
283            )
284
285
286class PrimaryObjective(Objective):
287    """The main objective, but users should program against Objective directly."""
288
289    __slots__ = ()
290
291    @property
292    def name(self) -> str:
293        return self._elemental.primary_objective_name
294
295    @property
296    def is_maximize(self) -> bool:
297        return self._elemental.get_attr(enums.BoolAttr0.MAXIMIZE, ())
298
299    @is_maximize.setter
300    def is_maximize(self, is_maximize: bool) -> None:
301        self._elemental.set_attr(enums.BoolAttr0.MAXIMIZE, (), is_maximize)
302
303    @property
304    def offset(self) -> float:
305        return self._elemental.get_attr(enums.DoubleAttr0.OBJECTIVE_OFFSET, ())
306
307    @offset.setter
308    def offset(self, value: float) -> None:
309        self._elemental.set_attr(enums.DoubleAttr0.OBJECTIVE_OFFSET, (), value)
310
311    @property
312    def priority(self) -> int:
313        return self._elemental.get_attr(enums.IntAttr0.OBJECTIVE_PRIORITY, ())
314
315    @priority.setter
316    def priority(self, value: int) -> None:
317        self._elemental.set_attr(enums.IntAttr0.OBJECTIVE_PRIORITY, (), value)
318
319    def set_linear_coefficient(self, var: variables.Variable, coef: float) -> None:
320        from_model.model_is_same(self, var)
321        self._elemental.set_attr(
322            enums.DoubleAttr1.OBJECTIVE_LINEAR_COEFFICIENT, (var.id,), coef
323        )
324
325    def get_linear_coefficient(self, var: variables.Variable) -> float:
326        from_model.model_is_same(self, var)
327        return self._elemental.get_attr(
328            enums.DoubleAttr1.OBJECTIVE_LINEAR_COEFFICIENT, (var.id,)
329        )
330
331    def linear_terms(self) -> Iterator[variables.LinearTerm]:
332        keys = self._elemental.get_attr_non_defaults(
333            enums.DoubleAttr1.OBJECTIVE_LINEAR_COEFFICIENT
334        )
335        var_index = 0
336        coefs = self._elemental.get_attrs(
337            enums.DoubleAttr1.OBJECTIVE_LINEAR_COEFFICIENT, keys
338        )
339        for i in range(len(keys)):
340            yield variables.LinearTerm(
341                variable=variables.Variable(self._elemental, int(keys[i, var_index])),
342                coefficient=float(coefs[i]),
343            )
344
345    def set_quadratic_coefficient(
346        self,
347        first_variable: variables.Variable,
348        second_variable: variables.Variable,
349        coef: float,
350    ) -> None:
351        from_model.model_is_same(self, first_variable)
352        from_model.model_is_same(self, second_variable)
353        self._elemental.set_attr(
354            enums.SymmetricDoubleAttr2.OBJECTIVE_QUADRATIC_COEFFICIENT,
355            (first_variable.id, second_variable.id),
356            coef,
357        )
358
359    def get_quadratic_coefficient(
360        self,
361        first_variable: variables.Variable,
362        second_variable: variables.Variable,
363    ) -> float:
364        from_model.model_is_same(self, first_variable)
365        from_model.model_is_same(self, second_variable)
366        return self._elemental.get_attr(
367            enums.SymmetricDoubleAttr2.OBJECTIVE_QUADRATIC_COEFFICIENT,
368            (first_variable.id, second_variable.id),
369        )
370
371    def quadratic_terms(self) -> Iterator[variables.QuadraticTerm]:
372        keys = self._elemental.get_attr_non_defaults(
373            enums.SymmetricDoubleAttr2.OBJECTIVE_QUADRATIC_COEFFICIENT
374        )
375        coefs = self._elemental.get_attrs(
376            enums.SymmetricDoubleAttr2.OBJECTIVE_QUADRATIC_COEFFICIENT, keys
377        )
378        for i in range(len(keys)):
379            yield variables.QuadraticTerm(
380                variables.QuadraticTermKey(
381                    variables.Variable(self._elemental, int(keys[i, 0])),
382                    variables.Variable(self._elemental, int(keys[i, 1])),
383                ),
384                coefficient=float(coefs[i]),
385            )
386
387    def clear(self) -> None:
388        self._elemental.clear_attr(enums.DoubleAttr0.OBJECTIVE_OFFSET)
389        self._elemental.clear_attr(enums.DoubleAttr1.OBJECTIVE_LINEAR_COEFFICIENT)
390        self._elemental.clear_attr(
391            enums.SymmetricDoubleAttr2.OBJECTIVE_QUADRATIC_COEFFICIENT
392        )
393
394    def __eq__(self, other: Any) -> bool:
395        if isinstance(other, PrimaryObjective):
396            return self._elemental is other._elemental
397        return False
398
399    def __hash__(self) -> int:
400        return hash(self._elemental)
401
402
403class AuxiliaryObjective(Objective):
404    """An additional objective that can be optimized after objectives."""
405
406    __slots__ = ("_id",)
407
408    def __init__(self, elem: elemental.Elemental, obj_id: int) -> None:
409        """Internal only, prefer Model functions (add_auxiliary_objective() and get_auxiliary_objective())."""
410        super().__init__(elem)
411        if not isinstance(obj_id, int):
412            raise TypeError(
413                f"obj_id type should be int, was: {type(obj_id).__name__!r}"
414            )
415        self._id: int = obj_id
416
417    @property
418    def name(self) -> str:
419        return self._elemental.get_element_name(
420            enums.ElementType.AUXILIARY_OBJECTIVE, self._id
421        )
422
423    @property
424    def id(self) -> int:
425        """Returns the id of this objective."""
426        return self._id
427
428    @property
429    def is_maximize(self) -> bool:
430        return self._elemental.get_attr(
431            enums.BoolAttr1.AUXILIARY_OBJECTIVE_MAXIMIZE, (self._id,)
432        )
433
434    @is_maximize.setter
435    def is_maximize(self, is_maximize: bool) -> None:
436        self._elemental.set_attr(
437            enums.BoolAttr1.AUXILIARY_OBJECTIVE_MAXIMIZE,
438            (self._id,),
439            is_maximize,
440        )
441
442    @property
443    def offset(self) -> float:
444        return self._elemental.get_attr(
445            enums.DoubleAttr1.AUXILIARY_OBJECTIVE_OFFSET, (self._id,)
446        )
447
448    @offset.setter
449    def offset(self, value: float) -> None:
450        self._elemental.set_attr(
451            enums.DoubleAttr1.AUXILIARY_OBJECTIVE_OFFSET,
452            (self._id,),
453            value,
454        )
455
456    @property
457    def priority(self) -> int:
458        return self._elemental.get_attr(
459            enums.IntAttr1.AUXILIARY_OBJECTIVE_PRIORITY, (self._id,)
460        )
461
462    @priority.setter
463    def priority(self, value: int) -> None:
464        self._elemental.set_attr(
465            enums.IntAttr1.AUXILIARY_OBJECTIVE_PRIORITY,
466            (self._id,),
467            value,
468        )
469
470    def set_linear_coefficient(self, var: variables.Variable, coef: float) -> None:
471        from_model.model_is_same(self, var)
472        self._elemental.set_attr(
473            enums.DoubleAttr2.AUXILIARY_OBJECTIVE_LINEAR_COEFFICIENT,
474            (self._id, var.id),
475            coef,
476        )
477
478    def get_linear_coefficient(self, var: variables.Variable) -> float:
479        from_model.model_is_same(self, var)
480        return self._elemental.get_attr(
481            enums.DoubleAttr2.AUXILIARY_OBJECTIVE_LINEAR_COEFFICIENT,
482            (
483                self._id,
484                var.id,
485            ),
486        )
487
488    def linear_terms(self) -> Iterator[variables.LinearTerm]:
489        keys = self._elemental.slice_attr(
490            enums.DoubleAttr2.AUXILIARY_OBJECTIVE_LINEAR_COEFFICIENT,
491            0,
492            self._id,
493        )
494        var_index = 1
495        coefs = self._elemental.get_attrs(
496            enums.DoubleAttr2.AUXILIARY_OBJECTIVE_LINEAR_COEFFICIENT, keys
497        )
498        for i in range(len(keys)):
499            yield variables.LinearTerm(
500                variable=variables.Variable(self._elemental, int(keys[i, var_index])),
501                coefficient=float(coefs[i]),
502            )
503
504    def set_quadratic_coefficient(
505        self,
506        first_variable: variables.Variable,
507        second_variable: variables.Variable,
508        coef: float,
509    ) -> None:
510        raise ValueError("Quadratic auxiliary objectives are not supported.")
511
512    def get_quadratic_coefficient(
513        self,
514        first_variable: variables.Variable,
515        second_variable: variables.Variable,
516    ) -> float:
517        from_model.model_is_same(self, first_variable)
518        from_model.model_is_same(self, second_variable)
519        if not self._elemental.element_exists(
520            enums.ElementType.VARIABLE, first_variable.id
521        ):
522            raise ValueError(f"Variable {first_variable} does not exist")
523        if not self._elemental.element_exists(
524            enums.ElementType.VARIABLE, second_variable.id
525        ):
526            raise ValueError(f"Variable {second_variable} does not exist")
527        return 0.0
528
529    def quadratic_terms(self) -> Iterator[variables.QuadraticTerm]:
530        return iter(())
531
532    def clear(self) -> None:
533        """Clears objective coefficients and offset. Does not change direction."""
534        self._elemental.clear_attr(enums.DoubleAttr1.AUXILIARY_OBJECTIVE_OFFSET)
535        self._elemental.clear_attr(
536            enums.DoubleAttr2.AUXILIARY_OBJECTIVE_LINEAR_COEFFICIENT
537        )
538
539    def __eq__(self, other: Any) -> bool:
540        if isinstance(other, AuxiliaryObjective):
541            return self._elemental is other._elemental and self._id == other._id
542        return False
543
544    def __hash__(self) -> int:
545        return hash((self._elemental, self._id))