Two-stage robust network row and design under demand uncertahty
Two-stage robust network row and design under demand uncertahty
复制标题
DOI：
10.1287/opre.1070.0428
复制
发表时间：
2007-07-01
影响因子：
2.7
通讯作者：
Zhang, Muhong
中科院分区：
文献类型：
--
作者：
Atamtuerk, Alper;Zhang, Muhong
提出了一种求解需求不确定网络流和设计问题的两阶段稳健优化方法。在两阶段网络优化中，将流决策的一个子集推迟到不确定需求实现之后。与单阶段优化相比，这种追索权操作的可用性使人能够提出不那么保守的解决方案。然而，这种优势往往是有代价的：两阶段优化通常比单阶段优化要困难得多。对于需求不确定的网络流和设计，我们给出了具有指数约束的第一阶段稳健决策的特征，并证明了即使对于二部图上的网络流问题，相应的分离问题也是NP-难的。与需求不确定的单阶段稳健优化不同，两阶段稳健优化允许通过允许的“需求不确定预算”来控制解的保守性。在预算不确定的情况下，我们给出了随机需求向量稳健解不可行概率的一个上界。我们推广了多商品网络流和设计的方法，并给出了对批量和选址运输问题的应用。通过投影第二阶段流动变量，我们定义了两阶段最小-最大-最小优化问题的一个上界问题。最后，我们给出了两阶段随机优化的计算结果。
We describe a two-stage robust optimization approach for solving network flow and design problems with uncertain demand. In two-stage network optimization, one defers a subset of the flow decisions until after the realization of the uncertain demand. Availability of such a recourse action allows one to come up with less conservative solutions compared to single-stage optimization. However, this advantage often comes at a price: two-stage optimization is, in general, significantly harder than single-stage optimization.For network flow and design under demand uncertainty, we give a characterization of the first-stage robust decisions with an exponential number of constraints and prove that the corresponding separation problem is NP-hard even for a network flow problem on a bipartite graph. We show, however, that if the second-stage network topology is totally ordered or an arborescence, then the separation problem is tractable.Unlike single-stage robust optimization under demand uncertainty, two-stage robust optimization allows one to control conservatism of the solutions by means of an allowed "budget for demand uncertainty." Using a budget of uncertainty, we provide an upper bound on the probability of infeasibility of a robust solution for a random demand vector. We generalize the approach to multicommodity network flow and design, and give applications to lot-sizing and location-transportation problems. By projecting out second-stage flow variables, we define an upper bounding problem for the two-stage min-max-min optimization problem. Finally, we present computational results comparing the proposed two-stage stochastic optimization.