Sparsity of integer formulations for binary programs

Christopher Hojny, Hendrik Lüthen, Marc E. Pfetsch (Corresponding author)

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

This paper considers integer formulations of binary sets X of minimum sparsity, i.e., the maximal number of non-zeros for each row of the corresponding constraint matrix is minimized. Providing a constructive mechanism for computing the minimum sparsity, we derive sparsest integer formulations of several combinatorial problems, including the traveling salesman problem. We also show that sparsest formulations are NP-hard to separate, while (under mild assumptions) there exists a dense formulation of X separable in polynomial time.

Original languageEnglish
Pages (from-to)348-352
Number of pages5
JournalOperations Research Letters
Volume47
Issue number5
DOIs
Publication statusPublished - Sep 2019
Externally publishedYes

Keywords

  • IP formulation
  • Separation complexity
  • Sparsity

Fingerprint Dive into the research topics of 'Sparsity of integer formulations for binary programs'. Together they form a unique fingerprint.

  • Cite this