Bayesian Hyperparameter Optimization with ALASPO and Applications

Abstract

Das ALASPO Framework wendet Large Neighbourhood Search (LNS) auf Answer Set Programming (ASP) an und hat sich bereits bei der Lösung verschiedener Optimierungsprobleme bewährt. Um das Verhalten der LNS-Schleife zu steuern, bietet ALASPO eine Vielzahl von Konfigurationsoptionen, die in Kombination mit allen möglichen Parametern des zugrundeliegenden ASP-Solvers zu einem riesigen Konfigurationsraum führen. Um diese Problematik zu adressieren, integrieren wir das Framework für Bayessche Optimierung SMAC3 in ALASPO, um ein automatisches Tuning von ALASPO Konfigurationen zu ermöglichen. Weiters gruppieren wir die bereitgestellten Instanzen anhand ihrer Eigenschaften, so dass wir mehrere optimale Konfigurationen erhalten, eine für jede Gruppe ähnlicher Instanzen. Das Ergebnis des Tunings kann dann für zukünftige ALASPO Durchläufe mit bisher unbekannten Instanzen verwendet werden, um automatisch eine geeignete Konfiguration basierend auf den Eigenschaften der jeweiligen Instanz auszuwählen und anzuwenden. Wir evaluieren unsere Methodik anhand von vier Benchmark-Problemen und zeigen, dass unser Tuning bei einigen dieser Probleme zu signifikanten Verbesserungen gegenüber der Standardkonfiguration führen kann, während wir ebenso ihre Grenzen aufzeigen, wenn keine ausreichenden Verbesserungsmöglichkeiten vorhanden sind.

The ALASPO framework applies Large Neighbourhood Search (LNS) to Answer Set Programming (ASP), and has proven to be effective in tackling a number of different optimization problems. To control the behaviour of the LNS loop, ALASPO offers many configuration options, that, when combined with all of the possible solving and grounding parameters of the underlying ASP solver, result in a vast configuration space. To address this challenge, we integrate the SMAC3 framework for Bayesian Optimization into ALASPO to enable the automatic tuning of ALASPO configurations. Additionally, we cluster the provided instances based on their characteristics, allowing us to obtain multiple optimal configurations, one for each cluster of similar instances. After tuning, the result can be used for future ALASPO runs on unseen instances to automatically select and apply an appropriate configuration based on the characteristics of the given instance. We evaluate our methodology on a set of four benchmark problems and show that tuning can, for some of them, provide significant improvements over using the default configuration, while also demonstrating its limitations whenever there are insufficient opportunities for advancement.