A Dynamic Programming Approach for a Class of Robust Optimization Problems
A Dynamic Programming Approach for a Class of Robust Optimization Problems
复制标题
一类鲁棒优化问题的动态规划方法
作者：
A. Agra;M. C. Santos;D. Nace;M. Poss
解决鲁棒优化问题的常用方法是将问题分解
主问题（MP）和对抗分离问题（AP）。MP包含原始
鲁棒的约束，然而仅针对有限数量的场景编写。其他场景包括
通过求解AP动态生成。在这项工作中，我们考虑预算的不确定性多面体
从Bertsimas和Sim，在文献中广泛使用，并提出了新的动态规划
基于允许的最大偏差数求解AP的算法，
偏差的大小。我们的算法可以应用于鲁棒约束，发生在
各种应用程序，如批量计算、带时间窗的TSP、调度问题和库存
路由问题，以及许多其他问题。我们展示了如何简单版本的算法导致
当确定性问题是凸的时，将其转换为FPTAS。我们在数字上评估我们的方法，
批量问题，显示与经典的MIP重新制定的AP的比较。
Common approaches to solve a robust optimization problem decompose the problem
into a master problem (MP) and adversarial separation problems (APs). MP contains the original
robust constraints, however written only for finite numbers of scenarios. Additional scenarios are
generated on the fly by solving the APs. We consider in this work the budgeted uncertainty polytope
from Bertsimas and Sim, widely used in the literature, and propose new dynamic programming
algorithms to solve the APs that are based on the maximum number of deviations allowed and
on the size of the deviations. Our algorithms can be applied to robust constraints that occur in
various applications such as lot-sizing, TSP with time-windows, scheduling problems, and inventory
routing problems, among many others. We show how the simple version of the algorithms leads
to a FPTAS when the deterministic problem is convex. We assess numerically our approach on a
lot-sizing problem, showing a comparison with the classical MIP reformulation of the AP.