  In Answer Set Programming (ASP), the user can define declaratively a problem
and solve it with efficient solvers; practical applications of ASP are
countless and several constraint problems have been successfully solved with
ASP. On the other hand, solution time usually grows in a superlinear way
(often, exponential) with respect to the size of the instance, which is
impractical for large instances. A widely used approach is to split the
optimization problem into sub-problems that are solved in sequence, some
committing to the values assigned by others, and reconstructing a valid
assignment for the whole problem by juxtaposing the solutions of the single
sub-problems. On the one hand this approach is much faster, due to the
superlinear behavior; on the other hand, it does not provide any guarantee of
optimality: committing to the assignment of one sub-problem can rule out the
optimal solution from the search space. In other research areas, Logic-Based
Benders Decomposition (LBBD) proved effective; in LBBD, the problem is
decomposed into a Master Problem (MP) and one or several Sub-Problems (SP). The
solution of the MP is passed to the SPs, that can possibly fail. In case of
failure, a no-good is returned to the MP, that is solved again with the
addition of the new constraint. The solution process is iterated until a valid
solution is obtained for all the sub-problems or the MP is proven infeasible.
The obtained solution is provably optimal under very mild conditions. In this
paper, we apply for the first time LBBD to ASP, exploiting an application in
health care as case study. Experimental results show the effectiveness of the
approach. We believe that the availability of LBBD can further increase the
practical applicability of ASP technologies.
