Speeding Up Logic-Based Benders Decomposition by Strengthening Cuts with Graph Neural Networks

被引:0
作者
Varga, Johannes [1 ]
Karlsson, Emil [2 ,3 ]
Raidl, Guenther R. [1 ]
Ronnberg, Elina [2 ]
Lindsten, Fredrik [4 ]
Rodemann, Tobias [5 ]
机构
[1] TU Wien, Inst Log & Computat, Vienna, Austria
[2] Linkoping Univ, Dept Math, Linkoping, Sweden
[3] Saab AB, S-58188 Linkoping, Sweden
[4] Linkoping Univ, Dept Comp & Informat Sci, Linkoping, Sweden
[5] Honda Res Inst Europe, Offenbach, Germany
来源
MACHINE LEARNING, OPTIMIZATION, AND DATA SCIENCE, LOD 2023, PT I | 2024年 / 14505卷
关键词
Logic-based Benders Decomposition; Cut Strengthening; Graph Neural Networks; Job Scheduling;
D O I
10.1007/978-3-031-53969-5_3
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
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.
引用
收藏
页码:24 / 38
页数:15
相关论文
共 50 条
[41]   Domination based graph neural networks [J].
Meybodi, Mohsen Alambardar ;
Safari, Mahdi ;
Davoodijam, Ensieh .
International Journal of Computers and Applications, 2024, 46 (11) :998-1005
[42]   Markov Logic meets Graph Neural Networks: A Study for Situational Awareness [J].
Nguyen, Van .
2021 IEEE 24TH INTERNATIONAL CONFERENCE ON INFORMATION FUSION (FUSION), 2021, :805-812
[43]   Graph-based Recommendation using Graph Neural Networks [J].
Dossena, Marco ;
Irwin, Christopher ;
Portinale, Luigi .
2022 21ST IEEE INTERNATIONAL CONFERENCE ON MACHINE LEARNING AND APPLICATIONS, ICMLA, 2022, :1769-1774
[44]   UNTANGLE: Unlocking Routing and Logic Obfuscation Using Graph Neural Networks-based Link Prediction [J].
Alrahis, Lilas ;
Patnaik, Satwik ;
Hanif, Muhammad Abdullah ;
Shafique, Muhammad ;
Sinanoglu, Ozgur .
2021 IEEE/ACM INTERNATIONAL CONFERENCE ON COMPUTER AIDED DESIGN (ICCAD), 2021,
[45]   Social Recommendation based on Graph Neural Networks [J].
Sun, Hongji ;
Lin, Lili ;
Chen, Riqing .
2020 IEEE INTL SYMP ON PARALLEL & DISTRIBUTED PROCESSING WITH APPLICATIONS, INTL CONF ON BIG DATA & CLOUD COMPUTING, INTL SYMP SOCIAL COMPUTING & NETWORKING, INTL CONF ON SUSTAINABLE COMPUTING & COMMUNICATIONS (ISPA/BDCLOUD/SOCIALCOM/SUSTAINCOM 2020), 2020, :489-496
[46]   Logic-Informed Graph Neural Networks for Structural Form-Finding [J].
Bleker, Lazlo ;
Tam, Kam -Ming Mark ;
D'Acunto, Pierluigi .
ADVANCED ENGINEERING INFORMATICS, 2024, 61
[47]   Graph Rewiring and Preprocessing for Graph Neural Networks Based on Effective Resistance [J].
Shen, Xu ;
Lio, Pietro ;
Yang, Lintao ;
Yuan, Ru ;
Zhang, Yuyang ;
Peng, Chengbin .
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2024, 36 (11) :6330-6343
[48]   Attention-based graph neural networks: a survey [J].
Chengcheng Sun ;
Chenhao Li ;
Xiang Lin ;
Tianji Zheng ;
Fanrong Meng ;
Xiaobin Rui ;
Zhixiao Wang .
Artificial Intelligence Review, 2023, 56 :2263-2310
[49]   ReGAE: Graph Autoencoder Based on Recursive Neural Networks [J].
Malkowski, Adam ;
Grzechocinski, Jakub ;
Wawrzynski, Pawel .
NEURAL INFORMATION PROCESSING, ICONIP 2022, PT IV, 2023, 1791 :263-274
[50]   Artist Similarity Based on Heterogeneous Graph Neural Networks [J].
da Silva, Angelo Cesar Mendes ;
Silva, Diego Furtado ;
Marcacini, Ricardo Marcondes .
IEEE-ACM TRANSACTIONS ON AUDIO SPEECH AND LANGUAGE PROCESSING, 2024, 32 :3717-3729