package operations_research.pdlp

Get desktop application:
View/edit binary Protocol Buffers messages

At the end of each iteration, regardless of whether the step was accepted or not, the adaptive rule updates the step_size as the minimum of two potential step sizes defined by the following two exponents.

Used in: PrimalDualHybridGradientParams

• optional double step_size_reduction_exponent = 1

  The step size reduction exponent defines a step size given by (1 - (total_steps_attempted + 1)^(-step_size_reduction_exponent)) * step_size_limit where step_size_limit is the maximum allowed step size at the current iteration. This should be between 0.1 and 1.

• optional double step_size_growth_exponent = 2

  The step size growth exponent defines a step size given by (1 + (total_steps_attempted + 1)^(-step_size_growth_exponent)) * step_size_. This should be between 0.1 and 1.

Information measuring how close a candidate is to establishing feasibility and optimality; see also TerminationCriteria.

Used in: math_opt.SolveResultProto.PdlpOutput, IterationStats

• optional PointType candidate_type = 1

  Type of the candidate point described by this ConvergenceInformation.

• optional double primal_objective = 2

  The primal objective. The primal need not be feasible.

• optional double dual_objective = 3

  The dual objective. The dual need not be feasible. The dual objective includes the contributions from reduced costs. NOTE: The definition of dual_objective changed in OR-tools version 9.8. See https://developers.google.com/optimization/lp/pdlp_math#reduced_costs_dual_residuals_and_the_corrected_dual_objective for details.

• optional double corrected_dual_objective = 4

  If possible (e.g., when all primal variables have lower and upper bounds), a correct dual bound. The value is negative infinity if no corrected dual bound is available.

• optional double l_inf_primal_residual = 5

  The maximum violation of any primal constraint, i.e., the l_∞ norm of the violations.

• optional double l2_primal_residual = 6

  The l_2 norm of the violations of primal constraints.

• optional double l_inf_componentwise_primal_residual = 24

  The maximum relative violation of any primal constraint, with an absolute offset, i.e., the l_∞ norm of [violation / (eps_ratio + |bound|)] where eps_ratio = eps_optimal_primal_residual_absolute / eps_optimal_primal_residual_relative and bound is the violated bound.

• optional double l_inf_dual_residual = 7

  The maximum violation of any dual constraint, i.e., the l_∞ norm of the violations.

• optional double l2_dual_residual = 8

  The l_2 norm of the violations of dual constraints.

• optional double l_inf_componentwise_dual_residual = 25

  The maximum relative violation of any dual constraint, with an absolute offset, i.e., the l_∞ norm of [violation / (eps_ratio + |objective|)] where eps_ratio = eps_optimal_dual_residual_absolute / eps_optimal_dual_residual_relative

• optional double l_inf_primal_variable = 14

  The maximum absolute value of the primal variables, i.e., the l_∞ norm. This is useful to detect when the primal iterates are diverging. Divergence of the primal variables could be an algorithmic issue, or indicate that the dual is infeasible.

• optional double l2_primal_variable = 15

  The l_2 norm of the primal variables.

• optional double l_inf_dual_variable = 16

  The maximum absolute value of the dual variables, i.e., the l_∞ norm. This is useful to detect when the dual iterates are diverging. Divergence of the dual variables could be an algorithmic issue, or indicate the primal is infeasible.

• optional double l2_dual_variable = 17

  The l_2 norm of the dual variables.

Details about one primal feasibility or dual feasibility polishing phase within a solve with `use_feasibility_polishing`. See `SolveLog` for descriptions of the fields with the same name.

Used in: SolveLog

• optional PolishingPhaseType polishing_phase_type = 1

• optional int32 main_iteration_count = 2

  The iteration count for the main iteration when this feasibility polishing phase was triggered.

• optional PrimalDualHybridGradientParams params = 3

• optional TerminationReason termination_reason = 4

• optional int32 iteration_count = 5

• optional double solve_time_sec = 6

• optional IterationStats solution_stats = 7

• optional PointType solution_type = 8

• repeated IterationStats iteration_stats = 9

Information measuring how close a point is to establishing primal or dual infeasibility (i.e. has no solution); see also TerminationCriteria.

Used in: IterationStats

• optional double max_primal_ray_infeasibility = 1

  Let x_ray be the algorithm's estimate of the primal extreme ray where x_ray is a vector that satisfies the sign constraints for a ray, scaled such that its infinity norm is one (the sign constraints are the variable bound constraints, with all finite bounds mapped to zero). A simple and typical choice of x_ray is x_ray = x / | x |_∞ where x is the current primal iterate projected onto the primal ray sign constraints. For this value compute the maximum absolute error in the primal linear program with the right hand side set to zero.

