{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,31]],"date-time":"2025-07-31T00:44:13Z","timestamp":1753922653466,"version":"3.40.3"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030954697"},{"type":"electronic","value":"9783030954703"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-030-95470-3_22","type":"book-chapter","created":{"date-parts":[[2022,2,1]],"date-time":"2022-02-01T10:07:13Z","timestamp":1643710033000},"page":"283-298","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Learning Beam Search: Utilizing Machine Learning to\u00a0Guide Beam Search for\u00a0Solving Combinatorial Optimization Problems"],"prefix":"10.1007","author":[{"given":"Marc","family":"Huber","sequence":"first","affiliation":[]},{"given":"G\u00fcnther R.","family":"Raidl","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,2]]},"reference":[{"key":"22_CR1","unstructured":"Abe, K., Xu, Z., Sato, I., Sugiyama, M.: Solving NP-hard problems on graphs with extended AlphaGo Zero. arXiv:1905.11623 [cs, stat] (2020)"},{"issue":"5","key":"22_CR2","doi-asserted-by":"publisher","first-page":"1513","DOI":"10.1016\/j.cor.2008.02.003","volume":"36","author":"H Akeba","year":"2009","unstructured":"Akeba, H., Hifib, M., Mhallah, R.: A beam search algorithm for the circular packing problem. Comput. Oper. Res. 36(5), 1513\u20131528 (2009)","journal-title":"Comput. Oper. Res."},{"issue":"1","key":"22_CR3","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1016\/j.cor.2010.05.008","volume":"38","author":"C Blum","year":"2011","unstructured":"Blum, C., Miralles, C.: On solving the assembly line worker assignment and balancing problem via beam search. Comput. Oper. Res. 38(1), 328\u2013339 (2011)","journal-title":"Comput. Oper. Res."},{"key":"22_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/978-3-540-74446-7_11","volume-title":"Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Effective Heuristics","author":"C Blum","year":"2007","unstructured":"Blum, C., Blesa, M.J.: Probabilistic beam search for the longest common subsequence problem. In: St\u00fctzle, T., Birattari, M., Hoos, H.H. (eds.) SLS 2007. LNCS, vol. 4638, pp. 150\u2013161. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-74446-7_11"},{"key":"22_CR5","unstructured":"Dai, H., Khalil, E.B., Zhang, Y., Dilkina, B., Song, L.: Learning combinatorial optimization algorithms over graphs. In: Advances in Neural Information Processing Systems, vol. 31, pp. 6348\u20136358. Curran Associates, Inc. (2017)"},{"key":"22_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-030-62867-3_5","volume-title":"Optimization and Applications","author":"M Djukanovic","year":"2020","unstructured":"Djukanovic, M., Berger, C., Raidl, G.R., Blum, C.: On Solving a generalized constrained longest common subsequence problem. In: Olenev, N., Evtushenko, Y., Khachay, M., Malkova, V. (eds.) OPTIMA 2020. LNCS, vol. 12422, pp. 55\u201370. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-62867-3_5"},{"key":"22_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/978-3-030-37599-7_14","volume-title":"Machine Learning, Optimization, and Data Science","author":"M Djukanovic","year":"2019","unstructured":"Djukanovic, M., Raidl, G.R., Blum, C.: A beam search for the longest common subsequence problem guided by a novel approximate expected length calculation. In: Nicosia, G., Pardalos, P., Umeton, R., Giuffrida, G., Sciacca, V. (eds.) LOD 2019. LNCS, vol. 11943, pp. 154\u2013167. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-37599-7_14"},{"issue":"2","key":"22_CR8","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1016\/j.ejor.2004.04.015","volume":"165","author":"M Ghirardi","year":"2005","unstructured":"Ghirardi, M., Potts, C.N.: Makespan minimization for scheduling unrelated parallel machines: a recovering beam search approach. Eur. J. Oper. Res. 165(2), 457\u2013467 (2005)","journal-title":"Eur. J. Oper. Res."},{"key":"22_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/978-3-540-69068-9_24","volume-title":"Combinatorial Pattern Matching","author":"Z Gotthilf","year":"2008","unstructured":"Gotthilf, Z., Hermelin, D., Lewenstein, M.: Constrained LCS: hardness and approximation. In: Ferragina, P., Landau, G.M. (eds.) CPM 2008. LNCS, vol. 5029, pp. 255\u2013262. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-69068-9_24"},{"key":"22_CR10","doi-asserted-by":"crossref","unstructured":"Gusfield, D.: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, New York (1997)","DOI":"10.1017\/CBO9780511574931"},{"key":"22_CR11","unstructured":"He, H., Daum\u00e9, H.C., Eisner, J.M.: Learning to search in branch-and-bound algorithms. In: Ghahramani, Z., et al. (eds.) Advances in Neural Information Processing Systems, vol. 27. Curran Associates, Inc. (2014)"},{"key":"22_CR12","unstructured":"Huang, J., Patwary, M., Diamos, G.: Coloring big graphs with AlphaGo Zero. arXiv:1902.10162 [cs] (2019)"},{"issue":"14","key":"22_CR13","doi-asserted-by":"publisher","first-page":"i295","DOI":"10.1093\/bioinformatics\/btz375","volume":"35","author":"L Huang","year":"2019","unstructured":"Huang, L., et al.: LinearFold: linear-time approximate RNA folding by 5\u2019-to-3\u2019 dynamic programming and beam search. Bioinformatics 35(14), i295\u2013i304 (2019)","journal-title":"Bioinformatics"},{"key":"22_CR14","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2021.04.032","author":"M Karimi-Mamaghan","year":"2021","unstructured":"Karimi-Mamaghan, M., Mohammadi, M., Meyer, P., Karimi-Mamaghan, A.M., Talbi, E.G.: Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: a state-of-the-art. Eur. J. Oper. Res. (2021). https:\/\/doi.org\/10.1016\/j.ejor.2021.04.032","journal-title":"Eur. J. Oper. Res."},{"key":"22_CR15","doi-asserted-by":"crossref","unstructured":"Khalil, E.B., Bodic, P.L., Song, L., Nemhauser, G., Dilkina, B.: Learning to branch in mixed integer programming. In: Proceedings of the 26th International Joint Conference on Artificial Intelligence, pp. 724\u2013731. AAAI Press (2016)","DOI":"10.1609\/aaai.v30i1.10080"},{"key":"22_CR16","doi-asserted-by":"crossref","unstructured":"Khalil, E.B., Dilkina, B., Nemhauser, G.L., Ahmed, S., Shao, Y.: Learning to run heuristics in tree search. In: Proceedings of the 26th International Joint Conference on Artificial Intelligence, pp. 659\u2013666. Melbourne, Australia (2017)","DOI":"10.24963\/ijcai.2017\/92"},{"key":"22_CR17","unstructured":"Kingma, D.P., Ba, J.: Adam: a method for stochastic optimization. In: Proceedings of the 3rd International Conference on Learning Representations, San Diego, CA (2015)"},{"key":"22_CR18","unstructured":"Laterre, A., et al.: Ranked reward: enabling self-play reinforcement learning for combinatorial optimization. In: AAAI 2019 Workshop on Reinforcement Learning on Games. AAAI Press (2018)"},{"key":"22_CR19","doi-asserted-by":"crossref","unstructured":"Lowerre, B.: The harpy speech recognition system. Ph.D. thesis, Carnegie Mellon University, Pittsburgh, PA (1976)","DOI":"10.1121\/1.2003013"},{"issue":"2","key":"22_CR20","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D Maier","year":"1978","unstructured":"Maier, D.: The complexity of some problems on subsequences and supersequences. J. ACM 25(2), 322\u2013336 (1978)","journal-title":"J. ACM"},{"key":"22_CR21","unstructured":"Mittal, A., Dhawan, A., Manchanda, S., Medya, S., Ranu, S., Singh, A.: Learning heuristics over large graphs via deep reinforcement learning. arXiv:1903.03332 [cs, stat] (2019)"},{"key":"22_CR22","unstructured":"Negrinho, R., Gormley, M., Gordon, G.J.: Learning beam search policies via imitation learning. In: Bengio, S., et al. (eds.) Advances in Neural Information Processing Systems, vol. 31, pp. 10652\u201310661. Curran Associates, Inc. (2018)"},{"key":"22_CR23","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1080\/00207548808947840","volume":"26","author":"PS Ow","year":"1988","unstructured":"Ow, P.S., Morton, T.E.: Filtered beam search in scheduling. Int. J. Prod. Res. 26, 297\u2013307 (1988)","journal-title":"Int. J. Prod. Res."},{"issue":"1","key":"22_CR24","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.cor.2007.07.006","volume":"36","author":"SJ Shyu","year":"2009","unstructured":"Shyu, S.J., Tsai, C.Y.: Finding the longest common subsequence for multiple biological sequences by ant colony optimization. Comput. Oper. Res. 36(1), 73\u201391 (2009)","journal-title":"Comput. Oper. Res."},{"issue":"6419","key":"22_CR25","doi-asserted-by":"publisher","first-page":"1140","DOI":"10.1126\/science.aar6404","volume":"362","author":"D Silver","year":"2018","unstructured":"Silver, D., et al.: A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science 362(6419), 1140\u20131144 (2018)","journal-title":"Science"},{"key":"22_CR26","unstructured":"Song, J., Lanka, R., Zhao, A., Bhatnagar, A., Yue, Y., Ono, M.: Learning to search via retrospective imitation. arXiv:1804.00846 [cs, stat] (2019)"},{"key":"22_CR27","unstructured":"Sutskever, I., Vinyals, O., Le, Q.V.: Sequence to sequence learning with neural networks. In: Advances in Neural Information Processing Systems, vol. 27. Curran Associates, Inc. (2014)"},{"key":"22_CR28","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/j.ipl.2003.07.001","volume":"88","author":"Y Tsai","year":"2003","unstructured":"Tsai, Y.: The constrained longest common subsequence problem. Inf. Process. Lett. 88, 173\u2013176 (2003)","journal-title":"Inf. Process. Lett."},{"key":"22_CR29","doi-asserted-by":"crossref","unstructured":"Weiss, D., Alberti, C., Collins, M., Petrov, S.: Structured training for neural network transition-based parsing (2015)","DOI":"10.3115\/v1\/P15-1032"}],"container-title":["Lecture Notes in Computer Science","Machine Learning, Optimization, and Data Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-95470-3_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T11:57:51Z","timestamp":1674647871000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-95470-3_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783030954697","9783030954703"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-95470-3_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"2 February 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LOD","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Machine Learning, Optimization, and Data Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Grasmere","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"United Kingdom","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 October 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 October 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"mod2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/lod2021.icas.cc\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"215","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"86","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"40% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"5-6","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"1-2","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}