Answer set programming via mixed integer programming
Guohua Liu, Tomi Janhunen, Ilkka Niemeiä · 2012
Answer set programming is a programming paradigm where a given problem is formalized as a logic program whose an-swer sets correspond to the solutions to the problem. In this paper, we link answer set programming with another widely applied paradigm, viz. mixed integer programming. As a the-oretical result, we establish translations from non-disjunctive logic programs to linear constraints used in mixed integer programming so that the solutions to the constraints corre-spond to the answer sets of the programs. These translations create the basis for an extended answer set programming lan-guage that includes linear constraints as a primitive and en-ables more compact encodings of problems. On a practical level, we have implemented a prototype system that com-putes answer sets using a state-of-the-art mixed integer pro-gramming solver. The reported experiments demonstrate the effectiveness of this approach applied to a number of opti-mization problems and problems with variables ranging over large domains.