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