×

Robust multicovers with budgeted uncertainty. (English) Zbl 1430.90545

Summary: The min-\(q\)-multiset multicover problem presented in this paper is a special version of the multiset multicover problem. For a fixed positive integer \(q\), we are given a finite ground set \(J\), an integral demand for each element in \(J\) and a collection of subsets of \(J\). The task is to choose sets of the collection (multiple choices are allowed) such that each element in \(J\) is covered at least as many times as specified by the demand of the element. In contrast to multiset multicover, in min-\(q\)-multiset multicover each of the chosen subsets may only cover up to \(q\) of its elements with multiple choices being allowed. Our main focus is a robust version of min-\(q\)-multiset multicover, called robust min-\(q\)-multiset multicover, in which the demand of each element in \(J\) may vary in a given interval with an additional budget constraint bounding the sum of the demands. Again, the task is to find a selection of subsets which is feasible for all admissible demands. We show that the non-robust version is NP-complete for \(q\) greater than two, whereas the robust version is strongly NP-hard for any positive \(q\). Furthermore, we present two solution approaches based on constraint generation and investigate the corresponding separation problems. We present computational results using randomly generated instances as well as instances emerging from the problem of locating emergency doctors.

MSC:

90C35 Programming involving graphs or networks
90C10 Integer programming
90C27 Combinatorial optimization
90C31 Sensitivity, stability, parametric optimization
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network flows, (1993), Prentice Hall: Prentice Hall Englewood Cliffs, New Jersey · Zbl 1201.90001
[2] Alon, N.; Awerbuch, B.; Azar, Y.; Buchbinder, N.; Naor, J., The online set cover problem, Proceedings of the 35th, 100-105, (2003) · Zbl 1192.90154
[3] Ben-Tal, A.; El Ghaoui, L.; Nemirovski, A., Robust optimization, Princeton series in applied mathematics, (2009), Princeton University Press · Zbl 1221.90001
[4] Ben-Tal, A.; Goryashko, A.; Guslitzer, E.; Nemirovski, A., Adjustable robust solutions of uncertain linear programs, Mathematical Programming, 99, 2, 351-376, (2004) · Zbl 1089.90037
[5] Ben-Tal, A.; Nemirovski, A., Robust convex optimization, Mathematics of Operations Research, 23, 769-805, (1998) · Zbl 0977.90052
[6] Ben-Tal, A.; Nemirovski, A., Robust solutions of uncertain linear programs, Operations Research Letters, 25, 1, 1-13, (1999) · Zbl 0941.90053
[7] Ben-Tal, A.; Nemirovski, A., Robust solutions of uncertain linear programming problems contaminated with uncertain data, Mathematical Programming, 88, 411-421, (2000) · Zbl 0964.90025
[8] Bertsimas, D.; Sim, M., Robust discrete optimization and network flows, Mathematical Programming, 98, 1, 49-71, (2003) · Zbl 1082.90067
[9] Bertsimas, D.; Sim, M., The price of robustness, Operations Research, 52, 1, 35-53, (2004) · Zbl 1165.90565
[10] Bougeret, M.; Pessoa, A. A.; Poss, M., Robust scheduling with budgeted uncertainty, Discrete Applied Mathematics, (2018)
[11] Brucker, C. (2011). Rettungswachen, Rettungs- und Intensivtransporthubschrauberstationen, Integrierte Leitstellen bzw. Rettungsleitstellen in Rheinland-Pfalz. https://www.bks-portal.rlp.de/sites/default/files/og-group/7832/65/dokumente/Rettungswachen; Brucker, C. (2011). Rettungswachen, Rettungs- und Intensivtransporthubschrauberstationen, Integrierte Leitstellen bzw. Rettungsleitstellen in Rheinland-Pfalz. https://www.bks-portal.rlp.de/sites/default/files/og-group/7832/65/dokumente/Rettungswachen
[12] Buchbinder, N.; Naor, J., Online primal-dual algorithms for covering and packing problems, Proceedings of the 13th, 3669, 689-701, (2005) · Zbl 1151.68748
[13] Chassein, A.; Goerigk, M.; Kasperski, A.; Zielinski, P., On recoverable and two-stage robust selection problems with budgeted uncertainty, European Journal of Operational Research, 265, 2, 423-436, (2018) · Zbl 1374.90321
[14] (Desaulniers, G.; Desrosiers, J.; Solomon, M. M., Column generation, (2005), Springer) · Zbl 1084.90002
[15] Feige, U.; Jain, K.; Mahdian, M.; Mirrokni, V., Robust combinatorial optimization with exponential scenarios, Proceedings of the international conference on integer programming and combinatorial optimization. Proceedings of the international conference on integer programming and combinatorial optimization, Lecture notes in computer science, 4513, 439-453, (2007), Springer · Zbl 1136.90451
[16] Fischetti, M., Cutting plane versus compact formulations for uncertain (integer) linear programs, Mathematical Programming Computation, 4, 3, 273-293, (2012) · Zbl 1275.90046
[17] Gabrel, V.; Lacroix, M.; Murat, C.; Remli, N., Robust location transportation problems under uncertain demands, Discrete Applied Mathematics, 164, 100-111, (2014) · Zbl 1331.90096
[18] Gabrel, V.; Murat, C.; Thiele, A., Recent advances in robust optimization: an overview, European Journal of Operational Research, 235, 3, 471-483, (2014) · Zbl 1305.90390
[19] Garey, M. R.; Johnson, D. S., Computers and intractability, (1979), W. H. Freeman and Company New York · Zbl 0411.68039
[20] Grötschel, M.; Lovász, L.; Schrijver, A., Geometric algorithms and combinatorial optimization, (1988), Springer-Verlag: Springer-Verlag Berlin Heidelberg · Zbl 0634.05001
[21] Gupta, A.; Nagarajan, V.; Ravi, R., Thresholded covering algorithms for robust and max-min optimization, Proceedings of the international colloquium on automata, languages and programming. Proceedings of the international colloquium on automata, languages and programming, Lecture notes in computer science, 6198, 262-274, (2010), Springer · Zbl 1287.68180
[22] Gurobi Optimization, Inc. (2016). Gurobi optimizer reference manual. http://www.gurobi.com; Gurobi Optimization, Inc. (2016). Gurobi optimizer reference manual. http://www.gurobi.com
[23] Hua, Q. S.; Wang, Y.; Yu, D.; Lau, F. C.M., Set multi-covering via inclusion-exclusion, Theoretical Computer Science, 410, 38-40, 3882-3892, (2009) · Zbl 1171.68048
[24] Hua, Q.-S.; Yu, D.; Lau, F. C.M.; Wang, Y., Exact algorithms for set multicover and multiset multicover problems, (Dong, Y.; Du, D.-Z.; Ibarra, O., Algorithms and computation, (2009), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 34-44 · Zbl 1272.68334
[25] Kasperski, A., Discrete optimization with interval data: minmax regret and fuzzy approach, Studies in fuzziness and soft computing, (2008), Springer Berlin Heidelberg · Zbl 1154.90017
[26] Kasperski, A.; Zieliński, P., Robust discrete optimization under discrete and interval uncertainty: a survey, (Doumpos, M.; Zopounidis, C.; Grigoroudis, E., Robustness analysis in decision aiding, optimization, and analytics. Robustness analysis in decision aiding, optimization, and analytics, International series in operations research & management science, 241, (2016), Springer International Publishing), 113-143
[27] Kouvelis, P.; Yu, G., Robust discrete optimization and its applications, Nonconvex optimization and its applications, (1996), Springer US
[28] Lutter, P.; Degel, D.; Büsing, C.; Koster, A. M.C. A.; Werners, B., Improved handling of uncertainty and robustness in set covering problems, European Journal of Operational Research, 263, 1, 35-49, (2017) · Zbl 1380.90161
[29] Minoux, M., On 2-stage robust lp with rhs uncertainty: complexity results and applications, Journal of Global Optimization, 49, 3, 521-537, (2011) · Zbl 1213.90172
[30] Nasrabadi, E., & Orlin, J. B. (2013). Robust optimization with incremental recourse. arXiv:1312.4075; Nasrabadi, E., & Orlin, J. B. (2013). Robust optimization with incremental recourse. arXiv:1312.4075
[31] Nemhauser, G. L.; Wolsey, L. A., Integer and combinatorial optimization, Wiley-Interscience series in discrete mathematics and optimization, (1999), John Wiley & Sons · Zbl 0944.90001
[32] OpenStreetMap contributors (2017). Planet dumpretrieved from https://planet.osm.orghttps://www.openstreetmap.org; OpenStreetMap contributors (2017). Planet dumpretrieved from https://planet.osm.orghttps://www.openstreetmap.org
[33] Rajagopalan, S.; Vazirani, V. V., Primal-dual RNC approximation algorithms for set cover and covering integer programs, SIAM Journal on Computing, 28, 2, 525-540, (1998) · Zbl 0914.68096
[34] Schrijver, A., Theory of linear and integer programming, (1986), John Wiley & Sons · Zbl 0665.90063
[35] Soyster, A. L., Convex programming with set-inclusive constraints and applications to inexact linear programming, Operations Research, 21, 1154-1157, (1973) · Zbl 0266.90046
[36] Wolsey, L. A.; Pochet, Y., Production planning by mixed integer programming, Springer series in operations research and financial engineering, (2006), Springer · Zbl 1102.90039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.