Package google.research.optimization.v1.mathopt

Index

BasisProto (message)
BasisStatusProto (enum)
DualRayProto (message)
DualSolutionProto (message)
EmphasisProto (enum)
FeasibilityStatusProto (enum)
IndicatorConstraintProto (message)
LPAlgorithmProto (enum)
LimitProto (enum)
LinearConstraintsProto (message)
LinearExpressionProto (message)
ModelProto (message)
ModelSolveParametersProto (message)
ObjectiveBoundsProto (message)
ObjectiveProto (message)
PrimalRayProto (message)
PrimalSolutionProto (message)
ProblemStatusProto (message)
QuadraticConstraintProto (message)
SecondOrderConeConstraintProto (message)
SolutionHintProto (message)
SolutionProto (message)
SolutionStatusProto (enum)
SolveParametersProto (message)
SolveResultProto (message)
SolveStatsProto (message)
SolverTypeProto (enum)
SosConstraintProto (message)
SparseBasisStatusVector (message)
SparseDoubleMatrixProto (message)
SparseDoubleVectorProto (message)
SparseInt32VectorProto (message)
SparseVectorFilterProto (message)
TerminationProto (message)
TerminationReasonProto (enum)
VariablesProto (message)

BasisProto

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 by a Basis. A basis assigns a BasisStatusProto 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.

Fields

Fields
`constraint_status`	`SparseBasisStatusVector` Constraint basis status. Requirements: * constraint_status.ids is equal to LinearConstraints.ids.
`variable_status`	`SparseBasisStatusVector` Variable basis status. Requirements: * constraint_status.ids is equal to VariablesProto.ids.
`basic_dual_feasibility`	`SolutionStatusProto` This is an advanced feature used by MathOpt to characterize feasibility of suboptimal LP solutions (optimal solutions will always have status SOLUTION_STATUS_FEASIBLE). 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 ModelSolveParametersProto.initial_basis, this value is ignored. It is only relevant for the basis returned by SolutionProto.basis.

constraint_status

SparseBasisStatusVector

Constraint basis status.

Requirements: * constraint_status.ids is equal to LinearConstraints.ids.

variable_status

SparseBasisStatusVector

Variable basis status.

Requirements: * constraint_status.ids is equal to VariablesProto.ids.

basic_dual_feasibility

SolutionStatusProto

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

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 ModelSolveParametersProto.initial_basis, this value is ignored. It is only relevant for the basis returned by SolutionProto.basis.

BasisStatusProto

Status of a variable/constraint in a LP basis.

Enums
`BASIS_STATUS_UNSPECIFIED`	Guard value representing no status.
`BASIS_STATUS_FREE`	The variable/constraint is free (it has no finite bounds).
`BASIS_STATUS_AT_LOWER_BOUND`	The variable/constraint is at its lower bound (which must be finite).
`BASIS_STATUS_AT_UPPER_BOUND`	The variable/constraint is at its upper bound (which must be finite).
`BASIS_STATUS_FIXED_VALUE`	The variable/constraint has identical finite lower and upper bounds.
`BASIS_STATUS_BASIC`	The variable/constraint is basic.

DualRayProto

A direction of unbounded improvement to the dual of an optimization, problem; equivalently, a certificate of primal infeasibility.

E.g. consider the primal dual pair linear program pair: (Primal) (Dual) min c * x max b * y s.t. A * x >= b s.t. y * A + r = c x >= 0 y, r >= 0. The dual ray is the pair (y, r) satisfying: b * y > 0 y * A + r = 0 y, r >= 0 Observe that adding a positive multiple of (y, r) to dual feasible solution maintains dual feasibility and improves the objective (proving the dual is unbounded). The dual ray also proves the primal problem is infeasible.

In the message DualRay below, y is dual_values and r is reduced_costs.

Fields

dual_values

SparseDoubleVectorProto

Requirements: * dual_values.ids are elements of LinearConstraints.ids. * dual_values.values must all be finite.

reduced_costs

SparseDoubleVectorProto

Requirements: * reduced_costs.ids are elements of VariablesProto.ids. * reduced_costs.values must all be finite.

DualSolutionProto

A solution to the dual of an optimization problem.

E.g. consider the primal dual pair linear program pair: (Primal) (Dual) min c * x max b * y s.t. A * x >= b s.t. y * A + r = c x >= 0 y, r >= 0. The dual solution is the pair (y, r). It is feasible if it satisfies the constraints from (Dual) above.

In the message below, y is dual_values, r is reduced_costs, and b * y is objective value.

Fields
`dual_values`	`SparseDoubleVectorProto` Requirements: * dual_values.ids are elements of LinearConstraints.ids. * dual_values.values must all be finite.
`reduced_costs`	`SparseDoubleVectorProto` Requirements: * reduced_costs.ids are elements of VariablesProto.ids. * reduced_costs.values must all be finite.
`feasibility_status`	`SolutionStatusProto` Feasibility status of the solution according to the underlying solver.
`objective_value`	`double`

EmphasisProto

Effort level applied to an optional task while solving (see SolveParametersProto for use).

Emphasis is used to configure a solver feature as follows: * If a solver doesn't support the feature, only UNSPECIFIED will always be valid, any other setting will typically an invalid argument error (some solvers may also accept OFF). * If the solver supports the feature: - When set to UNSPECIFIED, the underlying default is used. - When the feature cannot be turned off, OFF will return an error. - If the feature is enabled by default, the solver default is typically mapped to MEDIUM. - If the feature is supported, LOW, MEDIUM, HIGH, and VERY HIGH will never give an error, and will map onto their best match.

Enums
`EMPHASIS_UNSPECIFIED`
`EMPHASIS_OFF`
`EMPHASIS_LOW`
`EMPHASIS_MEDIUM`
`EMPHASIS_HIGH`
`EMPHASIS_VERY_HIGH`

FeasibilityStatusProto

Problem feasibility status as claimed by the solver (solver is not required to return a certificate for the claim).

