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.
|
|
| FullText | Links: – Type: pdflink Text: Availability: 1 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 178623028 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: On the complexity of separating cutting planes for the knapsack polytope. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Del+Pia%2C+Alberto%22">Del Pia, Alberto</searchLink><relatesTo>1</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Linderoth%2C+Jeff%22">Linderoth, Jeff</searchLink><relatesTo>1</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Zhu%2C+Haoran%22">Zhu, Haoran</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> hzhu94@wisc.edu</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Mathematical+Programming%22">Mathematical Programming</searchLink>. Jul2024, Vol. 206 Issue 1/2, p33-59. 27p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Polynomial+time+algorithms%22">Polynomial time algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Backpacks%22">Backpacks</searchLink><br /><searchLink fieldCode="DE" term="%22Complexity+%28Philosophy%29%22">Complexity (Philosophy)</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=178623028 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s10107-023-01963-3 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 27 StartPage: 33 Subjects: – SubjectFull: Polynomial time algorithms Type: general – SubjectFull: Backpacks Type: general – SubjectFull: Complexity (Philosophy) Type: general Titles: – TitleFull: On the complexity of separating cutting planes for the knapsack polytope. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Del Pia, Alberto – PersonEntity: Name: NameFull: Linderoth, Jeff – PersonEntity: Name: NameFull: Zhu, Haoran IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 07 Text: Jul2024 Type: published Y: 2024 Identifiers: – Type: issn-print Value: 00255610 Numbering: – Type: volume Value: 206 – Type: issue Value: 1/2 Titles: – TitleFull: Mathematical Programming Type: main |
| ResultId | 1 |
