Since the early 50's many discrete optimization techniques have been accumulated and have made a significant contribution towards solving decision problems using a quantitative (model) representation. During the 80's more and more logic-based modelling frameworks for IP have been proposed. These frameworks can be divided into two classes: one is constructing IP models by the predicate calculus in which the representative approach is proposed by McKinnon & Williams ; another is constructing IP models by the propositional calculus in which two representative
approaches are proposed by Hadjiconstantinou & Mitra and Raman & Grossmann separately.
Hadjiconstantinou & Mitra propose a modelling tool which use propositional calculus as a basis for formalizing the modelling of IP. The reformulation procedure of the logical model into a IP model uses the reverse Polish notation to represent compound propositions: terminal nodes represent atomic propositions or linear restrictions; intermediate nodes represent logical connectives.
A IP model equivalent to the logical model is built while the tree is traversed in Polish notation from from the bottom to the top. A 0-1 decision variable is associated to each terminal node and compound propositions found. The association of logical statements and 0-1 decision variables follows transformation rule of the form:
Because the propositional calculus is limited to only unary and binary logical operators, this approach is restricted to statements which are either true or false and can't (or be difficult to) declare predicates (n-ary relations) between objects, such as ``exactly k out of n, ``at most k out of n''.
Raman & Grossmann propose a modelling framework based on propositional calculus and a specialized algorithm for discrete linear programming problems. The approach is to first convert the propositional calculus model into its CNF (conjunctive normal form) and then to obtain the equivalent IP form. Also, they propose an algorithm which is similar to a branch and bound search except that the branching is done directly on the disjuctions at expense of successive addition and deletion of constraints for the active disjunctions. It is interesting to note that the proposed solution algorithm takes advantages of the logic relationships in order to solve the IP problem.
The approach has two disadvantages: one is that it can not (or would be difficult to) represent the predicates between objects because of propositional calculus; another is that it may be prohibitively expensive in space and time to express a model in disjunctive or conjunctive normal form.
Mckinnon & Williams propose logic-based modelling framworks based on the predicate calculus and a series of transformation rules which automatically converts all the input predicates into a normal form ``ge-form'' from which an IP model can be created. The input predicates are a fragment of the first-order predicate calcules where variables (restricted to be real/integer numbers) are used in the representation of linear (in)equalities and logical relationships.
Predicate calculus can be seen as an improvement of propositional calculus as it augment the ability to express knowledge and general principles. Instead of being restricted to statements which are either true or false, one can also declare predicates (n-ary relations) between objects. So, in this paper, we follow McKinnon & Williams' approach and expand it so that it can transform the logic form in propositional calculus into the IP. Also, we improve the transformation from ``ge-form'' to IP form so that it becomes more valid and efficient.