Pre-code thoughts, benchmark scope and goals

[stephane-caron]

The benchmark reported in the README only targets a limited number of problems and does not provide a fair comparison between solvers. For instance, solvers with default settings that return less precise solutions faster are advantaged if we only look at out-of-the-box computation time.

We will improve on this in qpsolvers/qpsolvers#70 following the methodology proposed in the OSQP paper and reproduced in proxqp_benchmark.

This thread is here to discuss work items and exchange feedback. Share your thoughts so that we converge on a meaningful bench!

Scope

• Target audience: non-expert users who compare QP solvers before committing to one
• Output: a Markdown report stored in benchmark/results.md with summary reported to README.md
• Cold start only (we can add warm start in a later iteration)
• Dense and sparse problems
• Include the Maros-Meszaros test set

Metrics

• Success rate on test set problems
• Computation time (cold start: build and solve included)
• Primal accuracy

Validation

Solutions can be validated by casting all inequalities to $l \leq C x \leq u$ and checking that, at the primal-dual solution $(x^*, y^*)$,

$$ \begin{align} \Vert (C x^* - u)_{+} + (C x^* - l)_{-} \Vert_\infty & \leq \epsilon_{abs} \\ \Vert P x^* + q + A^T y^* \Vert_\infty & \leq \epsilon_{\mathit{abs}} \end{align} $$

where $\epsilon_{abs}$ is an absolute tolerance parameter. We could check three settings, such as lax ($\epsilon_{abs} = 10^{-3}$), medium ($\epsilon_{abs} = 10^{-5}$) and high accuracy ($\epsilon_{abs} = 10^{-7}$).

See also

• OSQP paper where the validation process was proposed
• jrl-qp/benchmarks
• proxqp_benchmark