Recoverable robust optimization with commitment

• 成果类型: Article; Early Access
• 署名作者: Hommelsheim, Felix; Megow, Nicole; Muluk, Komal; Peis, Britta
• 署名单位: University of Bremen; University of Cologne; RWTH Aachen University; Dortmund University of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02385-7
• 发表日期: 2026-06-22
• 关键词: combinatorial optimization; robust optimization; Recourse; computational complexity; SPANNING TREE PROBLEM; algorithms; POWER

摘要

We propose a model for recoverable robust optimization with commitment. Given a combinatorial optimization problem and uncertainty about elements that may fail, we ask for a robust solution that, after the failing elements are revealed, can be augmented in a limited way. However, we commit to preserve the non-failing elements of the initial solution. We settle the computational complexity of such a robust counterpart of various classical polynomial-time solvable combinatorial optimization problems. We show, for the weighted matroid independent set problem, that an optimal solution to the nominal problem is also optimal for its robust counterpart. Indeed, matroids are provably the only structures with this strong property. Robust counterparts of other problems are NP-hard such as the matching problem and the stable set problem, even in bipartite graphs. However, we establish polynomial-time algorithms for the robust counterparts of the unweighted stable set problem in bipartite graphs and the weighted stable set problem in interval graphs, also known as the interval scheduling problem.