Answer Set Programming via Mixed Integer Programming
Answer Set Programming via Mixed Integer Programming
复制标题
通过混合整数编程进行答案集编程
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
I. Niemelä
中科院分区：
文献类型：
--
作者：
Guohua Liu;T. Janhunen;I. Niemelä
答案集编程是一种编程范式，其中给定的问题被形式化为逻辑程序，其答案集对应于问题的解决方案。在本文中，我们链接回答集规划与另一个广泛应用的范例，即混合整数规划。作为一个理论结果，我们建立翻译从非析取逻辑程序的线性约束混合整数规划中使用，使解决方案的约束对应的答案集的程序。这些翻译为扩展的答案集编程语言创建了基础，该语言包括线性约束作为原语，并实现了更紧凑的问题编码。在实践层面上，我们已经实现了一个原型系统，使用最先进的混合整数规划求解器计算答案集。所报道的实验证明了这种方法的有效性，适用于一些优化问题和问题的变量范围超过大域。
Answer set programming is a programming paradigm where a given problem is formalized as a logic program whose answer 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 theoretical result, we establish translations from non-disjunctive logic programs to linear constraints used in mixed integer programming so that the solutions to the constraints correspond to the answer sets of the programs. These translations create the basis for an extended answer set programming language that includes linear constraints as a primitive and enables more compact encodings of problems. On a practical level, we have implemented a prototype system that computes answer sets using a state-of-the-art mixed integer programming solver. The reported experiments demonstrate the effectiveness of this approach applied to a number of optimization problems and problems with variables ranging over large domains.