EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

242. Learning to Branch in Combinatorial Optimization with Graph Pointer Networks

Invited abstract in session MD-3: (Deep) Reinforcement Learning for Combinatorial Optimization 2, stream Data Science Meets Optimization.

Monday, 14:30-16:00
Room: 1005 (building: 202)

Authors (first author is the speaker)

1. Bo Jiang
College of Systems Engineering, National University of Defense Technology
2. Rui Wang
College of System Engineering, National University of Defense Technology
3. Gang Zhou
College of Systems Engineering, National University of Defense Technology

Abstract

This paper proposes a novel graph pointer network (GPN) model to learn branching rules for branch-and-bound (B&B) algorithms in combinatorial optimization. B&B is a widely used exact method that can solve various NP-hard problems, such as set covering, facility location, and maximum independent set. However, B&B relies on manually designed heuristics to select the branching variables, which are often suboptimal and inefficient. The GPN model aims to automatically learn these heuristics from data, by imitating the expert strong branching rule. The GPN model consists of two components: a graph neural network that encodes the graph structure of the problem state, and a pointer mechanism that outputs the branching probabilities based on the global and historical features. The model is trained by minimizing the Kullback-Leibler divergence between the predicted and the expert distributions. Experiments on three benchmark problems show that the GPN model outperforms both the classic and the state-of-the-art machine learning-based B&B methods in terms of solving speed and search tree size. The GPN model also demonstrates remarkable generalization abilities, adapting to unseen and larger instances. This paper presents an innovative approach to enhancing the performance of B&B algorithms using deep learning techniques.

Keywords

Status: accepted

Back to the list of papers