A Convex Approximation for Two-Stage Mixed-Integer Recourse Models with a Uniform Error Bound
针对两阶段混合整数追索模型，提出一种凸逼近方法，并推导出依赖于随机变量概率密度函数总变差的误差界，该误差界在总变差趋于零时收敛到零。
We develop a convex approximation for two-stage mixed-integer recourse models, and we derive an error bound for this approximation that depends on the total variations of the probability density functions of the random variables in the model. We show that the error bound converges to zero if all these total variations converge to zero. Our convex approximation is a generalization of the one in Romeijnders, van der Vlerk, and Klein Haneveld [Math. Program., to appear] restricted to totally unimodular integer recourse models. For this special case it has the best worst-case error bound possible. The error bound in this paper is the first in the general setting of mixed-integer recourse models. As main building blocks in its derivation we generalize the asymptotic periodicity results of Gomory [Linear Algebra Appl., 2 (1969), pp. 451--558] for pure integer programs to the mixed-integer case, and we use the total variation error bounds on the expectation of periodic functions derived in Romeijnders, van der Vlerk, and Klein Haneveld [Math. Program., to appear].