Abstract
Recently, deep neural networks have demonstrated remarkable performance in addressing combinatorial optimization challenges. The expressive power of graph neural networks combined with Reinforcement Learning (RL) enabled learning heuristics that rival or even surpass conventional methods. Such advancements have paved the way for Neural Combinatorial Optimization (NCO), an emerging paradigm that enables end-to-end heuristic learning without the reliance on expert knowledge. In this paper, we propose an NCO approach to learn heuristics for the vast family of Combinatorial Optimization Problems (COPs) defined on K-partite hypergraphs, including multi-dimensional assignment or scheduling problems. Central to our approach is the ability to represent sophisticated functions on K-partite hypergraphs, using a novel family of neural networks. We show that our heuristic competes with other ones in comparable settings and that our method can also be applied to more complex real-life assignment and scheduling problems.
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
Balas, E., Saltzman, M.J.: An algorithm for the three-index assignment problem. Oper. Res. 39(1), 150–161 (1991)
Bekker, H., Braad, E.P., Goldengorin, B.: Using bipartite and multidimensional matching to select the roots of a system of polynomial equations. In: Gervasi, O., et al. (eds.) ICCSA 2005, Part IV. LNCS, vol. 3483, pp. 397–406. Springer, Heidelberg (2005). https://doi.org/10.1007/11424925_43
Bello, I., Pham, H., Le, Q.V., Norouzi, M., Bengio, S.: Neural combinatorial optimization with reinforcement learning (2017). https://doi.org/10.48550/arXiv.1611.09940, arXiv:1611.09940 [cs, stat]
Ceselli, A., Righini, G.: A branch-and-price algorithm for the multilevel generalized assignment problem. Oper. Res. 54(6), 1172–1184 (2006)
Croes, G.A.: A method for solving traveling-salesman problems. Oper. Res. 6(6), 791–812 (1958)
Dang, X., Cheng, Q., Zhu, H.: Indoor multiple sound source localization via multi-dimensional assignment data association. IEEE/ACM Trans. Audio Speech Lang. Process. 27(12), 1944–1956 (2019). https://doi.org/10.1109/TASLP.2019.2935837
Feng, Y., You, H., Zhang, Z., Ji, R., Gao, Y.: Hypergraph neural networks. CoRR abs/1809.09401 (2018). http://arxiv.org/abs/1809.09401
French, A.P., Wilson, J.M.: Heuristic solution methods for the multilevel generalized assignment problem. J. Heuristics 8, 143–153 (2002)
Frieze, A., Yadegar, J.: An algorithm for solving 3-dimensional assignment problems with application to scheduling a teaching practice. J. Oper. Res. Soc. 32, 989–995 (1981)
Gao, Y., Feng, Y., Ji, S., Ji, R.: HGNN+: general hypergraph neural networks. IEEE Trans. Pattern Anal. Mach. Intell. 45(3), 3181–3199 (2022)
Garey, M.R., Johnson, D.S.: Computers and Intractability, vol. 174. Freeman, San Francisco (1979)
Gibbons, D., Lim, C.C., Shi, P.: Deep learning for bipartite assignment problems. In: 2019 IEEE International Conference on Systems, Man and Cybernetics (SMC), pp. 2318–2325 (2019). https://doi.org/10.1109/SMC.2019.8914228
Glover, F., Hultz, J., Klingman, D.: Improved computer-based planning techniques, part 1. Interfaces 8(4), 16–25 (1978)
Gutin, G., Goldengorin, B., Huang, J.: Worst case analysis of max-regret, greedy and other heuristics for multidimensional assignment and traveling salesman problems. In: Erlebach, T., Kaklamanis, C. (eds.) WAOA 2006. LNCS, vol. 4368, pp. 214–225. Springer, Heidelberg (2007). https://doi.org/10.1007/11970125_17
Horowitz, E., Sahni, S.: Exact and approximate algorithms for scheduling nonidentical processors. J. ACM (JACM) 23(2), 317–327 (1976)
Karapetyan, D., Gutin, G., Goldengorin, B.: Empirical evaluation of construction heuristics for the multidimensional assignment problem. arXiv preprint arXiv:0906.2960 (2009)
Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016)
Kool, W., van Hoof, H., Welling, M.: Attention, learn to solve routing problems! (2019). https://doi.org/10.48550/arXiv.1803.08475, arXiv:1803.08475 [cs, stat]
Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. 21(2), 498–516 (1973)
Pierskalla, W.P.: The multidimensional assignment problem. Oper. Res. 16(2), 422–431 (1968)
Puterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, Hoboken (2014)
Rainjonneau, S., et al.: Quantum algorithms applied to satellite mission planning for earth observation. IEEE J. Sel. Top. Appl. Earth Observ. Remote Sens. 16, 7062–7075 (2023). https://doi.org/10.1109/jstars.2023.3287154, http://dx.doi.org/10.1109/JSTARS.2023.3287154
Schlichtkrull, M., Kipf, T.N., Bloem, P., van den Berg, R., Titov, I., Welling, M.: Modeling relational data with graph convolutional networks. In: Gangemi, A., et al. (eds.) ESWC 2018. LNCS, vol. 10843, pp. 593–607. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-93417-4_38
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., Klimov, O.: Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 (2017)
Spieksma, F.C., Woeginger, G.J.: Geometric three-dimensional assignment problems. Eur. J. Oper. Res. 91(3), 611–618 (1996)
Sutton, R.S., Barto, A.G.: Reinforcement Learning: An Introduction. MIT Press, Cambridge (2018)
Vaswani, A., et al.: Attention is all you need. In: Advances in Neural Information Processing Systems, vol. 30 (2017)
Vinyals, O., Fortunato, M., Jaitly, N.: Pointer networks (2017). https://doi.org/10.48550/arXiv.1506.03134, arXiv:1506.03134 [cs, stat]
Wang, J., Song, G., Liang, Z., Demeulemeester, E., Hu, X., Liu, J.: Unrelated parallel machine scheduling with multiple time windows: an application to earth observation satellite scheduling. Comput. Oper. Res. 149, 106010 (2023)
Whitney, H.: A theorem on graphs. Ann. Math. 378–390 (1931)
Zhang, R., et al.: Learning to solve multiple-TSP with time window and rejections via deep reinforcement learning. IEEE Trans. Intell. Transp. Syst. 1–12 (2022). https://doi.org/10.1109/TITS.2022.3207011
Acknowledgment
We acknowledge the support of the IRT-MINDS project.
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
Zouitine, M., Berjaoui, A., Lagnoux, A., Pellegrini, C., Rachelson, E. (2024). Learning Heuristics for Combinatorial Optimization Problems on K-Partite Hypergraphs. 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_21
Download citation
DOI: https://doi.org/10.1007/978-3-031-60599-4_21
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)