Filling the gap in weighted set covering problem test instances: implications for both researchers and practitioners
DOI:
https://doi.org/10.12928/ijio.v6i1.10836Keywords:
metaheuristics, operations research, weighted set covering problems, integer programming software, Beasley’s OR-LibraryAbstract
Since 1990, the quality of approximate solution methods for solving weighted set covering problems (WSCPs) has been measured based on how well they solve 65 WSCPs available in Beasley’s OR-Library. In a 2024 paper, it has been shown that guaranteed optimal solutions can easily be obtained for 55 weighted set covering problems (WSCPs) in Beasley’s OR-Library using general-purpose integer programming software. These 55 WSCPs have 500 rows and 5,000 columns or less and were solved in a few seconds on a standard PC. However, the remaining 10 WSCPs have 1000 rows and 10,000 columns and either required considerably more than 1000 seconds to obtain guaranteed optimums (data set NRG) or no optimums were obtained (NRH). The purpose of this short paper is to try to quantify the solution times needed to solve WSCPs using general-purpose integer programming software that are larger than 500 rows and 5,000 columns, but less than 1,000 rows and 10,000 columns. This is important because the size and solution time gap is so large that solution times go from a few seconds for the 55 “smaller” WSCPs to very large solution times for the two largest data sets. To fill this gap, 40 new WSCP instances are defined and their solution times are analyzed to determine when to expect that WSCPs, based on size and density, can be solved to optimality in a timely manner using general-purpose integer programming software like Gurobi or CPLEX.
References
R. M. Karp, “Reducibility among combinatorial problems,” in Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds) Complexity of Computer Computations. The IBM Research Symposia Series. Springer, Boston, MA, 1972, pp. 85–103, doi: 10.1007/978-1-4684-2001-2_9.
M. R. Garey, D.S. Johnson. “Computers and Intractability”. Freeman, San Francisco. 1979.
F. J. Vasko, F. E. Wolf, and K. L. Stott, “Optimal Selection of Ingot Sizes via Set Covering”, Operations Research, 35, 346-353, 1987, doi: 10.1287/opre.35.3.346.
F. J. Vasko, F. E. Wolf, and K. L. Stott, “A Set Covering Approach to Metallurgical Grade Assignment,” European Journal of Operational Research, 38, 27-34, 1989, doi: 10.1016/0377-2217(89)90465-7.
D. D. Newhart, K. L. Stott, and F. J. Vasko, “Consolidating Product Sizes to Minimize Inventory Levels for a Multi-stage Production and Distribution System. Journal of the Operational Research Society 44, 7, 637-644, 1993, doi: 10.1038/sj/jors/0440701
F. J. Vasko, F. E. Wolf, K. L. Stott, and O. Ehrsam, “Bethlehem Steel Combines Cutting Stock and Set Covering to Enhance Customer Service”. Mathematical Computer Modelling 16, 9-17, 1992, doi: 10.1016/0895-7177(92)90075-V.
Z. Feng, H. Okamura, T. Dohi, W.Y. Yun, “Reliability Computing Methods of Probabilistic Location Set Covering Problem Considering Wireless Network Applications”, IEEE Transactions on Reliability, August 21, 2023, doi: 10.1109/TR.2023.3301929.
J. Bramel, D, Simchi-Levi, “On the Effectiveness of Set Covering Formulations for the Vehicle Routing Problem with Time Windows”, Operations Research, 45, 2, March-April 1997, doi: 10.1287/opre.45.2.295.
Y. Park, C. S. Ko, I. Moon, “Unmanned aerial vehicle radius set covering problem for emergency wireless network”, Computers and Operations Research, 170, 2024, doi: 10.1016/j.cor.2024.106765.
S. S. V. Vianna, “The set covering problem applied to optimization of gas detectors in chemical process plants”, Computers and Chemical Engineering, 121, 388-395, 2019, doi: 10.1016/j.compchemeng.2018.11.008.
F. Khosghgehbari, S, Mohammand, J. Mirzapour Al-e-Hashem, “Ambulance location routing problem considering all sources of uncertainty: Progressive estimating algorithm”, Computers and Operations Research, 160, 2023, doi: 10.1016/j.cor.2023.106400.
B. Erdebilli, S. G. A. Ozsahin, “Uncertainty management with an autonomous approach to fuzzy set-covering facility location models’’, Journal of Intelligent and Fuzzy Systems, 46, 8233-8246, 2022, doi: 10.3233/JIFS-213220.
B. S. Vierira, T. Ferrari, G. M. Ribiero, L. Bahiense, R. D. O. Filho, C. A. Abramides, N. F. R. Campos Junior, “A progressive hybrid set covering based algorithm for the traffic counting location problem”, Expert Systems with Applications, 160, 2020, doi: 10.1016/j.eswa.2020.113641.
M. Yaghini, M. Karimi, M. Rahbar, “A set covering approach for multi-depot train driver scheduling”, Journal of Combinatorial Optimization, 29, 636-654, 2015, doi: 10.1007/s10878-013-9612-1.
J. Heil, K. Hoffmann, and U. Buscher, “Railway crew scheduling: Models, methods and applications,” European Journal of Operational Research, 283, 2, pp. 405–425, 2020, doi: 10.1016/j.ejor.2019.06.016.
J. E. Beasley, OR Library, 1990, available at: http://people.brunel.ac.uk/mastjjb/jeb/info.html.
J. E. Beasley, “A Heuristic for the Non-unicost Set Covering Problem Using Local Branching”, International Transactions in Operational Research, 1-19, 2024. doi: 10.1111/itor.13446, https://doi.org/10.1111/itor.13446.
B. Crawford, R. Soto, H. Mella, de la Fuente, C. Elortegui, W. Palma, C. Torres-Rojas, C. Vasconcellos-Gaete, M. Becerra, J. Peña, S. Misra, “Binary Fruit Fly Swarm Algorithms for the Set Covering Problem”, Computers, Materials & Continua, 71, 3, 4295-4318, 2022, doi: 10.32604/cmc.2022.023068.
B, Crawford, R. Soto, N. G. Astorga, J. Lemus-Romani, S. Misra, M. Castillo, F. Cisternas-Caneo, D. Tapia, M. Becerra-Rozas, “Balancing Exploration-Exploitation in the Set Covering Problem Resolution with a Self-adaptive Intelligent Water Drops Algorithm”, Advances in Science, Technology and Engineering Systems Journal, 6. 1. 134-145, 2021, doi: 10.25046/aj060115.
V. Reyes, I. Araya, “A GRASP-based Scheme for the Set Covering Problem”, Operational Research, 21, 2391-2408, 2021, doi: 10.1007/s12351-019-00514-z.
B. Crawford, R. Soto, R. Olivares, G. Embry, D. Flores, W. Palma, C. Castro, F. Paredes, J. M. Rubio, “A Binary Monkey Search Algorithm Variation for Solving the Set Covering Problem”, Natural Computing, 19, 825-841, 2020, doi: 10.1007/s11047-019-09752-8.
A. Hashemi, H. Gholami, U. Venkatadri, S. S. Karganroudi, S. Khouri, A. Wojceiechowski, and D. Streimikiene, “A New Direct Coefficient-Based Heuristic Algorithm for Set Covering Problems”, International Journal of Fuzzy Systems, 24, 2,1131-1147, 2022, doi: 10.1007/s40815-021-01208-5.
T.Adamo, G. Ghiani, E. Guerriero, and D. Pareo, “A Surprisal-Based Greedy Heuristic for the Set Covering Problem”, Algorithms,16, 321, 2023, doi: 10.3390/a16070321.
C. Luo, W. Xing, S. Cai, and C. Hu, “NuSC: An Effective Local Search Algorithm for Solving the Set Covering Problem”, IEEE transactions on cybernetics, 54, 3, 2024, doi: 10.1109/TCYB.2022.3199147.
J. E. Beasley, “An algorithm for set covering problem,” European Journal of Operational Research, vol. 31, no. 1, pp. 85–93, 1987, doi: 10.1016/0377-2217(87)90141-X.
S. Sundar and A. Singh, “A hybrid heuristic for the set covering problem,” Operational Research, 12, 3, 345–365, 2012, doi: 10.1007/s12351-010-0086-y.
J. E. Beasley and K. Jørnsten, “Enhancing an algorithm for set covering problems,” European Journal of Operational Research, 58, 2, 293–300, 1992, doi: 10.1016/0377-2217(92)90215-U.
E. Balas and M. C. Carrera, “A dynamic subgradient-based branch-and-bound procedure for set covering,” Operational Research, vol. 44, no. 6, pp. 875–890, 1996, doi: 10.1287/opre.44.6.875.
F. Carrabs, R. Cerulli, R. Mansini, L. Moreshini, and D. Serra, “Solving the Set Covering Problem with Conflicts on Sets: A new parallel GRASP”, Computers and Operations Research, 2024, doi: 10.1016/j.cor.2024.106620.
S.Saffari, Y. Fathi, “Set covering problem with conflict constraints”, Computers and Operations Research, 2022, doi: 10.1016/j.cor.2022.105763.
B. Yelbay, S. I. Birbil, and K. Bulbul. “The Set Covering Problem Revisited: An Empirical Study of the Value of Dual Information”, Journal of Industrial and Management Optimization, 11, 2, 575-594, 2015, doi: 10.3934/jimo.2015.11.575.
A. Caprara, M. Fischetti, and P. Toth, “A Heuristic Method for the Set Covering Problem”, Opns Res, 47, 5, 730-743, 1999, doi: 10.1287/opre.47.5.730.
G. Lan, G. DePuy, and G. Whitehouse, “An Effective and Simple Heuristic for the Set Covering Problem”, European Journal of Operational Research, 176, 3, 1387-1403, 2007, doi: 10.1016/j.ejor.2005.09.028.
T. Koch, T. Achterberg, E. Andersen, O. Bastert, T. Berthold, R.E. Bixby, E. Danna, G. Gamrath, A.M. Gleixner, S. Heinz, A. Lodi, H. Mittelmann, T. Ralphs, D. Salvagnin, D.E. Steffy, K. Wolter, MIPLIB 2010, Mathematical Programming Computation, 3, 2011, doi: 10.1007/s12532-011-0025-9.
T. Koch, A. Martin, M.E. Pfetsch, Progress in academic computational integer programming, in: M. Jünger, G. Reinelt (Eds.), Facets of Combinatorial Optimization, Springer, Berlin, Heidelberg, 483–506, 2013, doi: 10.1007/978-3-642-38189-8_19.
A. Gleixner, G. Hendel, G. Gamrath, T. Achterberg, M. Bastubbe, T. Berthold, P.M. Christophel, K. Jarck, T. Koch, J. Linderoth, M. Lübbecke, H.D. Mittelmann, D. Ozyurt, T.K. Ralphs, D. Salvagnin, Y. Shinano, “MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library,” Mathematical Programming Computation, 13, pp. 443-490, 2021, doi: 10.1007/s12532-020-00194-3.
E.R. Bixby, M. Fenelon, Z. Gu, E. Rothberg, R. Wunderling, MIP: theory and practice — closing the gap, in: M.J.D. Powell, S. Scholtes (Eds.), System Modelling and Optimization, Springer US, Boston, MA, 2000, pp. 19–49, doi: 10.1007/978-0-387-35514-6_2.
E.R. Bixby, M. Fenelon, Z. Gu, E. Rothberg, R. Wunderling, Mixed-integer programming: a progress report, in: M. Grötschel (Ed.), The Sharpest Cut: The Impact of Manfred Padberg and His Work, SIAM, Philadelphia, PA, 2004, pp. 309–325, doi: 10.1137/1.9780898718805.ch18.
R. E. Bixby, “A Brief History of Linear and Mixed-Integer Programming Computation.” Documenta Mathematica, 107–121, 2012, doi: 10.4171/dms/6/16.
T. Koch, T. Berthold, J. Pedersen, “Progress in Mathematical Programming Solvers from 2001 to 2020”, EURO Journal on Computational Optimization 10, 1-18, 2022, doi: 10.1016/j.ejco.2022.100031.
GUROBI Optimizer Reference Manual, 10.0 version, Gurobi Optimization, Beaverton, Oregon, U.S.A. 2023.
User's Manual for CPLEX, 22.1.1 version, IBM, Armonk, New York, U.S.A. 2022.
User's Manual for CPLEX, 12.10 version, IBM, Armonk, New York, U.S.A. 2021.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Francis J. Vasko, Yun Lu, Myung Soon Song, Dominic Rando
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
License and Copyright Agreement
In submitting the manuscript to the journal, the authors certify that:
- They are authorized by their co-authors to enter into these arrangements.
- The work described has not been formally published before, except in the form of an abstract or as part of a published lecture, review, thesis, or overlay journal. Please also carefully read the International Journal of Industrial Optimization (IJIO) Author Guidelines at http://journal2.uad.ac.id/index.php/ijio/about/submissions#onlineSubmissions
- That it is not under consideration for publication elsewhere,
- That its publication has been approved by all the author(s) and by the responsible authorities tacitly or explicitly of the institutes where the work has been carried out.
- They secure the right to reproduce any material that has already been published or copyrighted elsewhere.
- They agree to the following license and copyright agreement.
Copyright
Authors who publish with the International Journal of Industrial Optimization (IJIO) agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License (CC BY-SA 4.0) that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
1.png)
