Two-stage quadratic integer programs with stochastic right-hand sides
Two-stage quadratic integer programs with stochastic right-hand sides
复制标题
具有随机右侧的两阶段二次整数规划
作者：
Osman Y. Özaltın;O. Prokopyev;A. Schaefer
考虑了随机右端的两阶段二次整数规划问题，并给出了一个等价的利用值函数的重构形式。我们提出了一个两阶段的解决方案。第一阶段构造两个阶段的二次整数规划的值函数。第二阶段使用全局分支定界算法或水平集方法求解重构。本文导出了二次整数规划值函数的一些基本性质，并将它们应用于算法中。我们表明，我们的方法可以解决的情况下，其广泛的形式是数百个数量级以上的最大的二次整数规划的情况下，在文献中解决。
We consider two-stage quadratic integer programs with stochastic right-hand sides, and present an equivalent reformulation using value functions. We propose a two-phase solution approach. The first phase constructs value functions of quadratic integer programs in both stages. The second phase solves the reformulation using a global branch-and-bound algorithm or a level-set approach. We derive some basic properties of value functions of quadratic integer programs and utilize them in our algorithms. We show that our approach can solve instances whose extensive forms are hundreds of orders of magnitude larger than the largest quadratic integer programming instances solved in the literature.