Using machine learning to predict the number of alternative solutions to a minimum cardinality set covering problem

Brooks Emerick, Yun Lu, Francis J. Vasko

Abstract


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%. 

Keywords


Minimum cardinality set covering problem; Unicost set covering problem; Machine learning; Regression trees; Number of alternative optimal solution

Full Text:

PDF

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.




DOI: https://doi.org/10.12928/ijio.v2i1.2948

Refbacks

  • There are currently no refbacks.


Copyright (c) 2021 Brooks Emerick, Yun Lu, Francis J. Vasko

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

=================================================================================

International Journal of Industrial Optimization (IJIO)
ISSN: 2714-6006, e-ISSN: 2723-3022
Universitas Ahmad Dahlan, 4th Campus
Jl. Ringroad Selatan, Kragilan, Tamanan, Banguntapan, Bantul, Yogyakarta, Indonesia 55191
Phone: +62 (274) 563515, 511830, 379418, 371120 ext. 4902, Fax: +62 274 564604

View IJIO Stats