TY - JOUR

T1 - Simple integer recourse models : convexity and convex approximations

AU - Klein Haneveld, W.K.

AU - Stougie, L.

AU - Vlerk, van der, M.H.

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

U2 - 10.1007/s10107-006-0718-4

DO - 10.1007/s10107-006-0718-4

M3 - Article

SN - 0025-5610

VL - 108

SP - 435

EP - 473

JO - Mathematical Programming

JF - Mathematical Programming

IS - 2-3

ER -