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 language | English |
---|---|
Pages (from-to) | 348-352 |
Number of pages | 5 |
Journal | Operations Research Letters |
Volume | 47 |
Issue number | 5 |
DOIs | |
Publication status | Published - Sept 2019 |
Externally published | Yes |
Keywords
- IP formulation
- Separation complexity
- Sparsity