期刊
SIAM JOURNAL ON OPTIMIZATION
卷 26, 期 3, 页码 1799-1823出版社
SIAM PUBLICATIONS
DOI: 10.1137/15M1007070
关键词
robust optimization; budgeted uncertainty; dynamic programming; row-and-column generation; FPTAS
资金
- French ministry MAE
- French ministry MENESR
- Jacques Hadamard Mathematical Foundation(FMJH) Gaspard Monge Program for optimization and operations research
- EDF
- FCT (Fundacao para a Ciencia e a Tecnologia) through CIDMA [UID/MAT/04106/2013]
- FCT (Fundacao para a Ciencia e a Tecnologia) through program COMPETE [FCOMP-01-0124-FEDER-041898, EXPL/MAT-NAN/1761/2013]
- CIDMA
- FCT [UID/MAT/04106/2013]
Common approaches to solving a robust optimization problem decompose the problem into a master problem (MP) and adversarial problems (APs). The MP contains the original robust constraints, written, however, 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, the traveling salesman problem with time windows, scheduling problems, and inventory routing problems, among many others. We show how the simple version of the algorithms leads to a fully polynomial time approximation scheme when the deterministic problem is convex. We assess numerically our approach on a lot-sizing problem, showing a comparison with the classical mixed integer linear programming reformulation of the AP.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据