QP solvers benchmark

Benchmark for quadratic programming (QP) solvers available in Python.

The goal of this benchmark is to help us compare and select QP solvers. Its methodology is open to discussions. New test sets are also welcome. Feel free to add one that better represents the kind of problems you are working on.

Solvers

Solver	Keyword	Algorithm	Matrices	License
Clarabel	`clarabel`	Interior point	Sparse	Apache-2.0
CVXOPT	`cvxopt`	Interior point	Dense	GPL-3.0
ECOS	`ecos`	Interior point	Sparse	GPL-3.0
Gurobi	`gurobi`	Interior point	Sparse	Commercial
HiGHS	`highs`	Active set	Sparse	MIT
MOSEK	`mosek`	Interior point	Sparse	Commercial
NPPro	`nppro`	Active set	Dense	Commercial
OSQP	`osqp`	Douglas–Rachford	Sparse	Apache-2.0
ProxQP	`proxqp`	Augmented Lagrangian	Dense & Sparse	BSD-2-Clause
qpOASES	`qpoases`	Active set	Dense	LGPL-2.1
qpSWIFT	`qpswift`	Interior point	Sparse	GPL-3.0
quadprog	`quadprog`	Goldfarb-Idnani	Dense	GPL-2.0
SCS	`scs`	Douglas–Rachford	Sparse	MIT

Test sets and results

The benchmark has different test sets that represent different use cases for QP solvers. Click on a test set to check out its report.

Test set	Keyword	Description
GitHub free-for-all	`github_ffa`	Test set built by the community on GitHub, new problems are welcome!
Maros-Meszaros	`maros_meszaros`	Standard set of problems designed to be difficult.
Maros-Meszaros dense	`maros_meszaros_dense`	Subset of the Maros-Meszaros test set restricted to smaller dense problems.

Metrics

We evaluate QP solvers based on the following metrics:

Success rate: percentage of problems a solver is able to solve on a given test set.
Computation time: time a solver takes to solve a given problem.
Optimality conditions: we evaluate all three optimality conditions:
- Primal residual: maximum error on equality and inequality constraints at the returned solution.
- Dual residual: maximum error on the dual feasibility condition at the returned solution.
- Duality gap: value of the duality gap at the returned solution.
Cost error: difference between the solution cost and the known optimal cost.

Shifted geometric mean

Each metric (computation time, primal and dual residuals, duality gap) produces a different ranking of solvers for each problem. To aggregate those rankings into a single metric over the whole test set, we use the shifted geometric mean (shm), which is a standard to aggregate computation times in benchmarks for optimization software. This mean has the advantage of being compromised by neither large outliers (as opposed to the arithmetic mean) nor by small outliers (in contrast to the geometric geometric mean). Check out the references below for further details.

Here are some intuitive interpretations:

A solver with a shifted-geometric-mean runtime of $Y$ is $Y$ times slower than the best solver over the test set.
A solver with a shifted-geometric-mean primal residual $R$ is $R$ times less accurate on equality and inequality constraints than the best solver over the test set.

Limitations

Here are some known areas of improvement for this benchmark:

Cold start only: we don't evaluate warm-start performance for now.

Check out the issue tracker for ongoing works and future improvements.

Installation

You can install the benchmark and its dependencies in an isolated environment using conda:

conda create -f environment.yaml
conda activate qpsolvers_benchmark

Alternatively, you can install the benchmark on your system using pip:

pip install qpsolvers_benchmark

By default, the benchmark will run all supported solvers it finds.

Running the benchmark

Once dependencies are installed, you will be able to run the main benchmark.py script from the repository. Pick up the keyword corresponding to the desired test set, for instance maros_meszaros, and pass it to the run command:

python benchmark.py maros_meszaros run

You can also run a specific solver, problem or set of solver settings:

python benchmark.py maros_meszaros_dense run --solver proxqp --settings default

Check out python benchmark.py --help for all available commands and arguments.

Plots

The command line ships a plot command to compare solver performances over a test set for a specific metric. For instance, run:

python benchmark.py maros_meszaros_dense plot runtime high_accuracy

To generate the following plot:

Contributing

Contributions to improving this benchmark are welcome. You can for instance propose new problems, or share the runtimes you obtain on your machine. Check out the contribution guidelines for details.

darnstrom / qpsolvers_benchmark Goto Github PK