Optimization Online


Mathematical Programming Approaches for Generating p-Efficient Points

Miguel Lejeune (mlejeune***at***gwu.edu)
Nilay Noyan (nnoyan***at***sabanciuniv.edu)

Abstract: Probabilistically constrained problems, in which the random variables are finitely distributed, are non-convex in general and hard to solve. The p-efficiency concept has been widely used to develop efficient methods to solve such problems. Those methods require the generation of p-efficient points (pLEPs) and use an enumeration scheme to identify pLEPs. In this paper, we consider a random vector characterized by a finite set of scenarios and generate pLEPs by solving a mixed-integer programming (MIP) problem. We solve this computationally challenging MIP problem with a new mathematical programming framework. It involves solving a series of increasingly tighter outer approximations and employs, as algorithmic techniques, a bundle preprocessing method, strengthening valid inequalities, and a fixing strategy. The method is exact (resp., heuristic) and ensures the generation of pLEPs (resp., quasi pLEPs) if the fixing strategy is no (resp., is) employed, and it can be used to generate multiple pLEPs. To the best of our knowledge, generating a set of pLEPs using an optimization-based approach and developing effective methods for the application of the p-efficiency concept to the random variables described by a finite set of scenarios are novel. We present extensive numerical results that highlight the computational efficiency and effectiveness of the overall framework and of each of the specific algorithmic techniques.

Keywords: Stochastic programming; probabilistic constraints; p-efficiency; outer approximation; valid inequalities

Category 1: Stochastic Programming

Citation: Lejeune, M. and N. Noyan, 2010. An Efficient Method for Generating p-efficient Points, European Journal of Operational Research, 20(2): 590-600. dx.doi.org/10.1016/j.ejor.2010.05.025

Download: [PDF]

Entry Submitted: 04/25/2010
Entry Accepted: 04/25/2010
Entry Last Modified: 01/15/2012

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