A multi-term, polyhedral relaxation of a 0–1 multilinear function for Boolean logical pattern generation

Kedong Yan, Hong Seo Ryoo

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

Abstract

0–1 multilinear program (MP) holds a unifying theory to LAD pattern generation. This paper studies a multi-term relaxation of the objective function of the pattern generation MP for a tight polyhedral relaxation in terms of a small number of stronger 0–1 linear inequalities. Toward this goal, we analyze data in a graph to discover useful neighborhood properties among a set of objective terms around a single constraint term. In brief, they yield a set of facet-defining inequalities for the 0–1 multilinear polytope associated with the McCormick inequalities that they replace. The construction and practical utility of the new inequalities are illustrated on a small example and thoroughly demonstrated through numerical experiments with 12 public machine learning datasets.

Original languageEnglish
Pages (from-to)705-735
Number of pages31
JournalJournal of Global Optimization
Volume74
Issue number4
DOIs
Publication statusPublished - 2019 Aug 15

Keywords

  • 0–1 multilinear programming
  • Facet-defining inequalities
  • Graph
  • Logical analysis of data
  • Multi-term polyhedral relaxation
  • Pattern
  • Star

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research
  • Control and Optimization
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'A multi-term, polyhedral relaxation of a 0–1 multilinear function for Boolean logical pattern generation'. Together they form a unique fingerprint.

Cite this