Speeding Up Logic-Based Benders Decomposition by Strengthening Cuts with Graph Neural NetworksShow others and affiliations
2024 (English)In: Machine Learning, Optimization, and Data Science / [ed] Giuseppe Nicosia, Varun Ojha, Emanuele La Malfa, Gabriele La Malfa, Panos M. Pardalos, Renato Umeton, Cham: Springer, 2024, p. 24-38Conference paper, Published paper (Refereed)
Abstract [en]
Logic-based Benders decomposition is a technique to solve optimization problems to optimality. It works by splitting the problem into a master problem, which neglects some aspects of the problem, and a subproblem, which is used to iteratively produce cuts for the master problem to account for those aspects. It is critical for the computational performance that these cuts are strengthened, but the strengthening of cuts comes at the cost of solving additional subproblems. In this work we apply a graph neural network in an autoregressive fashion to approximate the compilation of an irreducible cut, which then only requires few postprocessing steps to ensure its validity. We test the approach on a job scheduling problem with a single machine and multiple time windows per job and compare to approaches from the literature. Results show that our approach is capable of considerably reducing the number of subproblems that need to be solved and hence the total computational effort.
Place, publisher, year, edition, pages
Cham: Springer, 2024. p. 24-38
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 14505
Keywords [en]
Logic-based Benders Decomposition; Cut Strengthening; Graph Neural Networks; Job Scheduling
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-200891DOI: 10.1007/978-3-031-53969-5_3ISI: 001217088300003ISBN: 9783031539688 (print)ISBN: 9783031539695 (electronic)OAI: oai:DiVA.org:liu-200891DiVA, id: diva2:1838192
Conference
9th International Conference, LOD 2023, Grasmere, UK, September 22–26, 2023
Note
Funding Agencies|Honda Research Institute Europe
2024-02-152024-02-152024-12-20Bibliographically approved