• optional double primal_ray_linear_objective = 2

  The value of the linear part of the primal objective (ignoring additive constants) evaluated at x_ray, i.e., c' * x_ray where c is the objective coefficient vector.

• optional double primal_ray_quadratic_norm = 3

  The l_∞ norm of the vector resulting from taking the quadratic matrix from primal objective and multiplying it by the primal variables. For linear programming problems this is zero.

• optional double max_dual_ray_infeasibility = 4

  Let (y_ray, r_ray) be the algorithm's estimate of the dual and reduced cost extreme ray where (y_ray, r_ray) is a vector (satisfying the dual variable constraints) scaled such that its infinity norm is one. A simple and typical choice of y_ray is (y_ray, r_ray) = (y, r) / max(| y |_∞, | r |_∞) where y is the current dual iterate and r is the current dual reduced costs. Consider the quadratic program we are solving but with the objective (both quadratic and linear terms) set to zero. This forms a linear program (label this linear program (1)) with no objective. Take the dual of (1) and compute the maximum absolute value of the constraint error for (y_ray, r_ray) to obtain the value of max_dual_ray_infeasibility.

• optional double dual_ray_objective = 5

  The objective of the linear program labeled (1) in the previous paragraph.

• optional PointType candidate_type = 6

  Type of the point used to compute the InfeasibilityInformation.

All values in IterationStats assume that the primal quadratic program is a minimization problem and the dual is a maximization problem. Problems should be transformed to this form if they are not already in this form. The dual vector is defined to be the vector of multipliers on the linear constraints, that is, excluding dual multipliers on variable bounds (reduced costs).

Used in: FeasibilityPolishingDetails, SolveLog

• optional int32 iteration_number = 1

  The iteration number at which these stats were recorded. By convention, iteration counts start at 1, and the stats correspond to the solution *after* the iteration. Therefore stats from iteration 0 are the stats at the starting point.

• repeated ConvergenceInformation convergence_information = 2

  A set of statistics measuring how close a point is to establishing primal and dual feasibility and optimality. This field is repeated since there might be several different points that are considered.

• repeated InfeasibilityInformation infeasibility_information = 3

  A set of statistics measuring how close a point is to establishing primal or dual infeasibility (i.e., has no solution). This field is repeated since there might be several different points that could establish infeasibility.

• repeated PointMetadata point_metadata = 11

  Auxiliary statistics for each type of point.

• optional double cumulative_kkt_matrix_passes = 4

  The cumulative number of passes through the KKT matrix since the start of the solve. One pass is a multply by the constraint matrix, its transpose and the matrix that defines the quadratic part of the objective. For example, each iteration of mirror saddle prox contributes 2.0 to this sum. This is a float because it can include fractional passes through the data. For example, in an active set method we may only use a submatrix with 20% of the nonzeros of the KKT matrix at each iteration in which case 0.2 would be added to the total.

• optional int32 cumulative_rejected_steps = 5

  The total number of rejected steps (e.g., within a line search procedure) since the start of the solve.

• optional double cumulative_time_sec = 6

  The amount of time passed since we started solving the problem (see solver log `solve_time_sec` which records total time).

• optional RestartChoice restart_used = 7

  The kind of restart that occurred at this iteration, or NO_RESTART if a restart did not occur.

• optional double step_size = 8

  Step size used at this iteration. Note that the step size used for the primal update is step_size / primal_weight, while the one used for the dual update is step_size * primal_weight.

• optional double primal_weight = 9

  Primal weight controlling the relation between primal and dual step sizes. See field 'step_size' for a detailed description.

Used in: PrimalDualHybridGradientParams

• optional double step_size_downscaling_factor = 1

  At every inner iteration the algorithm can decide to accept the step size or to update it to step_size = step_size_downscaling_factor * step_size. This parameter should lie between 0 and 1. The default is the value used in Malitsky and Pock (2016).

