Solving a Class of Stochastic Mixed Integer Programs with Branch and Price

Abstract

Stochastic mixed-integer program – Column generation – Branch and priceWe begin this paper by identifying a class of stochastic mixed-integer programs that have column-oriented formulations suitable for solution by a branch-and-price algorithm (B&P). We then survey a number of examples, and use a stochastic facility-location problem (SFLP) for a detailed demonstration of the relevant modeling and solution techniques. Computational results with a scenario representation of uncertain costs, demands, and capacities show that B&P can be orders of magnitude faster than solving the standard formulation by branch and bound. We also demonstrate how B&P can solving SFLP exactly - as exactly as a deterministic mixed-integer program - when demands and other parameters can be represented as certain types of independent, random variables, e.g. independent, normal random variables with integer means and variances.