Enums
`FEASIBILITY_STATUS_UNSPECIFIED`	Guard value representing no status.
`FEASIBILITY_STATUS_UNDETERMINED`	Solver does not claim a status.
`FEASIBILITY_STATUS_FEASIBLE`	Solver claims the problem is feasible.
`FEASIBILITY_STATUS_INFEASIBLE`	Solver claims the problem is infeasible.

IndicatorConstraintProto

Data for representing a single indicator constraint of the form: Variable(indicator_id) = (activate_on_zero ? 0 : 1) ⇒ lower_bound <= expression <= upper_bound.

If a variable involved in this constraint (either the indicator, or appearing in expression) is deleted, it is treated as if it were set to zero. In particular, deleting the indicator variable means that the indicator constraint is vacuous if activate_on_zero is false, and that it is equivalent to a linear constraint if activate_on_zero is true.

Fields
`activate_on_zero`	`bool` If true, then if the indicator variable takes value 0, the implied constraint must hold. Otherwise, if the indicator variable takes value 1, then the implied constraint must hold.
`expression`	`SparseDoubleVectorProto` Must be a valid linear expression with respect to the containing model: * All stated conditions on `SparseDoubleVectorProto`, * All elements of `expression.values` must be finite, * `expression.ids` are a subset of `VariablesProto.ids`.
`lower_bound`	`double` Must have value in [-inf, inf); cannot be NaN.
`upper_bound`	`double` Must have value in (-inf, inf]; cannot be NaN.
`name`	`string` Parent messages may have uniqueness requirements on this field; e.g., see `ModelProto.indicator_constraints` and `IndicatorConstraintUpdatesProto.new_constraints`.
`indicator_id`	`int64` An ID corresponding to a binary variable, or unset. If unset, the indicator constraint is ignored. If set, we require that: * VariablesProto.integers[indicator_id] = true, * VariablesProto.lower_bounds[indicator_id] >= 0, * VariablesProto.upper_bounds[indicator_id] <= 1. These conditions are not validated by MathOpt, but if not satisfied will lead to the solver returning an error upon solving.

LPAlgorithmProto

Selects an algorithm for solving linear programs.

Enums
`LP_ALGORITHM_UNSPECIFIED`
`LP_ALGORITHM_PRIMAL_SIMPLEX`	The (primal) simplex method. Typically can provide primal and dual solutions, primal/dual rays on primal/dual unbounded problems, and a basis.
`LP_ALGORITHM_DUAL_SIMPLEX`	The dual simplex method. Typically can provide primal and dual solutions, primal/dual rays on primal/dual unbounded problems, and a basis.
`LP_ALGORITHM_BARRIER`	The barrier method, also commonly called an interior point method (IPM). Can typically give both primal and dual solutions. Some implementations can also produce rays on unbounded/infeasible problems. A basis is not given unless the underlying solver does "crossover" and finishes with simplex.
`LP_ALGORITHM_FIRST_ORDER`	An algorithm based around a first-order method. These will typically produce both primal and dual solutions, and potentially also certificates of primal and/or dual infeasibility. First-order methods typically will provide solutions with lower accuracy, so users should take care to set solution quality parameters (e.g., tolerances) and to validate solutions.

LimitProto

When a Solve() stops early with TerminationReasonProto FEASIBLE or NO_SOLUTION_FOUND, the specific limit that was hit.

Enums
`LIMIT_UNSPECIFIED`	Used as a null value when we terminated not from a limit (e.g. TERMINATION_REASON_OPTIMAL).
`LIMIT_UNDETERMINED`	The underlying solver does not expose which limit was reached.
`LIMIT_ITERATION`	An iterative algorithm stopped after conducting the maximum number of iterations (e.g. simplex or barrier iterations).
`LIMIT_TIME`	The algorithm stopped after a user-specified computation time.
`LIMIT_NODE`	A branch-and-bound algorithm stopped because it explored a maximum number of nodes in the branch-and-bound tree.
`LIMIT_SOLUTION`	The algorithm stopped because it found the required number of solutions. This is often used in MIPs to get the solver to return the first feasible solution it encounters.
`LIMIT_MEMORY`	The algorithm stopped because it ran out of memory.
`LIMIT_CUTOFF`	The solver was run with a cutoff (e.g. SolveParameters.cutoff_limit was set) on the objective, indicating that the user did not want any solution worse than the cutoff, and the solver concluded there were no solutions at least as good as the cutoff. Typically no further solution information is provided.
`LIMIT_OBJECTIVE`	The algorithm stopped because it either found a solution or a bound better than a limit set by the user (see SolveParameters.objective_limit and SolveParameters.best_bound_limit).
`LIMIT_NORM`	The algorithm stopped because the norm of an iterate became too large.
`LIMIT_INTERRUPTED`	The algorithm stopped because of an interrupt signal or a user interrupt request.
`LIMIT_SLOW_PROGRESS`	The algorithm stopped because it was unable to continue making progress towards the solution.
`LIMIT_OTHER`	The algorithm stopped due to a limit not covered by one of the above. Note that LIMIT_UNDETERMINED is used when the reason cannot be determined, and LIMIT_OTHER is used when the reason is known but does not fit into any of the above alternatives. TerminationProto.detail may contain additional information about the limit.

LinearConstraintsProto

As used below, we define "#linear constraints" = size(LinearConstraintsProto.ids).

Fields
`ids[]`	`int64` Must be nonnegative and strictly increasing. The max(int64) value can't be used.
`lower_bounds[]`	`double` Should have length equal to #linear constraints, values in [-inf, inf).
`upper_bounds[]`	`double` Should have length equal to #linear constraints, values in (-inf, inf].
`names[]`	`string` If not set, assumed to be all empty strings. Otherwise, should have length equal to #linear constraints. All nonempty names must be distinct.

LinearExpressionProto

A sparse representation of a linear expression (a weighted sum of variables, plus a constant offset).

Fields

Fields
`ids[]`	`int64` Ids of variables. Must be sorted (in increasing ordering) with all elements distinct.
`coefficients[]`	`double` Must have equal length to ids. Values must be finite may not be NaN.
`offset`	`double` Must be finite and may not be NaN.

