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 language | English |
---|---|
Pages (from-to) | 705-735 |
Number of pages | 31 |
Journal | Journal of Global Optimization |
Volume | 74 |
Issue number | 4 |
DOIs | |
Publication status | Published - 2019 Aug 15 |
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