Using machine learning to predict the number of alternative solutions to a minimum cardinality set covering problem
DOI:
https://doi.org/10.12928/ijio.v2i1.2948Keywords:
Minimum cardinality set covering problem, Unicost set covering problem, Machine learning, Regression trees, Number of alternative optimal solutionAbstract
Although the characterization of alternative optimal solutions for linear programming problems is well known, such characterizations for combinatorial optimization problems are essentially non-existent. This is the first article to qualitatively predict the number of alternative optima for a classic NP-hard combinatorial optimization problem, namely, the minimum cardinality (also called unicost) set covering problem (MCSCP). For the MCSCP, a set must be covered by a minimum number of subsets selected from a specified collection of subsets of the given set. The MCSCP has numerous industrial applications that require that a secondary objective is optimized once the size of a minimum cover has been determined. To optimize the secondary objective, the number of MCSCP solutions is optimized. In this article, for the first time, a machine learning methodology is presented to generate categorical regression trees to predict, qualitatively (extra-small, small, medium, large, or extra-large), the number of solutions to an MCSCP. Within the machine learning toolbox of MATLAB®, 600,000 unique random MCSCPs were generated and used to construct regression trees. The prediction quality of these regression trees was tested on 5000 different MCSCPs. For the 5-output model, the average accuracy of being at most one off from the predicted category was 94.2%.ÂReferences
C. Saleh, R.A.C. Leuuveano, M.N.A. Rahman, B. M. Deros, & N.R., Dzakiyullah. (2015). Predicting of CO2 emissions using an artificial neural network: the case of the sugar industry. Adv. Sci. Lett., 21, 3079-3083.
D. K. Williams Jr., A. L. Kovach, D. C. Muddiman, & K. W. Hanck. (2009). Utilizing artificial neural networks in MATLAB to achieve parts-per-billion mass measurement accuracy with a fourier transform ion cyclotron resonance mass spectrometer. American Society for Mass Spectrometry, 20, 1301-1310.
E.L. Lawler. (1972). Procedure for computing the K best solutions to discrete optimization problems and its application to the shortest path problem. Management Science, 18(7), 401-405.
F. J. Vasko, F. E. Wolf, & K. L. Stott. (1987). Optimal selection of ingot sizes via set covering. Opns Res, 35, 346-353.
F. J. Vasko, F. E. Wolf, & K. L. Stott. (1989). A set covering approach to metallurgical grade Assignment. Eur J Opl Res, 38, 27-34.
F. J. Vasko, D. D. Newhart, & A. D. Strauss. (2005). Coal blending models for optimum cokemaking and blast furnace operation. Journal of the Operational Research Society, 56 (3), 235-243.
F. S. Hillier & J. Lieberman. (2010). Introduction to Operations Research. 9th Edition, New York: McGraw-Hill.
H.W. Hamacher & M. Queyranne, M. (1985). K-best solutions to combinatorial optimization problems. Annals of Operations research, 4, 123-145.
H. Taha. (2017). Operations Research: An Introduction, 10th Edition, Pearson, Boston, MA.
MATLAB. (2020). Statistics and Machine Learning Toolbox User’s Guide. R2020a, 1 Apple Hill Dr, Natick, MA 01760-2098.
R. E., Bixby. (2012). A brief history of linear and mixed-integer programming computation. Documenta Mathematica Extra volume ISMP, 107-121.
R. M. Karp. (1972). Reducibility among combinatorial problems,†in Complexity of Computer Computations, Miller R E and Thatcher J W (eds), 85-103. Plenum, New York.
T. Huang, Y. Gong, & J. Zhang. (2018). Seeking multiple solutions of combinatorial optimization problems: a proof of principle studyâ€, in 2018 IEEE Symposium Series on Computational Intelligence (SSCI), 1212-1218. Bangalore, India.
D. K. Williams Jr., A. L. Kovach, D. C. Muddiman, & K. W. Hanck. (2009). Utilizing artificial neural networks in MATLAB to achieve parts-per-billion mass measurement accuracy with a fourier transform ion cyclotron resonance mass spectrometer. American Society for Mass Spectrometry, 20, 1301-1310.
E.L. Lawler. (1972). Procedure for computing the K best solutions to discrete optimization problems and its application to the shortest path problem. Management Science, 18(7), 401-405.
F. J. Vasko, F. E. Wolf, & K. L. Stott. (1987). Optimal selection of ingot sizes via set covering. Opns Res, 35, 346-353.
F. J. Vasko, F. E. Wolf, & K. L. Stott. (1989). A set covering approach to metallurgical grade Assignment. Eur J Opl Res, 38, 27-34.
F. J. Vasko, D. D. Newhart, & A. D. Strauss. (2005). Coal blending models for optimum cokemaking and blast furnace operation. Journal of the Operational Research Society, 56 (3), 235-243.
F. S. Hillier & J. Lieberman. (2010). Introduction to Operations Research. 9th Edition, New York: McGraw-Hill.
H.W. Hamacher & M. Queyranne, M. (1985). K-best solutions to combinatorial optimization problems. Annals of Operations research, 4, 123-145.
H. Taha. (2017). Operations Research: An Introduction, 10th Edition, Pearson, Boston, MA.
MATLAB. (2020). Statistics and Machine Learning Toolbox User’s Guide. R2020a, 1 Apple Hill Dr, Natick, MA 01760-2098.
R. E., Bixby. (2012). A brief history of linear and mixed-integer programming computation. Documenta Mathematica Extra volume ISMP, 107-121.
R. M. Karp. (1972). Reducibility among combinatorial problems,†in Complexity of Computer Computations, Miller R E and Thatcher J W (eds), 85-103. Plenum, New York.
T. Huang, Y. Gong, & J. Zhang. (2018). Seeking multiple solutions of combinatorial optimization problems: a proof of principle studyâ€, in 2018 IEEE Symposium Series on Computational Intelligence (SSCI), 1212-1218. Bangalore, India.
Downloads
Published
2021-02-24
How to Cite
Emerick, B., Lu, Y., & Vasko, F. J. (2021). Using machine learning to predict the number of alternative solutions to a minimum cardinality set covering problem. International Journal of Industrial Optimization, 2(1), 1–16. https://doi.org/10.12928/ijio.v2i1.2948
Issue
Section
Articles
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)
