Adjustable Robust Optimization with Discrete Uncertainty
研究离散不确定性下的两阶段可调鲁棒优化问题，提出一种可将其转化为仅含目标不确定性的精确重构方法，并扩展了分支切割枚举算法，在设施选址和多背包问题上验证了有效性。
In this paper, we study adjustable robust optimization (ARO) problems with discrete uncertainty. Under a very general modeling framework, we show that such two-stage robust problems can be exactly reformulated as ARO problems with objective uncertainty only. This reformulation is valid with and without the fixed recourse assumption and is not limited to continuous wait-and-see decision variables unlike most of the existing literature. Additionally, we extend an enumerative algorithm akin to a branch-and-cut scheme for which we study the asymptotic convergence. We discuss how to apply the reformulation on two variants of well-known optimization problems, a facility location problem in which uncertainty may affect the capacity values and a multiple knapsack problem with uncertain weights, and we report extensive computational results demonstrating the effectiveness of the approach. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms – Discrete. Funding: This work was supported by the Air Force Office of Scientific Research [Grants FA8655-20-1-7012, FA8655-20-1-7019].