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