Graph, clique and facet of boolean logical polytope

Kedong Yan, Hong Seo Ryoo

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

Logical analysis of data (LAD) discovers useful knowledge from a set of data in the form of a Boolean pattern for classifying future data. Generating a pattern has been shown to be equivalent to solving a 0–1 multilinear program (MP). Thus, the success of LAD is tightly related to how efficiently practical instances of pattern generation MP’s can be solved. For a polyhedral relaxation of LAD pattern generation MP, this paper introduces a new notion of similarity among data that allows for simultaneously relaxing multiple terms of the objective function of MP into a single valid inequality for the Boolean MP polytope. Specifically, we present a framework for constructing three types of strong valid inequalities from cliques in multiple graph representations of data that collectively yield a tight polyhedral relaxation of MP. Furthermore, we specify conditions under which each type of the new inequalities defines a facet of the MP polytope. In comparison with methods from the literature, benefits of the new inequalities are validated through classification experiments with 8 public machine learning datasets.

Original languageEnglish
Pages (from-to)1015-1052
Number of pages38
JournalJournal of Global Optimization
Volume82
Issue number4
DOIs
Publication statusPublished - 2022 Apr

Bibliographical note

Funding Information:
Kedong Yan: This work was supported by National Natural Science Foundation of China (Grant Number: 61806095) and Fundamental Research Funds for the Central Universities (Grant Number: 30920021130). Hong Seo Ryoo: This research was supported by Samsung Science and Technology Foundation under Project Number SSTF-BA1501-03 and Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (Grant Number: 2017R1D1A1A02018729.).

Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

Keywords

  • 0–1 multilinear programming
  • Boolean polytope
  • Clique
  • Facet
  • Graph
  • Logical analysis of data
  • Multi-term relaxation
  • Polyhedral relaxation

ASJC Scopus subject areas

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

Fingerprint

Dive into the research topics of 'Graph, clique and facet of boolean logical polytope'. Together they form a unique fingerprint.

Cite this