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.
|
|
Be the first to leave a comment!
