package operations_research.service.v1.mathopt

Get desktop application:
View/edit binary Protocol Buffers messages

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.

Used in: ModelSolveParametersProto, SolutionProto

• optional SparseBasisStatusVector constraint_status = 1

  Constraint basis status. Requirements: * constraint_status.ids is equal to LinearConstraints.ids.

• optional SparseBasisStatusVector variable_status = 2

  Variable basis status. Requirements: * constraint_status.ids is equal to VariablesProto.ids.

• SolutionStatusProto basic_dual_feasibility = 3

  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.

Status of a variable/constraint in a LP basis.

Used in: SparseBasisStatusVector

• BASIS_STATUS_UNSPECIFIED = 0

  Guard value representing no status.

• BASIS_STATUS_FREE = 1

  The variable/constraint is free (it has no finite bounds).

• BASIS_STATUS_AT_LOWER_BOUND = 2

  The variable/constraint is at its lower bound (which must be finite).

• BASIS_STATUS_AT_UPPER_BOUND = 3

  The variable/constraint is at its upper bound (which must be finite).

• BASIS_STATUS_FIXED_VALUE = 4

  The variable/constraint has identical finite lower and upper bounds.

• BASIS_STATUS_BASIC = 5

  The variable/constraint is basic.

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.

Used in: SolveResultProto

• optional SparseDoubleVectorProto dual_values = 1

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

• optional SparseDoubleVectorProto reduced_costs = 2

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

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.

Used in: SolutionProto

• optional SparseDoubleVectorProto dual_values = 1

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

• optional SparseDoubleVectorProto reduced_costs = 2

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

• optional double objective_value = 3

  TODO(b/195295177): consider making this non-optional Objective value as computed by the underlying solver.

• SolutionStatusProto feasibility_status = 4

  Feasibility status of the solution according to the underlying solver.

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.

Used in: SolveParametersProto

• EMPHASIS_UNSPECIFIED = 0

• EMPHASIS_OFF = 1

• EMPHASIS_LOW = 2

• EMPHASIS_MEDIUM = 3

• EMPHASIS_HIGH = 4

• EMPHASIS_VERY_HIGH = 5

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

Used in: ProblemStatusProto

• FEASIBILITY_STATUS_UNSPECIFIED = 0

  Guard value representing no status.

• FEASIBILITY_STATUS_UNDETERMINED = 1

  Solver does not claim a status.

• FEASIBILITY_STATUS_FEASIBLE = 2

  Solver claims the problem is feasible.

• FEASIBILITY_STATUS_INFEASIBLE = 3

  Solver claims the problem is infeasible.

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.

Used in: ModelProto

• optional int64 indicator_id = 1

  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.

• bool activate_on_zero = 6

  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.

• optional SparseDoubleVectorProto expression = 2

  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`.

• double lower_bound = 3

  Must have value in [-inf, inf); cannot be NaN.

• double upper_bound = 4

  Must have value in (-inf, inf]; cannot be NaN.

• string name = 5

  Parent messages may have uniqueness requirements on this field; e.g., see `ModelProto.indicator_constraints` and `IndicatorConstraintUpdatesProto.new_constraints`.

Selects an algorithm for solving linear programs.

Used in: SolveParametersProto

• LP_ALGORITHM_UNSPECIFIED = 0

• LP_ALGORITHM_PRIMAL_SIMPLEX = 1

  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 = 2

  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 = 3

  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 = 4

  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.

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

Used in: TerminationProto

• LIMIT_UNSPECIFIED = 0

  Used as a null value when we terminated not from a limit (e.g. TERMINATION_REASON_OPTIMAL).

• LIMIT_UNDETERMINED = 1

  The underlying solver does not expose which limit was reached.

• LIMIT_ITERATION = 2

  An iterative algorithm stopped after conducting the maximum number of iterations (e.g. simplex or barrier iterations).

• LIMIT_TIME = 3

  The algorithm stopped after a user-specified computation time.

• LIMIT_NODE = 4

  A branch-and-bound algorithm stopped because it explored a maximum number of nodes in the branch-and-bound tree.

• LIMIT_SOLUTION = 5

  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 = 6

  The algorithm stopped because it ran out of memory.

• LIMIT_CUTOFF = 12

  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 = 7

  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 = 8

  The algorithm stopped because the norm of an iterate became too large.

• LIMIT_INTERRUPTED = 9

  The algorithm stopped because of an interrupt signal or a user interrupt request.

• LIMIT_SLOW_PROGRESS = 10

  The algorithm stopped because it was unable to continue making progress towards the solution.

• LIMIT_OTHER = 11

  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.

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

Used in: ModelProto

• repeated int64 ids = 1

  Must be nonnegative and strictly increasing. The max(int64) value can't be used.

• repeated double lower_bounds = 2

  Should have length equal to #linear constraints, values in [-inf, inf).

• repeated double upper_bounds = 3

  Should have length equal to #linear constraints, values in (-inf, inf].

• repeated string names = 4

  If not set, assumed to be all empty strings. Otherwise, should have length equal to #linear constraints. All nonempty names must be distinct. TODO(b/169575522): we may relax this.

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

Used in: SecondOrderConeConstraintProto, SosConstraintProto

• repeated int64 ids = 1

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

• repeated double coefficients = 2

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

• double offset = 3

  Must be finite and may not be NaN.

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.

Used in: SolveMathOptModelRequest

• string name = 1

• optional VariablesProto variables = 2

• optional ObjectiveProto objective = 3

  The primary objective in the model.

• map<int64, ObjectiveProto> auxiliary_objectives = 10

  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`.

