ortools.math_opt.python.solution

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