Benchmarking
In the field of optimization, benchmarking is the research area focussed on how to investigate algorithm performance experimentally. The goal is to get a reliable and replicable impression of how good and how efficient algorithms are. This then serves as foundation for the decision which algorithm to use for a given real-world problem and/or how we may improve performance by research. Since this research direction is a mixture of experiments and statistics, it gives me a chance to do some programming for research (yeah!) and contribute packages like moptipy which practically implement theoretically-grounded best practices into industry-grade software based on many years of experience.
Introduction
Optimization problems usually are not singular tasks that can be solved once and then everyone is happy. Instead, they are classes of tasks. The Traveling Salesperson Problem (TSP), for example, asks us to find the shortest round-trip tour through n cities. Each instance of the TSP may have a different number of cities and cities at different locations. Thus, we cannot solve “The TSP,” but instead develop algorithms that can solve TSPs.
Now, since every instance of the TSP may be different, it is hard to say which algorithm is really good. Maybe we have an algorithm that can only solve instances with specific properties and performs really bad on others. Or maybe we have one algorithm that is fast, but its solution quality is not so good, and another algorithm that is slow, but usually delivers good solutions. Maybe we even have an algorithm that can solve both TSPs and Quadratic Assignment Problems (QAPs), but pays for this with slightly lower solution quality or longer runtime. Thus, the question which algorithms are good, or reliably good, generally good, fast, or efficient is not always easy to answer.
This is the field of benchmarking. We use experiments to investigate algorithm performance. We try to do this in a statistically sound and replicable way. And I have worked on this field for quite some years. For example, I have organized several workshops on the topic at international conferences. I also give talks related to it. And I contributed heaps of open source software, ranging from the modern moptipy Python package over the TSP Suite and the optimizationBenchmarking packages to the early AOAB and the yet-earlier DGPF.
Posts
Measuring the Runtime of (Optimization) Algorithms
My research area is metaheuristic optimization, i.e., algorithms that can find good approximate solutions for computationally hard problems in feasible time. The Traveling Salesperson Problem (TSP) is an example for such an optimization task. In a TSP, $n$ cities and the distances between them are given and the goal is to find the shortest round-trip tour that goes through each city exactly once and then returns to its starting point. The TSP is $\mathcal{NP}$-hard, meaning that any currently known algorithm for finding the exact / globally best solution for all possible TSP instances will need a time which grows exponentially with $n$ on the worst case instances. And this is unlikely to change. In other words, if a TSP instance has $n$ cities, then the worst-case runtime of any exact TSP solver is in ${\mathcal{O}}(2^n)$. Well, today we have algorithms that can exactly solve a wide range of problems with tens of thousands of nodes and approximate the solution of million-node problems with an error of less than one part per thousand. This is pretty awesome, but the worst-case runtime to find the exact (optimal) solution is still exponential.
Publications
Core Papers
- Thomas Weise (汤卫思) and Zhize WU (吴志泽): Replicable Self-Documenting Experiments with Arbitrary Search Spaces and Algorithms. Genetic and Evolutionary Computation Conference Companion (GECCO'2023) Companion, July 15-19, 2023, Lisbon, Portugal, pages 1891-1899. New York, NY, USA: ACM.
- Thomas Weise (汤卫思), Yan CHEN (陈岩), Xinlu LI (李新路), and Zhize WU (吴志泽): Selecting a diverse set of benchmark instances from a tunable model problem for black-box discrete optimization algorithms. Applied Soft Computing Journal (ASOC) 92:106269. June 2020.
- Thomas Weise (汤卫思), Xiao-Feng WANG (王晓峰), Qi QI (齐琪), Bin LI (李斌), and Ke TANG (唐珂): Automatically discovering clusters of algorithm and problem instance behaviors as well as their causes from experimental data, algorithm setups, and instance features. Applied Soft Computing Journal (ASOC), 73:366–382, December 2018.
Complete List
- Thomas Weise (汤卫思) and Zhize WU (吴志泽): Replicable Self-Documenting Experiments with Arbitrary Search Spaces and Algorithms. Genetic and Evolutionary Computation Conference Companion (GECCO'2023) Companion, July 15-19, 2023, Lisbon, Portugal, pages 1891-1899. New York, NY, USA: ACM.
- Zhiyang LIU (刘志洋), Thomas Weise (汤卫思), and Zhize WU (吴志泽): Detection of Personal Protective Equipment in Factories: A Survey and Benchmark Dataset. 18th International Conference Intelligent Computing Methodologies (ICIC'2022), August 7-11, 2022, Xi'an, China, Part III, pages 448-459. Lecture Notes in Computer Science (LNCS), sub-series LNAI, volume 13395.
- Shuoyi RAN (冉烁依), Thomas Weise (汤卫思), and Zhize WU (吴志泽): Chemical Safety Sign Detection: A Survey and Benchmark. 2022 International Joint Conference on Neural Networks (IJCNN'2022), part of the IEEE World Congress on Computational Intelligence (IEEE WCCI'2022), July 18-23, 2022, Padova, Italy. IEEE.
- Thomas Weise (汤卫思), Markus Wagner, Bin LI (李斌), Xingyi ZHANG (张兴义), and Jörg Lässig: Special Issue on Benchmarking of Computational Intelligence Algorithms in the Applied Soft Computing Journal (Editorial). Applied Soft Computing Journal (ASOC) 93:106502. August 2020.
- Thomas Weise (汤卫思), Yan CHEN (陈岩), Xinlu LI (李新路), and Zhize WU (吴志泽): Selecting a diverse set of benchmark instances from a tunable model problem for black-box discrete optimization algorithms. Applied Soft Computing Journal (ASOC) 92:106269. June 2020.
- Thomas Weise (汤卫思), Yuezhong WU (吴越钟), Weichen LIU (刘伟臣), and Raymond Chiong: Implementation Issues in Optimization Algorithms: Do they matter? Journal of Experimental & Theoretical Artificial Intelligence (JETAI) 31(4):533-554. 2019.
- Thomas Weise (汤卫思), Xiao-Feng WANG (王晓峰), Qi QI (齐琪), Bin LI (李斌), and Ke TANG (唐珂): Automatically discovering clusters of algorithm and problem instance behaviors as well as their causes from experimental data, algorithm setups, and instance features. Applied Soft Computing Journal (ASOC), 73:366–382, December 2018.
- Thomas Weise (汤卫思) and Zijun WU (吴自军): Difficult Features of Combinatorial Optimization Problems and the Tunable W-Model Benchmark Problem for Simulating them. >Genetic and Evolutionary Computation Conference (GECCO'2018) Companion, July 15-19, 2018, Kyoto, Japan, pages 1769-1776, New York, NY, USA: ACM.
- Markus Ullrich, Thomas Weise (汤卫思), Abhishek Awasthi, and Jörg Lässig: A Generic Problem Instance Generator for Discrete Optimization Problems. Genetic and Evolutionary Computation Conference (GECCO'2018) Companion, July 15-19, 2018, Kyoto, Japan, pages 1761-1768 New York, NY, USA: ACM.
- Qi QI (齐琪), Thomas Weise (汤卫思), and Bin LI (李斌): Optimization Algorithm Behavior Modeling: A Study on the Traveling Salesman Problem. 10th International Conference on Advanced Computational Intelligence (ICACI'2018), March 29-31, 2018, Xiamen, Fujian, China, IEEE, pages 861-866.
- Thomas Weise (汤卫思): From Standardized Data Formats to Standardized Tools for Optimization Algorithm Benchmarking. 16th IEEE Conference on Cognitive Informatics & Cognitive Computing (ICCI*CC'2017), July 26-28, 2017, University of Oxford, Oxford, UK, pages 490-497. Los Alamitos, CA, USA: IEEE Computer Society Press.
- Qi QI (齐琪), Thomas Weise (汤卫思), and Bin LI (李斌): Modeling Optimization Algorithm Runtime Behavior and its Applications. Genetic and Evolutionary Computation Conference (GECCO'2017) Companion, July 15-19, 2017, Berlin, Germany, New York, NY, USA: ACM Press, pages 115-116.
- Thomas Weise (汤卫思), Yuezhong WU (吴越钟), Raymond Chiong, Ke TANG (唐珂), and Jörg Lässig: Global versus Local Search: The Impact of Population Sizes on Evolutionary Algorithm Performance. Journal of Global Optimization (JOGO) 66(3):511-534. November 2016.
- Yuezhong WU (吴越钟), Thomas Weise (汤卫思), and Raymond Chiong: Local Search for the Traveling Salesman Problem: A Comparative Study. 14th IEEE Conference on Cognitive Informatics & Cognitive Computing (ICCI*CC'2015), July 6-8, 2015, Beijing, China, pages 213-220, Los Alamitos, CA, USA: IEEE Computer Society Press.
- Thomas Weise (汤卫思) and Raymond Chiong: An Alternative Way of Presenting Statistical Test Results when Evaluating the Performance of Stochastic Approaches. Neurocomputing 147:235-238. January 2015.
- Thomas Weise (汤卫思), Stefan Niemczyk, Hendrik Skubch (ヘンドリック スクバ), Roland Reichle, and Kurt Geihs: A Tunable Model for Multi-Objective, Epistatic, Rugged, and Neutral Fitness Landscapes. 10th Annual Conference on Genetic and Evolutionary Computation Conference (GECCO'2008), pages 795-802, July 12-16, 2008, Atlanta, GA, USA. New York, NY, USA: ACM Press.