Abstract
In this paper, we address the following probabilistic version (PSC) of the set covering problem: \({\min\{cx\,|\,{\mathbb P}(Ax \ge \xi) \ge p, x \in \{0, 1\}^N\}}\) where A is a 0-1 matrix, \({\xi}\) is a random 0-1 vector and \({p \in (0,1]}\) is the threshold probability level. We introduce the concepts of p-inefficiency and polarity cuts. While the former is aimed at deriving an equivalent MIP reformulation of (PSC), the latter is used as a strengthening device to obtain a stronger formulation. Simplifications of the MIP model which result when one of the following conditions hold are briefly discussed: A is a balanced matrix, A has the circular ones property, the components of \({\xi}\) are pairwise independent, the distribution function of \({\xi}\) is a stationary distribution or has the disjunctive shattering property. We corroborate our theoretical findings by an extensive computational experiment on a test-bed consisting of almost 10,000 probabilistic instances. This test-bed was created using deterministic instances from the literature and consists of probabilistic variants of the set covering model and capacitated versions of facility location, warehouse location and k-median models. Our computational results show that our procedure is orders of magnitude faster than any of the existing approaches to solve (PSC), and in many cases can reduce hours of computing time to a fraction of a second.
Similar content being viewed by others
References
Balas E.: Disjunctive programming, properties of the convex hull of feasible points. Discret. Appl. Math. 89(1-3), 3–44 (1998)
Balas E., Saxena A.: Optimizing over the split closure. Math. Program. Ser. A 113(2), 219–240 (2008)
Bartholdi J.J.III, Orlin J.B., Ratliff H.D.: Cyclic scheduling via integer programs with circular ones. Oper. Res. 28, 1074–1085 (1980)
Beasley, J.E.: OR-Library. http://www.people.brunel.ac.uk/~mastjjb/jeb/info.html
Beraldi P., Ruszczyński A.: The probabilistic set covering problem. Oper. Res. 50, 956–967 (2002)
Beraldi P., Ruszczyński A.: A branch and bound method for stochastic integer problems under probabilistic constraints. Optim. Methods Softw. 17(3), 359–382 (2002)
Charnes A., Cooper W.W., Symonds G.H.: Cost horizons and certainty equivalents: an approach to stochastic programming of heating oil. Manag. Sci. 4, 235–263 (1958)
Christof, T., Lobel, A.: PORTA - POlyhedron Representation Transformation Algorithm. http://www.zib.de/Optimization/Software/Porta/
COIN: Computational infrastructure for operations research. http://www.coin-or.org
Cornuejols G., Conforti M.: Balanced 0,1,-1 Matrices, bicoloring and total dual integrality. Math. Program. 71, 249–258 (1995)
Cornuejols, G.: Combinatorial Optimization: Packing and Covering. Published by SIAM (2001) in the CBMS-NSF Regional Conference Series in Applied Mathematics CBMS 74 (2000)
Dentcheva D., Prékopa A., Ruszczyński A.: Concavity and efficient points of discrete distributions in probabilistic programming. Math. Program. 89, 55–77 (2000)
Lodi A., Fischetti M.: Optimizing over the first Chvátal closure. Math. Program. 110(1), 3–20 (2007)
Holmberg K., Ronnqvist M., Yuan D.: An exact algorithm for the capacited facility location 517 problems with single sourcing. Eur. J. Oper. Res. 113, 544–559 (1999)
Kallenberg O.: Probabilistic Symmetries and Invariance Principles. Springer, Heidelberg (2005)
Lejeune M.A., Ruszczyński A.: An efficient method trajectory method for probabilistic inventory-production-distribution problems. Oper. Res. 55(2), 378–394 (2007)
Luedtke J., Ahmed S., Nemhauser G.: Strong MIP Formulations for Chance Constrained Linear Programs with Random Right-Hand Side. INFORMS Conference, Pittsburgh (2006)
Prékopa A.: Dual method for a one-stage stochastic programming with random rhs obeying a discrete probability distribution. Z. Oper. Res. 34, 441–461 (1990)
Prékopa A.: Stochastic Programming. Kluwer, Boston (1995)
Prékopa A.: Probabilistic programming models. In: Ruszczyński, A., Shapiro, A. (eds) Stochastic Programming: Handbook in Operations Research and Management Science, vol. 10, Chap. 5, pp. 267–351. Elsevier Science Ltd, Amsterdam (2003)
Prékopa A., Vizvari B., Badics T.: Programming under probabilistic constraint with discrete random variable. In: Giannessi, F., Komlósi, S., Rapcsák, T. (eds) New Trends in Mathematical Programming, MA, Boston (1998)
Saxena, A., Goyal, V., Lejeune, M.A.: MIP reformulations of the probabilistic set covering problem, Tepper Working Paper No. 2007-E3 (2007)
Sen S.: Relaxations for probabilistically constrained programs with discrete random variables. Oper. Res. Lett. 11(2), 81–86 (1992)
de Souza C., Balas E.: The vertex separator problem: algorithms and computations. Math. Program. 103(3), 609–631 (2005)
Toth P., Vigo D.: Branch-and-bound algorithms for the capacitated VRP. In: Toth, P., Vigo, D. (eds) The Vehicle Routing Problem, pp. 29–52. SIAM, Philadelphia (2001)
Author information
Authors and Affiliations
Corresponding author
Additional information
Anureet Saxena’s research was supported by the National Science Foundation through grant #DMI-0352885 and by the Office of Naval Research through contract N00014-03-1-0133. Vineet Goyal’s research was supported in part by NSF grant CCF-0430751 and ITR grant CCR-0122581.
Rights and permissions
About this article
Cite this article
Saxena, A., Goyal, V. & Lejeune, M.A. MIP reformulations of the probabilistic set covering problem. Math. Program. 121, 1–31 (2010). https://doi.org/10.1007/s10107-008-0224-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-008-0224-y