ids[]

int64

Ids of variables. Must be sorted (in increasing ordering) with all elements distinct.

coefficients[]

double

Must have equal length to ids. Values must be finite may not be NaN.

offset

double

Must be finite and may not be NaN.

ModelProto

An optimization problem. MathOpt supports: - Continuous and integer decision variables with optional finite bounds. - Linear and quadratic objectives (single or multiple objectives), either minimized or maximized. - A number of constraints types, including: * Linear constraints * Quadratic constraints * Second-order cone constraints * Logical constraints > SOS1 and SOS2 constraints > Indicator constraints

By default, constraints are represented in "id-to-data" maps. However, we represent linear constraints in a more efficient "struct-of-arrays" format.

Fields
`name`	`string`
`variables`	`VariablesProto`
`objective`	`ObjectiveProto` The primary objective in the model.
`auxiliary_objectives`	`map<int64, ObjectiveProto>` Auxiliary objectives for use in multi-objective models. Map key IDs must be in [0, max(int64)). Each priority, and each nonempty name, must be unique and also distinct from the primary `objective`.
`linear_constraints`	`LinearConstraintsProto`
`linear_constraint_matrix`	`SparseDoubleMatrixProto` The variable coefficients for the linear constraints. If a variable involved in this constraint is deleted, it is treated as if it were set to zero. Requirements: * linear_constraint_matrix.row_ids are elements of linear_constraints.ids. * linear_constraint_matrix.column_ids are elements of variables.ids. * Matrix entries not specified are zero. * linear_constraint_matrix.values must all be finite.
`quadratic_constraints`	`map<int64, QuadraticConstraintProto>` Quadratic constraints in the model.
`second_order_cone_constraints`	`map<int64, SecondOrderConeConstraintProto>` Second-order cone constraints in the model.
`sos1_constraints`	`map<int64, SosConstraintProto>` SOS1 constraints in the model, which constrain that at most one `expression` can be nonzero. The optional `weights` entries are an implementation detail used by the solver to (hopefully) converge more quickly. In more detail, solvers may (or may not) use these weights to select branching decisions that produce "balanced" children nodes.
`sos2_constraints`	`map<int64, SosConstraintProto>` SOS2 constraints in the model, which constrain that at most two entries of `expression` can be nonzero, and they must be adjacent in their ordering. If no `weights` are provided, this ordering is their linear ordering in the `expressions` list; if `weights` are presented, the ordering is taken with respect to these values in increasing order.
`indicator_constraints`	`map<int64, IndicatorConstraintProto>` Indicator constraints in the model, which enforce that, if a binary "indicator variable" is set to one, then an "implied constraint" must hold.

ModelSolveParametersProto

Fields
`variable_values_filter`	`SparseVectorFilterProto` Filter that is applied to all returned sparse containers keyed by variables in PrimalSolutionProto and PrimalRayProto (PrimalSolutionProto.variable_values, PrimalRayProto.variable_values). Requirements: * filtered_ids are elements of VariablesProto.ids.
`dual_values_filter`	`SparseVectorFilterProto` Filter that is applied to all returned sparse containers keyed by linear constraints in DualSolutionProto and DualRay (DualSolutionProto.dual_values, DualRay.dual_values). Requirements: * filtered_ids are elements of LinearConstraints.ids.
`reduced_costs_filter`	`SparseVectorFilterProto` Filter that is applied to all returned sparse containers keyed by variables in DualSolutionProto and DualRay (DualSolutionProto.reduced_costs, DualRay.reduced_costs). Requirements: * filtered_ids are elements of VariablesProto.ids.
`initial_basis`	`BasisProto` Optional initial basis for warm starting simplex LP solvers. If set, it is expected to be valid according to `ValidateBasis` in `validators/solution_validator.h` for the current `ModelSummary`.
`solution_hints[]`	`SolutionHintProto` Optional solution hints. If the underlying solver only accepts a single hint, the first hint is used.
`branching_priorities`	`SparseInt32VectorProto` Optional branching priorities. Variables with higher values will be branched on first. Variables for which priorities are not set get the solver's default priority (usually zero). Requirements: * branching_priorities.values must be finite. * branching_priorities.ids must be elements of VariablesProto.ids.

ObjectiveBoundsProto

Bounds on the optimal objective value.

Fields

Fields
`primal_bound`	`double` Solver claims the optimal value is equal or better (smaller for minimization and larger for maximization) than primal_bound up to the solvers primal feasibility tolerance (see warning below): * primal_bound is trivial (+inf for minimization and -inf maximization) when the solver does not claim to have such bound. * primal_bound can be closer to the optimal value than the objective of the best primal feasible solution. In particular, primal_bound may be non-trivial even when no primal feasible solutions are returned. Warning: The precise claim is that there exists a primal solution that: * is numerically feasible (i.e. feasible up to the solvers tolerance), and * has an objective value primal_bound. This numerically feasible solution could be slightly infeasible, in which case primal_bound could be strictly better than the optimal value. Translating a primal feasibility tolerance to a tolerance on primal_bound is non-trivial, specially when the feasibility tolerance is relatively large (e.g. when solving with PDLP).
`dual_bound`	`double` Solver claims the optimal value is equal or worse (larger for minimization and smaller for maximization) than dual_bound up to the solvers dual feasibility tolerance (see warning below): * dual_bound is trivial (-inf for minimization and +inf maximization) when the solver does not claim to have such bound. Similarly to primal_bound, this may happen for some solvers even when returning optimal. MIP solvers will typically report a bound even if it is imprecise. * for continuous problems dual_bound can be closer to the optimal value than the objective of the best dual feasible solution. For MIP one of the first non-trivial values for dual_bound is often the optimal value of the LP relaxation of the MIP. * dual_bound should be better (smaller for minimization and larger for maximization) than primal_bound up to the solvers tolerances (see warning below). Warning: * For continuous problems, the precise claim is that there exists a dual solution that: * is numerically feasible (i.e. feasible up to the solvers tolerance), and * has an objective value dual_bound. This numerically feasible solution could be slightly infeasible, in which case dual_bound could be strictly worse than the optimal value and primal_bound. Similar to the primal case, translating a dual feasibility tolerance to a tolerance on dual_bound is non-trivial, specially when the feasibility tolerance is relatively large. However, some solvers provide a corrected version of dual_bound that can be numerically safer. This corrected version can be accessed through the solver's specific output (e.g. for PDLP, pdlp_output.convergence_information.corrected_dual_objective). * For MIP solvers, dual_bound may be associated to a dual solution for some continuous relaxation (e.g. LP relaxation), but it is often a complex consequence of the solvers execution and is typically more imprecise than the bounds reported by LP solvers.

