Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
Public Member Functions | Public Attributes | List of all members
operations_research::math_opt::Termination Struct Reference

All information regarding why a call to Solve() terminated. More...

#include <solve_result.h>

Public Member Functions

 Termination (bool is_maximize, TerminationReason reason, std::string detail={})
 
bool limit_reached () const
 
absl::Status EnsureIsOptimalOrFeasible () const
 
const PrimalSolution & best_primal_solution () const
 
double objective_value () const
 
double objective_value (Objective objective) const
 
double best_objective_bound () const
 
const VariableMap< double > & variable_values () const
 
bool bounded () const
 Returns true only if the problem has been shown to be feasible and bounded.
 
bool has_ray () const
 
const VariableMap< double > & ray_variable_values () const
 
bool has_dual_feasible_solution () const
 
const LinearConstraintMap< double > & dual_values () const
 
const VariableMap< double > & reduced_costs () const
 
bool has_dual_ray () const
 
const LinearConstraintMap< double > & ray_dual_values () const
 
const VariableMap< double > & ray_reduced_costs () const
 
bool has_basis () const
 Indicates if the best solution has an associated basis.
 
const LinearConstraintMap< BasisStatus > & constraint_status () const
 
const VariableMap< BasisStatus > & variable_status () const
 

Public Attributes

TerminationReason reason
 
std::optional< Limit > limit
 
std::string detail
 
ProblemStatus problem_status
 Feasibility statuses for primal and dual problems.
 
ObjectiveBounds objective_bounds
 Bounds on the optimal objective value.
 

Detailed Description

All information regarding why a call to Solve() terminated.

Definition at line 289 of file solve_result.h.

Constructor & Destructor Documentation

◆ Termination()

operations_research::math_opt::Termination::Termination ( bool is_maximize,
TerminationReason reason,
std::string detail = {} )

Returns a Termination with the provided reason and details along with trivial bounds and kUndetermined statuses. A variety of static factory functions are provided below for common Termination conditions, generally prefer these if applicable.

Definition at line 216 of file solve_result.cc.

Member Function Documentation

◆ best_objective_bound()

double operations_research::math_opt::Termination::best_objective_bound ( ) const

A bound on the best possible objective value.

best_objective_bound() is always equal to dual_bound(), so they can be used interchangeably.

◆ best_primal_solution()

const PrimalSolution & operations_research::math_opt::Termination::best_primal_solution ( ) const

Returns true if the reason of this Terminationis /TerminationReason::kOptimalorTerminationReason::kFeasible`, or false / otherwise. bool IsOptimalOrFeasible() const;

/ Returns an OkStatus if the reason of this Termination is / TerminationReason::kOptimal, or an InternalError otherwise. / / In most use cases, at least for MIPs, EnsureIsOptimalOrFeasible should be / used instead. absl::Status EnsureIsOptimal() const;

/ Returns true if the reason of this Termination is / TerminationReason::kOptimal, or false otherwise. / / In most use cases, at least for MIPs, IsOptimalOrFeasible should be / used instead. bool IsOptimal() const;

/ Returns an OkStatus if the reason of this Termination is reason, or an / InternalError otherwise. absl::Status EnsureReasonIs(TerminationReason reason) const;

/ Returns an OkStatus if the reason of this Termination is in reasons, or / an InternalError otherwise. absl::Status EnsureReasonIsAnyOf( std::initializer_list<TerminationReason> reasons) const;

/ Returns termination with reason kOptimal, the provided objective for both / primal and dual bounds, and kFeasible primal and dual statuses. static Termination Optimal(double objective_value, std::string detail = {});

/ Returns termination with reason kOptimal, the provided objective bounds and / kFeasible primal and dual statuses. static Termination Optimal(double primal_objective_value, double dual_objective_value, std::string detail = {});

/ Returns a termination with reason kInfeasible, primal status kInfeasible / and the provided dual status. / / It sets a trivial primal bound and a dual bound based on the provided dual / status, which should be kFeasible or kUndetermined. If the dual status is / kUndetermined, then the dual bound will be trivial and if the dual status / is kFeasible, then the dual bound will be equal to the primal bound. / / The convention for infeasible MIPs is that dual_feasibility_status is / feasible (There always exist a dual feasible convex relaxation of an / infeasible MIP). static Termination Infeasible(bool is_maximize, FeasibilityStatus dual_feasibility_status = FeasibilityStatus::kUndetermined, std::string detail = {});

/ Returns a termination with reason kInfeasibleOrUnbounded, primal status / kUndetermined, the provided dual status (which should be kUndetermined or / kInfeasible) and trivial bounds. / / primal_or_dual_infeasible is set if dual_feasibility_status is / kUndetermined. static Termination InfeasibleOrUnbounded( bool is_maximize, FeasibilityStatus dual_feasibility_status = FeasibilityStatus::kUndetermined, std::string detail = {});

/ Returns a termination with reason kUnbounded, primal status kFeasible, / dual status kInfeasible and unbounded bounds. static Termination Unbounded(bool is_maximize, std::string detail = {});

/ Returns a termination with reason kNoSolutionFound and primal status / kUndetermined. / / Assumes dual solution exists iff optional_dual_objective is set even if / infinite (some solvers return feasible dual solutions without an objective / value). optional_dual_objective should not be set when limit is / kCutoff for a valid TerminationProto to be returned (use LimitCutoff() / below instead). / / It sets a trivial primal bound. The dual bound is either set to the / optional_dual_objective if set, else to a trivial value. / /

Todo
(b/290359402): Consider improving to require a finite dual bound when / dual feasible solutions are returned. static Termination NoSolutionFound( bool is_maximize, Limit limit, std::optional<double> optional_dual_objective = std::nullopt, std::string detail = {});

/ Returns a termination with reason kFeasible and primal status kFeasible. / The dual status depends on optional_dual_objective. / / finite_primal_objective should be finite and limit should not be / kCutoff for a valid TerminationProto to be returned (use LimitCutoff() / below instead). / / Assumes dual solution exists iff optional_dual_objective is set even if / infinite (some solvers return feasible dual solutions without an objective / value). If set the dual status is set to kFeasible, else / it is kUndetermined. / / It sets the primal bound based on the primal objective. The dual bound is / either set to the optional_dual_objective if set, else to a trivial value. / /

Todo
(b/290359402): Consider improving to require a finite dual bound when / dual feasible solutions are returned. static Termination Feasible( bool is_maximize, Limit limit, double finite_primal_objective, std::optional<double> optional_dual_objective = std::nullopt, std::string detail = {});

/ Calls NoSolutionFound() with LIMIT_CUTOFF LIMIT. static Termination Cutoff(bool is_maximize, std::string detail = {});

/ Will return an error if termination_proto.reason is UNSPECIFIED. static absl::StatusOr<Termination> FromProto( const TerminationProto& termination_proto); TerminationProto Proto() const;

std::string ToString() const; };

std::ostream& operator<<(std::ostream& ostr, const Termination& termination);

template <typename Sink> void AbslStringify(Sink& sink, const Termination& termination) { sink.Append(termination.ToString()); }

/ The result of solving an optimization problem with Solve(). struct SolveResult { explicit SolveResult(Termination termination) : termination(std::move(termination)) {}

/ The reason the solver stopped. Termination termination;

/ Statistics on the solve process, e.g. running time, iterations. SolveStats solve_stats;

/ Basic solutions use, as of Nov 2021: All convex optimization solvers (LP, convex QP) return only one / solution as a primal dual pair. Only MI(Q)P solvers return more than one solution. MIP solvers do not / return any dual information, or primal infeasible solutions. Solutions / are returned in order of best primal objective first. Gurobi solves / nonconvex QP (integer or continuous) as MIQP.

/ The general contract for the order of solutions that future solvers should / implement is to order by: / 1. The solutions with a primal feasible solution, ordered by best primal / objective first. / 2. The solutions with a dual feasible solution, ordered by best dual / objective (unknown dual objective is worst) / 3. All remaining solutions can be returned in any order. std::vector<Solution> solutions;

/ Directions of unbounded primal improvement, or equivalently, dual / infeasibility certificates. Typically provided for TerminationReasons / kUnbounded and kInfeasibleOrUnbounded. std::vector<PrimalRay> primal_rays;

/ Directions of unbounded dual improvement, or equivalently, primal / infeasibility certificates. Typically provided for TerminationReason / kInfeasible. std::vector<DualRay> dual_rays;

/ Solver specific output from Gscip. Only populated if Gscip is used. GScipOutput gscip_solver_specific_output; / Solver specific output from Pdlp. Only populated if Pdlp is used. SolveResultProto::PdlpOutput pdlp_solver_specific_output;

/ Returns the SolveResult equivalent of solve_result_proto. / / Returns an error if: / * Any solution or ray cannot be read from proto (e.g. on a subfield, / ids.size != values.size). / * termination or solve_stats cannot be read from proto. / See the FromProto() functions for these types for details. / /

Note
this is (intentionally) a much weaker test than ValidateResult(). The / guarantees are just strong enough to ensure that a SolveResult and / SolveResultProto can round trip cleanly, e.g. we do not check that a / termination reason optimal implies that there is at least one primal / feasible solution. / / While ValidateResult() is called automatically when you are solving / locally, users who are reading a solution from disk, solving remotely, or / getting their SolveResultProto (or SolveResult) by any other means are / encouraged to either call ValidateResult() themselves, do their own / validation, or not rely on the strong guarantees of ValidateResult() / and just treat SolveResult as a simple struct. static absl::StatusOr<SolveResult> FromProto( const ModelStorage* model, const SolveResultProto& solve_result_proto);

/ Returns the proto equivalent of this. / /

Note
the proto uses a oneof for solver specific output. This method / will fail if multiple solver specific outputs are set. / /
Todo
(b/231134639): investigate removing the oneof from the proto. absl::StatusOr<SolveResultProto> Proto() const;

absl::Duration solve_time() const { return solve_stats.solve_time; }

/ A primal bound on the optimal objective value as described in / ObjectiveBounds. Will return a valid (possibly infinite) bound even if / no primal feasible solutions are available. double primal_bound() const;

/ A dual bound on the optimal objective value as described in / ObjectiveBounds. Will return a valid (possibly infinite) bound even if / no dual feasible solutions are available. double dual_bound() const;

/ Indicates if at least one primal feasible solution is available. / / For SolveResults generated by calling Solver::Solve(), when / termination.reason is TerminationReason::kOptimal or / TerminationReason::kFeasible, this is guaranteed to be true and need not be / checked. SolveResult objects generated directed from a proto need not have / this property. bool has_primal_feasible_solution() const;

/ Returns the best primal feasible solution. CHECK fails if no such solution / is available; check this using has_primal_feasible_solution().

◆ bounded()

bool operations_research::math_opt::Termination::bounded ( ) const

Returns true only if the problem has been shown to be feasible and bounded.

◆ constraint_status()

const LinearConstraintMap< BasisStatus > & operations_research::math_opt::Termination::constraint_status ( ) const

The constraint basis status for the best solution. Will CHECK fail if the best solution does not have an associated basis.

◆ dual_values()

const LinearConstraintMap< double > & operations_research::math_opt::Termination::dual_values ( ) const

The dual values associated to the best solution.

If there is at least one primal feasible solution, this corresponds to the dual values associated to the best primal feasible solution. Will CHECK fail if the best solution does not have an associated dual feasible solution.

◆ EnsureIsOptimalOrFeasible()

absl::Status operations_research::math_opt::Termination::EnsureIsOptimalOrFeasible ( ) const

Returns an OkStatus if the reason of this Termination is TerminationReason::kOptimal or TerminationReason::kFeasible, or an InternalError otherwise.

Definition at line 359 of file solve_result.cc.

◆ has_basis()

bool operations_research::math_opt::Termination::has_basis ( ) const

Indicates if the best solution has an associated basis.

◆ has_dual_feasible_solution()

bool operations_research::math_opt::Termination::has_dual_feasible_solution ( ) const

Indicates if the best solution has an associated dual feasible solution.

This is NOT guaranteed to be true when termination.reason is TerminationReason::kOptimal. It also may be true even when the best solution does not have an associated primal feasible solution.

◆ has_dual_ray()

bool operations_research::math_opt::Termination::has_dual_ray ( ) const
inline

Indicates if at least one dual ray is available.

This is NOT guaranteed to be true when termination.reason is TerminationReason::kInfeasible.

Definition at line 618 of file solve_result.h.

◆ has_ray()

bool operations_research::math_opt::Termination::has_ray ( ) const
inline

Indicates if at least one primal ray is available.

This is NOT guaranteed to be true when termination.reason is TerminationReason::kUnbounded or TerminationReason::kInfeasibleOrUnbounded.

Definition at line 585 of file solve_result.h.

◆ limit_reached()

bool operations_research::math_opt::Termination::limit_reached ( ) const

Returns true if a limit was reached (i.e. if reason is kFeasible or kNoSolutionFound, and limit is not empty).

Definition at line 323 of file solve_result.cc.

◆ objective_value() [1/2]

double operations_research::math_opt::Termination::objective_value ( ) const

The objective value of the best primal feasible solution. Will CHECK fail if there are no primal feasible solutions.

primal_bound() above is guaranteed to be at least as good (larger or equal for max problems and smaller or equal for min problems) as objective_value() and will never CHECK fail, so it may be preferable in some cases. Note that primal_bound() could be better than objective_value() even for optimal terminations, but on such optimal termination, both should satisfy the optimality tolerances.

◆ objective_value() [2/2]

double operations_research::math_opt::Termination::objective_value ( Objective objective) const

◆ ray_dual_values()

const LinearConstraintMap< double > & operations_research::math_opt::Termination::ray_dual_values ( ) const

The dual values from the first dual ray. Will CHECK fail if there are no dual rays.

◆ ray_reduced_costs()

const VariableMap< double > & operations_research::math_opt::Termination::ray_reduced_costs ( ) const

The reduced from the first dual ray. Will CHECK fail if there are no dual rays.

◆ ray_variable_values()

const VariableMap< double > & operations_research::math_opt::Termination::ray_variable_values ( ) const

The variable values from the first primal ray. Will CHECK fail if there are no primal rays.

◆ reduced_costs()

const VariableMap< double > & operations_research::math_opt::Termination::reduced_costs ( ) const

The reduced costs associated to the best solution.

If there is at least one primal feasible solution, this corresponds to the reduced costs associated to the best primal feasible solution. Will CHECK fail if the best solution does not have an associated dual feasible solution.

◆ variable_status()

const VariableMap< BasisStatus > & operations_research::math_opt::Termination::variable_status ( ) const

The variable basis status for the best solution. Will CHECK fail if the best solution does not have an associated basis.

◆ variable_values()

const VariableMap< double > & operations_research::math_opt::Termination::variable_values ( ) const

The variable values from the best primal feasible solution. Will CHECK fail if there are no primal feasible solutions.

Member Data Documentation

◆ detail

std::string operations_research::math_opt::Termination::detail

Additional typically solver specific information about termination. Not all solvers can always determine the limit which caused termination, Limit::kUndetermined is used when the cause cannot be determined.

Definition at line 311 of file solve_result.h.

◆ limit

std::optional<Limit> operations_research::math_opt::Termination::limit

A Termination within a SolveResult returned by math_opt::Solve() satisfies some additional invariants:

  • limit is set iff reason is kFeasible or kNoSolutionFound.
  • if the limit is kCutoff, the termination reason will be kNoSolutionFound.

Definition at line 306 of file solve_result.h.

◆ objective_bounds

ObjectiveBounds operations_research::math_opt::Termination::objective_bounds

Bounds on the optimal objective value.

Definition at line 317 of file solve_result.h.

◆ problem_status

ProblemStatus operations_research::math_opt::Termination::problem_status

Feasibility statuses for primal and dual problems.

Definition at line 314 of file solve_result.h.

◆ reason

TerminationReason operations_research::math_opt::Termination::reason

Additional information in limit when value is kFeasible or kNoSolutionFound, see limit for details.

Definition at line 299 of file solve_result.h.

The documentation for this struct was generated from the following files: