Distribution-dependent robust linear optimization with applications to inventory control.
Distribution-dependent robust linear optimization with applications to inventory control.
复制标题
DOI：
10.1007/s10479-013-1467-4
复制
发表时间：
2015-08-01
影响因子：
4.8
通讯作者：
Paschalidis IC
中科院分区：
文献类型：
--
作者：
Kang SC;Brisimi TS;Paschalidis IC
本文研究了具有数据不确定性的线性规划问题，并将其应用于一个重要的库存控制问题。约束矩阵的每个元素都受到不确定性的影响，并且被建模为具有有界支持的随机变量。经典的鲁棒优化方法，这个问题产生一个解决方案，保证可行性。由于这种方法往往是过于保守时，应用程序可以容忍一个小的不可行的机会，人们会感兴趣的是获得一个不太保守的解决方案与一定的概率保证的可行性。在文献中的一个强大的配方产生这样的解决方案，但它不使用任何分布信息的不确定数据。在这项工作中，我们表明，使用分布信息导致一个同样强大的解决方案（即，在可行性的相同概率保证下）但具有更好的客观值。特别是，通过利用分布信息，我们建立更强的上限约束违反概率的解决方案。这些界限使我们能够“注入”更少的保守性的配方，这反过来又产生了一个更具成本效益的解决方案（50%或更多，在某些数值实例）。为了说明我们的方法的有效性，我们考虑了离散时间的随机库存控制问题，一定的服务质量的约束。数值试验表明，在库存控制问题的鲁棒优化中使用分布信息，与不使用此类信息的情况相比，可节省36%-54%的成本。
This paper tackles linear programming problems with data uncertainty and applies it to an important inventory control problem. Each element of the constraint matrix is subject to uncertainty and is modeled as a random variable with a bounded support. The classical robust optimization approach to this problem yields a solution with guaranteed feasibility. As this approach tends to be too conservative when applications can tolerate a small chance of infeasibility, one would be interested in obtaining a less conservative solution with a certain probabilistic guarantee of feasibility. A robust formulation in the literature produces such a solution, but it does not use any distributional information on the uncertain data. In this work, we show that the use of distributional information leads to an equally robust solution (i.e., under the same probabilistic guarantee of feasibility) but with a better objective value. In particular, by exploiting distributional information, we establish stronger upper bounds on the constraint violation probability of a solution. These bounds enable us to “inject” less conservatism into the formulation, which in turn yields a more cost-effective solution (by 50% or more in some numerical instances). To illustrate the effectiveness of our methodology, we consider a discrete-time stochastic inventory control problem with certain quality of service constraints. Numerical tests demonstrate that the use of distributional information in the robust optimization of the inventory control problem results in 36%–54% cost savings, compared to the case where such information is not used.