On the complexity of separating cutting planes for the knapsack polytope.
Saved in:
| Title: | On the complexity of separating cutting planes for the knapsack polytope. |
|---|---|
| Authors: | Del Pia, Alberto1 (AUTHOR), Linderoth, Jeff1 (AUTHOR), Zhu, Haoran1 (AUTHOR) hzhu94@wisc.edu |
| Source: | Mathematical Programming. Jul2024, Vol. 206 Issue 1/2, p33-59. 27p. |
| Subjects: | Polynomial time algorithms, Backpacks, Complexity (Philosophy) |
| 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 N P -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. Moreover, we provide a natural generalization of (1, k)-configuration inequality which is easier to separate and contains the original (1, k)-configuration inequality as a strict sub-family. [ABSTRACT FROM AUTHOR] |
| Copyright of Mathematical Programming is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| 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 N P -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. Moreover, we provide a natural generalization of (1, k)-configuration inequality which is easier to separate and contains the original (1, k)-configuration inequality as a strict sub-family. [ABSTRACT FROM AUTHOR] |
|---|---|
| ISSN: | 00255610 |
| DOI: | 10.1007/s10107-023-01963-3 |
