Source-linked AI summary
Best practices for comparing optimization algorithms
Vahid Beiranvand, Warren Hare, Yves Lucet
TL;DR
The paper reviews how to benchmark optimization algorithms fairly and comprehensively, emphasizing explicit experimental design, suitable test sets and performance measures, and transparent analysis. It also examines reporting and visualization practices, showing that conclusions depend on the performance aspect being measured and the comparison design.
Problem
Benchmarking optimization algorithms requires careful choices to produce fair, unbiased, and useful comparisons for selecting methods.
Method
The paper systematically reviews benchmarking steps, including experimental design, test-set and metric selection, data analysis, visualization, and automation.
Results
The review identifies performance profiles, accuracy profiles, and convergence plots as complementary reporting tools whose usefulness depends on the comparison objective and test-set scope.
Takeaways & Limitations
Benchmarking studies should define their questions and important performance aspects before experimentation, then analyze and report results transparently and fairly.
Takeaways & Limitations
Conclusions are constrained by algorithm assumptions about problem structure, parameter sensitivity, and simplified timing measurements on multi-core machines.
Abstract
from arXiv · showhide
Comparing, or benchmarking, of optimization algorithms is a complicated task that involves many subtle considerations to yield a fair and unbiased evaluation. In this paper, we systematically review the benchmarking process of optimization algorithms, and discuss the challenges of fair comparison. We provide suggestions for each step of the comparison process and highlight the pitfalls to avoid when evaluating the performance of optimization algorithms. We also discuss various methods of reporting the benchmarking results. Finally, some suggestions for future research are presented to improve the current benchmarking process.
1 Introduction
Optimization benchmarking is valuable but difficult: subjective choices and unclear comparisons can produce misleading conclusions. The paper reviews the benchmarking process and organizes best-practice guidance around designing, conducting, analyzing, and reporting comparisons.
- Benchmarking compares algorithm implementations on shared test problems using performance metrics, but clear overall superiority rarely emerges in practice.Possible metrics include speed, memory use, and final function value across problems.
- Well-designed comparisons can reveal algorithm strengths and weaknesses, assess software versions, and guide algorithm selection for real-world problems.
- Poor benchmarking can hide strengths or weaknesses, report nonexistent improvements, or recommend an incorrect algorithm for a situation.
- The paper addresses subjective choices involving test sets, computing environments, and performance criteria to promote comprehensive, less-biased comparisons.
- The review focuses on serial, single-objective algorithms and generally presents ideas using continuous unconstrained problems for ease of exposition.
- Its framework covers clarifying the benchmarking reason, selecting test sets, performing experiments, and analyzing and reporting results.
2 Reason for benchmarking
A benchmarking study should begin by clarifying what comparison question it addresses and which aspect of algorithm performance matters. Those decisions determine the relevant test problems, performance metrics, and analysis.
- The purpose of a numerical comparison guides the rest of the benchmarking process and should be clarified before experiments begin.
- Benchmarking may support algorithm selection, evaluation of a novel method, software-version comparison, or assessment of option settings.
- These objectives rank algorithms within a context, so the context should guide subsequent benchmarking choices.
- For a real-world application, the test problems should come from examples of that application.
- A new method should be compared where its distinguishing behavior matters, rather than against unrelated methods on mismatched problem classes.
- Questions about speed, feasibility, coverage, global optimality, or local accuracy should determine which performance metrics are collected and how results are analyzed.
3 Test sets
Meaningful benchmarking requires shared, sufficiently varied test sets chosen for the comparison goal. The paper discusses test-set sources, starting-point and hidden-structure biases, and the differing generalizability of real-world versus artificial problems.
- Competing algorithms must be evaluated on the same test set with the same performance measures for benchmarking results to be meaningful.
- Real-world test sets provide application-specific information but may be small and difficult to generalize beyond that application.
- Artificial and randomly generated sets can be very large and reveal algorithmic characteristics, but their connection to real-world performance may be difficult to justify.
- A test set should avoid too few problems and insufficient difficulty variety, because both can limit information about relative algorithm performance.The paper recommends at least 20 problems for a reliable conclusion when possible.
- Different starting points can bias comparisons; generating starting points per problem and giving every algorithm the same ones supports fairer and more reliable testing.
- Benchmark designers should inspect test sets for hidden structures, since features such as integer-valued solution coordinates can favor particular algorithmic behaviors.
4 Performing the experiments
Fair benchmarking requires separating environmental from algorithmic influences, choosing performance measures tied to research questions, and reporting experiments transparently. Experiments should assess efficiency, reliability, and output quality while accounting for algorithm type and stochastic variation.
- Experimental factors: Benchmarking aims to measure algorithmic factors while assuming rankings remain stable across the environmental conditions under study.Environmental factors include hardware, operating systems, memory, programming language, compilers, and programmer skill.
- Performance measures: Performance data should be collected by running every algorithm on the test set, with measures selected according to the study’s research questions.Comparative measures generally cover efficiency, reliability, and quality of algorithmic output.
- Efficiency: Efficiency is measured primarily by fundamental evaluations and running time, with memory usage as a less common alternative.Fundamental evaluations can include objective, gradient, Hessian, or constraint-function evaluations; running time may use CPU or wall-clock time.
- Efficiency: CPU-time precision is reduced when memory-access costs dominate, while multi-core systems make complete timing attribution difficult.Researchers should explain how simplified timing measurements support their conclusions; wall-clock time and hardware specifications are usually reported for multi-core machines.
- Efficiency: Running-time measures should match the algorithm, such as branch-and-bound nodes or iterations for simplex and interior-point methods, and background operations should be minimized.Manuscripts should clearly state which form of running time was collected.
- Reliability: Reliability concerns performance across diverse problems: stochastic algorithms require repeated tests, and aggregated results should retain standard deviations or run-level data.Multiple starting points are often preferable, while storing each run separately preserves information that averages alone cannot reconstruct.
5 Analyzing and reporting the results
Benchmarking results can be reported through tables, graphics, and performance profiles, each balancing completeness, compactness, and interpretive limits. Performance profiles summarize efficiency and success across test sets, while trajectory and convergence plots expose behavior on individual problems.
- Numerical tables: Numerical tables provide the most complete benchmarking record, but their size often makes appendices or linked online material more suitable.Summary tables are more readable but necessarily discard benchmarking information.
- Graphics: Trajectory plots connect iterates to visualize algorithm paths, but they cover one test problem per plot and are limited for higher-dimensional functions.They are mainly useful for understanding algorithm behavior rather than evaluating overall benchmark performance.
- Graphics: Convergence plots show the best function value against evaluations, revealing behaviors such as rapid starts, stalling, and eventual superiority, but only for one test problem.In the example, M1 starts well, M2 decreases steadily, M3 initially decreases fastest, and M4 ultimately finds the lowest value.
- Performance profiles: Performance-profile interpretation must remain relative to the best method because switching can invalidate direct comparisons among other methods.A separate profile without the leading method is recommended when comparing the second- and third-ranked methods.
- Performance profiles: Performance profiles compactly compare methods across many problems while incorporating speed and success rate relative to the best method.The profile value ρ_s(τ) represents the portion of problems whose performance ratio is within factor τ of the best ratio.
- Accuracy and data profiles: Accuracy and data profiles expose application-relevant trade-offs by comparing attainable precision or problems solved within an evaluation budget.In the examples, M1 dominates moderate accuracy, M3 reaches higher accuracy, and M4 solves roughly 22% of problems within 100 simplex gradients.
6 Automated benchmarking
Automated benchmarking tools can streamline test-set development, solver execution, and performance analysis, while potentially reducing comparison bias. However, limited flexibility, expert-oriented usability, and customization requirements currently constrain their widespread adoption.
- Capabilities: Automated tools support developing test sets, running multiple optimization algorithms, and analyzing and visualizing benchmarking data.The reviewed tools include PAVER, HAL, Optimization Test Environment, EDACC, LIBOPT, and CUTEr.
- Capabilities: PAVER provides online facilities for automated performance analysis, visualization, and processing of benchmarking data.It uses solution information such as objective values, resource time, iterations, and solver status obtained from an optimization engine.
- Capabilities: HAL supports large computational experiments, database-based management of algorithms, test sets, and results, and distributed computation on computer clusters.Its stated advantage is a general-purpose design spanning different categories of optimization algorithms.
- Capabilities: The Optimization Test Environment organizes and solves large test sets, extracts subsets using predefined measures, performs statistical analysis, and verifies feasibility and correctness.It also reports varied information about optimization results.
- Limitations: Automation may reduce biased comparisons by removing some comparison decisions from algorithm designers, but current tools restrict experimental flexibility and require expert use or customization.The paper states that experiments beyond default facilities are often nontrivial and that the tools are not yet ready for widespread use.
7 Conclusion
The paper recommends an a priori, transparent, and reproducible benchmarking design tailored to the research question, while identifying important unresolved comparisons and scope boundaries. It highlights parallel and multi-objective optimization, differing algorithm assumptions, domain rescaling, and parameter sensitivity as areas requiring further care or research.
- Conclusion: A fair benchmark should begin with an a priori design that clarifies research questions, selects suitable test sets and measures, and analyzes data transparently and completely.The paper presents guidance and literature review for each stage of this process.
- Conclusion: Benchmarking reports should describe algorithms, parameters, test problems, computational environments, and statistical techniques in enough detail to support reproducibility.The paper notes that complete replication can nevertheless be difficult because published descriptions and computational environments are limited or rapidly changing.
- Scope boundaries: The paper offers a high-level baseline for best practices rather than an all-encompassing treatment of every optimization-algorithm genre.It emphasizes that many genre-specific nuances remain.
- Future research: Two major research gaps are benchmarking parallel optimization algorithms and benchmarking multi-objective optimization algorithms.The paper identifies both areas as requiring further research.
- Future research: Parallel benchmarking requires attention to time, test sets, speedup, efficiency, and other measures shaped by parallel processing and technological change.These concerns motivate dedicated research on benchmarking parallel optimization algorithms.
- Future research: Multi-objective benchmarking remains in its infancy because appropriate test sets and performance measures have yet to emerge.The paper describes research into proper benchmarking in this area as highly valuable.
- Scope boundaries: Comparisons can be constrained when algorithms differ in nature or assumptions, including deterministic versus non-deterministic methods and differing treatments of domain scaling.The paper also warns that parameter sensitivity should be examined across a range of values because it can affect the validity of conclusions.
- Scope boundaries: Global-optimization comparisons may depend on whether algorithms or users handle rescaling to the unit hypercube, limiting the conclusions drawn from numerical results.The paper notes that different assumptions about problem structure can affect test-set selection and interpretation.