On solving integer robust optimization problems with integer decision-dependent uncertainty sets

• 成果类型: Article; Early Access
• 署名作者: Lozano, Leonardo; Borrero, Juan S.
• 署名单位: University System of Ohio; University of Cincinnati; State University System of Florida; University of South Florida
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-025-02249-6
• 发表日期: 2025

摘要

We study a class of decision-making problems under uncertainty, where the planner hedges against the worst-case realization in an integer uncertainty set that has a functional dependence on the decisions of the planner. We propose three methods to reformulate and solve these problems: the first is based on a single-level 'semi-infinite' reformulation, where the dependence of the uncertainty on the decisions is modeled with auxiliary binary variables; the second is based on a single-follower bilevel reformulation; and the third one is a multiple-follower bilevel reformulation where each robust constraint is associated with a follower. We provide additional enhancements to strengthen the linear programming relaxation of the single-level formulation and propose a column and constraint generation algorithm to solve it. The multiple-follower bilevel formulation is further transformed into a multicommodity flow single-level mixed-integer problem by exploiting recent advancements in decision diagrams. We perform numerical experiments that show the column and constraint generation algorithm can solve small- and medium- scale instances within a few minutes. This method is outperformed by the multicommodity flow formulation when dealing with problems with a single robust constraint. We complement our experiments by using the column and constraint generation algorithm to solve a constrained shortest path problem with maintenance decisions and uncertain arc failures. The proposed method can solve instances of this problem with hundreds of nodes and thousand of arcs in a few minutes.