A machine learning framework for neighbor generation in metaheuristic search

被引:1
作者
Liu, Defeng [1 ]
Perreault, Vincent [1 ]
Hertz, Alain [1 ]
Lodi, Andrea [2 ]
机构
[1] Polytech Montreal, Dept Math & Ind Engn, Montreal, PQ, Canada
[2] Cornell Tech & Technion IIT, Jacobs Technion Cornell Inst, New York, NY 10044 USA
关键词
combinatorial optimization; metaheuristics; Tabu Search; Large Neighborhood Search; machine learning; Graph Neural Networks; Mixed Integer Programming (MIP); COMBINATORIAL OPTIMIZATION;
D O I
10.3389/fams.2023.1128181
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
This paper presents a methodology for integrating machine learning techniques into metaheuristics for solving combinatorial optimization problems. Namely, we propose a general machine learning framework for neighbor generation in metaheuristic search. We first define an efficient neighborhood structure constructed by applying a transformation to a selected subset of variables from the current solution. Then, the key of the proposed methodology is to generate promising neighbors by selecting a proper subset of variables that contains a descent of the objective in the solution space. To learn a good variable selection strategy, we formulate the problem as a classification task that exploits structural information from the characteristics of the problem and from high-quality solutions. We validate our methodology on two metaheuristic applications: a Tabu Search scheme for solving a Wireless Network Optimization problem and a Large Neighborhood Search heuristic for solving Mixed-Integer Programs. The experimental results show that our approach is able to achieve a satisfactory trade-offs between the exploration of a larger solution space and the exploitation of high-quality solution regions on both applications.
引用
收藏
页数:15
相关论文
共 32 条
[1]  
Balcon M-F., 2018, P 35 INT C MACH LEAR
[2]  
Bello I., 2016, PREPRINT
[3]   Machine learning for combinatorial optimization: A methodological tour d'horizon [J].
Bengio, Yoshua ;
Lodi, Andrea ;
Prouvost, Antoine .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2021, 290 (02) :405-421
[4]   Measuring the impact of primal heuristics [J].
Berthold, Timo .
OPERATIONS RESEARCH LETTERS, 2013, 41 (06) :611-614
[5]   Progress in computational mixed integer programming - A look back from the other side of the tipping point [J].
Bixby, Robert ;
Rothberg, Edward .
ANNALS OF OPERATIONS RESEARCH, 2007, 149 (01) :37-41
[6]   Metaheuristics in combinatorial optimization: Overview and conceptual comparison [J].
Blum, C ;
Roli, A .
ACM COMPUTING SURVEYS, 2003, 35 (03) :268-308
[7]  
Cappart Q, 2022, Arxiv, DOI arXiv:2102.09544
[8]   Exploring relaxation induced neighborhoods to improve MIP solutions [J].
Danna, E ;
Rothberg, E ;
Le Pape, C .
MATHEMATICAL PROGRAMMING, 2005, 102 (01) :71-90
[9]  
Fey M, 2019, Arxiv, DOI [arXiv:1903.02428, DOI 10.48550/ARXIV.1903.02428]
[10]   Local branching [J].
Fischetti, M ;
Lodi, A .
MATHEMATICAL PROGRAMMING, 2003, 98 (1-3) :23-47