A Learning based Branch and Bound for Maximum Common Subgraph Problems
This work addresses a specific bottleneck in combinatorial optimization for researchers and practitioners, but it is incremental as it builds on existing branch-and-bound methods.
The paper tackled the problem of improving branch-and-bound algorithms for maximum common subgraph problems by developing a reinforcement learning-based branching heuristic to reduce search tree size, and experiments showed it outperforms the current best algorithm.
Branch-and-bound (BnB) algorithms are widely used to solve combinatorial problems, and the performance crucially depends on its branching heuristic.In this work, we consider a typical problem of maximum common subgraph (MCS), and propose a branching heuristic inspired from reinforcement learning with a goal of reaching a tree leaf as early as possible to greatly reduce the search tree size.Extensive experiments show that our method is beneficial and outperforms current best BnB algorithm for the MCS.