Abstract
Algorithm selection is a class of meta-algorithms that has emerged as a crucial approach for solving complex combinatorial optimization problems. Successful algorithm selection involves navigating a diverse landscape of solvers, each designed with distinct heuristics and search strategies. It is a classification problem in which statistical features of a problem instance are used to select the algorithm that should tackle it most efficiently. However, minimal attention has been given to investigating algorithm selection decisions. This work presents a framework for iterative feature selection and explainable multi-class classification in Algorithm Selection for the Capacitated Lot Sizing Problem (CLSP). The CLSP is a combinatorial optimization problem widely studied with important industrial applications. The framework reduces the features considered by the machine learning approach and uses SHAP analysis to investigate their contribution to the selection. The analysis shows which instance type characteristics positively affect the relative performance of a heuristic. The approach can be used to improve the algorithm selection’s transparency and inform the developer of an algorithm’s weak and strong points. The experimental analysis shows that the framework selector provides valuable insights with a narrow optimality gap close to a parallel deployment of the heuristic set that generalises well to instances considerably bigger than the training ones.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bischl, B., et al.: ASlib: a benchmark library for algorithm selection. Artif. Intell. 237, 41–58 (2016)
Chen, W.H., Thizy, J.M.: Analysis of relaxations for the multi-item capacitated lot-sizing problem. Ann. Oper. Res. 26, 29–72 (1990). https://doi.org/10.1007/BF02248584
Copil, K., Wörbelauer, M., Meyr, H., Tempelmeier, H.: Simultaneous lotsizing and scheduling problems: a classification and review of models. OR Spect. 39(1), 1–64 (2017). https://doi.org/10.1007/s00291-015-0429-4
Dalla, M., Visentin, A., O’Sullivan, B.: Automated SAT problem feature extraction using convolutional autoencoders. In: IEEE International Conference on Tools with Artificial Intelligence (ICTAI) (2021)
Dixon, P.S., Silver, E.A.: A heuristic solution procedure for the multi-item, single-level, limited capacity, lot-sizing problem. J. Oper. Manag. 2(1), 23–39 (1981). https://doi.org/10.1016/0272-6963(81)90033-4
Dogramaci, A., Panayiotopoulos, J.C., Adam, N.R.: The dynamic lot-sizing problem for multiple items under limited capacity. AIIE Trans. 13(4), 294–303 (1981). https://doi.org/10.1080/05695558108974565
Gebruers, C., Hnich, B., Bridge, D., Freuder, E.: Using cbr to select solution strategies in constraint programming. In: Munoz-Avila, H., Ricci, F. (eds.) ICCBR 2005. LNCS, vol. 3620, pp. 222–236. Springer, Heidelberg (2005). https://doi.org/10.1007/11536406_19
Günther, H.O.: Planning lot sizes and capacity requirements in a single stage production system. Eur. J. Oper. Res. 31(2), 223–231 (1987). https://doi.org/10.1016/0377-2217(87)90026-9
Hurley, B., Kotthoff, L., Malitsky, Y., O’Sullivan, B.: Proteus: a hierarchical portfolio of solvers and transformations. In: Simonis, H. (ed.) CPAIOR 2014. LNCS, vol. 8451, pp. 301–317. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-319-07046-9_22
Kärcher, J., Meyr, H.: A machine learning approach for identifying the best solution heuristic for a large scaled capacitated lotsizing problem. In: Preprint - Research Square (2023). https://doi.org/10.21203/rs.3.rs-3709286/v1
Karimi, B., Fatemi Ghomi, S., Wilson, J.: The capacitated lot sizing problem: a review of models and algorithms. Omega 31(5), 365–378 (2003). https://doi.org/10.1016/S0305-0483(03)00059-8
Kerschke, P., Hoos, H.H., Neumann, F., Trautmann, H.: Automated algorithm selection: survey and perspectives. Evol. Comput. 27(1), 3–45 (2019)
Kostovska, A., Doerr, C., Džeroski, S., Kocev, D., Panov, P., Eftimov, T.: Explainable model-specific algorithm selection for multi-label classification. In: 2022 IEEE Symposium Series on Computational Intelligence (SSCI), pp. 39–46. IEEE (2022)
Kotthoff, L.: Algorithm selection for combinatorial search problems: a survey. In: Data Mining and Constraint Programming: Foundations of a Cross-Disciplinary Approach, pp. 149–190 (2016)
Lambrecht, M.R., Vanderveken, H.: Heuristic procedures for the single operation, multi-item loading problem. AIIE Trans. 11(4), 319–326 (1979). https://doi.org/10.1080/05695557908974478
Lindauer, M., van Rijn, J.N., Kotthoff, L.: The algorithm selection competitions 2015 and 2017. Artif. Intell. 272, 86–100 (2019)
Lundberg, S.M., Lee, S.I.: A unified approach to interpreting model predictions. Adv. Neural Inf. Process. Syst. 30, 1–10 (2017)
Müller, D., Müller, M.G., Kress, D., Pesch, E.: An algorithm selection approach for the flexible job shop scheduling problem: choosing constraint programming solvers through machine learning. Eur. J. Oper. Res. 302(3), 874–891 (2022)
Pulatov, D., Anastacio, M., Kotthoff, L., Hoos, H.: Opening the black box: automated software analysis for algorithm selection. In: International Conference on Automated Machine Learning, pp. 6–1. PMLR (2022)
Ramya, R., Rajendran, C., Ziegler, H., Mohapatra, S., Ganesh, K., et al.: Capacitated Lot Sizing Problems in Process Industries. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-030-01222-9
Sadreddin, A., Mouhoub, M., Sadaoui, S.: Portfolio selection for sat instances. In: 2022 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pp. 2962–2967. IEEE (2022)
Shao, X., Wang, H., Zhu, X., Xiong, F., Mu, T., Zhang, Y.: EFFECT: explainable framework for meta-learning in automatic classification algorithm selection. Inf. Sci. 622, 211–234 (2023)
Wolpert, D.H., Macready, W.G.: No free lunch theorems for optimization. IEEE Trans. Evol. Comput. 1(1), 67–82 (1997)
Xu, L., Hutter, F., Hoos, H.H., Leyton-Brown, K.: SATzilla: portfolio-based algorithm selection for sat. J. Artif. Intell. Res. 32, 565–606 (2008)
Acknowledgments
This publication has emanated from research supported by Science Foundation Ireland under Grant No. 12/RC/2289-P2 at Insight, the SFI Research Centre for Data Analytics, which is co-funded under the European Regional Development Fund, and by the EU Horizon project TAILOR (952215). The authors gratefully acknowledge useful inputs from Lars Kotthoff.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Visentin, A., Gallchóir, A.Ó., Kärcher, J., Meyr, H. (2024). Explainable Algorithm Selection for the Capacitated Lot Sizing Problem. In: Dilkina, B. (eds) Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2024. Lecture Notes in Computer Science, vol 14743. Springer, Cham. https://doi.org/10.1007/978-3-031-60599-4_16
Download citation
DOI: https://doi.org/10.1007/978-3-031-60599-4_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-60601-4
Online ISBN: 978-3-031-60599-4
eBook Packages: Computer ScienceComputer Science (R0)