A Branch-Reduce-Cut Algorithm for the Global Optimization of Probabilistically Constrained Linear Programs

Myun-Seok Cheon (powstoneisye.gatech.edu)
Shabbir Ahmed (sahmedisye.gatech.edu)
Faiz Al-Khayyal (faizisye.gatech.edu)

Abstract: We consider probabilistic constrained linear programs with general distributions for the uncertain parameters. These problems generally involve non-convex feasible sets. We develop a branch and bound algorithm that searches for a global solution to this problem by successively partitioning the non-convex feasible region and by using bounds on the objective function to fathom inferior partitions. This basic algorithm is enhanced by domain reduction and cutting plane strategies to reduce the size of the partitions and hence tighten bounds. The proposed branch-reduce-cut algorithm exploits the monotonicity properties inherent in the problem, and requires solving linear programming subproblems. We provide convergence proofs for the algorithm. Some illustrative numerical results involving problems with discrete distributions are presented.

Keywords:

Category 1: Stochastic Programming

Category 2: Global Optimization

Citation: Submitted for publication, 2004

Download: [PDF]

Entry Submitted: 09/24/2004
Entry Accepted: 09/27/2004
Entry Last Modified: 09/24/2004

Modify/Update this entry