Modelling Integer Programing with Logic : Language and Implementation

概要

論文の詳細を見る
The classical algebraic modelling approach for integer programming (IP) is not suitable for some real world IP problems, since the algebraic formulations allow only for the description of mathematical relations, not logical relations. In this paper, we present a language L^+ for IP, in which we write logical specification of an IP problem. L^+ is a language based on the predicate logic, but is extended with meta predicates such as at least (m, S), where m is a non-negative integer, meaning that at least m predicates in the set S of formulas hold. The meta predicates facilitate reasoning about a model of an IP problem rigorously and logically. L^+ is executable in the sense that formulas in L^+ are mechanically translated into a set of mathematical formulas, called IP formulas, which most of existing IP solvers accept. We give a systematic method for translating formulas in L^+ to IP formulas. The translation is rigorously defined, verified and implemented in Mathematica 3. 0. Our work follows the approach of McKinon and Williams, and elaborated the language in that (1) it is rigorously defined, (2) transformation to IP formulas is more optimised and verified, and (3) the transformation is completely given in Mathematica 3. 0 and is integrated into IP solving environment as a tool for IP.
社団法人電子情報通信学会の論文
2000-08-25