Tight representation of logical constraints as cardinality rules

Hong Yan, J. N. Hooker

Research output: Journal article publicationJournal articleAcademic researchpeer-review

28 Citations (Scopus)

Abstract

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,...,Amare true, then at least l of the propositions B1,...,Bnare true. The main result of the paper is that the procedure in fact provides a convex hull description.
Original languageEnglish
Pages (from-to)363-377
Number of pages15
JournalMathematical Programming, Series B
Volume85
Issue number2
DOIs
Publication statusPublished - 1 Jan 1999

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this