primal_bound

double

Solver claims the optimal value is equal or better (smaller for minimization and larger for maximization) than primal_bound up to the solvers primal feasibility tolerance (see warning below): * primal_bound is trivial (+inf for minimization and -inf maximization) when the solver does not claim to have such bound. * primal_bound can be closer to the optimal value than the objective of the best primal feasible solution. In particular, primal_bound may be non-trivial even when no primal feasible solutions are returned. Warning: The precise claim is that there exists a primal solution that: * is numerically feasible (i.e. feasible up to the solvers tolerance), and * has an objective value primal_bound. This numerically feasible solution could be slightly infeasible, in which case primal_bound could be strictly better than the optimal value. Translating a primal feasibility tolerance to a tolerance on primal_bound is non-trivial, specially when the feasibility tolerance is relatively large (e.g. when solving with PDLP).

dual_bound

double

Solver claims the optimal value is equal or worse (larger for minimization and smaller for maximization) than dual_bound up to the solvers dual feasibility tolerance (see warning below): * dual_bound is trivial (-inf for minimization and +inf maximization) when the solver does not claim to have such bound. Similarly to primal_bound, this may happen for some solvers even when returning optimal. MIP solvers will typically report a bound even if it is imprecise. * for continuous problems dual_bound can be closer to the optimal value than the objective of the best dual feasible solution. For MIP one of the first non-trivial values for dual_bound is often the optimal value of the LP relaxation of the MIP. * dual_bound should be better (smaller for minimization and larger for maximization) than primal_bound up to the solvers tolerances (see warning below). Warning: * For continuous problems, the precise claim is that there exists a dual solution that: * is numerically feasible (i.e. feasible up to the solvers tolerance), and * has an objective value dual_bound. This numerically feasible solution could be slightly infeasible, in which case dual_bound could be strictly worse than the optimal value and primal_bound. Similar to the primal case, translating a dual feasibility tolerance to a tolerance on dual_bound is non-trivial, specially when the feasibility tolerance is relatively large. However, some solvers provide a corrected version of dual_bound that can be numerically safer. This corrected version can be accessed through the solver's specific output (e.g. for PDLP, pdlp_output.convergence_information.corrected_dual_objective). * For MIP solvers, dual_bound may be associated to a dual solution for some continuous relaxation (e.g. LP relaxation), but it is often a complex consequence of the solvers execution and is typically more imprecise than the bounds reported by LP solvers.

ObjectiveProto

Fields
`maximize`	`bool` false is minimize, true is maximize
`offset`	`double` Must be finite and not NaN.
`linear_coefficients`	`SparseDoubleVectorProto` ObjectiveProto terms that are linear in the decision variables. Requirements: * linear_coefficients.ids are elements of VariablesProto.ids. * VariablesProto not specified correspond to zero. * linear_coefficients.values must all be finite. * linear_coefficients.values can be zero, but this just wastes space.
`quadratic_coefficients`	`SparseDoubleMatrixProto` Objective terms that are quadratic in the decision variables. Requirements in addition to those on SparseDoubleMatrixProto messages: * Each element of quadratic_coefficients.row_ids and each element of quadratic_coefficients.column_ids must be an element of VariablesProto.ids. * The matrix must be upper triangular: for each i, quadratic_coefficients.row_ids[i] <= quadratic_coefficients.column_ids[i]. Notes: * Terms not explicitly stored have zero coefficient. * Elements of quadratic_coefficients.coefficients can be zero, but this just wastes space.
`name`	`string` Parent messages may have uniqueness requirements on this field; e.g., see ModelProto.objectives and AuxiliaryObjectivesUpdatesProto.new_objectives.
`priority`	`int64` For multi-objective problems, the priority of this objective relative to the others (lower is more important). This value must be nonnegative. Furthermore, each objective priority in the model must be distinct at solve time. This condition is not validated at the proto level, so models may temporarily have objectives with the same priority.

PrimalRayProto

A direction of unbounded improvement to an optimization problem; equivalently, a certificate of infeasibility for the dual of the optimization problem.

E.g. consider a simple linear program: min c * x s.t. A * x >= b x >= 0 A primal ray is an x that satisfies: c * x < 0 A * x >= 0 x >= 0 Observe that given a feasible solution, any positive multiple of the primal ray plus that solution is still feasible, and gives a better objective value. A primal ray also proves the dual optimization problem infeasible.

In the message PrimalRay below, variable_values is x.

Fields

variable_values

SparseDoubleVectorProto

Requirements: * variable_values.ids are elements of VariablesProto.ids. * variable_values.values must all be finite.

PrimalSolutionProto

A solution to an optimization problem.

E.g. consider a simple linear program: min c * x s.t. A * x >= b x >= 0. A primal solution is assignment values to x. It is feasible if it satisfies A * x >= b and x >= 0 from above. In the message PrimalSolutionProto below, variable_values is x and objective_value is c * x.

Fields
`variable_values`	`SparseDoubleVectorProto` Requirements: * variable_values.ids are elements of VariablesProto.ids. * variable_values.values must all be finite.
`objective_value`	`double` Objective value as computed by the underlying solver. Cannot be infinite or NaN.
`auxiliary_objective_values`	`map<int64, double>` Auxiliary objective values as computed by the underlying solver. Keys must be valid auxiliary objective IDs. Values cannot be infinite or NaN.
`feasibility_status`	`SolutionStatusProto` Feasibility status of the solution according to the underlying solver.

