Tight representation of logical constraints as cardinality rules

A mathematical programming model may contain qualitative as well as quantitative elements. One may, for example, wish to combine a rule base with numerical constraints. This raises the issue of how to represent logical constraints in inequality form so that they have a useful linear relaxation. We provide a simple recursive procedure that generates a convex hull description of any logical condition that can be written as a ‘cardinality rule’, which seems to be a form that occurs often in practice. A cardinality rule asserts that if at least k of the propositions A1,...,Am are true, then at least 𝓁 of the propositions B1,...,Bn are true. The main result of the paper is that the procedure in fact provides a convex hull description.