A multi-term, polyhedral relaxation of a 0-1 multilinear function for Boolean logical pattern generation
- Authors
- Yan, Kedong; Ryoo, Hong Seo
- Issue Date
- Aug-2019
- Publisher
- SPRINGER
- Keywords
- Logical analysis of data; Pattern; 0-1 multilinear programming; Multi-term polyhedral relaxation; Facet-defining inequalities; Graph; Star
- Citation
- JOURNAL OF GLOBAL OPTIMIZATION, v.74, no.4, pp.705 - 735
- Indexed
- SCIE
SCOPUS
- Journal Title
- JOURNAL OF GLOBAL OPTIMIZATION
- Volume
- 74
- Number
- 4
- Start Page
- 705
- End Page
- 735
- URI
- https://scholar.korea.ac.kr/handle/2021.sw.korea/63670
- DOI
- 10.1007/s10898-018-0680-8
- ISSN
- 0925-5001
- 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.
- Files in This Item
- There are no files associated with this item.
- Appears in
Collections - College of Engineering > School of Industrial and Management Engineering > 1. Journal Articles
![qrcode](https://api.qrserver.com/v1/create-qr-code/?size=55x55&data=https://scholar.korea.ac.kr/handle/2021.sw.korea/63670)
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.