EUVIMEDEUVIMED entdecken
Open Access · CC BY-SA 4.0

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

Brooks Emerick, Yun Lu, Francis J. Vasko

International Journal of Industrial Optimization · 2021

DOI: 10.12928/ijio.v2i1.2948 ↗

Kurz gefasst

Fachartikel in der Zeitschrift International Journal of Industrial Optimization, 2021. Verfasst von Brooks Emerick und 2 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref). Der Volltext ist frei zugänglich (Open Access, CC BY-SA 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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

Zitieren

APA

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. https://doi.org/10.12928/ijio.v2i1.2948

Vancouver

Emerick B, Lu Y, Vasko FJ. Using machine learning to predict the number of alternative solutions to a minimum cardinality set covering problem. International Journal of Industrial Optimization. 2021. doi:10.12928/ijio.v2i1.2948

BibTeX
@article{Emerick2021,
  author = {Emerick, Brooks and Lu, Yun and Vasko, Francis J.},
  title = {Using machine learning to predict the number of alternative solutions to a minimum cardinality set covering problem},
  journal = {International Journal of Industrial Optimization},
  year = {2021},
  doi = {10.12928/ijio.v2i1.2948}
}
Kostenlos starten →