• optional LinearConstraintsProto linear_constraints = 4

• optional SparseDoubleMatrixProto linear_constraint_matrix = 5

  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.

• map<int64, QuadraticConstraintProto> quadratic_constraints = 6

  Quadratic constraints in the model.

• map<int64, SecondOrderConeConstraintProto> second_order_cone_constraints = 11

  Second-order cone constraints in the model.

• map<int64, SosConstraintProto> sos1_constraints = 7

  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.

• map<int64, SosConstraintProto> sos2_constraints = 8

  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.

• map<int64, IndicatorConstraintProto> indicator_constraints = 9

  Indicator constraints in the model, which enforce that, if a binary "indicator variable" is set to one, then an "implied constraint" must hold.

TODO(b/183628247): follow naming convention in fields below. Parameters to control a single solve that that are specific to the input model (see SolveParametersProto for model independent parameters).

Used in: SolveMathOptModelRequest

• optional SparseVectorFilterProto variable_values_filter = 1

  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.

• optional SparseVectorFilterProto dual_values_filter = 2

  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.

• optional SparseVectorFilterProto reduced_costs_filter = 3

  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.

• optional BasisProto initial_basis = 4

  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`.

• repeated SolutionHintProto solution_hints = 5

  Optional solution hints. If the underlying solver only accepts a single hint, the first hint is used.

• optional SparseInt32VectorProto branching_priorities = 6

  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.

Bounds on the optimal objective value.

Used in: TerminationProto

• double primal_bound = 2

  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).

• double dual_bound = 3

  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.

Used in: ModelProto

• bool maximize = 1

  false is minimize, true is maximize

• double offset = 2

  Must be finite and not NaN.

• optional SparseDoubleVectorProto linear_coefficients = 3

  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.

• optional SparseDoubleMatrixProto quadratic_coefficients = 4

  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.

• string name = 5

  Parent messages may have uniqueness requirements on this field; e.g., see ModelProto.objectives and AuxiliaryObjectivesUpdatesProto.new_objectives.

• int64 priority = 6

  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.

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.

Used in: SolveResultProto

• optional SparseDoubleVectorProto variable_values = 1

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

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.

Used in: SolutionProto

• optional SparseDoubleVectorProto variable_values = 1

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

• double objective_value = 2

  Objective value as computed by the underlying solver. Cannot be infinite or NaN.

• map<int64, double> auxiliary_objective_values = 4

  Auxiliary objective values as computed by the underlying solver. Keys must be valid auxiliary objective IDs. Values cannot be infinite or NaN.

• SolutionStatusProto feasibility_status = 3

  Feasibility status of the solution according to the underlying solver.

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.

Used in: SolveStatsProto, TerminationProto

• FeasibilityStatusProto primal_status = 1

  Status for the primal problem.

• FeasibilityStatusProto dual_status = 2

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

• bool primal_or_dual_infeasible = 3

  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).

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.

Used in: ModelProto

• optional SparseDoubleVectorProto linear_terms = 1

  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.

• optional SparseDoubleMatrixProto quadratic_terms = 2

  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.

• double lower_bound = 3

  Must have value in [-inf, inf), and be less than or equal to `upper_bound`.

• double upper_bound = 4

  Must have value in (-inf, inf], and be greater than or equal to `lower_bound`.

• string name = 5

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

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.

Used in: ModelProto

• optional LinearExpressionProto upper_bound = 1

• repeated LinearExpressionProto arguments_to_norm = 2

• string name = 3

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

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). TODO(b/183616124): Add hint-priorities to variable_values.

Used in: ModelSolveParametersProto

• optional SparseDoubleVectorProto variable_values = 1

  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.

• optional SparseDoubleVectorProto dual_values = 2

  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.

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.

Used in: SolveResultProto

• optional PrimalSolutionProto primal_solution = 1

• optional DualSolutionProto dual_solution = 2

• optional BasisProto basis = 3

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

Used in: BasisProto, DualSolutionProto, PrimalSolutionProto

• SOLUTION_STATUS_UNSPECIFIED = 0

  Guard value representing no status.

• SOLUTION_STATUS_UNDETERMINED = 1

  Solver does not claim a feasibility status.

• SOLUTION_STATUS_FEASIBLE = 2

  Solver claims the solution is feasible.

• SOLUTION_STATUS_INFEASIBLE = 3

  Solver claims the solution is infeasible.

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.

Used in: SolveMathOptModelRequest

• optional google.protobuf.Duration time_limit = 1

  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.

• optional int64 iteration_limit = 2

  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.

• optional int64 node_limit = 24

  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.

• optional double cutoff_limit = 20

  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.

• optional double objective_limit = 21

  The solver stops early as soon as it finds a solution at least this good, with termination reason FEASIBLE and limit OBJECTIVE.

• optional double best_bound_limit = 22

  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.

• optional int32 solution_limit = 23

  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.

• bool enable_output = 3

  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.

• optional int32 threads = 4

  If set, it must be >= 1.

• optional int32 random_seed = 5

  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)).

• optional double absolute_gap_tolerance = 18

  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.

• optional double relative_gap_tolerance = 17

  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.

• optional int32 solution_pool_size = 25

  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.

• LPAlgorithmProto lp_algorithm = 6

  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).

• EmphasisProto presolve = 7

  Effort on simplifying the problem before starting the main algorithm, or the solver default effort level if EMPHASIS_UNSPECIFIED.

• EmphasisProto cuts = 8

  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.

• EmphasisProto heuristics = 9

  Effort in finding feasible solutions beyond those encountered in the complete search procedure (MIP only), or the solver default effort level if EMPHASIS_UNSPECIFIED.

• EmphasisProto scaling = 10

  Effort in rescaling the problem to improve numerical stability, or the solver default effort level if EMPHASIS_UNSPECIFIED.

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.

Used in: SolveMathOptModelResponse

• optional TerminationProto termination = 2

  The reason the solver stopped.

• repeated SolutionProto solutions = 3

  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.

• repeated PrimalRayProto primal_rays = 4

  Directions of unbounded primal improvement, or equivalently, dual infeasibility certificates. Typically provided for TerminationReasonProtos UNBOUNDED and DUAL_INFEASIBLE

• repeated DualRayProto dual_rays = 5

  Directions of unbounded dual improvement, or equivalently, primal infeasibility certificates. Typically provided for TerminationReasonProto INFEASIBLE.

• optional SolveStatsProto solve_stats = 6

  Statistics on the solve process, e.g. running time, iterations.

Used in: SolveResultProto

• optional google.protobuf.Duration solve_time = 1

  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.

• optional ProblemStatusProto problem_status = 4

  Feasibility statuses for primal and dual problems.

• int64 simplex_iterations = 5

• int64 barrier_iterations = 6

• int64 first_order_iterations = 8

• int64 node_count = 7

This message is used to specify some hints on the resources a remote solve is expected to use. These parameters are hints and may be ignored by the remote server (in particular in case of solve in a local subprocess, for example). When using SolveService.Solve and SolveService.ComputeInfeasibleSubsystem, these hints are mostly optional as some defaults will be computed based on the other parameters. When using SolveService.StreamSolve these hints are used to dimension the resources available during the execution of every action; thus it is recommended to set them.

Used in: SolveMathOptModelRequest

• optional double cpu = 1

  The number of CPUs this solve should be allocated (time-averaged over a short implementation-defined window). Must be finite and >=1.0. Note that if the SolveParametersProto.threads is not set then this parameter should also be left unset.

• optional double ram = 2

  The limit of RAM for the solve in bytes. Must be finite and >=512000.

The solvers supported by MathOpt.

Used in: SolveMathOptModelRequest

• SOLVER_TYPE_UNSPECIFIED = 0

• SOLVER_TYPE_GSCIP = 1

  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 = 2

  Gurobi solver (third party). Supports LP, MIP, and nonconvex integer quadratic problems. Generally the fastest option, but has special licensing.

• SOLVER_TYPE_GLOP = 3

  Google's Glop solver. Supports LP with primal and dual simplex methods.

• SOLVER_TYPE_CP_SAT = 4

  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 = 5

  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 = 6

  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 = 7

  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 = 8

  The Embedded Conic Solver (ECOS) (third party). Supports LP and SOCP problems. Uses interior point methods (barrier).

• SOLVER_TYPE_SCS = 9

  The Splitting Conic Solver (SCS) (third party). Supports LP and SOCP problems. Uses a first-order method.

• SOLVER_TYPE_HIGHS = 10

  The HiGHS Solver (third party). Supports LP and MIP problems (convex QPs are unimplemented).

• SOLVER_TYPE_SANTORINI = 11

  MathOpt's reference implementation of a MIP solver. Slow/not recommended for production. Not an LP solver (no dual information returned).

• SOLVER_TYPE_XPRESS = 12

  Fico XPRESS solver (third party). Supports LP, MIP, and nonconvex integer quadratic problems. A fast option, but has special licensing.

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.

Used in: ModelProto

• repeated LinearExpressionProto expressions = 1

  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.

• repeated double weights = 2

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

• string name = 3

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

A sparse representation of a vector of basis statuses.

Used in: BasisProto

• repeated int64 ids = 1

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

• repeated BasisStatusProto values = 2

  Must have equal length to ids.

A sparse representation of a vector of bools.

• repeated int64 ids = 1

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

• repeated bool values = 2

  Must have equal length to ids.

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.

Used in: ModelProto, ObjectiveProto, QuadraticConstraintProto

• repeated int64 row_ids = 1

• repeated int64 column_ids = 2

• repeated double coefficients = 3

  May not contain NaN.

A sparse representation of a vector of doubles.

Used in: DualRayProto, DualSolutionProto, IndicatorConstraintProto, ObjectiveProto, PrimalRayProto, PrimalSolutionProto, QuadraticConstraintProto, SolutionHintProto

• repeated int64 ids = 1

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

• repeated double values = 2

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

A sparse representation of a vector of ints.

Used in: ModelSolveParametersProto

• repeated int64 ids = 1

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

• repeated int32 values = 2

  Must have equal length to ids.

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).

Used in: ModelSolveParametersProto

• bool skip_zero_values = 1

  For SparseBoolVectorProto "zero" is `false`.

• bool filter_by_ids = 2

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

• repeated int64 filtered_ids = 3

  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.

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

Used in: SolveResultProto

• TerminationReasonProto reason = 1

  Additional information in `limit` when value is TERMINATION_REASON_FEASIBLE or TERMINATION_REASON_NO_SOLUTION_FOUND, see `limit` for details.

• LimitProto limit = 2

  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.

• string detail = 3

  Additional typically solver specific information about termination.

• optional ProblemStatusProto problem_status = 4

  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.

• optional ObjectiveBoundsProto objective_bounds = 5

  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

The reason a call to Solve() terminates.

Used in: TerminationProto

• TERMINATION_REASON_UNSPECIFIED = 0

• TERMINATION_REASON_OPTIMAL = 1

  A provably optimal solution (up to numerical tolerances) has been found.

• TERMINATION_REASON_INFEASIBLE = 2

  The primal problem has no feasible solutions.

• TERMINATION_REASON_UNBOUNDED = 3

  The primal problem is feasible and arbitrarily good solutions can be found along a primal ray.

• TERMINATION_REASON_INFEASIBLE_OR_UNBOUNDED = 4

  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 = 5

  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 = 9

  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 = 6

  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 = 7

  The algorithm stopped because it encountered unrecoverable numerical error. No solution information is available.

• TERMINATION_REASON_OTHER_ERROR = 8

  The algorithm stopped because of an error not covered by one of the statuses defined above. No solution information is available.

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

Used in: ModelProto

• repeated int64 ids = 1

  Must be nonnegative and strictly increasing. The max(int64) value can't be used.

• repeated double lower_bounds = 2

  Should have length equal to #variables, values in [-inf, inf).

• repeated double upper_bounds = 3

  Should have length equal to #variables, values in (-inf, inf].

• repeated bool integers = 4

  Should have length equal to #variables. Value is false for continuous variables and true for integer variables.

• repeated string names = 5

  If not set, assumed to be all empty strings. Otherwise, should have length equal to #variables. All nonempty names must be distinct. TODO(b/169575522): we may relax this.