Linear Reformulation of Probabilistically Constrained Optimization Problems Using Combinatorial Patterns

Miguel A. Lejeune

George Washington University, Washington, DC, USA; mlejeune@gwu.edu

Abstract: We propose a new methodological framework for the solution of probabilistically constrained optimization problems. It is based on the integration of recent developments in the stochastic programming and combinatorial pattern recognition fields. The method involves the binarization of the probability distribution and the generation of a consistent partially defined Boolean function (pdBf) representing the combination (F; p) of the binarized probability distribution F and the enforced probability level p. We show that the pdBf representing (F; p) can be compactly extended as an isotone Boolean functional extension and modelled as a disjunctive normal form (DNF). The DNF is a collection of combinatorial patterns defining each a set of sufficient conditions for a probabilistic constraint to hold. We propose a new mathematical programming approach for the derivation of combinatorial patterns, which has the advantage, as compared to enumerative methods, of alleviating the computational burden for the generation of patterns with large degree. The generation of a pattern with large coverage (resp., a disjunctive normal form) permits the derivation of a tight linear programming outer approximation (resp., an MIP deterministic equivalent) of the probabilistic problem. The method is implemented for the solution of a numerical problem. Extensions to the present study are discussed.