• optional double linesearch_contraction_factor = 2

  Contraction factor used in the linesearch condition of Malitsky and Pock. A step size is accepted if primal_weight * primal_stepsize * norm(constraint_matrix' * (next_dual - current_dual)) is less than linesearch_contraction_factor * norm(next_dual - current_dual). The default is the value used in Malitsky and Pock (2016).

• optional double step_size_interpolation = 3

  Malitsky and Pock linesearch rule permits an arbitrary choice of the first step size guess within an interval [m, M]. This parameter determines where in that interval to pick the step size. In particular, the next stepsize is given by m + step_size_interpolation*(M - m). The default is the value used in Malitsky and Pock (2016).

Used in: TerminationCriteria

• OPTIMALITY_NORM_UNSPECIFIED = 0

• OPTIMALITY_NORM_L_INF = 1

  The infinity norm.

• OPTIMALITY_NORM_L2 = 2

  The Euclidean norm.

• OPTIMALITY_NORM_L_INF_COMPONENTWISE = 3

  The infinity norm of component-wise relative errors offset by the ratio of the absolute and relative error tolerances, i.e., the l_∞ norm of [residual / (eps_ratio + |bound|)], where eps_ratio = eps_optimal_{X}_residual_absolute / eps_optimal_{X}_residual_relative where {X} is either primal or dual, and bound is the corresponding primal or dual bound (that is, the violated constraint bound for primal residuals, and the objective coefficient for dual residuals). Using eps_ratio in this norm means that if the norm is <= eps_optimal_{X}_residual_relative, then the residuals satisfy residual <= eps_optimal_{X}_residual_absolute + eps_optimal_{X}_residual_relative * |bound|

Used in: IterationStats

• optional PointType point_type = 1

  Type of the point that this metadata corresponds to.

• repeated double random_primal_projections = 2

  Projections of the primal solution onto random planes.

• repeated double random_dual_projections = 3

  Projections of the dual solution onto random planes.

• optional int64 active_primal_variable_count = 4

  The number of primal variables that are not at their bounds.

• optional int64 active_dual_variable_count = 5

  The number of dual variables that are not at their bounds.

• optional int64 active_primal_variable_change = 6

  The number of primal variables that have a different bound status than they did at the last restart.

• optional int64 active_dual_variable_change = 7

  The number of dual variables that have a different bound status than they did at the last restart.

Identifies the type of point used to compute the fields in a given proto; see ConvergenceInformation and InfeasibilityInformation.

Used in: ConvergenceInformation, FeasibilityPolishingDetails, InfeasibilityInformation, PointMetadata, SolveLog

• POINT_TYPE_UNSPECIFIED = 0

• POINT_TYPE_CURRENT_ITERATE = 1

  Current iterate (x_k, y_k).

• POINT_TYPE_ITERATE_DIFFERENCE = 2

  Difference of iterates (x_{k+1} - x_k, y_{k+1} - y_k).

• POINT_TYPE_AVERAGE_ITERATE = 3

  Average of iterates since the last restart.

• POINT_TYPE_NONE = 4

  There is no corresponding point.

• POINT_TYPE_PRESOLVER_SOLUTION = 5

  Output of presolver.

• POINT_TYPE_FEASIBILITY_POLISHING_SOLUTION = 6

  Combined solution from primal and dual feasibility polishing.

Used in: FeasibilityPolishingDetails

• POLISHING_PHASE_TYPE_UNSPECIFIED = 0

• POLISHING_PHASE_TYPE_PRIMAL_FEASIBILITY = 1

• POLISHING_PHASE_TYPE_DUAL_FEASIBILITY = 2

Parameters for PrimalDualHybridGradient() in primal_dual_hybrid_gradient.h. While the defaults are generally good, it is usually worthwhile to perform a parameter sweep to find good settings for a particular family of problems. The following parameters should be considered for tuning: - restart_strategy (jointly with major_iteration_frequency) - primal_weight_update_smoothing (jointly with initial_primal_weight) - presolve_options.use_glop - l_inf_ruiz_iterations - l2_norm_rescaling In addition, tune num_threads to speed up the solve.

Used in: math_opt.SolveParametersProto, FeasibilityPolishingDetails, SolveLog

• optional TerminationCriteria termination_criteria = 1

• optional int32 num_threads = 2

  The number of threads to use. Must be positive. Try various values of num_threads, up to the number of physical cores. Performance may not be monotonically increasing with the number of threads because of memory bandwidth limitations.

• optional int32 num_shards = 27

  For more efficient parallel computation, the matrices and vectors are divided (virtually) into num_shards shards. Results are computed independently for each shard and then combined. As a consequence, the order of computation, and hence floating point roundoff, depends on the number of shards so reproducible results require using the same value for num_shards. However, for efficiency num_shards should a be at least num_threads, and preferably at least 4*num_threads to allow better load balancing. If num_shards is positive, the computation will use that many shards. Otherwise a default that depends on num_threads will be used.

• optional SchedulerType scheduler_type = 32

  The type of scheduler used for CPU multi-threading. See the documentation of the corresponding enum for more details.

• optional bool record_iteration_stats = 3

  If true, the iteration_stats field of the SolveLog output will be populated at every iteration. Note that we only compute solution statistics at termination checks. Setting this parameter to true may substantially increase the size of the output.

• optional int32 verbosity_level = 26

  The verbosity of logging. 0: No informational logging. (Errors are logged.) 1: Summary statistics only. No iteration-level details. 2: A table of iteration-level statistics is logged. (See ToShortString() in primal_dual_hybrid_gradient.cc). 3: A more detailed table of iteration-level statistics is logged. (See ToString() in primal_dual_hybrid_gradient.cc). 4: For iteration-level details, prints the statistics of both the average (prefixed with A) and the current iterate (prefixed with C). Also prints internal algorithmic state and details. Logging at levels 2-4 also includes messages from level 1.

• optional double log_interval_seconds = 31

  Time between iteration-level statistics logging (if `verbosity_level > 1`). Since iteration-level statistics are only generated when performing termination checks, logs will be generated from next termination check after `log_interval_seconds` have elapsed. Should be >= 0.0. 0.0 (the default) means log statistics at every termination check.

• optional int32 major_iteration_frequency = 4

  The frequency at which extra work is performed to make major algorithmic decisions, e.g., performing restarts and updating the primal weight. Major iterations also trigger a termination check. For best performance using the NO_RESTARTS or EVERY_MAJOR_ITERATION rule, one should perform a log-scale grid search over this parameter, for example, over powers of two. ADAPTIVE_HEURISTIC is mostly insensitive to this value.

• optional int32 termination_check_frequency = 5

  The frequency (based on a counter reset every major iteration) to check for termination (involves extra work) and log iteration stats. Termination checks do not affect algorithmic progress unless termination is triggered.

• optional PrimalDualHybridGradientParams.RestartStrategy restart_strategy = 6

  NO_RESTARTS and EVERY_MAJOR_ITERATION occasionally outperform the default. If using a strategy other than ADAPTIVE_HEURISTIC, you must also tune major_iteration_frequency.

• optional double primal_weight_update_smoothing = 7

  This parameter controls exponential smoothing of log(primal_weight) when a primal weight update occurs (i.e., when the ratio of primal and dual step sizes is adjusted). At 0.0, the primal weight will be frozen at its initial value and there will be no dynamic updates in the algorithm. At 1.0, there is no smoothing in the updates. The default of 0.5 generally performs well, but has been observed on occasion to trigger unstable swings in the primal weight. We recommend also trying 0.0 (disabling primal weight updates), in which case you must also tune initial_primal_weight.

• optional double initial_primal_weight = 8

  The initial value of the primal weight (i.e., the ratio of primal and dual step sizes). The primal weight remains fixed throughout the solve if primal_weight_update_smoothing = 0.0. If unset, the default is the ratio of the norm of the objective vector to the L2 norm of the combined constraint bounds vector (as defined above). If this ratio is not finite and positive, then the default is 1.0 instead. For tuning, try powers of 10, for example, from 10^{-6} to 10^6.

• optional PrimalDualHybridGradientParams.PresolveOptions presolve_options = 16

• optional int32 l_inf_ruiz_iterations = 9

  Number of L_infinity Ruiz rescaling iterations to apply to the constraint matrix. Zero disables this rescaling pass. Recommended values to try when tuning are 0, 5, and 10.

• optional bool l2_norm_rescaling = 10

  If true, applies L_2 norm rescaling after the Ruiz rescaling. Heuristically this has been found to help convergence.

• optional double sufficient_reduction_for_restart = 11

  For ADAPTIVE_HEURISTIC and ADAPTIVE_DISTANCE_BASED only: A relative reduction in the potential function by this amount always triggers a restart. Must be between 0.0 and 1.0.

• optional double necessary_reduction_for_restart = 17

  For ADAPTIVE_HEURISTIC only: A relative reduction in the potential function by this amount triggers a restart if, additionally, the quality of the iterates appears to be getting worse. The value must be in the interval [sufficient_reduction_for_restart, 1). Smaller values make restarts less frequent, and larger values make them more frequent.

• optional PrimalDualHybridGradientParams.LinesearchRule linesearch_rule = 12

  Linesearch rule applied at each major iteration.

• optional AdaptiveLinesearchParams adaptive_linesearch_parameters = 18

• optional MalitskyPockParams malitsky_pock_parameters = 19

• optional double initial_step_size_scaling = 25

  Scaling factor applied to the initial step size (all step sizes if linesearch_rule == CONSTANT_STEP_SIZE_RULE).

• repeated int32 random_projection_seeds = 28

  Seeds for generating (pseudo-)random projections of iterates during termination checks. For each seed, the projection of the primal and dual solutions onto random planes in primal and dual space will be computed and added the IterationStats if record_iteration_stats is true. The random planes generated will be determined by the seeds, the primal and dual dimensions, and num_threads.

• optional double infinite_constraint_bound_threshold = 22

  Constraint bounds with absolute value at least this threshold are replaced with infinities. NOTE: This primarily affects the relative convergence criteria. A smaller value makes the relative convergence criteria stronger. It also affects the problem statistics LOG()ed at the start of the run, and the default initial primal weight, since that is based on the norm of the bounds.

• optional bool handle_some_primal_gradients_on_finite_bounds_as_residuals = 29

  See https://developers.google.com/optimization/lp/pdlp_math#treating_some_variable_bounds_as_infinite for a description of this flag.

• optional bool use_diagonal_qp_trust_region_solver = 23

  When solving QPs with diagonal objective matrices, this option can be turned on to enable an experimental solver that avoids linearization of the quadratic term. The `diagonal_qp_solver_accuracy` parameter controls the solve accuracy. TODO(user): Turn this option on by default for quadratic programs after numerical evaluation.

• optional double diagonal_qp_trust_region_solver_tolerance = 24

  The solve tolerance of the experimental trust region solver for diagonal QPs, controlling the accuracy of binary search over a one-dimensional scaling parameter. Smaller values imply smaller relative error of the final solution vector. TODO(user): Find an expression for the final relative error.

• optional bool use_feasibility_polishing = 30

  If true, periodically runs feasibility polishing, which attempts to move from latest average iterate to one that is closer to feasibility (i.e., has smaller primal and dual residuals) while probably increasing the objective gap. This is useful primarily when the feasibility tolerances are fairly tight and the objective gap tolerance is somewhat looser. Note that this does not change the termination criteria, but rather can help achieve the termination criteria more quickly when the objective gap is not as important as feasibility. `use_feasibility_polishing` cannot be used with glop presolve, and requires `handle_some_primal_gradients_on_finite_bounds_as_residuals == false`. `use_feasibility_polishing` can only be used with linear programs. Feasibility polishing runs two separate phases, primal feasibility and dual feasibility. The primal feasibility phase runs PDHG on the primal feasibility problem (obtained by changing the objective vector to all zeros), using the average primal iterate and zero dual (which is optimal for the primal feasibility problem) as the initial solution. The dual feasibility phase runs PDHG on the dual feasibility problem (obtained by changing all finite variable and constraint bounds to zero), using the average dual iterate and zero primal (which is optimal for the dual feasibility problem) as the initial solution. The primal solution from the primal feasibility phase and dual solution from the dual feasibility phase are then combined (forming a solution of type `POINT_TYPE_FEASIBILITY_POLISHING_SOLUTION`) and checked against the termination criteria.

• optional bool apply_feasibility_polishing_after_limits_reached = 33

  If true, feasibility polishing will be applied after the iteration limit, kkt limit, or time limit is reached. This can result in a solution that is closer to feasibility, at the expense of violating the limit by a moderate amount.

• optional bool apply_feasibility_polishing_if_solver_is_interrupted = 34

  If true, feasibility polishing will be applied after the solver is interrupted. This can result in a solution that is closer to feasibility, at the expense of not stopping as promptly when interrupted.

Used in: PrimalDualHybridGradientParams

• LINESEARCH_RULE_UNSPECIFIED = 0

• ADAPTIVE_LINESEARCH_RULE = 1

  Applies the heuristic rule presented in Section 3.1 of https://arxiv.org/pdf/2106.04756.pdf (further generalized to QP). There is not a proof of convergence for it. It is usually the fastest in practice but sometimes behaves poorly.

• MALITSKY_POCK_LINESEARCH_RULE = 2

  Applies Malitsky & Pock linesearch rule. This guarantees an ergodic O(1/N) convergence rate https://arxiv.org/pdf/1608.08883.pdf. This is provably convergent but doesn't usually work as well in practice as ADAPTIVE_LINESEARCH_RULE.

• CONSTANT_STEP_SIZE_RULE = 3

  Uses a constant step size corresponding to an estimate of the maximum singular value of the constraint matrix.

Used in: PrimalDualHybridGradientParams

• optional bool use_glop = 1

  If true runs Glop's presolver on the given instance prior to solving. Note that convergence criteria are still interpreted with respect to the original problem. Certificates may not be available if presolve detects infeasibility. Glop's presolver cannot apply to problems with quadratic objectives or problems with more than 2^31 variables or constraints. It's often beneficial to enable the presolver, especially on medium-sized problems. At some larger scales, the presolver can become a serial bottleneck.

• optional glop.GlopParameters glop_parameters = 2

  Parameters to control glop's presolver. Only used when use_glop is true. These are merged with and override PDLP's defaults.

Used in: PrimalDualHybridGradientParams

• RESTART_STRATEGY_UNSPECIFIED = 0

• NO_RESTARTS = 1

  No restarts are performed. The average solution is cleared every major iteration, but the current solution is not changed.

• EVERY_MAJOR_ITERATION = 2

  On every major iteration, the current solution is reset to the average since the last major iteration.

• ADAPTIVE_HEURISTIC = 3

  A heuristic that adaptively decides on every major iteration whether to restart (this is forced approximately on increasing powers-of-two iterations), and if so to the current or to the average, based on reduction in a potential function. The rule more or less follows the description of the adaptive restart scheme in https://arxiv.org/pdf/2106.04756.pdf.

• ADAPTIVE_DISTANCE_BASED = 4

  A distance-based restarting scheme that restarts the algorithm whenever an appropriate potential function is reduced sufficiently. This check happens at every major iteration. TODO(user): Cite paper for the restart strategy and definition of the potential function, when available.

Easy-to-compute statistics for the quadratic program.

Used in: SolveLog

• optional int64 num_variables = 1

• optional int64 num_constraints = 2

• optional double constraint_matrix_col_min_l_inf_norm = 3

  Minimum row and column infinity norms of the constraint matrix. All-zero rows and columns are excluded. If the constraint matrix contains no nonzero entries, the values returned are 0.0.

• optional double constraint_matrix_row_min_l_inf_norm = 4

• optional int64 constraint_matrix_num_nonzeros = 5

  The number of (finite) nonzero entries in the constraint matrix.

• optional double constraint_matrix_abs_max = 6

  Max/min/mean/l2_norm of absolute values of (finite) elements in constraint matrix. Explicit zeros are included in the mean, but excluded from the min. Note that the maximum absolute value is also equal to the maximal row and column infinity norms of the constraint matrix. If the constraint matrix is empty, the values returned are 0.0 for the maximum, minimum, and l2_norm, and NaN for the average.

• optional double constraint_matrix_abs_min = 7

• optional double constraint_matrix_abs_avg = 8

• optional double constraint_matrix_l2_norm = 25

• optional double combined_bounds_max = 9

  Statistics of the combined vector of the constraint lower and upper bounds. Given parallel lower and upper bounds vectors, the "combined bounds" vector takes the maximum absolute value of each pair of bounds, ignoring all non- finite values. The comment in solvers.proto:TerminationCriteria provides an example of the combined bounds vector. The min is over the nonzero combined bounds. If there are no constraints, the values returned are 0 for the maximum, minimum, and l2 norm and NaN for the average.

• optional double combined_bounds_min = 10

• optional double combined_bounds_avg = 11

• optional double combined_bounds_l2_norm = 24

• optional double combined_variable_bounds_max = 28

  Statistics of the combined vector of the variable lower and upper bounds. See the comment before `combined_bounds_max` for a description of the "combined bounds" vector. The min is over the nonzero combined bounds. If there are no variables, the values returned are 0 for the maximum, minimum, and l2 norm and NaN for the average.

• optional double combined_variable_bounds_min = 29

• optional double combined_variable_bounds_avg = 30

• optional double combined_variable_bounds_l2_norm = 31

• optional int64 variable_bound_gaps_num_finite = 12

  Number of finite variable bound gaps, which are the elementwise difference between the upper and lower bounds on primal feasible solutions.

• optional double variable_bound_gaps_max = 13

  Max/min/mean/l2_norm over all finite variable bound gaps. The min excludes zero bound gaps (i.e., fixed variables). When there are no finite gaps, the values returned are 0 for the maximum, minimum, and l2_norm, and NaN for the average.

• optional double variable_bound_gaps_min = 14

• optional double variable_bound_gaps_avg = 15

• optional double variable_bound_gaps_l2_norm = 26

• optional double objective_vector_abs_max = 16

  Statistics of the objective vector. The min is over the nonzero terms.

• optional double objective_vector_abs_min = 17

• optional double objective_vector_abs_avg = 18

• optional double objective_vector_l2_norm = 23

• optional int64 objective_matrix_num_nonzeros = 19

• optional double objective_matrix_abs_max = 20

  Max/min/mean/l2_norm of absolute values of elements of the objective matrix. The min is over nonzero terms. If the objective matrix is empty, the returned values are 0.0, 0.0, NaN, and 0.0 respectively.

• optional double objective_matrix_abs_min = 21

• optional double objective_matrix_abs_avg = 22

• optional double objective_matrix_l2_norm = 27

Specifies whether a restart was performed on a given iteration.

Used in: IterationStats

• RESTART_CHOICE_UNSPECIFIED = 0

• RESTART_CHOICE_NO_RESTART = 1

  No restart on this iteration.

• RESTART_CHOICE_WEIGHTED_AVERAGE_RESET = 2

  The weighted average of iterates is cleared and reset to the current point. Note that from a mathematical perspective this can be equivalently viewed as restarting the algorithm but picking the restart point to be the current iterate.

• RESTART_CHOICE_RESTART_TO_AVERAGE = 3

  The algorithm is restarted at the average of iterates since the last restart.

The type of system used to schedule CPU threads to do work in parallel.

Used in: PrimalDualHybridGradientParams

• SCHEDULER_TYPE_UNSPECIFIED = 0

• SCHEDULER_TYPE_GOOGLE_THREADPOOL = 1

  Google ThreadPool with barrier synchronization.

• SCHEDULER_TYPE_EIGEN_THREADPOOL = 3

  Eigen non-blocking ThreadPool with barrier synchronization (see <Eigen/ThreadPool>) that uses Google threads.

• optional string instance_name = 1

  The name of the optimization problem.

• optional PrimalDualHybridGradientParams params = 14

  If solved with PDLP, the parameters for this solve.

• optional TerminationReason termination_reason = 3

  The reason that the solve terminated.

• optional string termination_string = 4

  Optional extra information about the termination reason.

• optional int32 iteration_count = 5

  The total number of iterations during the solve. For a solve with `use_feasibility_polishing` this count includes the iterations from the feasibility polishing phases.

• optional double preprocessing_time_sec = 13

  Time for preprocessing (everything before iteration 0). This is also included in `solve_time_sec`.

• optional double solve_time_sec = 6

  The runtime of the solve. Note: This should not be used for comparing methods unless care is taken to control for noise in runtime measurement. For a solve with `use_feasibility_polishing` this count includes the iterations from the feasibility polishing phases.

• optional IterationStats solution_stats = 8

  The `IterationStats` for the final iteration of the solver. For a solve with `use_feasibility_polishing`, the work metrics (iteration_count, cumulative_kkt_matrix_passes, etc.) will include the work done in the feasibility polishing phases. NOTE: Regardless of preprocessing (i.e. scaling or presolve) the optimality or infeasibility information is evaluated with respect to the original problem.

• optional PointType solution_type = 10

  The type of the output point that the solver returned. The quality of the point is reported in the corresponding entry of solution_stats.convergence_information and/or solution_stats.infeasibility_information. If termination_reason is TERMINATION_REASON_OPTIMAL, it's guaranteed that the corresponding entry of solution_stats.convergence_information satisfies the optimality conditions. Similarly, if termination_reason is either TERMINATION_REASON_PRIMAL_INFEASIBLE or TERMINATION_REASON_DUAL_INFEASIBLE the corresponding entry of solution_stats.infeasibility_information satisifes conditions for declaring primal or dual infeasibility, respectively. If termination_reason is anything else, e.g. TERMINATION_REASON_TIME_LIMIT or TERMINATION_REASON_PRIMAL_OR_DUAL_INFEASIBLE, the solution may not satisfy the optimality or infeasibility conditions.

• repeated IterationStats iteration_stats = 7

  A history of iteration stats for the solve. The iteration_number fields should be in increasing order. The frequency at which these stats should be recorded is not specified. This field is "more" optional than the others because it often significantly increases the size of the message, and because the information may not be available for third-party solvers. For a solve with `use_feasibility_polishing`, these iteration stats will only reflect the work done in the main iterations (not the feasibility polishing phases).

• optional QuadraticProgramStats original_problem_stats = 11

  Statistics of the original problem.

• optional QuadraticProgramStats preprocessed_problem_stats = 12

  Statistics of the problem after preprocessing.

• repeated FeasibilityPolishingDetails feasibility_polishing_details = 15

  If solving with `use_feasibility_polishing`, details about the primal and dual feasibility polishing phases.

Relevant readings on infeasibility certificates: (1) https://docs.mosek.com/modeling-cookbook/qcqo.html provides references explaining why the primal rays imply dual infeasibility and dual rays imply primal infeasibility. (2) The termination criteria for Mosek's linear programming optimizer https://docs.mosek.com/9.0/pythonfusion/solving-linear.html. (3) The termination criteria for OSQP is in section 3.3 of https://web.stanford.edu/~boyd/papers/pdf/osqp.pdf. (4) The termination criteria for SCS is in section 3.5 of https://arxiv.org/pdf/1312.3039.pdf.

Used in: PrimalDualHybridGradientParams

• optional OptimalityNorm optimality_norm = 1

  The norm that we are measuring the optimality criteria in.

• oneof optimality_criteria

  If none are set explicitly the deprecated eps_optimal_absolute and eps_optimal_relative are used to construct a SimpleOptimalityCriteria.

  • TerminationCriteria.SimpleOptimalityCriteria simple_optimality_criteria = 9

  • TerminationCriteria.DetailedOptimalityCriteria detailed_optimality_criteria = 10

• optional double eps_optimal_absolute = 2

  Absolute tolerance on primal residual, dual residual, and the objective gap. Deprecated, use simple_optimality_criteria instead. TODO(b/241462829) delete this deprecated field.

• optional double eps_optimal_relative = 3

  Relative tolerance on primal residual, dual residual, and the objective gap. Deprecated, use simple_optimality_criteria instead. TODO(b/241462829) delete this deprecated field.

• optional double eps_primal_infeasible = 4

  If the following two conditions hold we say that we have obtained an approximate dual ray, which is an approximate certificate of primal infeasibility. (1) dual_ray_objective > 0, (2) max_dual_ray_infeasibility / dual_ray_objective <= eps_primal_infeasible.

• optional double eps_dual_infeasible = 5

  If the following three conditions hold we say we have obtained an approximate primal ray, which is an approximate certificate of dual infeasibility. (1) primal_ray_linear_objective < 0, (2) max_primal_ray_infeasibility / (-primal_ray_linear_objective) <= eps_dual_infeasible (3) primal_ray_quadratic_norm / (-primal_ray_linear_objective) <= eps_dual_infeasible.

• optional double time_sec_limit = 6

  If termination_reason = TERMINATION_REASON_TIME_LIMIT then the solver has taken at least time_sec_limit time.

• optional int32 iteration_limit = 7

  If termination_reason = TERMINATION_REASON_ITERATION_LIMIT then the solver has taken at least iterations_limit iterations.

• optional double kkt_matrix_pass_limit = 8

  If termination_reason = TERMINATION_REASON_KKT_MATRIX_PASS_LIMIT then cumulative_kkt_matrix_passes is at least kkt_pass_limit.

Used in: TerminationCriteria

• optional double eps_optimal_primal_residual_absolute = 1

  Absolute tolerance on the primal residual.

• optional double eps_optimal_primal_residual_relative = 2

  Relative tolerance on the primal residual.

• optional double eps_optimal_dual_residual_absolute = 3

  Absolute tolerance on the dual residual.

• optional double eps_optimal_dual_residual_relative = 4

  Relative tolerance on the dual residual.

• optional double eps_optimal_objective_gap_absolute = 5

  Absolute tolerance on the objective gap.

• optional double eps_optimal_objective_gap_relative = 6

  Relative tolerance on the objective gap.

Used in: TerminationCriteria

• optional double eps_optimal_absolute = 1

  Absolute tolerance on the primal residual, dual residual, and objective gap.

• optional double eps_optimal_relative = 2

  Relative tolerance on the primal residual, dual residual, and objective gap.

Used in: FeasibilityPolishingDetails, SolveLog

• TERMINATION_REASON_UNSPECIFIED = 0

• TERMINATION_REASON_OPTIMAL = 1

• TERMINATION_REASON_PRIMAL_INFEASIBLE = 2

  Note in this situation the dual could be either unbounded or infeasible.

• TERMINATION_REASON_DUAL_INFEASIBLE = 3

  Note in this situation the primal could be either unbounded or infeasible.

• TERMINATION_REASON_TIME_LIMIT = 4

• TERMINATION_REASON_ITERATION_LIMIT = 5

• TERMINATION_REASON_KKT_MATRIX_PASS_LIMIT = 8

• TERMINATION_REASON_INTERRUPTED_BY_USER = 12

• TERMINATION_REASON_NUMERICAL_ERROR = 6

• TERMINATION_REASON_INVALID_PROBLEM = 9

  Indicates that the solver detected invalid problem data, e.g., inconsistent bounds.

• TERMINATION_REASON_INVALID_INITIAL_SOLUTION = 13

  Indicates that the solver detected that the initial solution that was provided was invalid, e.g., wrong size or containing NAN or inf.

• TERMINATION_REASON_INVALID_PARAMETER = 10

  Indicates that an invalid value for the parameters was detected.

• TERMINATION_REASON_OTHER = 7

• TERMINATION_REASON_PRIMAL_OR_DUAL_INFEASIBLE = 11

  Primal or dual infeasibility was detected (e.g. by presolve) but no certificate is available.