×

Stochastic programming with integer variables. (English) Zbl 1035.90053

Summary: Including integer variables into traditional stochastic linear programs has considerable implications for structural analysis and algorithm design. Starting from mean-risk approaches with different risk measures we identify corresponding two- and multi-stage stochastic integer programs that are large-scale block-structured mixed-integer linear programs if the underlying probability distributions are discrete. We highlight the role of mixed-integer value functions for structure and stability of stochastic integer programs. When applied to the block structures in stochastic integer programming, well known algorithmic principles such as branch-and-bound, Lagrangian relaxation, or cutting plane methods open up new directions of research. We review existing results in the field and indicate departure points for their extension.

MSC:

90C15 Stochastic programming
90C11 Mixed integer programming
90C06 Large-scale problems in mathematical programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI