#include <solution.h>

Public Member Functions
absl::Status	CheckModelStorage (const ModelStorage *expected_storage) const

BasisProto	Proto () const

Static Public Member Functions
static absl::StatusOr< Basis >	FromProto (const ModelStorage *model, const BasisProto &basis_proto)

Public Attributes
LinearConstraintMap< BasisStatus >	constraint_status

VariableMap< BasisStatus >	variable_status

std::optional< SolutionStatus >	basic_dual_feasibility

Detailed Description

A combinatorial characterization for a solution to a linear program.

The simplex method for solving linear programs always returns a "basic feasible solution" which can be described combinatorially as a Basis. A basis assigns a BasisStatus for every variable and linear constraint.

E.g. consider a standard form LP: min c * x s.t. A * x = b x >= 0 that has more variables than constraints and with full row rank A.

Let n be the number of variables and m the number of linear constraints. A valid basis for this problem can be constructed as follows:

All constraints will have basis status FIXED.
Pick m variables such that the columns of A are linearly independent and assign the status BASIC.
Assign the status AT_LOWER for the remaining n - m variables.

The basic solution for this basis is the unique solution of A * x = b that has all variables with status AT_LOWER fixed to their lower bounds (all zero). The resulting solution is called a basic feasible solution if it also satisfies x >= 0.

Definition at line 215 of file solution.h.

Member Function Documentation

◆ CheckModelStorage()

absl::Status operations_research::math_opt::Basis::CheckModelStorage ( const ModelStorage * expected_storage ) const

Returns a failure if the referenced variables don't belong to the input expected_storage (which must not be nullptr).

Definition at line 199 of file solution.cc.

◆ FromProto()

absl::StatusOr< Basis > operations_research::math_opt::Basis::FromProto	(	const ModelStorage *	model,
		const BasisProto &	basis_proto )

static

Returns the equivalent Basis object for basis_proto.

Returns an error if:

VariableBasisFromProto(basis_proto.variable_status) fails.
LinearConstraintBasisFromProto(basis_proto.constraint_status) fails.

Definition at line 183 of file solution.cc.

◆ Proto()

BasisProto operations_research::math_opt::Basis::Proto ( ) const

Returns the proto equivalent of this object.

The caller should use CheckModelStorage() as this function does not check internal consistency of the referenced variables and constraints.

Definition at line 216 of file solution.cc.

Member Data Documentation

◆ basic_dual_feasibility

std::optional<SolutionStatus> operations_research::math_opt::Basis::basic_dual_feasibility

This is an advanced feature used by MathOpt to characterize feasibility of suboptimal LP solutions (optimal solutions will always have status SolutionStatus::kFeasible).

For single-sided LPs it should be equal to the feasibility status of the associated dual solution. For two-sided LPs it may be different in some edge cases (e.g. incomplete solves with primal simplex).

If you are providing a starting basis via ModelSolveParameters.initial_basis, this value is ignored. It is only relevant for the basis returned by Solution.basis, and it is is always populated in a Basis returned by a call to Solve().

Definition at line 249 of file solution.h.

◆ constraint_status

LinearConstraintMap<BasisStatus> operations_research::math_opt::Basis::constraint_status

Definition at line 234 of file solution.h.

◆ variable_status

VariableMap<BasisStatus> operations_research::math_opt::Basis::variable_status

Definition at line 235 of file solution.h.

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

ortools/math_opt/cpp/solution.h
ortools/math_opt/cpp/solution.cc

Public Member Functions

Static Public Member Functions

Public Attributes