On the Complexity of Separation from the Knapsack Polytope

Alberto Del Pia, Jeff T. Linderoth, Haoran ZhuIPCO 2022 · OpenReview

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},
}
Figure