Modelling Integer Programming with Logic: Language and Implementation

Qiang LI; Yike GUO; Tetsuo IDA

Modelling Integer Programming with Logic: Language and Implementation

Qiang LI, Yike GUO, Tetsuo IDA

Full Text Views

0

Cite this

Summary :

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 ⁺ for IP, in which we write logical specification of an IP problem. ⁺ 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. ⁺ is executable in the sense that formulas in ⁺ 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 ⁺ to IP formulas. The translation is rigorously defined, verified and implemented in Mathematica 3.0. Our work follows the approach of McKinnon 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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.8 pp.1673-1680

Publication Date: 2000/08/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Numerical Analysis and Optimization

Cite this

Copy

Qiang LI, Yike GUO, Tetsuo IDA, "Modelling Integer Programming with Logic: Language and Implementation" in IEICE TRANSACTIONS on Fundamentals, vol. E83-A, no. 8, pp. 1673-1680, August 2000, doi: .
Abstract: 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 ⁺ for IP, in which we write logical specification of an IP problem. ⁺ 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. ⁺ is executable in the sense that formulas in ⁺ 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 ⁺ to IP formulas. The translation is rigorously defined, verified and implemented in Mathematica 3.0. Our work follows the approach of McKinnon 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e83-a_8_1673/_p

Copy

@ARTICLE{e83-a_8_1673,
author={Qiang LI, Yike GUO, Tetsuo IDA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Modelling Integer Programming with Logic: Language and Implementation},
year={2000},
volume={E83-A},
number={8},
pages={1673-1680},
abstract={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 ⁺ for IP, in which we write logical specification of an IP problem. ⁺ 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. ⁺ is executable in the sense that formulas in ⁺ 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 ⁺ to IP formulas. The translation is rigorously defined, verified and implemented in Mathematica 3.0. Our work follows the approach of McKinnon 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.},
keywords={},
doi={},
ISSN={},
month={August},}

Copy

TY - JOUR
TI - Modelling Integer Programming with Logic: Language and Implementation
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1673
EP - 1680
AU - Qiang LI
AU - Yike GUO
AU - Tetsuo IDA
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E83-A
IS - 8
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - August 2000
AB - 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 ⁺ for IP, in which we write logical specification of an IP problem. ⁺ 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. ⁺ is executable in the sense that formulas in ⁺ 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 ⁺ to IP formulas. The translation is rigorously defined, verified and implemented in Mathematica 3.0. Our work follows the approach of McKinnon 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.
ER -