Searching optimal answer sets with the help of MILP
Logic Journal of the IGPL · 05.10.2026 · 34 (6)
DOI: 10.1093/jigpal/jzag055 ↗Kurz gefasst
Fachartikel in der Zeitschrift Logic Journal of the IGPL, online erschienen am 09.11.2026. Verfasst von Wojciech Wieczorek und 2 weiteren Autor:innen. Die Arbeit nennt 34 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
Answer Set Programming (ASP) provides a highly expressive, declarative framework for modelling combinatorial optimisation problems, enabling concise representation of complex constraints and non-monotonic reasoning. However, its practical scalability is often challenging on hard or large instances, which continues to motivate research into more efficient solving. This paper describes an improved Mixed Integer Linear Programming (MILP) encoding for ASP solving used alongside efficient MILP solvers, which constitutes the foundation of a novel non-native solver called aspirena. The proposed encoding exploits the well-known characteristic of answer sets in a way that differs from previously known solvers based on the same idea. We compared our approach against the state of the art native solvers: dlv and clingo, alongside the selected translation-based solvers, namely: mingo (MILP), acyc2solver (MILP), ezsmt (SMT), and maxmodels (MaxSAT), in a series of experiments on fifteen hard optimisation benchmarks using the same settings as in ASP competitions. Detailed results demonstrate the competitive performance of our approach in terms of solving time, success rate, and overall score. Finally, the C++ implementation of aspirena, along with benchmark datasets, is available on GitHub for reproducibility.
Zitieren
APA
Wieczorek, W., Nowakowski, A., & Strąk, Ł. (2026). Searching optimal answer sets with the help of MILP. Logic Journal of the IGPL, 34(6). https://doi.org/10.1093/jigpal/jzag055
Vancouver
Wieczorek W, Nowakowski A, Strąk Ł. Searching optimal answer sets with the help of MILP. Logic Journal of the IGPL. 2026;34(6). doi:10.1093/jigpal/jzag055
BibTeX
@article{Wieczorek2026,
author = {Wieczorek, Wojciech and Nowakowski, Arkadiusz and Strąk, Łukasz},
title = {Searching optimal answer sets with the help of MILP},
journal = {Logic Journal of the IGPL},
year = {2026},
volume = {34},
number = {6},
doi = {10.1093/jigpal/jzag055}
}
EUVIMED