Formulating logical implications in combinatorial optimisation

When practical problems are formulated as combinatorial optimisation models one must often include logical implications between decisions. It is useful to express these implications as linear constraints involving binary variables, since linear constraints offer the possibility of using linear programming and branch and bound as an initial solution method. Often this formulation step of the modelling process seems far from evident to many practitioners, students and researchers. Therefore it is of interest to make simple rules available to clarify and help in this process. In this educationally oriented tutorial paper we introduce such a rule, LIP, the logical implication principle. It offers an easy and automatic way to translate elementary logical implications involving 0–1 variables into linear constraints. Based on an extremely simple cutting plane, we demonstrate how the rule is extended using complementarity and implicit binary variables, and leads to a simple but powerful instrument. This is illustrated by several examples of applications in various fields of Operational Research. The paper culminates in the description of a novel set of constraints which fully eliminate all permutation-equivalent solutions to numbered clustering problems.