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.
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