Anureet
Saxena
Title:
MIPing probabilistic constraints with random right hand sides
Abstract:
In this paper, we study the probabilistically constrained mixed
integer
programming problem (PCMIP) with binary random right hand side. This
problem has been previously considered by Beraldi and
Ruszczy´nski
where the authors develop a solution approach involving the a priori
enumeration of p-efficient points. We propose a new technique for the
enumeration of the p-efficient points allowing the reformulation of the
probabilistically constrained problem as a mixed-integer problem (MIP)
and the integration of the enumeration and solution phases. We
introduce the concept of p-inefficiency that leads to a significant
reduction in the size of our formulation. We also present a
strengthening procedure by generating a family of cuts, called polarity
cuts, for the MIP model. The strengthening procedure is extremely
efficient and closes a substantial fraction (15-30%) of the duality gap
at the root node in less than 0.5% of the total computation time. We
conducted computational experiments on probabilistic versions of set
covering and several variants of location problems. Our experiments
conducted over a test-bed of more than 3000 probabilistic instances
demonstrate that PCMIPs of simple and moderately difficult MIPs can
themselves be formulated as MIPs that can be solved in very reasonable
computational time. We discuss modifications of our model for the case
of stationary distribution and present related computational results.
(Joint work with V. Goyal and M. Lejeune)