Solving chance-constrained combinatorial problems to optimality

Olivier Klopfenstein(olivier.klopfensteinorange-ftgroup.com)

Abstract: The aim of this paper is to provide new efficient methods for solving general chance-constrained integer linear programs to optimality. Valid linear inequalities are given for these problems. They are proved to characterize properly the set of solutions. They are based on a specific scenario, whose definition impacts strongly on the quality of the linear relaxation built. A branch-and-cut algorithm is described to solve chance-constrained combinatorial problems to optimality. Numerical tests validate the theoretical analysis and illustrate the practical efficiency of the proposed approach.

Keywords: chance-constrained programming, integer linear programming

Category 1: Stochastic Programming

Category 2: Integer Programming (0-1 Programming )

Citation:

Download: [PDF]

Entry Submitted: 11/27/2007
Entry Accepted: 11/27/2007
Entry Last Modified: 11/27/2007

Modify/Update this entry