On the Complexity of Separation from the Knapsack Polytope
Lists
Only you see this
Abstract
We close three open problems on the separation complexity of valid inequalities for the knapsack polytope. Specifically, we establish that the separation problems for extended cover inequalities, (1, k)-configuration inequalities, and weight inequalities are all $$\mathcal {NP}$$ -complete. We also show that, when the number of constraints of the LP relaxation is constant and its optimal solution is an extreme point, then the separation problems of both extended cover inequalities and weight inequalities can be solved in polynomial time.
BibTeX
@inproceedings{pia2022complexity,
author = {Alberto Del Pia and Jeff T. Linderoth and Haoran Zhu},
title = {{On the Complexity of Separation from the Knapsack Polytope}},
booktitle = {IPCO},
year = {2022},
url = {https://openreview.net/forum?id=8_wHubheXWF},
}