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

    8 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

    Bibliographical note

    Publisher Copyright:
    © 2018, Springer Science+Business Media, LLC, part of Springer Nature.

    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