Optimization Online


Chance Constrained Mixed Integer Program: Bilinear and Linear Formulations, and Benders Decomposition

Bo Zeng (bzeng***at***usf.edu)
Yu An (yan2***at***mail.usf.edu)
Ludwig Kuznia (Ludwig.C.Kuznia***at***disney.com)

Abstract: In this paper, we study chance constrained mixed integer program with consideration of recourse decisions and their incurred cost, developed on a finite discrete scenario set. Through studying a non-traditional bilinear mixed integer formulation, we derive its linear counterparts and show that they could be stronger than existing linear formulations. We also develop a variant of Jensen's inequality that extends the one for stochastic program. To solve this challenging problem, we present a variant of Benders decomposition method in bilinear form, which actually provides an easy-to-use algorithm framework to integrate existing improvement techniques, along with a few enhancement strategies based on the structure of chance constrained program. Computational study shows that the presented Benders decomposition method outperforms a commercial solver by an order of magnitude on solving chance constrained program or detecting its infeasibility.

Keywords: chance constraint, stochastic program, bilinear formulation, linear formulation, Jensen's inequality, Benders decomposition

Category 1: Stochastic Programming

Category 2: Integer Programming


Download: [PDF]

Entry Submitted: 03/30/2014
Entry Accepted: 03/31/2014
Entry Last Modified: 05/30/2014

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 Optimization Society