### Abstract

Original language | English |
---|---|

Pages (from-to) | 348-352 |

Number of pages | 5 |

Journal | Operations Research Letters |

Volume | 47 |

Issue number | 5 |

DOIs | |

Publication status | Published - 2019 |

Externally published | Yes |

### Fingerprint

### Cite this

*Operations Research Letters*,

*47*(5), 348-352. https://doi.org/10.1016/j.orl.2019.06.001

}

*Operations Research Letters*, vol. 47, no. 5, pp. 348-352. https://doi.org/10.1016/j.orl.2019.06.001

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

Research output: Contribution to journal › Article › Academic › peer-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 -