Documentation

Solve Attributes

From the solver outcomes like solving time and primal and dual gaps, PAVER computes additional values.

Gaps

The gap specifies the relative gap between the primal and dual bounds reported by a solver. The gap between two values a and b is computed as $$ gap(a,b) = \begin{cases}0, & \textrm{if } |a-b| < tol, \\ \infty, & \textrm{if } \min(|a|,|b|)\lt tol, \\ \infty, & \textrm{if } \max(|a|,|b|)\gt\infty, \\ \infty, & \textrm{if } a\, b\lt 0, \\ \frac{a-b}{\min(|a|,|b|)}, & \textrm{otherwise,} \end{cases} $$ where tol is by default 1e-9. For instances with known optimal value, also the gap between primal and dual bound to optimal value are computed. These are denoted as primal gap and dual gap, respectively.

Integrals

If the progress of primal and/or dual bound during the solving progress is available, e.g., in form of a GAMS solvetrace file, PAVER can compute the primal integral, dual integral, and primal-dual integral [Berthold] from this information.
These values are computed as follows. Let $ t_0=0 \leq t_1 \leq \ldots \leq t_n = T $ be the points in time when information about the primal and dual bounds are available and denote these values as $p(t)$ and $d(t)$, respectively. Let $ opt $ be the known optimal value. Then the primal integral is obtained by integrating the relative difference of $p(t)$ and $ opt $ over the time: $$ \sum_{i=1}^n (t_i - t_{i-1})\cdot \min(|gap(p(t),opt)|, 1.0) $$ Analogously, the dual integral is obtained by integrating the relative difference of $d(t)$ and $ opt $ over the time: $$ \sum_{i=1}^n (t_i - t_{i-1})\cdot \min(|gap(opt,d(t))|, 1.0) $$ Finally, the primal-dual integral is obtained by integrating the relative difference of $p(t)$ and $d(t)$ over the time: $$ \sum_{i=1}^n (t_i - t_{i-1})\cdot \min(|gap(p(t),d(t))|, 1.0) $$ Note, that the formula we use for the gap is different from the one used in [Berthold] (we divide by the minimum of primal and dual bound, while [Berthold] divides by the maximum).

Statistics

Absolute Statistics

For a solve attribute and a filter, a table like the following may be shown:
Attribute values were projected onto interval [1.0, inf].

SolverA SolverB SolverC virt. best virt. worst
count 77.00 77.00 72.00 77.00 72.00
arith. mean 68.18 57.22 100.82 52.67 106.86
arith. std. 175.63 154.20 156.22 154.20 166.77
geom. mean 10.99 10.51 29.22 8.21 32.62
geom. std. 5.92 5.94 5.84 5.91 5.42
sh.geom. mean 18.52 18.20 41.58 14.96 44.22
sh.geom. std. 3.11 2.90 3.30 2.86 3.29
min 1.00 1.00 1.00 1.00 1.18
10.0% 1.38 1.02 2.46 1.00 2.85
25.0% 2.81 1.99 10.00 1.79 10.79
50.0% 7.92 8.68 36.12 7.46 37.47
75.0% 26.50 40.18 98.39 24.00 119.52
90.0% 175.49 125.89 386.89 97.70 386.89
max 912.34 902.50 663.14 902.50 667.91
geometric mean shift: 10.0

These numbers have the following meaning:

The virtual best and virtual worst solvers are computed instance-wise from the values of all solvers. If some solver does not provide a value, also the virtual worst one does not.

Bar charts for counts and mean values may be shown, too. Further, a box plot may plot the attribute values for each solver, together with the median (red line), 25% quantile (lower edge of the blue box), 75% quantile (upper edge of the blue box), the lowest data point still within 1.5 * (75%-quantile - 25%-quantile) of the 25% quantile (the lower whisker), the largest data point still within 1.5 * (75%-quantile - 25%-quantile) of the 75% quantile (the upper whisker), and data points that are beyond the whiskers (the outliers).

Relative Statistics

For a solve attribute, a filter, and a reference solver, a table like the following may be shown:
Performance with respect to virt. best:
Tolerance: relative 0.1 absolute 1.0
SolverA SolverB SolverC virt. worst
count 68.00 68.00 68.00 68.00
arith. mean 1.48 1.73 19.38 19.63
arith. std. 0.83 2.95 82.38 82.33
min 1.00 1.00 1.00 1.18
10.0% 1.00 1.00 1.03 1.35
25.0% 1.00 1.00 1.58 2.20
50.0% 1.02 1.00 3.81 4.12
75.0% 1.53 1.27 7.67 7.67
90.0% 2.74 1.97 20.93 20.93
max 5.08 24.22 642.43 642.43
better 0.00 0.00 0.00 0.00
close 46.00 45.00 13.00 6.00
worse 22.00 23.00 55.00 62.00

These numbers have the following meaning:

Performance Profiles

The performance profiles plot the number of instances (w.r.t. the current filter) for which a certain value is below x for increasing x. For an absolute performance profile, the value is the value of the solve attribute. For a relative performance profile [Dolan, Moré], the value is the ratio of the solve attribute value of the solver to the minimal one among all solvers. For an extended performance porfile [Mahajan, Leyffer, Kirches], the value is the ratio of the solve attribute value of the solver to the minimal one among all other solvers.

References