Wolfram Library Archive

Courseware Demos MathSource Technical Notes
All Collections Articles Books Conference Proceedings

Modelling integer programming with logic: Language and implementation

Q. Li
Y. K. Guo
Tetsuo Ida
Organization: University of Tsukuba
Department: Institute of Information Sciences and Electronics
Journal / Anthology

IEICE Transactions on Fundamentals of Electronics Communications & Computer Sciences
Year: 2000
Volume: E38A
Issue: 8
Page range: 1673-1680

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 relatons. 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 forulas 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 tranlastion is rigorously defined, verified, and implemented in Mathematica 3.0. Our work follows the approach of McKinnon and Williams, adn elaborated the language in that (1) it is rigorously defined, (2) transformation to IP frmulas is more optimized and verified, and (3) the transformation is completely given in Mathematica 3.0 and is integrated into the IP solving environment as a tool for IP.

*Applied Mathematics > Optimization
*Mathematics > Foundations of Mathematics > Logic

modelling, predicate logic, propositional logic, integer programming