Two-stage integer programs with stochastic right-hand sides: a superadditive dual approach
Two-stage integer programs with stochastic right-hand sides: a superadditive dual approach
复制标题
具有随机右侧的两阶段整数规划：超加性对偶方法
DOI：
--
复制
发表时间：
2006
影响因子：
2.7
通讯作者：
Brady Hunsaker
中科院分区：
文献类型：
--
作者：
N. Kong;A. Schaefer;Brady Hunsaker
本文研究了随机右端离散分布的两阶段纯整数规划问题。我们提出了一个等价的超加性对偶公式，在这两个阶段使用的值函数。给出了两个求值函数的算法。为了解决重新制定后获得的价值函数，我们开发了一个全球分支定界方法和水平集方法来找到一个最佳的投标。我们表明，我们的方法可以解决随机生成的实例，其扩展形式比文献中发现的实例的扩展形式大几个数量级。
We consider two-stage pure integer programs with discretely distributed stochastic right-hand sides. We present an equivalent superadditive dual formulation that uses the value functions in both stages. We give two algorithms for finding the value functions. To solve the reformulation after obtaining the value functions, we develop a global branch-and-bound approach and a level-set approach to find an optimal tender. We show that our method can solve randomly generated instances whose extensive forms are several orders of magnitude larger than the extensive forms of those instances found in the literature.