ortools.math_opt.python.solution

  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"""The solution to an optimization problem defined by Model in model.py."""
 16import dataclasses
 17import enum
 18from typing import Dict, Optional, TypeVar
 19
 20from ortools.math_opt import solution_pb2
 21from ortools.math_opt.python import linear_constraints
 22from ortools.math_opt.python import model
 23from ortools.math_opt.python import objectives
 24from ortools.math_opt.python import quadratic_constraints
 25from ortools.math_opt.python import sparse_containers
 26from ortools.math_opt.python import variables
 27
 28
 29@enum.unique
 30class BasisStatus(enum.Enum):
 31    """Status of a variable/constraint in a LP basis.
 32
 33    Attributes:
 34      FREE: The variable/constraint is free (it has no finite bounds).
 35      AT_LOWER_BOUND: The variable/constraint is at its lower bound (which must be
 36        finite).
 37      AT_UPPER_BOUND: The variable/constraint is at its upper bound (which must be
 38        finite).
 39      FIXED_VALUE: The variable/constraint has identical finite lower and upper
 40        bounds.
 41      BASIC: The variable/constraint is basic.
 42    """
 43
 44    FREE = solution_pb2.BASIS_STATUS_FREE
 45    AT_LOWER_BOUND = solution_pb2.BASIS_STATUS_AT_LOWER_BOUND
 46    AT_UPPER_BOUND = solution_pb2.BASIS_STATUS_AT_UPPER_BOUND
 47    FIXED_VALUE = solution_pb2.BASIS_STATUS_FIXED_VALUE
 48    BASIC = solution_pb2.BASIS_STATUS_BASIC
 49
 50
 51@enum.unique
 52class SolutionStatus(enum.Enum):
 53    """Feasibility of a primal or dual solution as claimed by the solver.
 54
 55    Attributes:
 56      UNDETERMINED: Solver does not claim a feasibility status.
 57      FEASIBLE: Solver claims the solution is feasible.
 58      INFEASIBLE: Solver claims the solution is infeasible.
 59    """
 60
 61    UNDETERMINED = solution_pb2.SOLUTION_STATUS_UNDETERMINED
 62    FEASIBLE = solution_pb2.SOLUTION_STATUS_FEASIBLE
 63    INFEASIBLE = solution_pb2.SOLUTION_STATUS_INFEASIBLE
 64
 65
 66def parse_optional_solution_status(
 67    proto: solution_pb2.SolutionStatusProto,
 68) -> Optional[SolutionStatus]:
 69    """Converts a proto SolutionStatus to an optional Python SolutionStatus."""
 70    return (
 71        None
 72        if proto == solution_pb2.SOLUTION_STATUS_UNSPECIFIED
 73        else SolutionStatus(proto)
 74    )
 75
 76
 77def optional_solution_status_to_proto(
 78    status: Optional[SolutionStatus],
 79) -> solution_pb2.SolutionStatusProto:
 80    """Converts an optional Python SolutionStatus to a proto SolutionStatus."""
 81    return solution_pb2.SOLUTION_STATUS_UNSPECIFIED if status is None else status.value
 82
 83
 84@dataclasses.dataclass
 85class PrimalSolution:
 86    """A solution to the optimization problem in a Model.
 87
 88    E.g. consider a simple linear program:
 89      min c * x
 90      s.t. A * x >= b
 91      x >= 0.
 92    A primal solution is assignment values to x. It is feasible if it satisfies
 93    A * x >= b and x >= 0 from above. In the class PrimalSolution variable_values
 94    is x and objective_value is c * x.
 95
 96    For the general case of a MathOpt optimization model, see go/mathopt-solutions
 97    for details.
 98
 99    Attributes:
100      variable_values: The value assigned for each Variable in the model.
101      objective_value: The value of the objective value at this solution. This
102        value may not be always populated.
103      auxiliary_objective_values: Set only for multi objective problems, the
104        objective value for each auxiliary objective, as computed by the solver.
105        This value will not always be populated.
106      feasibility_status: The feasibility of the solution as claimed by the
107        solver.
108    """
109
110    variable_values: Dict[variables.Variable, float] = dataclasses.field(
111        default_factory=dict
112    )
113    objective_value: float = 0.0
114    auxiliary_objective_values: Dict[objectives.AuxiliaryObjective, float] = (
115        dataclasses.field(default_factory=dict)
116    )
117    feasibility_status: SolutionStatus = SolutionStatus.UNDETERMINED
118
119    def to_proto(self) -> solution_pb2.PrimalSolutionProto:
120        """Returns an equivalent proto for a primal solution."""
121        return solution_pb2.PrimalSolutionProto(
122            variable_values=sparse_containers.to_sparse_double_vector_proto(
123                self.variable_values
124            ),
125            objective_value=self.objective_value,
126            auxiliary_objective_values={
127                obj.id: obj_value
128                for obj, obj_value in self.auxiliary_objective_values.items()
129            },
130            feasibility_status=self.feasibility_status.value,
131        )
132
133
134def parse_primal_solution(
135    proto: solution_pb2.PrimalSolutionProto,
136    mod: model.Model,
137    *,
138    validate: bool = True,
139) -> PrimalSolution:
140    """Returns an equivalent PrimalSolution from the input proto."""
141    result = PrimalSolution()
142    result.objective_value = proto.objective_value
143    for aux_id, obj_value in proto.auxiliary_objective_values.items():
144        result.auxiliary_objective_values[
145            mod.get_auxiliary_objective(aux_id, validate=validate)
146        ] = obj_value
147    result.variable_values = sparse_containers.parse_variable_map(
148        proto.variable_values, mod, validate=validate
149    )
150    status_proto = proto.feasibility_status
151    if status_proto == solution_pb2.SOLUTION_STATUS_UNSPECIFIED:
152        raise ValueError("Primal solution feasibility status should not be UNSPECIFIED")
153    result.feasibility_status = SolutionStatus(status_proto)
154    return result
155
156
157@dataclasses.dataclass
158class PrimalRay:
159    """A direction of unbounded objective improvement in an optimization Model.
160
161    Equivalently, a certificate of infeasibility for the dual of the optimization
162    problem.
163
164    E.g. consider a simple linear program:
165      min c * x
166      s.t. A * x >= b
167      x >= 0.
168    A primal ray is an x that satisfies:
169      c * x < 0
170      A * x >= 0
171      x >= 0.
172    Observe that given a feasible solution, any positive multiple of the primal
173    ray plus that solution is still feasible, and gives a better objective
174    value. A primal ray also proves the dual optimization problem infeasible.
175
176    In the class PrimalRay, variable_values is this x.
177
178    For the general case of a MathOpt optimization model, see
179    go/mathopt-solutions for details.
180
181    Attributes:
182      variable_values: The value assigned for each Variable in the model.
183    """
184
185    variable_values: Dict[variables.Variable, float] = dataclasses.field(
186        default_factory=dict
187    )
188
189    def to_proto(self) -> solution_pb2.PrimalRayProto:
190        """Returns an equivalent proto to this PrimalRay."""
191        return solution_pb2.PrimalRayProto(
192            variable_values=sparse_containers.to_sparse_double_vector_proto(
193                self.variable_values
194            )
195        )
196
197
198def parse_primal_ray(
199    proto: solution_pb2.PrimalRayProto,
200    mod: model.Model,
201    *,
202    validate: bool = True,
203) -> PrimalRay:
204    """Returns an equivalent PrimalRay from the input proto."""
205    result = PrimalRay()
206    result.variable_values = sparse_containers.parse_variable_map(
207        proto.variable_values, mod, validate=validate
208    )
209    return result
210
211
212@dataclasses.dataclass
213class DualSolution:
214    """A solution to the dual of the optimization problem given by a Model.
215
216    E.g. consider the primal dual pair linear program pair:
217      (Primal)              (Dual)
218      min c * x             max b * y
219      s.t. A * x >= b       s.t. y * A + r = c
220      x >= 0                y, r >= 0.
221    The dual solution is the pair (y, r). It is feasible if it satisfies the
222    constraints from (Dual) above.
223
224    Below, y is dual_values, r is reduced_costs, and b * y is objective_value.
225
226    For the general case, see go/mathopt-solutions and go/mathopt-dual (and note
227    that the dual objective depends on r in the general case).
228
229    Attributes:
230      dual_values: The value assigned for each LinearConstraint in the model.
231      quadratic_dual_values: The value assigned for each QuadraticConstraint in
232        the model.
233      reduced_costs: The value assigned for each Variable in the model.
234      objective_value: The value of the dual objective value at this solution.
235        This value may not be always populated.
236      feasibility_status: The feasibility of the solution as claimed by the
237        solver.
238    """
239
240    dual_values: Dict[linear_constraints.LinearConstraint, float] = dataclasses.field(
241        default_factory=dict
242    )
243    quadratic_dual_values: Dict[quadratic_constraints.QuadraticConstraint, float] = (
244        dataclasses.field(default_factory=dict)
245    )
246    reduced_costs: Dict[variables.Variable, float] = dataclasses.field(
247        default_factory=dict
248    )
249    objective_value: Optional[float] = None
250    feasibility_status: SolutionStatus = SolutionStatus.UNDETERMINED
251
252    def to_proto(self) -> solution_pb2.DualSolutionProto:
253        """Returns an equivalent proto for a dual solution."""
254        return solution_pb2.DualSolutionProto(
255            dual_values=sparse_containers.to_sparse_double_vector_proto(
256                self.dual_values
257            ),
258            reduced_costs=sparse_containers.to_sparse_double_vector_proto(
259                self.reduced_costs
260            ),
261            quadratic_dual_values=sparse_containers.to_sparse_double_vector_proto(
262                self.quadratic_dual_values
263            ),
264            objective_value=self.objective_value,
265            feasibility_status=self.feasibility_status.value,
266        )
267
268
269def parse_dual_solution(
270    proto: solution_pb2.DualSolutionProto,
271    mod: model.Model,
272    *,
273    validate: bool = True,
274) -> DualSolution:
275    """Returns an equivalent DualSolution from the input proto."""
276    result = DualSolution()
277    result.objective_value = (
278        proto.objective_value if proto.HasField("objective_value") else None
279    )
280    result.dual_values = sparse_containers.parse_linear_constraint_map(
281        proto.dual_values, mod, validate=validate
282    )
283    result.quadratic_dual_values = sparse_containers.parse_quadratic_constraint_map(
284        proto.quadratic_dual_values, mod, validate=validate
285    )
286    result.reduced_costs = sparse_containers.parse_variable_map(
287        proto.reduced_costs, mod, validate=validate
288    )
289    status_proto = proto.feasibility_status
290    if status_proto == solution_pb2.SOLUTION_STATUS_UNSPECIFIED:
291        raise ValueError("Dual solution feasibility status should not be UNSPECIFIED")
292    result.feasibility_status = SolutionStatus(status_proto)
293    return result
294
295
296@dataclasses.dataclass
297class DualRay:
298    """A direction of unbounded objective improvement in an optimization Model.
299
300    A direction of unbounded improvement to the dual of an optimization,
301    problem; equivalently, a certificate of primal infeasibility.
302
303    E.g. consider the primal dual pair linear program pair:
304      (Primal)              (Dual)
305      min c * x             max b * y
306      s.t. A * x >= b       s.t. y * A + r = c
307      x >= 0                y, r >= 0.
308
309    The dual ray is the pair (y, r) satisfying:
310      b * y > 0
311      y * A + r = 0
312      y, r >= 0.
313    Observe that adding a positive multiple of (y, r) to dual feasible solution
314    maintains dual feasibility and improves the objective (proving the dual is
315    unbounded). The dual ray also proves the primal problem is infeasible.
316
317    In the class DualRay below, y is dual_values and r is reduced_costs.
318
319    For the general case, see go/mathopt-solutions and go/mathopt-dual (and note
320    that the dual objective depends on r in the general case).
321
322    Attributes:
323      dual_values: The value assigned for each LinearConstraint in the model.
324      reduced_costs: The value assigned for each Variable in the model.
325    """
326
327    dual_values: Dict[linear_constraints.LinearConstraint, float] = dataclasses.field(
328        default_factory=dict
329    )
330    reduced_costs: Dict[variables.Variable, float] = dataclasses.field(
331        default_factory=dict
332    )
333
334    def to_proto(self) -> solution_pb2.DualRayProto:
335        """Returns an equivalent proto to this PrimalRay."""
336        return solution_pb2.DualRayProto(
337            dual_values=sparse_containers.to_sparse_double_vector_proto(
338                self.dual_values
339            ),
340            reduced_costs=sparse_containers.to_sparse_double_vector_proto(
341                self.reduced_costs
342            ),
343        )
344
345
346def parse_dual_ray(
347    proto: solution_pb2.DualRayProto, mod: model.Model, *, validate: bool = True
348) -> DualRay:
349    """Returns an equivalent DualRay from the input proto."""
350    result = DualRay()
351    result.dual_values = sparse_containers.parse_linear_constraint_map(
352        proto.dual_values, mod, validate=validate
353    )
354    result.reduced_costs = sparse_containers.parse_variable_map(
355        proto.reduced_costs, mod, validate=validate
356    )
357    return result
358
359
360@dataclasses.dataclass
361class Basis:
362    """A combinatorial characterization for a solution to a linear program.
363
364    The simplex method for solving linear programs always returns a "basic
365    feasible solution" which can be described combinatorially as a Basis. A basis
366    assigns a BasisStatus for every variable and linear constraint.
367
368    E.g. consider a standard form LP:
369      min c * x
370      s.t. A * x = b
371      x >= 0
372    that has more variables than constraints and with full row rank A.
373
374    Let n be the number of variables and m the number of linear constraints. A
375    valid basis for this problem can be constructed as follows:
376     * All constraints will have basis status FIXED.
377     * Pick m variables such that the columns of A are linearly independent and
378       assign the status BASIC.
379     * Assign the status AT_LOWER for the remaining n - m variables.
380
381    The basic solution for this basis is the unique solution of A * x = b that has
382    all variables with status AT_LOWER fixed to their lower bounds (all zero). The
383    resulting solution is called a basic feasible solution if it also satisfies
384    x >= 0.
385
386    See go/mathopt-basis for treatment of the general case and an explanation of
387    how a dual solution is determined for a basis.
388
389    Attributes:
390      variable_status: The basis status for each variable in the model.
391      constraint_status: The basis status for each linear constraint in the model.
392      basic_dual_feasibility: This is an advanced feature used by MathOpt to
393        characterize feasibility of suboptimal LP solutions (optimal solutions
394        will always have status SolutionStatus.FEASIBLE). For single-sided LPs it
395        should be equal to the feasibility status of the associated dual solution.
396        For two-sided LPs it may be different in some edge cases (e.g. incomplete
397        solves with primal simplex). For more details see
398        go/mathopt-basis-advanced#dualfeasibility. If you are providing a starting
399        basis via ModelSolveParameters.initial_basis, this value is ignored and
400        can be None. It is only relevant for the basis returned by Solution.basis,
401        and it is never None when returned from solve(). This is an advanced
402        status. For single-sided LPs it should be equal to the feasibility status
403        of the associated dual solution. For two-sided LPs it may be different in
404        some edge cases (e.g. incomplete solves with primal simplex). For more
405        details see go/mathopt-basis-advanced#dualfeasibility.
406    """
407
408    variable_status: Dict[variables.Variable, BasisStatus] = dataclasses.field(
409        default_factory=dict
410    )
411    constraint_status: Dict[linear_constraints.LinearConstraint, BasisStatus] = (
412        dataclasses.field(default_factory=dict)
413    )
414    basic_dual_feasibility: Optional[SolutionStatus] = None
415
416    def to_proto(self) -> solution_pb2.BasisProto:
417        """Returns an equivalent proto for the basis."""
418        return solution_pb2.BasisProto(
419            variable_status=_to_sparse_basis_status_vector_proto(self.variable_status),
420            constraint_status=_to_sparse_basis_status_vector_proto(
421                self.constraint_status
422            ),
423            basic_dual_feasibility=optional_solution_status_to_proto(
424                self.basic_dual_feasibility
425            ),
426        )
427
428
429def parse_basis(
430    proto: solution_pb2.BasisProto, mod: model.Model, *, validate: bool = True
431) -> Basis:
432    """Returns an equivalent Basis to the input proto."""
433    result = Basis()
434    for index, vid in enumerate(proto.variable_status.ids):
435        status_proto = proto.variable_status.values[index]
436        if status_proto == solution_pb2.BASIS_STATUS_UNSPECIFIED:
437            raise ValueError("Variable basis status should not be UNSPECIFIED")
438        result.variable_status[mod.get_variable(vid, validate=validate)] = BasisStatus(
439            status_proto
440        )
441    for index, cid in enumerate(proto.constraint_status.ids):
442        status_proto = proto.constraint_status.values[index]
443        if status_proto == solution_pb2.BASIS_STATUS_UNSPECIFIED:
444            raise ValueError("Constraint basis status should not be UNSPECIFIED")
445        result.constraint_status[mod.get_linear_constraint(cid, validate=validate)] = (
446            BasisStatus(status_proto)
447        )
448    result.basic_dual_feasibility = parse_optional_solution_status(
449        proto.basic_dual_feasibility
450    )
451    return result
452
453
454T = TypeVar("T", variables.Variable, linear_constraints.LinearConstraint)
455
456
457def _to_sparse_basis_status_vector_proto(
458    terms: Dict[T, BasisStatus],
459) -> solution_pb2.SparseBasisStatusVector:
460    """Converts a basis vector from a python Dict to a protocol buffer."""
461    result = solution_pb2.SparseBasisStatusVector()
462    if terms:
463        id_and_status = sorted(
464            (key.id, status.value) for (key, status) in terms.items()
465        )
466        ids, values = zip(*id_and_status)
467        result.ids[:] = ids
468        result.values[:] = values
469    return result
470
471
472@dataclasses.dataclass
473class Solution:
474    """A solution to the optimization problem in a Model."""
475
476    primal_solution: Optional[PrimalSolution] = None
477    dual_solution: Optional[DualSolution] = None
478    basis: Optional[Basis] = None
479
480    def to_proto(self) -> solution_pb2.SolutionProto:
481        """Returns an equivalent proto for a solution."""
482        return solution_pb2.SolutionProto(
483            primal_solution=(
484                self.primal_solution.to_proto()
485                if self.primal_solution is not None
486                else None
487            ),
488            dual_solution=(
489                self.dual_solution.to_proto()
490                if self.dual_solution is not None
491                else None
492            ),
493            basis=self.basis.to_proto() if self.basis is not None else None,
494        )
495
496
497def parse_solution(
498    proto: solution_pb2.SolutionProto,
499    mod: model.Model,
500    *,
501    validate: bool = True,
502) -> Solution:
503    """Returns a Solution equivalent to the input proto."""
504    result = Solution()
505    if proto.HasField("primal_solution"):
506        result.primal_solution = parse_primal_solution(
507            proto.primal_solution, mod, validate=validate
508        )
509    if proto.HasField("dual_solution"):
510        result.dual_solution = parse_dual_solution(
511            proto.dual_solution, mod, validate=validate
512        )
513    result.basis = (
514        parse_basis(proto.basis, mod, validate=validate)
515        if proto.HasField("basis")
516        else None
517    )
518    return result