How to (graphically) present computational results?

Question

I am interested in evaluating and demonstrating various aspects of the performance of general solvers for mathematical optimization problems (in particular MILPs). I assume that I have a good testset of instances. What "revealing" experiments should/could I perform, and more importantly, what graphical presentations can I provide to convey certain key aspects? These may refer to information on the testset, on the solver, on several different settings/versions of the solver, on particular aspects of the solver, etc. I am particularly interested in example figures from papers or talks.

Examples:

Performance variability displayed using the instance enlight13: 100 runs of the same instance, each time with differently permuted input, and resulting CPU times; taken from the MIPLIB2010 paper.

Performace profiles for different solvers on the same test set, the further "top left", the better.

What other graphical aids do you find enlightening when evaluating solvers?

Answer 1

Some further plots that can be helpful are bar charts with the type of solver going along the horizontal axis and the number of problem instances on the vertical axis. However, each bar is colour-coded with certain proportions that can indicate how "successful" a solver is compared to others.

Kronqvist et al. (2019) provide several such charts in their paper.

Figure 3 presents statistics regarding the termination of the solvers, e.g., how many errors and timeouts occurred. These values are as reported by the solver, but also include solver crashes where no solution was returned.

PAVER also verifies if the solver runs were completed successfully, e.g., by comparing the objective values returned to known values or bounds; if there is a discrepancy, these instances are given the status failed. Statistics on instances marked as failed are shown in Fig. 4.

Note that the environment used was PAVER 2.0, which is in fact open source. For further details see Bussieck et al. (2014).

Figure 5 shows the number of problems where the solver was able to obtain a solution within 0.1% and 1% of the best-known solution, but not necessarily able to verify optimality. The fgure shows that none of the solvers was able to obtain a solution within 1% of the best-known solution for all of the problems, given the 900 s time limit. For example, BARON was able to obtain a solution within 1% of the optimum for 317 problems, and SHOT obtained such a solution for 320 problems.

---

_References

_{[1] Kronqvist, J., Bernal, D. E., Lundell, A., Grossmann, I. E. (2019). A review and comparisons of solvers for convex MINLP. Optimization and Engineering. 20(2):397-455.}

_{[2] Bussieck, M. R., Dirkse, S. P., Vigerske, S. (2014). PAVER 2.0: an open source environment for automated performance analysis of benchmarking data. Journal of Global Optimization. 59(2-3):259-275.}

Answer 2

We've written a benchmark toolkit that spits out a html with a number of statistics we find useful. Of these, I'll highlight the ones that I use regularly in bold.

Over multiple datasets and multiple algorithms:

• Best Score Summary (Graph And Table) to see which algorithm works best
• Best Score Scalability Summary (Graph)
• Best Score Distribution Summary (Graph)
• Winning Score Difference Summary (Graph And Table)
• Worst Score Difference Percentage (ROI) Summary (Graph and Table) for talking to management stakeholders
• Score Calculation Speed Summary (Graph and Table): moves per second - it's a great way to determine constraint calculation efficiency
• Time Spent Summary (Graph And Table): most of the time, I am working within a fixed time budget, so this is useless then
• Time Spent Scalability Summary (Graph)
• Best Score Per Time Spent Summary (Graph)

Per dataset over multiple algorithms:

• Best Score Over Time Statistic (Graph And CSV): your second graph - this is by far, the most important graph for me
• Step Score Over Time Statistic (Graph And CSV): local search specific
• Score Calculation Speed over time Statistic (Graph And CSV)
• Best Solution Mutation Over Time Statistic (Graph And CSV): To see how much each new best solution differs from the previous best solution, by counting the number of planning variables which have a different value. In rare occasions this is very useful
• Move Count Per Step Statistic (Graph And CSV)
• Memory Use Statistic (Graph And CSV): Not as useful as you'd think in a JVM, due to inaccuracy. For day-to-day checks, I just use VisualVM. For accurate checks, I set up HonestProfiler.

Per dataset and algorithm combination:

• Constraint Match Total Best Score Over Time Statistic (Graph And CSV): To see which constraints are matched in the best score (and how much) over time
• Constraint Match Total Step Score Over Time Statistic (Graph And CSV)
• Picked Move Type Best Score Diff Over Time Statistic (Graph And CSV)
• Picked Move Type Step Score Diff Over Time Statistic (Graph And CSV)

Here's a VRP example of the 4 statistics in bold (reproducible with this app):

To see which algorithm worked best across the datasets:

To talk about Return On Investment to management:

To measure if the custom constraints are written efficiently:

To see where we should focus our time on to improve solution quality. The shape of this graph tells a lot. Notice here how the yellow Tabu Search gets temporarily stuck in local optima (a clear sign to invest is smarter neighborhoods). Notice how vanilla Late Acceptance is worst, but adding Nearby Selection in the mix, LA outperforms TS (which reminds me that we might want to write a paper on Nearby Selection, especially parabolic):

They all end up in a report like this:

Answer 3

There are a couple of situations where I would find box plots enlightening. For performance variability (either time to proven optimum or gap at a fixed time limit), box-and-whiskers plots with the performance measure on the vertical axis and the instance identifier on the horizontal axis (so one box per instance) make comparisons of instances easy. Similarly, for a comparison of algorithms, solvers or parameter combinations, performance measure (solution time to optimality or quality at a fixed time limit) on the vertical axis and algorithm/solver/whatever on the horizontal axis works nicely (albeit providing comparisons on only one quality measure).