ProblemStatusProto

Feasibility status of the primal problem and its dual (or the dual of a continuous relaxation) as claimed by the solver. The solver is not required to return a certificate for the claim (e.g. the solver may claim primal feasibility without returning a primal feasible solutuion). This combined status gives a comprehensive description of a solver's claims about feasibility and unboundedness of the solved problem. For instance,

a feasible status for primal and dual problems indicates the primal is feasible and bounded and likely has an optimal solution (guaranteed for problems without non-linear constraints).
a primal feasible and a dual infeasible status indicates the primal problem is unbounded (i.e. has arbitrarily good solutions).

Note that a dual infeasible status by itself (i.e. accompanied by an undetermined primal status) does not imply the primal problem is unbounded as we could have both problems be infeasible. Also, while a primal and dual feasible status may imply the existence of an optimal solution, it does not guarantee the solver has actually found such optimal solution.

Fields

Fields
`primal_status`	`FeasibilityStatusProto` Status for the primal problem.
`dual_status`	`FeasibilityStatusProto` Status for the dual problem (or for the dual of a continuous relaxation).
`primal_or_dual_infeasible`	`bool` If true, the solver claims the primal or dual problem is infeasible, but it does not know which (or if both are infeasible). Can be true only when primal_problem_status = dual_problem_status = kUndetermined. This extra information is often needed when preprocessing determines there is no optimal solution to the problem (but can't determine if it is due to infeasibility, unboundedness, or both).

primal_status

FeasibilityStatusProto

Status for the primal problem.

dual_status

FeasibilityStatusProto

Status for the dual problem (or for the dual of a continuous relaxation).

primal_or_dual_infeasible

bool

If true, the solver claims the primal or dual problem is infeasible, but it does not know which (or if both are infeasible). Can be true only when primal_problem_status = dual_problem_status = kUndetermined. This extra information is often needed when preprocessing determines there is no optimal solution to the problem (but can't determine if it is due to infeasibility, unboundedness, or both).

QuadraticConstraintProto

A single quadratic constraint of the form: lb <= sum{linear_terms} + sum{quadratic_terms} <= ub.

If a variable involved in this constraint is deleted, it is treated as if it were set to zero.

Fields
`linear_terms`	`SparseDoubleVectorProto` Terms that are linear in the decision variables. In addition to requirements on SparseDoubleVectorProto messages we require that: * linear_terms.ids are elements of VariablesProto.ids. * linear_terms.values must all be finite and not-NaN. Notes: * Variable ids omitted have a corresponding coefficient of zero. * linear_terms.values can be zero, but this just wastes space.
`quadratic_terms`	`SparseDoubleMatrixProto` Terms that are quadratic in the decision variables. In addition to requirements on SparseDoubleMatrixProto messages we require that: * Each element of quadratic_terms.row_ids and each element of quadratic_terms.column_ids must be an element of VariablesProto.ids. * The matrix must be upper triangular: for each i, quadratic_terms.row_ids[i] <= quadratic_terms.column_ids[i]. Notes: * Terms not explicitly stored have zero coefficient. * Elements of quadratic_terms.coefficients can be zero, but this just wastes space.
`lower_bound`	`double` Must have value in [-inf, inf), and be less than or equal to `upper_bound`.
`upper_bound`	`double` Must have value in (-inf, inf], and be greater than or equal to `lower_bound`.
`name`	`string` Parent messages may have uniqueness requirements on this field; e.g., see ModelProto.quadratic_constraints and QuadraticConstraintUpdatesProto.new_constraints.

SecondOrderConeConstraintProto

A single second-order cone constraint of the form:

||arguments_to_norm||_2 <= upper_bound,

where upper_bound and each element of arguments_to_norm are linear expressions.

If a variable involved in this constraint is deleted, it is treated as if it were set to zero.

Fields

Fields
`upper_bound`	`LinearExpressionProto`
`arguments_to_norm[]`	`LinearExpressionProto`
`name`	`string` Parent messages may have uniqueness requirements on this field; e.g., see `ModelProto.second_order_cone_constraints` and `SecondOrderConeConstraintUpdatesProto.new_constraints`.

upper_bound

LinearExpressionProto

arguments_to_norm[]

LinearExpressionProto

name

string

Parent messages may have uniqueness requirements on this field; e.g., see ModelProto.second_order_cone_constraints and SecondOrderConeConstraintUpdatesProto.new_constraints.

SolutionHintProto

A suggested starting solution for the solver.

MIP solvers generally only want primal information (variable_values), while LP solvers want both primal and dual information (dual_values).

Many MIP solvers can work with: (1) partial solutions that do not specify all variables or (2) infeasible solutions. In these cases, solvers typically solve a sub-MIP to complete/correct the hint.

How the hint is used by the solver, if at all, is highly dependent on the solver, the problem type, and the algorithm used. The most reliable way to ensure your hint has an effect is to read the underlying solvers logs with and without the hint.

Simplex-based LP solvers typically prefer an initial basis to a solution hint (they need to crossover to convert the hint to a basic feasible solution otherwise).

Fields

Fields
`variable_values`	`SparseDoubleVectorProto` A possibly partial assignment of values to the primal variables of the problem. The solver-independent requirements for this sub-message are: * variable_values.ids are elements of VariablesProto.ids. * variable_values.values must all be finite.
`dual_values`	`SparseDoubleVectorProto` A (potentially partial) assignment of values to the linear constraints of the problem. Requirements: * dual_values.ids are elements of LinearConstraintsProto.ids. * dual_values.values must all be finite.

variable_values

SparseDoubleVectorProto

A possibly partial assignment of values to the primal variables of the problem. The solver-independent requirements for this sub-message are: * variable_values.ids are elements of VariablesProto.ids. * variable_values.values must all be finite.

dual_values

SparseDoubleVectorProto

A (potentially partial) assignment of values to the linear constraints of the problem.

Requirements: * dual_values.ids are elements of LinearConstraintsProto.ids. * dual_values.values must all be finite.

SolutionProto

What is included in a solution depends on the kind of problem and solver. The current common patterns are 1. MIP solvers return only a primal solution. 2. Simplex LP solvers often return a basis and the primal and dual solutions associated to this basis. 3. Other continuous solvers often return a primal and dual solution solution that are connected in a solver-dependent form.

Requirements: * at least one field must be set; a solution can't be empty.

Fields
`primal_solution`	`PrimalSolutionProto`
`dual_solution`	`DualSolutionProto`
`basis`	`BasisProto`

SolutionStatusProto

Feasibility of a primal or dual solution as claimed by the solver.

Enums
`SOLUTION_STATUS_UNSPECIFIED`	Guard value representing no status.
`SOLUTION_STATUS_UNDETERMINED`	Solver does not claim a feasibility status.
`SOLUTION_STATUS_FEASIBLE`	Solver claims the solution is feasible.
`SOLUTION_STATUS_INFEASIBLE`	Solver claims the solution is infeasible.

SolveParametersProto

Parameters to control a single solve.

Contains both parameters common to all solvers e.g. time_limit, and parameters for a specific solver, e.g. gscip. If a value is set in both common and solver specific field, the solver specific setting is used.

The common parameters that are optional and unset or an enum with value unspecified indicate that the solver default is used.

Solver specific parameters for solvers other than the one in use are ignored.

Parameters that depends on the model (e.g. branching priority is set for each variable) are passed in ModelSolveParametersProto.

Fields
`time_limit`	`Duration` Maximum time a solver should spend on the problem (or infinite if not set). This value is not a hard limit, solve time may slightly exceed this value. This parameter is always passed to the underlying solver, the solver default is not used.
`enable_output`	`bool` Enables printing the solver implementation traces. The location of those traces depend on the solver. For SCIP and Gurobi this will be the standard output streams. For Glop and CP-SAT this will LOG(INFO). Note that if the solver supports message callback and the user registers a callback for it, then this parameter value is ignored and no traces are printed.
`lp_algorithm`	`LPAlgorithmProto` The algorithm for solving a linear program. If LP_ALGORITHM_UNSPECIFIED, use the solver default algorithm. For problems that are not linear programs but where linear programming is a subroutine, solvers may use this value. E.g. MIP solvers will typically use this for the root LP solve only (and use dual simplex otherwise).
`presolve`	`EmphasisProto` Effort on simplifying the problem before starting the main algorithm, or the solver default effort level if EMPHASIS_UNSPECIFIED.
`cuts`	`EmphasisProto` Effort on getting a stronger LP relaxation (MIP only), or the solver default effort level if EMPHASIS_UNSPECIFIED. NOTE: disabling cuts may prevent callbacks from having a chance to add cuts at MIP_NODE, this behavior is solver specific.
`heuristics`	`EmphasisProto` Effort in finding feasible solutions beyond those encountered in the complete search procedure (MIP only), or the solver default effort level if EMPHASIS_UNSPECIFIED.
`scaling`	`EmphasisProto` Effort in rescaling the problem to improve numerical stability, or the solver default effort level if EMPHASIS_UNSPECIFIED.
`iteration_limit`	`int64` Limit on the iterations of the underlying algorithm (e.g. simplex pivots). The specific behavior is dependent on the solver and algorithm used, but often can give a deterministic solve limit (further configuration may be needed, e.g. one thread). Typically supported by LP, QP, and MIP solvers, but for MIP solvers see also node_limit.
`node_limit`	`int64` Limit on the number of subproblems solved in enumerative search (e.g. branch and bound). For many solvers this can be used to deterministically limit computation (further configuration may be needed, e.g. one thread). Typically for MIP solvers, see also iteration_limit.
`cutoff_limit`	`double` The solver stops early if it can prove there are no primal solutions at least as good as cutoff. On an early stop, the solver returns termination reason NO_SOLUTION_FOUND and with limit CUTOFF and is not required to give any extra solution information. Has no effect on the return value if there is no early stop. It is recommended that you use a tolerance if you want solutions with objective exactly equal to cutoff to be returned. See the user guide for more details and a comparison with best_bound_limit.
`objective_limit`	`double` The solver stops early as soon as it finds a solution at least this good, with termination reason FEASIBLE and limit OBJECTIVE.
`best_bound_limit`	`double` The solver stops early as soon as it proves the best bound is at least this good, with termination reason FEASIBLE or NO_SOLUTION_FOUND and limit OBJECTIVE. See the user guide for more details and a comparison with cutoff_limit.
`solution_limit`	`int32` The solver stops early after finding this many feasible solutions, with termination reason FEASIBLE and limit SOLUTION. Must be greater than zero if set. It is often used get the solver to stop on the first feasible solution found. Note that there is no guarantee on the objective value for any of the returned solutions. Solvers will typically not return more solutions than the solution limit, but this is not enforced by MathOpt, see also b/214041169. Currently supported for Gurobi and SCIP, and for CP-SAT only with value 1.
`threads`	`int32` If set, it must be >= 1.
`random_seed`	`int32` Seed for the pseudo-random number generator in the underlying solver. Note that all solvers use pseudo-random numbers to select things such as perturbation in the LP algorithm, for tie-break-up rules, and for heuristic fixings. Varying this can have a noticeable impact on solver behavior. Although all solvers have a concept of seeds, note that valid values depend on the actual solver. - Gurobi: [0:GRB_MAXINT] (which as of Gurobi 9.0 is 2x10^9). - GSCIP: [0:2147483647] (which is MAX_INT or kint32max or 2^31-1). - GLOP: [0:2147483647] (same as above) In all cases, the solver will receive a value equal to: MAX(0, MIN(MAX_VALID_VALUE_FOR_SOLVER, random_seed)).
`absolute_gap_tolerance`	`double` An absolute optimality tolerance (primarily) for MIP solvers. The absolute GAP is the absolute value of the difference between: * the objective value of the best feasible solution found, * the dual bound produced by the search. The solver can stop once the absolute GAP is at most absolute_gap_tolerance (when set), and return TERMINATION_REASON_OPTIMAL. Must be >= 0 if set. See also relative_gap_tolerance.
`relative_gap_tolerance`	`double` A relative optimality tolerance (primarily) for MIP solvers. The relative GAP is a normalized version of the absolute GAP (defined on absolute_gap_tolerance), where the normalization is solver-dependent, e.g. the absolute GAP divided by the objective value of the best feasible solution found. The solver can stop once the relative GAP is at most relative_gap_tolerance (when set), and return TERMINATION_REASON_OPTIMAL. Must be >= 0 if set. See also absolute_gap_tolerance.
`solution_pool_size`	`int32` Maintain up to `solution_pool_size` solutions while searching. The solution pool generally has two functions: (1) For solvers that can return more than one solution, this limits how many solutions will be returned. (2) Some solvers may run heuristics using solutions from the solution pool, so changing this value may affect the algorithm's path. To force the solver to fill the solution pool, e.g. with the n best solutions, requires further, solver specific configuration.

SolveResultProto

The contract of when primal/dual solutions/rays is complex, see termination_reasons.md for a complete description.

Until an exact contract is finalized, it is safest to simply check if a solution/ray is present rather than relying on the termination reason.

Fields
`termination`	`TerminationProto` The reason the solver stopped.
`solutions[]`	`SolutionProto` 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.
`primal_rays[]`	`PrimalRayProto` Directions of unbounded primal improvement, or equivalently, dual infeasibility certificates. Typically provided for TerminationReasonProtos UNBOUNDED and DUAL_INFEASIBLE
`dual_rays[]`	`DualRayProto` Directions of unbounded dual improvement, or equivalently, primal infeasibility certificates. Typically provided for TerminationReasonProto INFEASIBLE.
`solve_stats`	`SolveStatsProto` Statistics on the solve process, e.g. running time, iterations.

SolveStatsProto

Fields
`solve_time`	`Duration` Elapsed wall clock time as measured by math_opt, roughly the time inside Solver::Solve(). Note: this does not include work done building the model.
`problem_status`	`ProblemStatusProto` Feasibility statuses for primal and dual problems.
`simplex_iterations`	`int64`
`barrier_iterations`	`int64`
`first_order_iterations`	`int64`
`node_count`	`int64`

SolverTypeProto

The solvers supported by MathOpt.

Enums
`SOLVER_TYPE_UNSPECIFIED`
`SOLVER_TYPE_GSCIP`	Solving Constraint Integer Programs (SCIP) solver (third party). Supports LP, MIP, and nonconvex integer quadratic problems. No dual data for LPs is returned though. Prefer GLOP for LPs.
`SOLVER_TYPE_GUROBI`	Gurobi solver (third party). Supports LP, MIP, and nonconvex integer quadratic problems. Generally the fastest option, but has special licensing.
`SOLVER_TYPE_GLOP`	Google's Glop solver. Supports LP with primal and dual simplex methods.
`SOLVER_TYPE_CP_SAT`	Google's CP-SAT solver. Supports problems where all variables are integer and bounded (or implied to be after presolve). Experimental support to rescale and discretize problems with continuous variables.
`SOLVER_TYPE_PDLP`	Google's PDLP solver. Supports LP and convex diagonal quadratic objectives. Uses first order methods rather than simplex. Can solve very large problems.
`SOLVER_TYPE_GLPK`	GNU Linear Programming Kit (GLPK) (third party). Supports MIP and LP. Thread-safety: GLPK use thread-local storage for memory allocations. As a consequence Solver instances must be destroyed on the same thread as they are created or GLPK will crash. It seems OK to call Solver::Solve() from another thread than the one used to create the Solver but it is not documented by GLPK and should be avoided. When solving a LP with the presolver, a solution (and the unbound rays) are only returned if an optimal solution has been found. Else nothing is returned. See glpk-5.0/doc/glpk.pdf page #40 available from glpk-5.0.tar.gz for details.
`SOLVER_TYPE_OSQP`	The Operator Splitting Quadratic Program (OSQP) solver (third party). Supports continuous problems with linear constraints and linear or convex quadratic objectives. Uses a first-order method.
`SOLVER_TYPE_ECOS`	The Embedded Conic Solver (ECOS) (third party). Supports LP and SOCP problems. Uses interior point methods (barrier).
`SOLVER_TYPE_SCS`	The Splitting Conic Solver (SCS) (third party). Supports LP and SOCP problems. Uses a first-order method.
`SOLVER_TYPE_HIGHS`	The HiGHS Solver (third party). Supports LP and MIP problems (convex QPs are unimplemented).
`SOLVER_TYPE_SANTORINI`	MathOpt's reference implementation of a MIP solver. Slow/not recommended for production. Not an LP solver (no dual information returned).

SosConstraintProto

Data for representing a single SOS1 or SOS2 constraint.

If a variable involved in this constraint is deleted, it is treated as if it were set to zero.

Fields

Fields
`expressions[]`	`LinearExpressionProto` The expressions over which to apply the SOS constraint: * SOS1: At most one element takes a nonzero value. * SOS2: At most two elements take nonzero values, and they must be adjacent in the repeated ordering.
`weights[]`	`double` Either empty or of equal length to expressions. If empty, default weights are 1, 2, ... If present, the entries must be unique.
`name`	`string` Parent messages may have uniqueness requirements on this field; e.g., see ModelProto.sos1_constraints and SosConstraintUpdatesProto.new_constraints.

expressions[]

LinearExpressionProto

The expressions over which to apply the SOS constraint: * SOS1: At most one element takes a nonzero value. * SOS2: At most two elements take nonzero values, and they must be adjacent in the repeated ordering.

weights[]

double

Either empty or of equal length to expressions. If empty, default weights are 1, 2, ... If present, the entries must be unique.

name

string

Parent messages may have uniqueness requirements on this field; e.g., see ModelProto.sos1_constraints and SosConstraintUpdatesProto.new_constraints.

SparseBasisStatusVector

A sparse representation of a vector of basis statuses.

Fields

Fields
`ids[]`	`int64` Must be sorted (in increasing ordering) with all elements distinct.
`values[]`	`BasisStatusProto` Must have equal length to ids.

ids[]

int64

Must be sorted (in increasing ordering) with all elements distinct.

values[]

BasisStatusProto

Must have equal length to ids.

SparseDoubleMatrixProto

A sparse representation of a matrix of doubles.

The matrix is stored as triples of row id, column id, and coefficient. These three vectors must be of equal length. For all i, the tuple (row_ids[i], column_ids[i]) should be distinct. Entries must be in row major order.

Fields

Fields
`row_ids[]`	`int64`
`column_ids[]`	`int64`
`coefficients[]`	`double` May not contain NaN.

row_ids[]

int64

column_ids[]

int64

coefficients[]

double

May not contain NaN.

SparseDoubleVectorProto

A sparse representation of a vector of doubles.

Fields

Fields
`ids[]`	`int64` Must be sorted (in increasing ordering) with all elements distinct.
`values[]`	`double` Must have equal length to ids. May not contain NaN.

ids[]

int64

Must be sorted (in increasing ordering) with all elements distinct.

values[]

double

Must have equal length to ids. May not contain NaN.

SparseInt32VectorProto

A sparse representation of a vector of ints.

Fields

Fields
`ids[]`	`int64` Should be sorted (in increasing ordering) with all elements distinct.
`values[]`	`int32` Must have equal length to ids.

ids[]

int64

Should be sorted (in increasing ordering) with all elements distinct.

values[]

int32

Must have equal length to ids.

SparseVectorFilterProto

This message allows to query/set specific parts of a SparseXxxxVector. The default behavior is not to filter out anything. A common usage is to query only parts of solutions (only non-zero values, and/or just a hand-picked set of variable values).

Fields

Fields
`skip_zero_values`	`bool` For SparseBoolVectorProto "zero" is `false`.
`filter_by_ids`	`bool` When true, return only the values corresponding to the IDs listed in filtered_ids.
`filtered_ids[]`	`int64` The list of IDs to use when filter_by_ids is true. Must be empty when filter_by_ids is false. NOTE: if this is empty, and filter_by_ids is true, you are saying that you do not want any information in the result.

skip_zero_values

bool

For SparseBoolVectorProto "zero" is false.

filter_by_ids

bool

When true, return only the values corresponding to the IDs listed in filtered_ids.

filtered_ids[]

int64

The list of IDs to use when filter_by_ids is true. Must be empty when filter_by_ids is false. NOTE: if this is empty, and filter_by_ids is true, you are saying that you do not want any information in the result.

TerminationProto

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

Fields
`reason`	`TerminationReasonProto` Additional information in `limit` when value is TERMINATION_REASON_FEASIBLE or TERMINATION_REASON_NO_SOLUTION_FOUND, see `limit` for details.
`limit`	`LimitProto` Is LIMIT_UNSPECIFIED unless reason is TERMINATION_REASON_FEASIBLE or TERMINATION_REASON_NO_SOLUTION_FOUND. Not all solvers can always determine the limit which caused termination, LIMIT_UNDETERMINED is used when the cause cannot be determined.
`detail`	`string` Additional typically solver specific information about termination.
`problem_status`	`ProblemStatusProto` Feasibility statuses for primal and dual problems. As of July 18, 2023 this message may be missing. If missing, problem_status can be found in SolveResultProto.solve_stats.
`objective_bounds`	`ObjectiveBoundsProto` Bounds on the optimal objective value. As of July 18, 2023 this message may be missing. If missing, objective_bounds.primal_bound can be found in SolveResultProto.solve.stats.best_primal_bound and objective_bounds.dual_bound can be found in SolveResultProto.solve.stats.best_dual_bound

TerminationReasonProto

The reason a call to Solve() terminates.

Enums
`TERMINATION_REASON_UNSPECIFIED`
`TERMINATION_REASON_OPTIMAL`	A provably optimal solution (up to numerical tolerances) has been found.
`TERMINATION_REASON_INFEASIBLE`	The primal problem has no feasible solutions.
`TERMINATION_REASON_UNBOUNDED`	The primal problem is feasible and arbitrarily good solutions can be found along a primal ray.
`TERMINATION_REASON_INFEASIBLE_OR_UNBOUNDED`	The primal problem is either infeasible or unbounded. More details on the problem status may be available in solve_stats.problem_status. Note that Gurobi's unbounded status may be mapped here.
`TERMINATION_REASON_IMPRECISE`	The problem was solved to one of the criteria above (Optimal, Infeasible, Unbounded, or InfeasibleOrUnbounded), but one or more tolerances was not met. Some primal/dual solutions/rays be present, but either they will be slightly infeasible, or (if the problem was nearly optimal) their may be a gap between the best solution objective and best objective bound. Users can still query primal/dual solutions/rays and solution stats, but they are responsible for dealing with the numerical imprecision.
`TERMINATION_REASON_FEASIBLE`	The optimizer reached some kind of limit and a primal feasible solution is returned. See SolveResultProto.limit_detail for detailed description of the kind of limit that was reached.
`TERMINATION_REASON_NO_SOLUTION_FOUND`	The optimizer reached some kind of limit and it did not find a primal feasible solution. See SolveResultProto.limit_detail for detailed description of the kind of limit that was reached.
`TERMINATION_REASON_NUMERICAL_ERROR`	The algorithm stopped because it encountered unrecoverable numerical error. No solution information is available.
`TERMINATION_REASON_OTHER_ERROR`	The algorithm stopped because of an error not covered by one of the statuses defined above. No solution information is available.

VariablesProto

As used below, we define "#variables" = size(VariablesProto.ids).

Fields
`ids[]`	`int64` Must be nonnegative and strictly increasing. The max(int64) value can't be used.
`lower_bounds[]`	`double` Should have length equal to #variables, values in [-inf, inf).
`upper_bounds[]`	`double` Should have length equal to #variables, values in (-inf, inf].
`integers[]`	`bool` Should have length equal to #variables. Value is false for continuous variables and true for integer variables.
`names[]`	`string` If not set, assumed to be all empty strings. Otherwise, should have length equal to #variables. All nonempty names must be distinct.