---
title: "Optimality-preserving Logic-Based Benders Decomposition of Answer Set Programs"
authors:
  - "Carmine Dodaro"
  - "Antonio Ielo"
  - "Marco Maratea"
  - "Cinzia Marte"
  - "Alice Tarzariol"
doi: "10.24963/ijcai.2026/424"
url: "https://ijcai.org/proceedings/2026/424"
pdf: "https://ijcai.org/proceedings/2026/0424.pdf"
venue: "Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence"
year: 2026
pages: "3810-3818"
track: "Main Track"
keywords:
  - "Knowledge Representation and Reasoning: Logic programming"
  - "Knowledge Representation and Reasoning: Non-monotonic reasoning"
---

# Optimality-preserving Logic-Based Benders Decomposition of Answer Set Programs

Carmine Dodaro, Antonio Ielo, Marco Maratea, Cinzia Marte, Alice Tarzariol

*Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence*, pages 3810-3818. DOI: [10.24963/ijcai.2026/424](https://doi.org/10.24963/ijcai.2026/424)

## Abstract

Bender Decomposition is a well-known solving technique in Operation Research that decomposes a problem into a master and a subproblem, which interact via “cuts". This technique has been extended to Logic-Based Bender Decomposition (LBBD), solving problems specified by logic-based languages and enabling a wider applicability. However, while Bender Decomposition guarantees optimality, LBBD does not: this property is problem-specific and depends on the defined decomposition and cuts.
In this paper, we present a theoretical analysis of the conditions under which LBBD, including cuts, can preserve optimality in the context of Answer Set Programming (ASP), a prominent logic-based language in the field of Artificial Intelligence.
We also introduce a general-purpose algorithm that employs both minimal unsatisfiable subsets and minimal correction subsets to define cuts in a fully automated, problem-independent way. The algorithm preserves the optimality guarantees of Bender Decomposition.
An empirical evaluation on real-world scheduling instances shows that our approach can find significantly more solutions, and more optimal ones, compared to a standard direct ASP encoding, while also consistently reducing the execution time.