Optimization Online


An integer programming approach for linear programs with probabilistic constraints

James Luedtke (luedtke***at***gatech.edu)
Shabbir Ahmed (sahmed***at***isye.gatech.edu)
George Nemhauser (gnemhaus***at***isye.gatech.edu)

Abstract: Linear programs with joint probabilistic constraints (PCLP) are difficult to solve because the feasible region is not convex. We consider a special case of PCLP in which only the right-hand side is random and this random vector has a finite distribution. We give a mixed-integer programming formulation for this special case and study the relaxation corresponding to a single row of the probabilistic constraint. We obtain two strengthened formulations. As a byproduct of this analysis, we obtain new results for the previously studied mixing set, subject to an additional knapsack inequality. We present computational results which indicate that by using our strengthened formulations, instances that are considerably larger than have been considered before can be solved to optimality.

Keywords: Stochastic programming, integer programming, probabilistic constraints, chance constraints, mixing set

Category 1: Stochastic Programming

Category 2: Integer Programming ((Mixed) Integer Linear Programming )


Download: [PDF]

Entry Submitted: 05/03/2007
Entry Accepted: 05/04/2007
Entry Last Modified: 05/02/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society