A hierarchy of bounds for stochastic mixed-integer programs
A hierarchy of bounds for stochastic mixed-integer programs
复制标题
随机混合整数规划的界限层次结构
作者：
B. Sandikçi;N. Kong;A. Schaefer
我们考虑具有追索权的一般两阶段smip，其中在问题的两个阶段都允许整数变量，并且在目标函数，约束矩阵（即技术矩阵和追索权矩阵）和右侧中允许随机性。我们通过推广观望解和使用期望值解的预期结果，建立了SMIP最优目标值的下界和上界层次结构。这些界限逐渐变得更强，但通常更难以计算。我们的数值研究表明，我们在本文中建立的边界相对于线性松弛所提供的边界是强的。因此，这种新的边界方法是目前用于解决smip的边界技术的补充工具，特别是对于大规模和表述不佳的问题。
We consider general two-stage SMIPs with recourse, in which integer variables are allowed in both stages of the problem and randomness is allowed in the objective function, the constraint matrices (i.e., the technology matrix and the recourse matrix), and the right-hand side. We develop a hierarchy of lower and upper bounds for the optimal objective value of an SMIP by generalizing the wait-and-see solution and the expected result of using the expected value solution. These bounds become progressively stronger but generally more difficult to compute. Our numerical study indicates the bounds we develop in this paper can be strong relative to those provided by linear relaxations. Hence this new bounding approach is a complementary tool to the current bounding techniques used in solving SMIPs, particularly for large-scale and poorly formulated problems.