ortools.math_opt.python.result

  1# Copyright 2010-2024 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
329def parse_termination(
330    termination_proto: result_pb2.TerminationProto,
331) -> Termination:
332    """Returns a Termination that is equivalent to termination_proto."""
333    reason_proto = termination_proto.reason
334    limit_proto = termination_proto.limit
335    if reason_proto == result_pb2.TERMINATION_REASON_UNSPECIFIED:
336        raise ValueError("Termination reason should not be UNSPECIFIED")
337    reason_is_limit = (
338        reason_proto == result_pb2.TERMINATION_REASON_NO_SOLUTION_FOUND
339    ) or (reason_proto == result_pb2.TERMINATION_REASON_FEASIBLE)
340    limit_set = limit_proto != result_pb2.LIMIT_UNSPECIFIED
341    if reason_is_limit != limit_set:
342        raise ValueError(
343            f"Termination limit (={limit_proto})) should take value other than "
344            f"UNSPECIFIED if and only if termination reason (={reason_proto}) is "
345            "FEASIBLE or NO_SOLUTION_FOUND"
346        )
347    termination = Termination()
348    termination.reason = TerminationReason(reason_proto)
349    termination.limit = Limit(limit_proto) if limit_set else None
350    termination.detail = termination_proto.detail
351    termination.problem_status = parse_problem_status(termination_proto.problem_status)
352    termination.objective_bounds = parse_objective_bounds(
353        termination_proto.objective_bounds
354    )
355    return termination
356
357
358@dataclasses.dataclass
359class SolveResult:
360    """The result of solving an optimization problem defined by a Model.
361
362    We attempt to return as much solution information (primal_solutions,
363    primal_rays, dual_solutions, dual_rays) as each underlying solver will provide
364    given its return status. Differences in the underlying solvers result in a
365    weak contract on what fields will be populated for a given termination
366    reason. This is discussed in detail in termination_reasons.md, and the most
367    important points are summarized below:
368      * When the termination reason is optimal, there will be at least one primal
369        solution provided that will be feasible up to the underlying solver's
370        tolerances.
371      * Dual solutions are only given for convex optimization problems (e.g.
372        linear programs, not integer programs).
373      * A basis is only given for linear programs when solved by the simplex
374        method (e.g., not with PDLP).
375      * Solvers have widely varying support for returning primal and dual rays.
376        E.g. a termination_reason of unbounded does not ensure that a feasible
377        solution or a primal ray is returned, check termination_reasons.md for
378        solver specific guarantees if this is needed. Further, many solvers will
379        provide the ray but not the feasible solution when returning an unbounded
380        status.
381      * When the termination reason is that a limit was reached or that the result
382        is imprecise, a solution may or may not be present. Further, for some
383        solvers (generally, convex optimization solvers, not MIP solvers), the
384        primal or dual solution may not be feasible.
385
386    Solver specific output is also returned for some solvers (and only information
387    for the solver used will be populated).
388
389    Attributes:
390      termination: The reason the solver stopped.
391      solve_stats: Statistics on the solve process, e.g. running time, iterations.
392      solutions: Lexicographically by primal feasibility status, dual feasibility
393        status, (basic dual feasibility for simplex solvers), primal objective
394        value and dual objective value.
395      primal_rays: Directions of unbounded primal improvement, or equivalently,
396        dual infeasibility certificates. Typically provided for terminal reasons
397        UNBOUNDED and DUAL_INFEASIBLE.
398      dual_rays: Directions of unbounded dual improvement, or equivalently, primal
399        infeasibility certificates. Typically provided for termination reason
400        INFEASIBLE.
401      gscip_specific_output: statistics returned by the gSCIP solver, if used.
402      osqp_specific_output: statistics returned by the OSQP solver, if used.
403      pdlp_specific_output: statistics returned by the PDLP solver, if used.
404    """
405
406    termination: Termination = dataclasses.field(default_factory=Termination)
407    solve_stats: SolveStats = dataclasses.field(default_factory=SolveStats)
408    solutions: List[solution.Solution] = dataclasses.field(default_factory=list)
409    primal_rays: List[solution.PrimalRay] = dataclasses.field(default_factory=list)
410    dual_rays: List[solution.DualRay] = dataclasses.field(default_factory=list)
411    # At most one of the below will be set
412    gscip_specific_output: Optional[gscip_pb2.GScipOutput] = None
413    osqp_specific_output: Optional[osqp_pb2.OsqpOutput] = None
414    pdlp_specific_output: Optional[result_pb2.SolveResultProto.PdlpOutput] = None
415
416    def solve_time(self) -> datetime.timedelta:
417        """Shortcut for SolveResult.solve_stats.solve_time."""
418        return self.solve_stats.solve_time
419
420    def primal_bound(self) -> float:
421        """Returns a primal bound on the optimal objective value as described in ObjectiveBounds.
422
423        Will return a valid (possibly infinite) bound even if no primal feasible
424        solutions are available.
425        """
426        return self.termination.objective_bounds.primal_bound
427
428    def dual_bound(self) -> float:
429        """Returns a dual bound on the optimal objective value as described in ObjectiveBounds.
430
431        Will return a valid (possibly infinite) bound even if no dual feasible
432        solutions are available.
433        """
434        return self.termination.objective_bounds.dual_bound
435
436    def has_primal_feasible_solution(self) -> bool:
437        """Indicates if at least one primal feasible solution is available.
438
439        When termination.reason is TerminationReason.OPTIMAL or
440        TerminationReason.FEASIBLE, this is guaranteed to be true and need not be
441        checked.
442
443        Returns:
444          True if there is at least one primal feasible solution is available,
445          False, otherwise.
446        """
447        if not self.solutions:
448            return False
449        return (
450            self.solutions[0].primal_solution is not None
451            and self.solutions[0].primal_solution.feasibility_status
452            == solution.SolutionStatus.FEASIBLE
453        )
454
455    def objective_value(self) -> float:
456        """Returns the objective value of the best primal feasible solution.
457
458        An error will be raised if there are no primal feasible solutions.
459        primal_bound() above is guaranteed to be at least as good (larger or equal
460        for max problems and smaller or equal for min problems) as objective_value()
461        and will never raise an error, so it may be preferable in some cases. Note
462        that primal_bound() could be better than objective_value() even for optimal
463        terminations, but on such optimal termination, both should satisfy the
464        optimality tolerances.
465
466         Returns:
467           The objective value of the best primal feasible solution.
468
469         Raises:
470           ValueError: There are no primal feasible solutions.
471        """
472        if not self.has_primal_feasible_solution():
473            raise ValueError("No primal feasible solution available.")
474        assert self.solutions[0].primal_solution is not None
475        return self.solutions[0].primal_solution.objective_value
476
477    def best_objective_bound(self) -> float:
478        """Returns a bound on the best possible objective value.
479
480        best_objective_bound() is always equal to dual_bound(), so they can be
481        used interchangeably.
482        """
483        return self.termination.objective_bounds.dual_bound
484
485    @overload
486    def variable_values(self, variables: None = ...) -> Dict[model.Variable, float]: ...
487
488    @overload
489    def variable_values(self, variables: model.Variable) -> float: ...
490
491    @overload
492    def variable_values(self, variables: Iterable[model.Variable]) -> List[float]: ...
493
494    def variable_values(self, variables=None):
495        """The variable values from the best primal feasible solution.
496
497        An error will be raised if there are no primal feasible solutions.
498
499        Args:
500          variables: an optional Variable or iterator of Variables indicating what
501            variable values to return. If not provided, variable_values returns a
502            dictionary with all the variable values for all variables.
503
504        Returns:
505          The variable values from the best primal feasible solution.
506
507        Raises:
508          ValueError: There are no primal feasible solutions.
509          TypeError: Argument is not None, a Variable or an iterable of Variables.
510          KeyError: Variable values requested for an invalid variable (e.g. is not a
511            Variable or is a variable for another model).
512        """
513        if not self.has_primal_feasible_solution():
514            raise ValueError("No primal feasible solution available.")
515        assert self.solutions[0].primal_solution is not None
516        if variables is None:
517            return self.solutions[0].primal_solution.variable_values
518        if isinstance(variables, model.Variable):
519            return self.solutions[0].primal_solution.variable_values[variables]
520        if isinstance(variables, Iterable):
521            return [
522                self.solutions[0].primal_solution.variable_values[v] for v in variables
523            ]
524        raise TypeError(
525            "unsupported type in argument for "
526            f"variable_values: {type(variables).__name__!r}"
527        )
528
529    def bounded(self) -> bool:
530        """Returns true only if the problem has been shown to be feasible and bounded."""
531        return (
532            self.termination.problem_status.primal_status == FeasibilityStatus.FEASIBLE
533            and self.termination.problem_status.dual_status
534            == FeasibilityStatus.FEASIBLE
535        )
536
537    def has_ray(self) -> bool:
538        """Indicates if at least one primal ray is available.
539
540        This is NOT guaranteed to be true when termination.reason is
541        TerminationReason.kUnbounded or TerminationReason.kInfeasibleOrUnbounded.
542
543        Returns:
544          True if at least one primal ray is available.
545        """
546        return bool(self.primal_rays)
547
548    @overload
549    def ray_variable_values(
550        self, variables: None = ...
551    ) -> Dict[model.Variable, float]: ...
552
553    @overload
554    def ray_variable_values(self, variables: model.Variable) -> float: ...
555
556    @overload
557    def ray_variable_values(
558        self, variables: Iterable[model.Variable]
559    ) -> List[float]: ...
560
561    def ray_variable_values(self, variables=None):
562        """The variable values from the first primal ray.
563
564        An error will be raised if there are no primal rays.
565
566        Args:
567          variables: an optional Variable or iterator of Variables indicating what
568            variable values to return. If not provided, variable_values() returns a
569            dictionary with the variable values for all variables.
570
571        Returns:
572          The variable values from the first primal ray.
573
574        Raises:
575          ValueError: There are no primal rays.
576          TypeError: Argument is not None, a Variable or an iterable of Variables.
577          KeyError: Variable values requested for an invalid variable (e.g. is not a
578            Variable or is a variable for another model).
579        """
580        if not self.has_ray():
581            raise ValueError("No primal ray available.")
582        if variables is None:
583            return self.primal_rays[0].variable_values
584        if isinstance(variables, model.Variable):
585            return self.primal_rays[0].variable_values[variables]
586        if isinstance(variables, Iterable):
587            return [self.primal_rays[0].variable_values[v] for v in variables]
588        raise TypeError(
589            "unsupported type in argument for "
590            f"ray_variable_values: {type(variables).__name__!r}"
591        )
592
593    def has_dual_feasible_solution(self) -> bool:
594        """Indicates if the best solution has an associated dual feasible solution.
595
596        This is NOT guaranteed to be true when termination.reason is
597        TerminationReason.Optimal. It also may be true even when the best solution
598        does not have an associated primal feasible solution.
599
600        Returns:
601          True if the best solution has an associated dual feasible solution.
602        """
603        if not self.solutions:
604            return False
605        return (
606            self.solutions[0].dual_solution is not None
607            and self.solutions[0].dual_solution.feasibility_status
608            == solution.SolutionStatus.FEASIBLE
609        )
610
611    @overload
612    def dual_values(
613        self, linear_constraints: None = ...
614    ) -> Dict[model.LinearConstraint, float]: ...
615
616    @overload
617    def dual_values(self, linear_constraints: model.LinearConstraint) -> float: ...
618
619    @overload
620    def dual_values(
621        self, linear_constraints: Iterable[model.LinearConstraint]
622    ) -> List[float]: ...
623
624    def dual_values(self, linear_constraints=None):
625        """The dual values associated to the best solution.
626
627        If there is at least one primal feasible solution, this corresponds to the
628        dual values associated to the best primal feasible solution. An error will
629        be raised if the best solution does not have an associated dual feasible
630        solution.
631
632        Args:
633          linear_constraints: an optional LinearConstraint or iterator of
634            LinearConstraint indicating what dual values to return. If not provided,
635            dual_values() returns a dictionary with the dual values for all linear
636            constraints.
637
638        Returns:
639          The dual values associated to the best solution.
640
641        Raises:
642          ValueError: The best solution does not have an associated dual feasible
643            solution.
644          TypeError: Argument is not None, a LinearConstraint or an iterable of
645            LinearConstraint.
646          KeyError: LinearConstraint values requested for an invalid
647            linear constraint (e.g. is not a LinearConstraint or is a linear
648            constraint for another model).
649        """
650        if not self.has_dual_feasible_solution():
651            raise ValueError(_NO_DUAL_SOLUTION_ERROR)
652        assert self.solutions[0].dual_solution is not None
653        if linear_constraints is None:
654            return self.solutions[0].dual_solution.dual_values
655        if isinstance(linear_constraints, model.LinearConstraint):
656            return self.solutions[0].dual_solution.dual_values[linear_constraints]
657        if isinstance(linear_constraints, Iterable):
658            return [
659                self.solutions[0].dual_solution.dual_values[c]
660                for c in linear_constraints
661            ]
662        raise TypeError(
663            "unsupported type in argument for "
664            f"dual_values: {type(linear_constraints).__name__!r}"
665        )
666
667    @overload
668    def reduced_costs(self, variables: None = ...) -> Dict[model.Variable, float]: ...
669
670    @overload
671    def reduced_costs(self, variables: model.Variable) -> float: ...
672
673    @overload
674    def reduced_costs(self, variables: Iterable[model.Variable]) -> List[float]: ...
675
676    def reduced_costs(self, variables=None):
677        """The reduced costs associated to the best solution.
678
679        If there is at least one primal feasible solution, this corresponds to the
680        reduced costs associated to the best primal feasible solution. An error will
681        be raised if the best solution does not have an associated dual feasible
682        solution.
683
684        Args:
685          variables: an optional Variable or iterator of Variables indicating what
686            reduced costs to return. If not provided, reduced_costs() returns a
687            dictionary with the reduced costs for all variables.
688
689        Returns:
690          The reduced costs associated to the best solution.
691
692        Raises:
693          ValueError: The best solution does not have an associated dual feasible
694            solution.
695          TypeError: Argument is not None, a Variable or an iterable of Variables.
696          KeyError: Variable values requested for an invalid variable (e.g. is not a
697            Variable or is a variable for another model).
698        """
699        if not self.has_dual_feasible_solution():
700            raise ValueError(_NO_DUAL_SOLUTION_ERROR)
701        assert self.solutions[0].dual_solution is not None
702        if variables is None:
703            return self.solutions[0].dual_solution.reduced_costs
704        if isinstance(variables, model.Variable):
705            return self.solutions[0].dual_solution.reduced_costs[variables]
706        if isinstance(variables, Iterable):
707            return [self.solutions[0].dual_solution.reduced_costs[v] for v in variables]
708        raise TypeError(
709            "unsupported type in argument for "
710            f"reduced_costs: {type(variables).__name__!r}"
711        )
712
713    def has_dual_ray(self) -> bool:
714        """Indicates if at least one dual ray is available.
715
716        This is NOT guaranteed to be true when termination.reason is
717        TerminationReason.Infeasible.
718
719        Returns:
720          True if at least one dual ray is available.
721        """
722        return bool(self.dual_rays)
723
724    @overload
725    def ray_dual_values(
726        self, linear_constraints: None = ...
727    ) -> Dict[model.LinearConstraint, float]: ...
728
729    @overload
730    def ray_dual_values(self, linear_constraints: model.LinearConstraint) -> float: ...
731
732    @overload
733    def ray_dual_values(
734        self, linear_constraints: Iterable[model.LinearConstraint]
735    ) -> List[float]: ...
736
737    def ray_dual_values(self, linear_constraints=None):
738        """The dual values from the first dual ray.
739
740        An error will be raised if there are no dual rays.
741
742        Args:
743          linear_constraints: an optional LinearConstraint or iterator of
744            LinearConstraint indicating what dual values to return. If not provided,
745            ray_dual_values() returns a dictionary with the dual values for all
746            linear constraints.
747
748        Returns:
749          The dual values from the first dual ray.
750
751        Raises:
752          ValueError: There are no dual rays.
753          TypeError: Argument is not None, a LinearConstraint or an iterable of
754            LinearConstraint.
755          KeyError: LinearConstraint values requested for an invalid
756            linear constraint (e.g. is not a LinearConstraint or is a linear
757            constraint for another model).
758        """
759        if not self.has_dual_ray():
760            raise ValueError("No dual ray available.")
761        if linear_constraints is None:
762            return self.dual_rays[0].dual_values
763        if isinstance(linear_constraints, model.LinearConstraint):
764            return self.dual_rays[0].dual_values[linear_constraints]
765        if isinstance(linear_constraints, Iterable):
766            return [self.dual_rays[0].dual_values[v] for v in linear_constraints]
767        raise TypeError(
768            "unsupported type in argument for "
769            f"ray_dual_values: {type(linear_constraints).__name__!r}"
770        )
771
772    @overload
773    def ray_reduced_costs(
774        self, variables: None = ...
775    ) -> Dict[model.Variable, float]: ...
776
777    @overload
778    def ray_reduced_costs(self, variables: model.Variable) -> float: ...
779
780    @overload
781    def ray_reduced_costs(self, variables: Iterable[model.Variable]) -> List[float]: ...
782
783    def ray_reduced_costs(self, variables=None):
784        """The reduced costs from the first dual ray.
785
786        An error will be raised if there are no dual rays.
787
788        Args:
789          variables: an optional Variable or iterator of Variables indicating what
790            reduced costs to return. If not provided, ray_reduced_costs() returns a
791            dictionary with the reduced costs for all variables.
792
793        Returns:
794          The reduced costs from the first dual ray.
795
796        Raises:
797          ValueError: There are no dual rays.
798          TypeError: Argument is not None, a Variable or an iterable of Variables.
799          KeyError: Variable values requested for an invalid variable (e.g. is not a
800            Variable or is a variable for another model).
801        """
802        if not self.has_dual_ray():
803            raise ValueError("No dual ray available.")
804        if variables is None:
805            return self.dual_rays[0].reduced_costs
806        if isinstance(variables, model.Variable):
807            return self.dual_rays[0].reduced_costs[variables]
808        if isinstance(variables, Iterable):
809            return [self.dual_rays[0].reduced_costs[v] for v in variables]
810        raise TypeError(
811            "unsupported type in argument for "
812            f"ray_reduced_costs: {type(variables).__name__!r}"
813        )
814
815    def has_basis(self) -> bool:
816        """Indicates if the best solution has an associated basis.
817
818        This is NOT guaranteed to be true when termination.reason is
819        TerminationReason.Optimal. It also may be true even when the best solution
820        does not have an associated primal feasible solution.
821
822        Returns:
823          True if the best solution has an associated basis.
824        """
825        if not self.solutions:
826            return False
827        return self.solutions[0].basis is not None
828
829    @overload
830    def constraint_status(
831        self, linear_constraints: None = ...
832    ) -> Dict[model.LinearConstraint, solution.BasisStatus]: ...
833
834    @overload
835    def constraint_status(
836        self, linear_constraints: model.LinearConstraint
837    ) -> solution.BasisStatus: ...
838
839    @overload
840    def constraint_status(
841        self, linear_constraints: Iterable[model.LinearConstraint]
842    ) -> List[solution.BasisStatus]: ...
843
844    def constraint_status(self, linear_constraints=None):
845        """The constraint basis status associated to the best solution.
846
847        If there is at least one primal feasible solution, this corresponds to the
848        basis associated to the best primal feasible solution. An error will
849        be raised if the best solution does not have an associated basis.
850
851
852        Args:
853          linear_constraints: an optional LinearConstraint or iterator of
854            LinearConstraint indicating what constraint statuses to return. If not
855            provided, returns a dictionary with the constraint statuses for all
856            linear constraints.
857
858        Returns:
859          The constraint basis status associated to the best solution.
860
861        Raises:
862          ValueError: The best solution does not have an associated basis.
863          TypeError: Argument is not None, a LinearConstraint or an iterable of
864            LinearConstraint.
865          KeyError: LinearConstraint values requested for an invalid
866            linear constraint (e.g. is not a LinearConstraint or is a linear
867            constraint for another model).
868        """
869        if not self.has_basis():
870            raise ValueError(_NO_BASIS_ERROR)
871        assert self.solutions[0].basis is not None
872        if linear_constraints is None:
873            return self.solutions[0].basis.constraint_status
874        if isinstance(linear_constraints, model.LinearConstraint):
875            return self.solutions[0].basis.constraint_status[linear_constraints]
876        if isinstance(linear_constraints, Iterable):
877            return [
878                self.solutions[0].basis.constraint_status[c] for c in linear_constraints
879            ]
880        raise TypeError(
881            "unsupported type in argument for "
882            f"constraint_status: {type(linear_constraints).__name__!r}"
883        )
884
885    @overload
886    def variable_status(
887        self, variables: None = ...
888    ) -> Dict[model.Variable, solution.BasisStatus]: ...
889
890    @overload
891    def variable_status(self, variables: model.Variable) -> solution.BasisStatus: ...
892
893    @overload
894    def variable_status(
895        self, variables: Iterable[model.Variable]
896    ) -> List[solution.BasisStatus]: ...
897
898    def variable_status(self, variables=None):
899        """The variable basis status associated to the best solution.
900
901        If there is at least one primal feasible solution, this corresponds to the
902        basis associated to the best primal feasible solution. An error will
903        be raised if the best solution does not have an associated basis.
904
905        Args:
906          variables: an optional Variable or iterator of Variables indicating what
907            reduced costs to return. If not provided, variable_status() returns a
908            dictionary with the reduced costs for all variables.
909
910        Returns:
911          The variable basis status associated to the best solution.
912
913        Raises:
914          ValueError: The best solution does not have an associated basis.
915          TypeError: Argument is not None, a Variable or an iterable of Variables.
916          KeyError: Variable values requested for an invalid variable (e.g. is not a
917            Variable or is a variable for another model).
918        """
919        if not self.has_basis():
920            raise ValueError(_NO_BASIS_ERROR)
921        assert self.solutions[0].basis is not None
922        if variables is None:
923            return self.solutions[0].basis.variable_status
924        if isinstance(variables, model.Variable):
925            return self.solutions[0].basis.variable_status[variables]
926        if isinstance(variables, Iterable):
927            return [self.solutions[0].basis.variable_status[v] for v in variables]
928        raise TypeError(
929            "unsupported type in argument for "
930            f"variable_status: {type(variables).__name__!r}"
931        )
932
933
934def _get_problem_status(
935    result_proto: result_pb2.SolveResultProto,
936) -> result_pb2.ProblemStatusProto:
937    if result_proto.termination.HasField("problem_status"):
938        return result_proto.termination.problem_status
939    return result_proto.solve_stats.problem_status
940
941
942def _get_objective_bounds(
943    result_proto: result_pb2.SolveResultProto,
944) -> result_pb2.ObjectiveBoundsProto:
945    if result_proto.termination.HasField("objective_bounds"):
946        return result_proto.termination.objective_bounds
947    return result_pb2.ObjectiveBoundsProto(
948        primal_bound=result_proto.solve_stats.best_primal_bound,
949        dual_bound=result_proto.solve_stats.best_dual_bound,
950    )
951
952
953def _upgrade_termination(
954    result_proto: result_pb2.SolveResultProto,
955) -> result_pb2.TerminationProto:
956    return result_pb2.TerminationProto(
957        reason=result_proto.termination.reason,
958        limit=result_proto.termination.limit,
959        detail=result_proto.termination.detail,
960        problem_status=_get_problem_status(result_proto),
961        objective_bounds=_get_objective_bounds(result_proto),
962    )
963
964
965def parse_solve_result(
966    proto: result_pb2.SolveResultProto, mod: model.Model
967) -> SolveResult:
968    """Returns a SolveResult equivalent to the input proto."""
969    result = SolveResult()
970    # TODO(b/290091715): change to parse_termination(proto.termination)
971    # once solve_stats proto no longer has best_primal/dual_bound/problem_status
972    # and problem_status/objective_bounds are guaranteed to be present in
973    # termination proto.
974    result.termination = parse_termination(_upgrade_termination(proto))
975    result.solve_stats = parse_solve_stats(proto.solve_stats)
976    for solution_proto in proto.solutions:
977        result.solutions.append(solution.parse_solution(solution_proto, mod))
978    for primal_ray_proto in proto.primal_rays:
979        result.primal_rays.append(solution.parse_primal_ray(primal_ray_proto, mod))
980    for dual_ray_proto in proto.dual_rays:
981        result.dual_rays.append(solution.parse_dual_ray(dual_ray_proto, mod))
982    if proto.HasField("gscip_output"):
983        result.gscip_specific_output = proto.gscip_output
984    elif proto.HasField("osqp_output"):
985        result.osqp_specific_output = proto.osqp_output
986    elif proto.HasField("pdlp_output"):
987        result.pdlp_specific_output = proto.pdlp_output
988    return result