17
$\begingroup$

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.

performance variability

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

enter image description here

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

$\endgroup$
8
$\begingroup$

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:

enter image description here

To talk about Return On Investment to management:

enter image description here

To measure if the custom constraints are written efficiently:

enter image description here

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):

enter image description here

They all end up in a report like this:

enter image description here

$\endgroup$
  • 1
    $\begingroup$ great ressources, I will have a closer look into this. $\endgroup$ – Marco Lübbecke Jul 11 at 8:09
  • $\begingroup$ Notice how that best score over time graph both proves that Tabu Search is better than Late Acceptance and also proves it vica versa. I often see papers that make such claims. It's like saying that a car with Michelin tires is better than one with Pirelli tires - there's far more involved than tires to make a car go fast. $\endgroup$ – Geoffrey De Smet Jul 11 at 9:25
6
$\begingroup$

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.

enter image description here

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).

enter image description here

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.

enter image description here


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.

$\endgroup$
  • 3
    $\begingroup$ Thank you for commenting our paper. We spent some time trying to come out with ways of visualizing the results of our comparison :) $\endgroup$ – David Bernal Jul 11 at 9:19
  • $\begingroup$ @DavidBernal You're welcome, I did not expect some of the authors to be on OR.SE. Figures 5 and 6 are indeed quite unique as I have not come across charts with those types of strata until now. $\endgroup$ – TheSimpliFire Jul 11 at 9:22
5
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.