Mathematical programming approaches for generating p-efficient points

This is the latest version of this item.

Official URL: http:/dx.doi.org/10.1016/j.ejor.2010.05.025

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.