title   
  

Mathematical programming approaches for generating p-efficient points

Lejeune, Miguel and Noyan, Nilay (2009) Mathematical programming approaches for generating p-efficient points. (Submitted)

WarningThere is a more recent version of this item available.

[img]PDF - Repository staff only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
208Kb

Abstract

P-efficient points (pLEPs), introduced by Prekopa (1990), are utilized to solve probabilistically constrained problems which have been receiving significant attention in a wide range of application fields. Due to their non-convex feasible regions such problems are hard to solve. In a special case, the probabilistic constraint is enforced jointly on constraints involving randomness only in the right hand side and the vector of random variables has a finite distribution. For this special class of problems, the concept of the p-efficient point has been widely used to develop associated ecient solution methods. Those methods require the generation of pLEPs. We consider a finite random vector that is characterized by a set of scenarios and propose a mathematical programming based approach to generate pLEPs. Using a mixed-integer formulation, we obtain a method to generate pLEPs based on a new preprocessing technique and iterative outer approximations. Moreover, some valid inequalities are derived to strengthen the formulations of the outer approximations, which result in improved computational performance of the proposed generation method. We also develop a heuristic algorithm to generate “quasi pLEPs” efficiently. To the best of our knowledge, developing an optimizationbased approach for generating multiple pLEPs and developing a method for generating pLEPs for random variables characterized by a set of scenarios are novel. We also present some numerical results to show the computational efficiency and effectiveness of the proposed methods.

Item Type:Article
Uncontrolled Keywords:Stochastic programming, probabilistic constraints, p-eciency, outer approximation
Subjects:Q Science > Q Science (General)
ID Code:13220
Deposited By:Nilay Noyan
Deposited On:04 Dec 2009 11:38
Last Modified:13 Oct 2010 10:49

Available Versions of this Item

Repository Staff Only: item control page