ortools.math_opt.python.result

   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 output from solving a mathematical optimization problem from model.py."""
  16import dataclasses
  17import datetime
  18import enum
  19from typing import Dict, Iterable, List, Optional, overload
  20
  21from ortools.math_opt import result_pb2
  22from ortools.math_opt.python import linear_constraints as linear_constraints_mod
  23from ortools.math_opt.python import model
  24from ortools.math_opt.python import solution
  25from ortools.math_opt.python import variables as variables_mod
  26from ortools.math_opt.solvers import osqp_pb2
  27from ortools.math_opt.solvers.gscip import gscip_pb2
  28
  29_NO_DUAL_SOLUTION_ERROR = (
  30    "Best solution does not have an associated dual feasible solution."
  31)
  32_NO_BASIS_ERROR = "Best solution does not have an associated basis."
  33
  34
  35@enum.unique
  36class FeasibilityStatus(enum.Enum):
  37    """Problem feasibility status as claimed by the solver.
  38
  39      (solver is not required to return a certificate for the claim.)
  40
  41    Attributes:
  42      UNDETERMINED: Solver does not claim a status.
  43      FEASIBLE: Solver claims the problem is feasible.
  44      INFEASIBLE: Solver claims the problem is infeasible.
  45    """
  46
  47    UNDETERMINED = result_pb2.FEASIBILITY_STATUS_UNDETERMINED
  48    FEASIBLE = result_pb2.FEASIBILITY_STATUS_FEASIBLE
  49    INFEASIBLE = result_pb2.FEASIBILITY_STATUS_INFEASIBLE
  50
  51
  52@dataclasses.dataclass(frozen=True)
  53class ProblemStatus:
  54    """Feasibility status of the primal problem and its dual (or dual relaxation).
  55
  56    Statuses are as claimed by the solver and a dual relaxation is the dual of a
  57    continuous relaxation for the original problem (e.g. the LP relaxation of a
  58    MIP). The solver is not required to return a certificate for the feasibility
  59    or infeasibility claims (e.g. the solver may claim primal feasibility without
  60    returning a primal feasible solutuion). This combined status gives a
  61    comprehensive description of a solver's claims about feasibility and
  62    unboundedness of the solved problem. For instance,
  63      * a feasible status for primal and dual problems indicates the primal is
  64        feasible and bounded and likely has an optimal solution (guaranteed for
  65        problems without non-linear constraints).
  66      * a primal feasible and a dual infeasible status indicates the primal
  67        problem is unbounded (i.e. has arbitrarily good solutions).
  68    Note that a dual infeasible status by itself (i.e. accompanied by an
  69    undetermined primal status) does not imply the primal problem is unbounded as
  70    we could have both problems be infeasible. Also, while a primal and dual
  71    feasible status may imply the existence of an optimal solution, it does not
  72    guarantee the solver has actually found such optimal solution.
  73
  74    Attributes:
  75      primal_status: Status for the primal problem.
  76      dual_status: Status for the dual problem (or for the dual of a continuous
  77        relaxation).
  78      primal_or_dual_infeasible: If true, the solver claims the primal or dual
  79        problem is infeasible, but it does not know which (or if both are
  80        infeasible). Can be true only when primal_problem_status =
  81        dual_problem_status = kUndetermined. This extra information is often
  82        needed when preprocessing determines there is no optimal solution to the
  83        problem (but can't determine if it is due to infeasibility, unboundedness,
  84        or both).
  85    """
  86
  87    primal_status: FeasibilityStatus = FeasibilityStatus.UNDETERMINED
  88    dual_status: FeasibilityStatus = FeasibilityStatus.UNDETERMINED
  89    primal_or_dual_infeasible: bool = False
  90
  91    def to_proto(self) -> result_pb2.ProblemStatusProto:
  92        """Returns an equivalent proto for a problem status."""
  93        return result_pb2.ProblemStatusProto(
  94            primal_status=self.primal_status.value,
  95            dual_status=self.dual_status.value,
  96            primal_or_dual_infeasible=self.primal_or_dual_infeasible,
  97        )
  98
  99
 100def parse_problem_status(proto: result_pb2.ProblemStatusProto) -> ProblemStatus:
 101    """Returns an equivalent ProblemStatus from the input proto."""
 102    primal_status_proto = proto.primal_status
 103    if primal_status_proto == result_pb2.FEASIBILITY_STATUS_UNSPECIFIED:
 104        raise ValueError("Primal feasibility status should not be UNSPECIFIED")
 105    dual_status_proto = proto.dual_status
 106    if dual_status_proto == result_pb2.FEASIBILITY_STATUS_UNSPECIFIED:
 107        raise ValueError("Dual feasibility status should not be UNSPECIFIED")
 108    return ProblemStatus(
 109        primal_status=FeasibilityStatus(primal_status_proto),
 110        dual_status=FeasibilityStatus(dual_status_proto),
 111        primal_or_dual_infeasible=proto.primal_or_dual_infeasible,
 112    )
 113
 114
 115@dataclasses.dataclass(frozen=True)
 116class ObjectiveBounds:
 117    """Bounds on the optimal objective value.
 118
 119  MOE:begin_intracomment_strip
 120  See go/mathopt-objective-bounds for more details.
 121  MOE:end_intracomment_strip
 122
 123  Attributes:
 124    primal_bound: Solver claims there exists a primal solution that is
 125      numerically feasible (i.e. feasible up to the solvers tolerance), and
 126      whose objective value is primal_bound.
 127
 128      The optimal value is equal or better (smaller for min objectives and
 129      larger for max objectives) than primal_bound, but only up to
 130      solver-tolerances.
 131
 132      MOE:begin_intracomment_strip
 133      See go/mathopt-objective-bounds for more details.
 134      MOE:end_intracomment_strip
 135    dual_bound: Solver claims there exists a dual solution that is numerically
 136      feasible (i.e. feasible up to the solvers tolerance), and whose objective
 137      value is dual_bound.
 138
 139      For MIP solvers, the associated dual problem may be some continuous
 140      relaxation (e.g. LP relaxation), but it is often an implicitly defined
 141      problem that is a complex consequence of the solvers execution. For both
 142      continuous and MIP solvers, the optimal value is equal or worse (larger
 143      for min objective and smaller for max objectives) than dual_bound, but
 144      only up to solver-tolerances. Some continuous solvers provide a
 145      numerically safer dual bound through solver's specific output (e.g. for
 146      PDLP, pdlp_output.convergence_information.corrected_dual_objective).
 147
 148      MOE:begin_intracomment_strip
 149      See go/mathopt-objective-bounds for more details.
 150      MOE:end_intracomment_strip
 151  """  # fmt: skip
 152
 153    primal_bound: float = 0.0
 154    dual_bound: float = 0.0
 155
 156    def to_proto(self) -> result_pb2.ObjectiveBoundsProto:
 157        """Returns an equivalent proto for objective bounds."""
 158        return result_pb2.ObjectiveBoundsProto(
 159            primal_bound=self.primal_bound, dual_bound=self.dual_bound
 160        )
 161
 162
 163def parse_objective_bounds(
 164    proto: result_pb2.ObjectiveBoundsProto,
 165) -> ObjectiveBounds:
 166    """Returns an equivalent ObjectiveBounds from the input proto."""
 167    return ObjectiveBounds(primal_bound=proto.primal_bound, dual_bound=proto.dual_bound)
 168
 169
 170@dataclasses.dataclass
 171class SolveStats:
 172    """Problem statuses and solve statistics returned by the solver.
 173
 174    Attributes:
 175      solve_time: Elapsed wall clock time as measured by math_opt, roughly the
 176        time inside solve(). Note: this does not include work done building the
 177        model.
 178      simplex_iterations: Simplex iterations.
 179      barrier_iterations: Barrier iterations.
 180      first_order_iterations: First order iterations.
 181      node_count: Node count.
 182    """
 183
 184    solve_time: datetime.timedelta = datetime.timedelta()
 185    simplex_iterations: int = 0
 186    barrier_iterations: int = 0
 187    first_order_iterations: int = 0
 188    node_count: int = 0
 189
 190    def to_proto(self) -> result_pb2.SolveStatsProto:
 191        """Returns an equivalent proto for a solve stats."""
 192        result = result_pb2.SolveStatsProto(
 193            simplex_iterations=self.simplex_iterations,
 194            barrier_iterations=self.barrier_iterations,
 195            first_order_iterations=self.first_order_iterations,
 196            node_count=self.node_count,
 197        )
 198        result.solve_time.FromTimedelta(self.solve_time)
 199        return result
 200
 201
 202def parse_solve_stats(proto: result_pb2.SolveStatsProto) -> SolveStats:
 203    """Returns an equivalent SolveStats from the input proto."""
 204    result = SolveStats()
 205    result.solve_time = proto.solve_time.ToTimedelta()
 206    result.simplex_iterations = proto.simplex_iterations
 207    result.barrier_iterations = proto.barrier_iterations
 208    result.first_order_iterations = proto.first_order_iterations
 209    result.node_count = proto.node_count
 210    return result
 211
 212
 213@enum.unique
 214class TerminationReason(enum.Enum):
 215    """The reason a solve of a model terminated.
 216
 217    These reasons are typically as reported by the underlying solver, e.g. we do
 218    not attempt to verify the precision of the solution returned.
 219
 220    The values are:
 221       * OPTIMAL: A provably optimal solution (up to numerical tolerances) has
 222           been found.
 223       * INFEASIBLE: The primal problem has no feasible solutions.
 224       * UNBOUNDED: The primal problem is feasible and arbitrarily good solutions
 225           can be found along a primal ray.
 226       * INFEASIBLE_OR_UNBOUNDED: The primal problem is either infeasible or
 227           unbounded. More details on the problem status may be available in
 228           solve_stats.problem_status. Note that Gurobi's unbounded status may be
 229           mapped here as explained in
 230           go/mathopt-solver-specific#gurobi-inf-or-unb.
 231       * IMPRECISE: The problem was solved to one of the criteria above (Optimal,
 232           Infeasible, Unbounded, or InfeasibleOrUnbounded), but one or more
 233           tolerances was not met. Some primal/dual solutions/rays may be present,
 234           but either they will be slightly infeasible, or (if the problem was
 235           nearly optimal) their may be a gap between the best solution objective
 236           and best objective bound.
 237
 238           Users can still query primal/dual solutions/rays and solution stats,
 239           but they are responsible for dealing with the numerical imprecision.
 240       * FEASIBLE: The optimizer reached some kind of limit and a primal feasible
 241           solution is returned. See SolveResultProto.limit_detail for detailed
 242           description of the kind of limit that was reached.
 243       * NO_SOLUTION_FOUND: The optimizer reached some kind of limit and it did
 244           not find a primal feasible solution. See SolveResultProto.limit_detail
 245           for detailed description of the kind of limit that was reached.
 246       * NUMERICAL_ERROR: The algorithm stopped because it encountered
 247           unrecoverable numerical error. No solution information is present.
 248       * OTHER_ERROR: The algorithm stopped because of an error not covered by one
 249           of the statuses defined above. No solution information is present.
 250    """
 251
 252    OPTIMAL = result_pb2.TERMINATION_REASON_OPTIMAL
 253    INFEASIBLE = result_pb2.TERMINATION_REASON_INFEASIBLE
 254    UNBOUNDED = result_pb2.TERMINATION_REASON_UNBOUNDED
 255    INFEASIBLE_OR_UNBOUNDED = result_pb2.TERMINATION_REASON_INFEASIBLE_OR_UNBOUNDED
 256    IMPRECISE = result_pb2.TERMINATION_REASON_IMPRECISE
 257    FEASIBLE = result_pb2.TERMINATION_REASON_FEASIBLE
 258    NO_SOLUTION_FOUND = result_pb2.TERMINATION_REASON_NO_SOLUTION_FOUND
 259    NUMERICAL_ERROR = result_pb2.TERMINATION_REASON_NUMERICAL_ERROR
 260    OTHER_ERROR = result_pb2.TERMINATION_REASON_OTHER_ERROR
 261
 262
 263@enum.unique
 264class Limit(enum.Enum):
 265    """The optimizer reached a limit, partial solution information may be present.
 266
 267    Values are:
 268       * UNDETERMINED: The underlying solver does not expose which limit was
 269           reached.
 270       * ITERATION: An iterative algorithm stopped after conducting the
 271           maximum number of iterations (e.g. simplex or barrier iterations).
 272       * TIME: The algorithm stopped after a user-specified amount of
 273           computation time.
 274       * NODE: A branch-and-bound algorithm stopped because it explored a
 275           maximum number of nodes in the branch-and-bound tree.
 276       * SOLUTION: The algorithm stopped because it found the required
 277           number of solutions. This is often used in MIPs to get the solver to
 278           return the first feasible solution it encounters.
 279       * MEMORY: The algorithm stopped because it ran out of memory.
 280       * OBJECTIVE: The algorithm stopped because it found a solution better
 281           than a minimum limit set by the user.
 282       * NORM: The algorithm stopped because the norm of an iterate became
 283           too large.
 284       * INTERRUPTED: The algorithm stopped because of an interrupt signal or a
 285           user interrupt request.
 286       * SLOW_PROGRESS: The algorithm stopped because it was unable to continue
 287           making progress towards the solution.
 288       * OTHER: The algorithm stopped due to a limit not covered by one of the
 289           above. Note that UNDETERMINED is used when the reason cannot be
 290           determined, and OTHER is used when the reason is known but does not fit
 291           into any of the above alternatives.
 292    """
 293
 294    UNDETERMINED = result_pb2.LIMIT_UNDETERMINED
 295    ITERATION = result_pb2.LIMIT_ITERATION
 296    TIME = result_pb2.LIMIT_TIME
 297    NODE = result_pb2.LIMIT_NODE
 298    SOLUTION = result_pb2.LIMIT_SOLUTION
 299    MEMORY = result_pb2.LIMIT_MEMORY
 300    OBJECTIVE = result_pb2.LIMIT_OBJECTIVE
 301    NORM = result_pb2.LIMIT_NORM
 302    INTERRUPTED = result_pb2.LIMIT_INTERRUPTED
 303    SLOW_PROGRESS = result_pb2.LIMIT_SLOW_PROGRESS
 304    OTHER = result_pb2.LIMIT_OTHER
 305
 306
 307@dataclasses.dataclass
 308class Termination:
 309    """An explanation of why the solver stopped.
 310
 311    Attributes:
 312      reason: Why the solver stopped, e.g. it found a provably optimal solution.
 313        Additional information in `limit` when value is FEASIBLE or
 314        NO_SOLUTION_FOUND, see `limit` for details.
 315      limit: If the solver stopped early, what caused it to stop. Have value
 316        UNSPECIFIED when reason is not NO_SOLUTION_FOUND or FEASIBLE. May still be
 317        UNSPECIFIED when reason is NO_SOLUTION_FOUND or FEASIBLE, some solvers
 318        cannot fill this in.
 319      detail: Additional, information beyond reason about why the solver stopped,
 320        typically solver specific.
 321      problem_status: Feasibility statuses for primal and dual problems.
 322      objective_bounds: Bounds on the optimal objective value.
 323    """
 324
 325    reason: TerminationReason = TerminationReason.OPTIMAL
 326    limit: Optional[Limit] = None
 327    detail: str = ""
 328    problem_status: ProblemStatus = ProblemStatus()
 329    objective_bounds: ObjectiveBounds = ObjectiveBounds()
 330
 331    def to_proto(self) -> result_pb2.TerminationProto:
 332        """Returns an equivalent protocol buffer to this Termination."""
 333        return result_pb2.TerminationProto(
 334            reason=self.reason.value,
 335            limit=(
 336                result_pb2.LIMIT_UNSPECIFIED if self.limit is None else self.limit.value
 337            ),
 338            detail=self.detail,
 339            problem_status=self.problem_status.to_proto(),
 340            objective_bounds=self.objective_bounds.to_proto(),
 341        )
 342
 343
 344def parse_termination(
 345    termination_proto: result_pb2.TerminationProto,
 346) -> Termination:
 347    """Returns a Termination that is equivalent to termination_proto."""
 348    reason_proto = termination_proto.reason
 349    limit_proto = termination_proto.limit
 350    if reason_proto == result_pb2.TERMINATION_REASON_UNSPECIFIED:
 351        raise ValueError("Termination reason should not be UNSPECIFIED")
 352    reason_is_limit = (
 353        reason_proto == result_pb2.TERMINATION_REASON_NO_SOLUTION_FOUND
 354    ) or (reason_proto == result_pb2.TERMINATION_REASON_FEASIBLE)
 355    limit_set = limit_proto != result_pb2.LIMIT_UNSPECIFIED
 356    if reason_is_limit != limit_set:
 357        raise ValueError(
 358            f"Termination limit (={limit_proto})) should take value other than "
 359            f"UNSPECIFIED if and only if termination reason (={reason_proto}) is "
 360            "FEASIBLE or NO_SOLUTION_FOUND"
 361        )
 362    termination = Termination()
 363    termination.reason = TerminationReason(reason_proto)
 364    termination.limit = Limit(limit_proto) if limit_set else None
 365    termination.detail = termination_proto.detail
 366    termination.problem_status = parse_problem_status(termination_proto.problem_status)
 367    termination.objective_bounds = parse_objective_bounds(
 368        termination_proto.objective_bounds
 369    )
 370    return termination
 371
 372
 373@dataclasses.dataclass
 374class SolveResult:
 375    """The result of solving an optimization problem defined by a Model.
 376
 377    We attempt to return as much solution information (primal_solutions,
 378    primal_rays, dual_solutions, dual_rays) as each underlying solver will provide
 379    given its return status. Differences in the underlying solvers result in a
 380    weak contract on what fields will be populated for a given termination
 381    reason. This is discussed in detail in termination_reasons.md, and the most
 382    important points are summarized below:
 383      * When the termination reason is optimal, there will be at least one primal
 384        solution provided that will be feasible up to the underlying solver's
 385        tolerances.
 386      * Dual solutions are only given for convex optimization problems (e.g.
 387        linear programs, not integer programs).
 388      * A basis is only given for linear programs when solved by the simplex
 389        method (e.g., not with PDLP).
 390      * Solvers have widely varying support for returning primal and dual rays.
 391        E.g. a termination_reason of unbounded does not ensure that a feasible
 392        solution or a primal ray is returned, check termination_reasons.md for
 393        solver specific guarantees if this is needed. Further, many solvers will
 394        provide the ray but not the feasible solution when returning an unbounded
 395        status.
 396      * When the termination reason is that a limit was reached or that the result
 397        is imprecise, a solution may or may not be present. Further, for some
 398        solvers (generally, convex optimization solvers, not MIP solvers), the
 399        primal or dual solution may not be feasible.
 400
 401    Solver specific output is also returned for some solvers (and only information
 402    for the solver used will be populated).
 403
 404    Attributes:
 405      termination: The reason the solver stopped.
 406      solve_stats: Statistics on the solve process, e.g. running time, iterations.
 407      solutions: Lexicographically by primal feasibility status, dual feasibility
 408        status, (basic dual feasibility for simplex solvers), primal objective
 409        value and dual objective value.
 410      primal_rays: Directions of unbounded primal improvement, or equivalently,
 411        dual infeasibility certificates. Typically provided for terminal reasons
 412        UNBOUNDED and DUAL_INFEASIBLE.
 413      dual_rays: Directions of unbounded dual improvement, or equivalently, primal
 414        infeasibility certificates. Typically provided for termination reason
 415        INFEASIBLE.
 416      gscip_specific_output: statistics returned by the gSCIP solver, if used.
 417      osqp_specific_output: statistics returned by the OSQP solver, if used.
 418      pdlp_specific_output: statistics returned by the PDLP solver, if used.
 419    """
 420
 421    termination: Termination = dataclasses.field(default_factory=Termination)
 422    solve_stats: SolveStats = dataclasses.field(default_factory=SolveStats)
 423    solutions: List[solution.Solution] = dataclasses.field(default_factory=list)
 424    primal_rays: List[solution.PrimalRay] = dataclasses.field(default_factory=list)
 425    dual_rays: List[solution.DualRay] = dataclasses.field(default_factory=list)
 426    # At most one of the below will be set
 427    gscip_specific_output: Optional[gscip_pb2.GScipOutput] = None
 428    osqp_specific_output: Optional[osqp_pb2.OsqpOutput] = None
 429    pdlp_specific_output: Optional[result_pb2.SolveResultProto.PdlpOutput] = None
 430
 431    def solve_time(self) -> datetime.timedelta:
 432        """Shortcut for SolveResult.solve_stats.solve_time."""
 433        return self.solve_stats.solve_time
 434
 435    def primal_bound(self) -> float:
 436        """Returns a primal bound on the optimal objective value as described in ObjectiveBounds.
 437
 438        Will return a valid (possibly infinite) bound even if no primal feasible
 439        solutions are available.
 440        """
 441        return self.termination.objective_bounds.primal_bound
 442
 443    def dual_bound(self) -> float:
 444        """Returns a dual bound on the optimal objective value as described in ObjectiveBounds.
 445
 446        Will return a valid (possibly infinite) bound even if no dual feasible
 447        solutions are available.
 448        """
 449        return self.termination.objective_bounds.dual_bound
 450
 451    def has_primal_feasible_solution(self) -> bool:
 452        """Indicates if at least one primal feasible solution is available.
 453
 454        When termination.reason is TerminationReason.OPTIMAL or
 455        TerminationReason.FEASIBLE, this is guaranteed to be true and need not be
 456        checked.
 457
 458        Returns:
 459          True if there is at least one primal feasible solution is available,
 460          False, otherwise.
 461        """
 462        if not self.solutions:
 463            return False
 464        sol = self.solutions[0]
 465        return (
 466            sol.primal_solution is not None
 467            and sol.primal_solution.feasibility_status
 468            == solution.SolutionStatus.FEASIBLE
 469        )
 470
 471    def objective_value(self) -> float:
 472        """Returns the objective value of the best primal feasible solution.
 473
 474        An error will be raised if there are no primal feasible solutions.
 475        primal_bound() above is guaranteed to be at least as good (larger or equal
 476        for max problems and smaller or equal for min problems) as objective_value()
 477        and will never raise an error, so it may be preferable in some cases. Note
 478        that primal_bound() could be better than objective_value() even for optimal
 479        terminations, but on such optimal termination, both should satisfy the
 480        optimality tolerances.
 481
 482         Returns:
 483           The objective value of the best primal feasible solution.
 484
 485         Raises:
 486           ValueError: There are no primal feasible solutions.
 487        """
 488        if not self.has_primal_feasible_solution():
 489            raise ValueError("No primal feasible solution available.")
 490        sol = self.solutions[0]
 491        assert sol.primal_solution is not None
 492        return sol.primal_solution.objective_value
 493
 494    def best_objective_bound(self) -> float:
 495        """Returns a bound on the best possible objective value.
 496
 497        best_objective_bound() is always equal to dual_bound(), so they can be
 498        used interchangeably.
 499        """
 500        return self.termination.objective_bounds.dual_bound
 501
 502    @overload
 503    def variable_values(
 504        self, variables: None = ...
 505    ) -> Dict[variables_mod.Variable, float]: ...
 506
 507    @overload
 508    def variable_values(self, variables: variables_mod.Variable) -> float: ...
 509
 510    @overload
 511    def variable_values(
 512        self, variables: Iterable[variables_mod.Variable]
 513    ) -> List[float]: ...
 514
 515    def variable_values(self, variables=None):
 516        """The variable values from the best primal feasible solution.
 517
 518        An error will be raised if there are no primal feasible solutions.
 519
 520        Args:
 521          variables: an optional Variable or iterator of Variables indicating what
 522            variable values to return. If not provided, variable_values returns a
 523            dictionary with all the variable values for all variables.
 524
 525        Returns:
 526          The variable values from the best primal feasible solution.
 527
 528        Raises:
 529          ValueError: There are no primal feasible solutions.
 530          TypeError: Argument is not None, a Variable or an iterable of Variables.
 531          KeyError: Variable values requested for an invalid variable (e.g. is not a
 532            Variable or is a variable for another model).
 533        """
 534        if not self.has_primal_feasible_solution():
 535            raise ValueError("No primal feasible solution available.")
 536        sol = self.solutions[0]
 537        assert sol.primal_solution is not None
 538        if variables is None:
 539            return sol.primal_solution.variable_values
 540        if isinstance(variables, variables_mod.Variable):
 541            return sol.primal_solution.variable_values[variables]
 542        if isinstance(variables, Iterable):
 543            return [sol.primal_solution.variable_values[v] for v in variables]
 544        raise TypeError(
 545            "unsupported type in argument for "
 546            f"variable_values: {type(variables).__name__!r}"
 547        )
 548
 549    def bounded(self) -> bool:
 550        """Returns true only if the problem has been shown to be feasible and bounded."""
 551        return (
 552            self.termination.problem_status.primal_status == FeasibilityStatus.FEASIBLE
 553            and self.termination.problem_status.dual_status
 554            == FeasibilityStatus.FEASIBLE
 555        )
 556
 557    def has_ray(self) -> bool:
 558        """Indicates if at least one primal ray is available.
 559
 560        This is NOT guaranteed to be true when termination.reason is
 561        TerminationReason.kUnbounded or TerminationReason.kInfeasibleOrUnbounded.
 562
 563        Returns:
 564          True if at least one primal ray is available.
 565        """
 566        return bool(self.primal_rays)
 567
 568    @overload
 569    def ray_variable_values(
 570        self, variables: None = ...
 571    ) -> Dict[variables_mod.Variable, float]: ...
 572
 573    @overload
 574    def ray_variable_values(self, variables: variables_mod.Variable) -> float: ...
 575
 576    @overload
 577    def ray_variable_values(
 578        self, variables: Iterable[variables_mod.Variable]
 579    ) -> List[float]: ...
 580
 581    def ray_variable_values(self, variables=None):
 582        """The variable values from the first primal ray.
 583
 584        An error will be raised if there are no primal rays.
 585
 586        Args:
 587          variables: an optional Variable or iterator of Variables indicating what
 588            variable values to return. If not provided, variable_values() returns a
 589            dictionary with the variable values for all variables.
 590
 591        Returns:
 592          The variable values from the first primal ray.
 593
 594        Raises:
 595          ValueError: There are no primal rays.
 596          TypeError: Argument is not None, a Variable or an iterable of Variables.
 597          KeyError: Variable values requested for an invalid variable (e.g. is not a
 598            Variable or is a variable for another model).
 599        """
 600        if not self.has_ray():
 601            raise ValueError("No primal ray available.")
 602        if variables is None:
 603            return self.primal_rays[0].variable_values
 604        if isinstance(variables, variables_mod.Variable):
 605            return self.primal_rays[0].variable_values[variables]
 606        if isinstance(variables, Iterable):
 607            return [self.primal_rays[0].variable_values[v] for v in variables]
 608        raise TypeError(
 609            "unsupported type in argument for "
 610            f"ray_variable_values: {type(variables).__name__!r}"
 611        )
 612
 613    def has_dual_feasible_solution(self) -> bool:
 614        """Indicates if the best solution has an associated dual feasible solution.
 615
 616        This is NOT guaranteed to be true when termination.reason is
 617        TerminationReason.Optimal. It also may be true even when the best solution
 618        does not have an associated primal feasible solution.
 619
 620        Returns:
 621          True if the best solution has an associated dual feasible solution.
 622        """
 623        if not self.solutions:
 624            return False
 625        sol = self.solutions[0]
 626        return (
 627            sol.dual_solution is not None
 628            and sol.dual_solution.feasibility_status == solution.SolutionStatus.FEASIBLE
 629        )
 630
 631    @overload
 632    def dual_values(
 633        self, linear_constraints: None = ...
 634    ) -> Dict[linear_constraints_mod.LinearConstraint, float]: ...
 635
 636    @overload
 637    def dual_values(
 638        self, linear_constraints: linear_constraints_mod.LinearConstraint
 639    ) -> float: ...
 640
 641    @overload
 642    def dual_values(
 643        self,
 644        linear_constraints: Iterable[linear_constraints_mod.LinearConstraint],
 645    ) -> List[float]: ...
 646
 647    def dual_values(self, linear_constraints=None):
 648        """The dual values associated to the best solution.
 649
 650        If there is at least one primal feasible solution, this corresponds to the
 651        dual values associated to the best primal feasible solution. An error will
 652        be raised if the best solution does not have an associated dual feasible
 653        solution.
 654
 655        Args:
 656          linear_constraints: an optional LinearConstraint or iterator of
 657            LinearConstraint indicating what dual values to return. If not provided,
 658            dual_values() returns a dictionary with the dual values for all linear
 659            constraints.
 660
 661        Returns:
 662          The dual values associated to the best solution.
 663
 664        Raises:
 665          ValueError: The best solution does not have an associated dual feasible
 666            solution.
 667          TypeError: Argument is not None, a LinearConstraint or an iterable of
 668            LinearConstraint.
 669          KeyError: LinearConstraint values requested for an invalid
 670            linear constraint (e.g. is not a LinearConstraint or is a linear
 671            constraint for another model).
 672        """
 673        if not self.has_dual_feasible_solution():
 674            raise ValueError(_NO_DUAL_SOLUTION_ERROR)
 675        sol = self.solutions[0]
 676        assert sol.dual_solution is not None
 677        if linear_constraints is None:
 678            return sol.dual_solution.dual_values
 679        if isinstance(linear_constraints, linear_constraints_mod.LinearConstraint):
 680            return sol.dual_solution.dual_values[linear_constraints]
 681        if isinstance(linear_constraints, Iterable):
 682            return [sol.dual_solution.dual_values[c] for c in linear_constraints]
 683        raise TypeError(
 684            "unsupported type in argument for "
 685            f"dual_values: {type(linear_constraints).__name__!r}"
 686        )
 687
 688    @overload
 689    def reduced_costs(
 690        self, variables: None = ...
 691    ) -> Dict[variables_mod.Variable, float]: ...
 692
 693    @overload
 694    def reduced_costs(self, variables: variables_mod.Variable) -> float: ...
 695
 696    @overload
 697    def reduced_costs(
 698        self, variables: Iterable[variables_mod.Variable]
 699    ) -> List[float]: ...
 700
 701    def reduced_costs(self, variables=None):
 702        """The reduced costs associated to the best solution.
 703
 704        If there is at least one primal feasible solution, this corresponds to the
 705        reduced costs associated to the best primal feasible solution. An error will
 706        be raised if the best solution does not have an associated dual feasible
 707        solution.
 708
 709        Args:
 710          variables: an optional Variable or iterator of Variables indicating what
 711            reduced costs to return. If not provided, reduced_costs() returns a
 712            dictionary with the reduced costs for all variables.
 713
 714        Returns:
 715          The reduced costs associated to the best solution.
 716
 717        Raises:
 718          ValueError: The best solution does not have an associated dual feasible
 719            solution.
 720          TypeError: Argument is not None, a Variable or an iterable of Variables.
 721          KeyError: Variable values requested for an invalid variable (e.g. is not a
 722            Variable or is a variable for another model).
 723        """
 724        if not self.has_dual_feasible_solution():
 725            raise ValueError(_NO_DUAL_SOLUTION_ERROR)
 726        sol = self.solutions[0]
 727        assert sol.dual_solution is not None
 728        if variables is None:
 729            return sol.dual_solution.reduced_costs
 730        if isinstance(variables, variables_mod.Variable):
 731            return sol.dual_solution.reduced_costs[variables]
 732        if isinstance(variables, Iterable):
 733            return [sol.dual_solution.reduced_costs[v] for v in variables]
 734        raise TypeError(
 735            "unsupported type in argument for "
 736            f"reduced_costs: {type(variables).__name__!r}"
 737        )
 738
 739    def has_dual_ray(self) -> bool:
 740        """Indicates if at least one dual ray is available.
 741
 742        This is NOT guaranteed to be true when termination.reason is
 743        TerminationReason.Infeasible.
 744
 745        Returns:
 746          True if at least one dual ray is available.
 747        """
 748        return bool(self.dual_rays)
 749
 750    @overload
 751    def ray_dual_values(
 752        self, linear_constraints: None = ...
 753    ) -> Dict[linear_constraints_mod.LinearConstraint, float]: ...
 754
 755    @overload
 756    def ray_dual_values(
 757        self, linear_constraints: linear_constraints_mod.LinearConstraint
 758    ) -> float: ...
 759
 760    @overload
 761    def ray_dual_values(
 762        self,
 763        linear_constraints: Iterable[linear_constraints_mod.LinearConstraint],
 764    ) -> List[float]: ...
 765
 766    def ray_dual_values(self, linear_constraints=None):
 767        """The dual values from the first dual ray.
 768
 769        An error will be raised if there are no dual rays.
 770
 771        Args:
 772          linear_constraints: an optional LinearConstraint or iterator of
 773            LinearConstraint indicating what dual values to return. If not provided,
 774            ray_dual_values() returns a dictionary with the dual values for all
 775            linear constraints.
 776
 777        Returns:
 778          The dual values from the first dual ray.
 779
 780        Raises:
 781          ValueError: There are no dual rays.
 782          TypeError: Argument is not None, a LinearConstraint or an iterable of
 783            LinearConstraint.
 784          KeyError: LinearConstraint values requested for an invalid
 785            linear constraint (e.g. is not a LinearConstraint or is a linear
 786            constraint for another model).
 787        """
 788        if not self.has_dual_ray():
 789            raise ValueError("No dual ray available.")
 790        ray = self.dual_rays[0]
 791        if linear_constraints is None:
 792            return ray.dual_values
 793        if isinstance(linear_constraints, linear_constraints_mod.LinearConstraint):
 794            return ray.dual_values[linear_constraints]
 795        if isinstance(linear_constraints, Iterable):
 796            return [ray.dual_values[v] for v in linear_constraints]
 797        raise TypeError(
 798            "unsupported type in argument for "
 799            f"ray_dual_values: {type(linear_constraints).__name__!r}"
 800        )
 801
 802    @overload
 803    def ray_reduced_costs(
 804        self, variables: None = ...
 805    ) -> Dict[variables_mod.Variable, float]: ...
 806
 807    @overload
 808    def ray_reduced_costs(self, variables: variables_mod.Variable) -> float: ...
 809
 810    @overload
 811    def ray_reduced_costs(
 812        self, variables: Iterable[variables_mod.Variable]
 813    ) -> List[float]: ...
 814
 815    def ray_reduced_costs(self, variables=None):
 816        """The reduced costs from the first dual ray.
 817
 818        An error will be raised if there are no dual rays.
 819
 820        Args:
 821          variables: an optional Variable or iterator of Variables indicating what
 822            reduced costs to return. If not provided, ray_reduced_costs() returns a
 823            dictionary with the reduced costs for all variables.
 824
 825        Returns:
 826          The reduced costs from the first dual ray.
 827
 828        Raises:
 829          ValueError: There are no dual rays.
 830          TypeError: Argument is not None, a Variable or an iterable of Variables.
 831          KeyError: Variable values requested for an invalid variable (e.g. is not a
 832            Variable or is a variable for another model).
 833        """
 834        if not self.has_dual_ray():
 835            raise ValueError("No dual ray available.")
 836        ray = self.dual_rays[0]
 837        if variables is None:
 838            return ray.reduced_costs
 839        if isinstance(variables, variables_mod.Variable):
 840            return ray.reduced_costs[variables]
 841        if isinstance(variables, Iterable):
 842            return [ray.reduced_costs[v] for v in variables]
 843        raise TypeError(
 844            "unsupported type in argument for "
 845            f"ray_reduced_costs: {type(variables).__name__!r}"
 846        )
 847
 848    def has_basis(self) -> bool:
 849        """Indicates if the best solution has an associated basis.
 850
 851        This is NOT guaranteed to be true when termination.reason is
 852        TerminationReason.Optimal. It also may be true even when the best solution
 853        does not have an associated primal feasible solution.
 854
 855        Returns:
 856          True if the best solution has an associated basis.
 857        """
 858        if not self.solutions:
 859            return False
 860        return self.solutions[0].basis is not None
 861
 862    @overload
 863    def constraint_status(
 864        self, linear_constraints: None = ...
 865    ) -> Dict[linear_constraints_mod.LinearConstraint, solution.BasisStatus]: ...
 866
 867    @overload
 868    def constraint_status(
 869        self, linear_constraints: linear_constraints_mod.LinearConstraint
 870    ) -> solution.BasisStatus: ...
 871
 872    @overload
 873    def constraint_status(
 874        self,
 875        linear_constraints: Iterable[linear_constraints_mod.LinearConstraint],
 876    ) -> List[solution.BasisStatus]: ...
 877
 878    def constraint_status(self, linear_constraints=None):
 879        """The constraint basis status associated to the best solution.
 880
 881        If there is at least one primal feasible solution, this corresponds to the
 882        basis associated to the best primal feasible solution. An error will
 883        be raised if the best solution does not have an associated basis.
 884
 885
 886        Args:
 887          linear_constraints: an optional LinearConstraint or iterator of
 888            LinearConstraint indicating what constraint statuses to return. If not
 889            provided, returns a dictionary with the constraint statuses for all
 890            linear constraints.
 891
 892        Returns:
 893          The constraint basis status associated to the best solution.
 894
 895        Raises:
 896          ValueError: The best solution does not have an associated basis.
 897          TypeError: Argument is not None, a LinearConstraint or an iterable of
 898            LinearConstraint.
 899          KeyError: LinearConstraint values requested for an invalid
 900            linear constraint (e.g. is not a LinearConstraint or is a linear
 901            constraint for another model).
 902        """
 903        if not self.has_basis():
 904            raise ValueError(_NO_BASIS_ERROR)
 905        basis = self.solutions[0].basis
 906        assert basis is not None
 907        if linear_constraints is None:
 908            return basis.constraint_status
 909        if isinstance(linear_constraints, linear_constraints_mod.LinearConstraint):
 910            return basis.constraint_status[linear_constraints]
 911        if isinstance(linear_constraints, Iterable):
 912            return [basis.constraint_status[c] for c in linear_constraints]
 913        raise TypeError(
 914            "unsupported type in argument for "
 915            f"constraint_status: {type(linear_constraints).__name__!r}"
 916        )
 917
 918    @overload
 919    def variable_status(
 920        self, variables: None = ...
 921    ) -> Dict[variables_mod.Variable, solution.BasisStatus]: ...
 922
 923    @overload
 924    def variable_status(
 925        self, variables: variables_mod.Variable
 926    ) -> solution.BasisStatus: ...
 927
 928    @overload
 929    def variable_status(
 930        self, variables: Iterable[variables_mod.Variable]
 931    ) -> List[solution.BasisStatus]: ...
 932
 933    def variable_status(self, variables=None):
 934        """The variable basis status associated to the best solution.
 935
 936        If there is at least one primal feasible solution, this corresponds to the
 937        basis associated to the best primal feasible solution. An error will
 938        be raised if the best solution does not have an associated basis.
 939
 940        Args:
 941          variables: an optional Variable or iterator of Variables indicating what
 942            reduced costs to return. If not provided, variable_status() returns a
 943            dictionary with the reduced costs for all variables.
 944
 945        Returns:
 946          The variable basis status associated to the best solution.
 947
 948        Raises:
 949          ValueError: The best solution does not have an associated basis.
 950          TypeError: Argument is not None, a Variable or an iterable of Variables.
 951          KeyError: Variable values requested for an invalid variable (e.g. is not a
 952            Variable or is a variable for another model).
 953        """
 954        if not self.has_basis():
 955            raise ValueError(_NO_BASIS_ERROR)
 956        basis = self.solutions[0].basis
 957        assert basis is not None
 958        if variables is None:
 959            return basis.variable_status
 960        if isinstance(variables, variables_mod.Variable):
 961            return basis.variable_status[variables]
 962        if isinstance(variables, Iterable):
 963            return [basis.variable_status[v] for v in variables]
 964        raise TypeError(
 965            "unsupported type in argument for "
 966            f"variable_status: {type(variables).__name__!r}"
 967        )
 968
 969    def to_proto(self) -> result_pb2.SolveResultProto:
 970        """Returns an equivalent protocol buffer for a SolveResult."""
 971        proto = result_pb2.SolveResultProto(
 972            termination=self.termination.to_proto(),
 973            solutions=[s.to_proto() for s in self.solutions],
 974            primal_rays=[r.to_proto() for r in self.primal_rays],
 975            dual_rays=[r.to_proto() for r in self.dual_rays],
 976            solve_stats=self.solve_stats.to_proto(),
 977        )
 978
 979        # Ensure that at most solver has solver specific output.
 980        existing_solver_specific_output = None
 981
 982        def has_solver_specific_output(solver_name: str) -> None:
 983            nonlocal existing_solver_specific_output
 984            if existing_solver_specific_output is not None:
 985                raise ValueError(
 986                    "found solver specific output for both"
 987                    f" {existing_solver_specific_output} and {solver_name}"
 988                )
 989            existing_solver_specific_output = solver_name
 990
 991        if self.gscip_specific_output is not None:
 992            has_solver_specific_output("gscip")
 993            proto.gscip_output.CopyFrom(self.gscip_specific_output)
 994        if self.osqp_specific_output is not None:
 995            has_solver_specific_output("osqp")
 996            proto.osqp_output.CopyFrom(self.osqp_specific_output)
 997        if self.pdlp_specific_output is not None:
 998            has_solver_specific_output("pdlp")
 999            proto.pdlp_output.CopyFrom(self.pdlp_specific_output)
1000        return proto
1001
1002
1003def _get_problem_status(
1004    result_proto: result_pb2.SolveResultProto,
1005) -> result_pb2.ProblemStatusProto:
1006    if result_proto.termination.HasField("problem_status"):
1007        return result_proto.termination.problem_status
1008    return result_proto.solve_stats.problem_status
1009
1010
1011def _get_objective_bounds(
1012    result_proto: result_pb2.SolveResultProto,
1013) -> result_pb2.ObjectiveBoundsProto:
1014    if result_proto.termination.HasField("objective_bounds"):
1015        return result_proto.termination.objective_bounds
1016    return result_pb2.ObjectiveBoundsProto(
1017        primal_bound=result_proto.solve_stats.best_primal_bound,
1018        dual_bound=result_proto.solve_stats.best_dual_bound,
1019    )
1020
1021
1022def _upgrade_termination(
1023    result_proto: result_pb2.SolveResultProto,
1024) -> result_pb2.TerminationProto:
1025    return result_pb2.TerminationProto(
1026        reason=result_proto.termination.reason,
1027        limit=result_proto.termination.limit,
1028        detail=result_proto.termination.detail,
1029        problem_status=_get_problem_status(result_proto),
1030        objective_bounds=_get_objective_bounds(result_proto),
1031    )
1032
1033
1034def parse_solve_result(
1035    proto: result_pb2.SolveResultProto,
1036    mod: model.Model,
1037    *,
1038    validate: bool = True,
1039) -> SolveResult:
1040    """Returns a SolveResult equivalent to the input proto."""
1041    result = SolveResult()
1042    # TODO(b/290091715): change to parse_termination(proto.termination)
1043    # once solve_stats proto no longer has best_primal/dual_bound/problem_status
1044    # and problem_status/objective_bounds are guaranteed to be present in
1045    # termination proto.
1046    result.termination = parse_termination(_upgrade_termination(proto))
1047    result.solve_stats = parse_solve_stats(proto.solve_stats)
1048    for solution_proto in proto.solutions:
1049        result.solutions.append(
1050            solution.parse_solution(solution_proto, mod, validate=validate)
1051        )
1052    for primal_ray_proto in proto.primal_rays:
1053        result.primal_rays.append(
1054            solution.parse_primal_ray(primal_ray_proto, mod, validate=validate)
1055        )
1056    for dual_ray_proto in proto.dual_rays:
1057        result.dual_rays.append(
1058            solution.parse_dual_ray(dual_ray_proto, mod, validate=validate)
1059        )
1060    if proto.HasField("gscip_output"):
1061        result.gscip_specific_output = proto.gscip_output
1062    elif proto.HasField("osqp_output"):
1063        result.osqp_specific_output = proto.osqp_output
1064    elif proto.HasField("pdlp_output"):
1065        result.pdlp_specific_output = proto.pdlp_output
1066    return result