ortools.math_opt.python.objectives

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