Simple integer recourse models: convexity and convex approximations
成果类型：
Article
署名作者：
Klein Haneveld, Willem K.; Stougie, Leen; van der Vlerk, Maarten H.
署名单位：
University of Groningen; Eindhoven University of Technology; Centrum Wiskunde & Informatica (CWI)
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-006-0718-4
发表日期：
2006
页码：
435-473
关键词：
摘要：
We consider the objective function of a simple recourse problem with fixed technology matrix and integer second-stage variables. Separability due to the simple recourse structure allows to study a one-dimensional version instead. Based on an explicit formula for the objective function, we derive a complete description of the class of probability density functions such that the objective function is convex. This result is also stated in terms of random variables. Next, we present a class of convex approximations of the objective function, which are obtained by perturbing the distributions of the right-hand side parameters. We derive a uniform bound on the absolute error of the approximation. Finally, we give a representation of convex simple integer recourse problems as continuous simple recourse problems, so that they can be solved by existing special purpose algorithms.