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-2 | Engels |
---|---|
Pagina's (van-tot) | 348-352 |
Aantal pagina's | 5 |
Tijdschrift | Operations Research Letters |
Volume | 47 |
Nummer van het tijdschrift | 5 |
DOI's | |
Status | Gepubliceerd - sep. 2019 |
Extern gepubliceerd | Ja |