# Sparse Mathematical Programming (SMP) Repository

## Applications

We assemble a repository for sparse QP problems of different scales, most of which come from applications in animation, geometry processing, and simulation. An overview of the repository is provided in the SMP page. Here we explain the storage format that is used in the Sparse Mathematical Programming repository (SMP) and also, the corresponding I/O routines of the format. We also explain how SMP is used in NASOQ benchmark to fairly compare different QP solvers across SMP problems.

## SMP storage format

Sparse Mathematical Programming (SMP) format aims for providing a unified and readable format that is compatible with existing sparse matrix formats such as matrix market format.
SMP uses the YAML format to serialize the matrices of a QP problem into a single unified file in a readable format.

An example SMP format is shown below:

```
Description": |
Sparse Mathematical Programming Repository
ID = 00000
category = Control
application = example
name = test01
group = test
source =
author = Kazem Cheshmi
date = 06/20
"Fixed": |
0
"Inequality": |
%%MatrixMarket matrix coordinate real symmetric
3 2 4
1 1 10
2 1 1
1 2 -1
3 2 1
"Inequality l-bounds": |
%%MatrixMarket matrix array real general
3 1
10
2
-50
"Inequality u-bounds": |
%%MatrixMarket matrix array real general
3 1
inf
10
10
"Linear": |
%%MatrixMarket matrix array real general
2 1
0
0
"Quadratic": |
%%MatrixMarket matrix coordinate real symmetric
2 2 2
1 1 2
2 2 2
```

As shown a QP problem in the SMP format is stored in the general form of:
\begin{align}
\min_x \quad \frac{1}{2} x^THx + q^Tx \quad \text{s.t.}
\quad Ax=b, \quad l \leq C' x\leq u
\end{align}
that is more compressed than the general form that NASOQ supports which we call *general inequality/equality form (IE)* and is shown below:
\begin{align}
\min_x \quad \frac{1}{2} x^THx + q^Tx \quad \text{s.t.}
\quad Ax=b, \quad C x\leq d
\end{align}
and also more compressed than another general form that we we call *general bounded form (bounded)* and is illustrated below:

These three representations lead to the same optimal solution however, they are different in terms of storage requirements and also the number of iterations that one solver might need to solve the problem.

### SMP conversion

We developed a repository for converting different representations of a QP problem, i.e., IE and Bounded forms to SMP and also from SMP to others. The repository does not have any dependency and to install:

```
git clone https://github.com/sympiler/smp-format
cd smp-format
mkdir build
cd build
cmake -DCMAKE_BUILD_TYPE=Release ..
make
```

After building, three drivers, i.e., `ie2smp`

, `bounded2smp`

, and `smp-convertor`

will be available. The `ie2smp`

driver takes all matrices of a QP problem in IE format which are stored in matrix market format and generates an SMP format.
The `bounded2smp`

driver takes all matrices of a QP instance in the bounded format which are again stored in matrix market format and generates an SMP format.
The `smp-convertor`

shows an example of how SMP format is used as an intermediate format to convert every two formats together.

## NASOQ benchmark

We also developed a unified framework to run all solvers with their settings for the problems in the SMP repository. The installation of the benchmark depends on the solvers that are added and their dependencies. The instructions for installing the benchmark is provided in the nasoq-benchmarks.

### Adding a new solver

Adding a new solver to the benchmark is easy.

The *first* step is to write a driver for the solver that takes an SMP format and generates the inputs that are needed for the solver. Three examples for OSQP, NASOQ, and Gurobi are provided in drivers subdirectory. As explained, the SMP repository provides support for different QP formats so they can be easily used here.

The *second* step is to update the CMake file in the `drivers`

subdirectory by adding a new project that builds the driver for the new solver.

The *third* step is to add a line to the `run_all.sh`

script, as shown below:

```
echo "Running [The name of the new solver] ..."
bash scripts/NASOQ_bench.sh $BUILDIR/drivers/[New-solver-bin] $DATASET $eps "-v [if it has a variant]"> logs/new-solver-e${eps}.csv
```

The `run_all`

script runs all installed solvers for the specified dataset and the requested accuracy and generates the performance profile graphs.