Benchmarking Algorithms for Submodular Optimization Problems Using IOHProfiler

arXiv (Cornell University)

Abstract

Submodular functions play a key role in the area of optimization as they allow to model many real-world problems that face diminishing returns. Evolutionary algorithms have been shown to obtain strong theoretical performance guarantees for a wide class of submodular problems under various types of constraints while clearly outperforming standard greedy approximation algorithms. This paper introduces a setup for benchmarking algorithms for submodular optimization problems with the aim to provide researchers with a framework to enhance and compare the performance of new algorithms for submodular problems. The focus is on the development of iterative search algorithms such as evolutionary algorithms with the implementation provided and integrated into IOHprofiler which allows for tracking and comparing the progress and performance of iterative search algorithms. We present a range of submodular optimization problems that have been integrated into IOHprofiler and show how the setup can be used for analyzing and comparing iterative search algorithms in various settings.

Authors 9

1. Frank Neumann

   Logistics Management Institute (United States) · The University of Adelaide

   Affiliation as printed

   Optimisation and Logistics

   School of Computer and Mathematical Sciences The University of Adelaide Adelaide , Australia

2. Aneta Neumann

   Logistics Management Institute (United States) · The University of Adelaide

   Affiliation as printed

   Optimisation and Logistics

   School of Computer and Mathematical Sciences The University of Adelaide Adelaide , Australia

3. Viet Anh Do

   Logistics Management Institute (United States) · The University of Adelaide

   Affiliation as printed

   Optimisation and Logistics

   School of Computer and Mathematical Sciences The University of Adelaide Adelaide , Australia

4. Jacob de Nobel Aachen

   Leiden University

   Affiliation as printed

   Leiden Institute of Advanced Computer Science Leiden University Leiden , The Netherlands

5. Diederick Vermetten Aachen

   Leiden University

   Affiliation as printed

   Leiden Institute of Advanced Computer Science Leiden University Leiden , The Netherlands

6. Saba Sadeghi Ahouei
7. Furong Ye Aachen

   Leiden University

   Affiliation as printed

   Leiden Institute of Advanced Computer Science Leiden University Leiden , The Netherlands

8. Hao Wang Aachen

   Leiden University

   Affiliation as printed

   Leiden Institute of Advanced Computer Science applied Quantum algorithms (aQa ) Leiden University Leiden , The Netherlands

9. Thomas Bäck