Recycling valid inequalities for robust combinatorial optimization with budgeted uncertainty: Recycling valid inequalities for robust combinatorial...: C. Büsing et al.
Saved in:
| Title: | Recycling valid inequalities for robust combinatorial optimization with budgeted uncertainty: Recycling valid inequalities for robust combinatorial...: C. Büsing et al. |
|---|---|
| Authors: | Büsing, Christina1 (AUTHOR) buesing@combi.rwth-aachen.de, Gersing, Timo1 (AUTHOR) gersing@combi.rwth-aachen.de, Koster, Arie M. C. A.2 (AUTHOR) koster@math2.rwth-aachen.de |
| Source: | Mathematical Programming. Mar2025, Vol. 210 Issue 1, p97-146. 50p. |
| Subjects: | Polyhedral combinatorics, Robust optimization, Computational mathematics, Mathematical programming, Combinatorial optimization |
| Abstract: | Robust combinatorial optimization with budgeted uncertainty is one of the most popular approaches for integrating uncertainty into optimization problems. The existence of a compact reformulation for (mixed-integer) linear programs and positive complexity results give the impression that these problems are relatively easy to solve. However, the practical performance of the reformulation is quite poor when solving robust integer problems, in particular due to its weak linear relaxation. To overcome this issue, we propose procedures to derive new classes of valid inequalities for robust combinatorial optimization problems. For this, we recycle valid inequalities of the underlying deterministic problem such that the additional variables from the robust formulation are incorporated. The valid inequalities to be recycled may either be readily available model constraints or actual cutting planes, where we can benefit from decades of research on valid inequalities for classical optimization problems. We first demonstrate the strength of the inequalities theoretically, by proving that recycling yields a facet-defining inequality in many cases, even if the original valid inequality was not facet-defining. Afterwards, we show in an extensive computational study that using recycled inequalities can lead to a significant improvement of the computation time when solving robust optimization problems. [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: 183375669 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Recycling valid inequalities for robust combinatorial optimization with budgeted uncertainty: Recycling valid inequalities for robust combinatorial...: C. Büsing et al. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Büsing%2C+Christina%22">Büsing, Christina</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> buesing@combi.rwth-aachen.de</i><br /><searchLink fieldCode="AR" term="%22Gersing%2C+Timo%22">Gersing, Timo</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> gersing@combi.rwth-aachen.de</i><br /><searchLink fieldCode="AR" term="%22Koster%2C+Arie+M%2E+C%2E+A%2E%22">Koster, Arie M. C. A.</searchLink><relatesTo>2</relatesTo> (AUTHOR)<i> koster@math2.rwth-aachen.de</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Mathematical+Programming%22">Mathematical Programming</searchLink>. Mar2025, Vol. 210 Issue 1, p97-146. 50p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Polyhedral+combinatorics%22">Polyhedral combinatorics</searchLink><br /><searchLink fieldCode="DE" term="%22Robust+optimization%22">Robust optimization</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+mathematics%22">Computational mathematics</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+programming%22">Mathematical programming</searchLink><br /><searchLink fieldCode="DE" term="%22Combinatorial+optimization%22">Combinatorial optimization</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Robust combinatorial optimization with budgeted uncertainty is one of the most popular approaches for integrating uncertainty into optimization problems. The existence of a compact reformulation for (mixed-integer) linear programs and positive complexity results give the impression that these problems are relatively easy to solve. However, the practical performance of the reformulation is quite poor when solving robust integer problems, in particular due to its weak linear relaxation. To overcome this issue, we propose procedures to derive new classes of valid inequalities for robust combinatorial optimization problems. For this, we recycle valid inequalities of the underlying deterministic problem such that the additional variables from the robust formulation are incorporated. The valid inequalities to be recycled may either be readily available model constraints or actual cutting planes, where we can benefit from decades of research on valid inequalities for classical optimization problems. We first demonstrate the strength of the inequalities theoretically, by proving that recycling yields a facet-defining inequality in many cases, even if the original valid inequality was not facet-defining. Afterwards, we show in an extensive computational study that using recycled inequalities can lead to a significant improvement of the computation time when solving robust optimization problems. [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=183375669 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s10107-024-02135-7 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 50 StartPage: 97 Subjects: – SubjectFull: Polyhedral combinatorics Type: general – SubjectFull: Robust optimization Type: general – SubjectFull: Computational mathematics Type: general – SubjectFull: Mathematical programming Type: general – SubjectFull: Combinatorial optimization Type: general Titles: – TitleFull: Recycling valid inequalities for robust combinatorial optimization with budgeted uncertainty: Recycling valid inequalities for robust combinatorial...: C. Büsing et al. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Büsing, Christina – PersonEntity: Name: NameFull: Gersing, Timo – PersonEntity: Name: NameFull: Koster, Arie M. C. A. IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 03 Text: Mar2025 Type: published Y: 2025 Identifiers: – Type: issn-print Value: 00255610 Numbering: – Type: volume Value: 210 – Type: issue Value: 1 Titles: – TitleFull: Mathematical Programming Type: main |
| ResultId | 1 |
