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 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 separable in polynomial time.
Original languageEnglish
Pages (from-to)348-352
Number of pages5
JournalOperations Research Letters
Volume47
Issue number5
DOIs
Publication statusPublished - 2019
Externally publishedYes

Fingerprint

Traveling salesman problem
Sparsity
Polynomials
Binary
Integer
Formulation
Combinatorial Problems
Travelling salesman problems
Polynomial time
NP-complete problem
Computing
NP-hard

Cite this

Hojny, Christopher ; Lüthen, Hendrik ; Pfetsch, Marc E. / Sparsity of integer formulations for binary programs. In: Operations Research Letters. 2019 ; Vol. 47, No. 5. pp. 348-352.
@article{7798a635f0e74dc09767cb28d6f95596,
title = "Sparsity of integer formulations for binary programs",
abstract = "This paper considers integer formulations of binary sets 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 separable in polynomial time.",
author = "Christopher Hojny and Hendrik L{\"u}then and Pfetsch, {Marc E.}",
year = "2019",
doi = "10.1016/j.orl.2019.06.001",
language = "English",
volume = "47",
pages = "348--352",
journal = "Operations Research Letters",
issn = "0167-6377",
publisher = "Elsevier",
number = "5",

}

Sparsity of integer formulations for binary programs. / Hojny, Christopher; Lüthen, Hendrik; Pfetsch, Marc E. (Corresponding author).

In: Operations Research Letters, Vol. 47, No. 5, 2019, p. 348-352.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Sparsity of integer formulations for binary programs

AU - Hojny, Christopher

AU - Lüthen, Hendrik

AU - Pfetsch, Marc E.

PY - 2019

Y1 - 2019

N2 - This paper considers integer formulations of binary sets 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 separable in polynomial time.

AB - This paper considers integer formulations of binary sets 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 separable in polynomial time.

U2 - 10.1016/j.orl.2019.06.001

DO - 10.1016/j.orl.2019.06.001

M3 - Article

VL - 47

SP - 348

EP - 352

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 5

ER -