Cliques for Multi-Term Linearization of 0–1 Multilinear Program for Boolean Logical Pattern Generation

Kedong Yan, Hong Seo Ryoo

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Citations (Scopus)


0–1 multilinear program (MP) holds a unifying theory to Boolean logical pattern generation. For a tighter polyhedral relaxation of MP, this note exploits cliques in the graph representation of data under analysis to generate valid inequalities for MP that subsume all previous results and, collectively, provide a much stronger relaxation of MP. A preliminary numerical study demonstrates strength and practical benefits of the new results.

Original languageEnglish
Title of host publicationOptimization of Complex Systems
Subtitle of host publicationTheory, Models, Algorithms and Applications, 2019
EditorsHoai An Le Thi, Hoai Minh Le, Tao Pham Dinh
PublisherSpringer Verlag
Number of pages11
ISBN (Print)9783030218027
Publication statusPublished - 2020
Event6th World Congress on Global Optimization, WCGO 2019 - Metz, France
Duration: 2019 Jul 82019 Jul 10

Publication series

NameAdvances in Intelligent Systems and Computing
ISSN (Print)2194-5357
ISSN (Electronic)2194-5365


Conference6th World Congress on Global Optimization, WCGO 2019

Bibliographical note

Funding Information:
1This work was supported by National Natural Science Foundation of China (Grant Number: 61806095.) 2Corresponding author. This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (Grant Number: 2017R1D1A1A02018729.)

Publisher Copyright:
© 2020, Springer Nature Switzerland AG.


  • 0–1 multilinear programming
  • 0–1 polyhedral relaxation
  • Clique
  • Graph
  • Logical analysis of data
  • Pattern

ASJC Scopus subject areas

  • Control and Systems Engineering
  • General Computer Science


Dive into the research topics of 'Cliques for Multi-Term Linearization of 0–1 Multilinear Program for Boolean Logical Pattern Generation'. Together they form a unique fingerprint.

Cite this