Approximate cutting plane approaches for exact solutions to robust optimization problems

Paetzold J, Schoebel A (2020)

Publication Type: Journal article

Publication year: 2020

Journal

European Journal of Operational Research Elsevier

Book Volume: 284

Pages Range: 20-30

Journal Issue: 1

DOI: 10.1016/j.ejor.2019.11.059

Abstract

In this paper we deal with cutting plane approaches for robust optimization. Such approaches work iteratively by solving a robust problem with reduced uncertainty set (robustification step) and determining a worst-case scenario in each iteration (pessimization step) which is then added to the reduced uncertainty set. We propose to enhance this scheme by solving the robustification and/or the pessimization step not exactly, but only approximately, that is, until an improvement to the current solution is possible. The resulting iterative approach is called approximate cutting plane approach. We prove that convergence to an optimal solution for approximate cutting plane approaches is still guaranteed under similar assumptions as for classical cutting plane approaches, in which both robustification and pessimization problem are solved exactly in each iteration. Experimentally, we investigate robust mixed integer linear optimization problems for mixed-integer polyhedral uncertainty sets of different difficulties. Solving the robustification or pessimization problem only approximately increases the number of iterations. Nevertheless, our results show that the approximate cutting plane approach becomes more efficient, in particular, if the robustification or the pessimization problem is hard.

Involved external institutions

Georg-August-Universität Göttingen DE Germany (DE) Technische Universität Kaiserslautern DE Germany (DE)

How to cite

APA:

Paetzold, J., & Schoebel, A. (2020). Approximate cutting plane approaches for exact solutions to robust optimization problems. European Journal of Operational Research, 284(1), 20-30. https://dx.doi.org/10.1016/j.ejor.2019.11.059

MLA:

Paetzold, Julius, and Anita Schoebel. "Approximate cutting plane approaches for exact solutions to robust optimization problems." European Journal of Operational Research 284.1 (2020): 20-30.

BibTeX: Download