ortools.math_opt.python.result

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