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

Kedong Yan; Hong Seo Ryoo

doi:10.1007/978-3-030-21803-4_38

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 proceeding › Conference contribution

5 Citations (Scopus)

Abstract

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 language	English
Title of host publication	Optimization of Complex Systems
Subtitle of host publication	Theory, Models, Algorithms and Applications, 2019
Editors	Hoai An Le Thi, Hoai Minh Le, Tao Pham Dinh
Publisher	Springer Verlag
Pages	376-386
Number of pages	11
ISBN (Print)	9783030218027
DOIs	https://doi.org/10.1007/978-3-030-21803-4_38
Publication status	Published - 2020
Event	6th World Congress on Global Optimization, WCGO 2019 - Metz, France Duration: 2019 Jul 8 → 2019 Jul 10

Publication series

Name	Advances in Intelligent Systems and Computing
Volume	991
ISSN (Print)	2194-5357
ISSN (Electronic)	2194-5365

Conference

Conference	6th World Congress on Global Optimization, WCGO 2019
Country/Territory	France
City	Metz
Period	19/7/8 → 19/7/10

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.

Keywords

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

Access to Document

10.1007/978-3-030-21803-4_38

Cite this

Yan, K., & Ryoo, H. S. (2020). Cliques for Multi-Term Linearization of 0–1 Multilinear Program for Boolean Logical Pattern Generation. In H. A. Le Thi, H. M. Le, & T. Pham Dinh (Eds.), Optimization of Complex Systems: Theory, Models, Algorithms and Applications, 2019 (pp. 376-386). (Advances in Intelligent Systems and Computing; Vol. 991). Springer Verlag. https://doi.org/10.1007/978-3-030-21803-4_38

Cliques for Multi-Term Linearization of 0–1 Multilinear Program for Boolean Logical Pattern Generation. / Yan, Kedong; Ryoo, Hong Seo.
Optimization of Complex Systems: Theory, Models, Algorithms and Applications, 2019. ed. / Hoai An Le Thi; Hoai Minh Le; Tao Pham Dinh. Springer Verlag, 2020. p. 376-386 (Advances in Intelligent Systems and Computing; Vol. 991).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Yan, K & Ryoo, HS 2020, Cliques for Multi-Term Linearization of 0–1 Multilinear Program for Boolean Logical Pattern Generation. in HA Le Thi, HM Le & T Pham Dinh (eds), Optimization of Complex Systems: Theory, Models, Algorithms and Applications, 2019. Advances in Intelligent Systems and Computing, vol. 991, Springer Verlag, pp. 376-386, 6th World Congress on Global Optimization, WCGO 2019, Metz, France, 19/7/8. https://doi.org/10.1007/978-3-030-21803-4_38

@inproceedings{19df9adf8a21408cb4cd53edb5abd7b0,

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

abstract = "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.",

keywords = "0–1 multilinear programming, 0–1 polyhedral relaxation, Clique, Graph, Logical analysis of data, Pattern",

author = "Kedong Yan and Ryoo, {Hong Seo}",

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: {\textcopyright} 2020, Springer Nature Switzerland AG.; 6th World Congress on Global Optimization, WCGO 2019 ; Conference date: 08-07-2019 Through 10-07-2019",

year = "2020",

doi = "10.1007/978-3-030-21803-4_38",

language = "English",

isbn = "9783030218027",

series = "Advances in Intelligent Systems and Computing",

publisher = "Springer Verlag",

pages = "376--386",

editor = "{Le Thi}, {Hoai An} and Le, {Hoai Minh} and {Pham Dinh}, Tao",

booktitle = "Optimization of Complex Systems",

}

TY - GEN

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

AU - Yan, Kedong

AU - Ryoo, Hong Seo

N1 - 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.

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

KW - 0–1 multilinear programming

KW - 0–1 polyhedral relaxation

KW - Clique

KW - Graph

KW - Logical analysis of data

KW - Pattern

UR - http://www.scopus.com/inward/record.url?scp=85068373576&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-21803-4_38

DO - 10.1007/978-3-030-21803-4_38

M3 - Conference contribution

AN - SCOPUS:85068373576

SN - 9783030218027

T3 - Advances in Intelligent Systems and Computing

SP - 376

EP - 386

BT - Optimization of Complex Systems

A2 - Le Thi, Hoai An

A2 - Le, Hoai Minh

A2 - Pham Dinh, Tao

PB - Springer Verlag

T2 - 6th World Congress on Global Optimization, WCGO 2019

Y2 - 8 July 2019 through 10 July 2019

ER -

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

Abstract

Publication series

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this