Sparsity of integer formulations for binary programs

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

2 Citaten (Scopus)

Samenvatting

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.

Originele taal-2Engels
Pagina's (van-tot)348-352
Aantal pagina's5
TijdschriftOperations Research Letters
Volume47
Nummer van het tijdschrift5
DOI's
StatusGepubliceerd - sep. 2019
Extern gepubliceerdJa

Vingerafdruk

Duik in de onderzoeksthema's van 'Sparsity of integer formulations for binary programs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit