Curriculum learning for multilevel budgeted combinatorial problems

Abstract

Learning heuristics for combinatorial optimization problems through graph neural networks have recently shown promising results on some classic NP-hard problems. These are single-level optimization problems with only one player. Multilevel combinatorial optimization problems are their generalization, encompassing situations with multiple players taking decisions sequentially. By framing them in a multi-agent reinforcement learning setting, we devise a value-based method to learn to solve multilevel budgeted combinatorial problems involving two players in a zero-sum game over a graph. Our framework is based on a simple curriculum: if an agent knows how to estimate the value of instances with budgets up to $B$, then solving instances with budget $B+1$ can be done in polynomial time regardless of the direction of the optimization by checking the value of every possible afterstate. Thus, in a bottom-up approach, we generate datasets of heuristically solved instances with increasingly larger budgets to train our agent. We report results close to optimality on graphs up to $100$ nodes and a $185\times$ speedup on average compared to the quickest exact solver known for the Multilevel Critical Node problem, a max-min-max trilevel problem that has been shown to be at least ${\Sigma }_2^p$-hard.

NeurIPS 2020, December 2020

References in corpus (13)

• Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift
• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• A continual learning survey: Defying forgetting in classification tasks
• Fast Graph Representation Learning with PyTorch Geometric
• Learning Combinatorial Optimization Algorithms over Graphs
• Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
• Exact Combinatorial Optimization with Graph Convolutional Neural Networks
• Attention, Learn to Solve Routing Problems!
• Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning
• A Theoretical Analysis of Deep Q-Learning
• Learning Montezuma's Revenge from a Single Demonstration
• Learning to Branch
• A simple yet effective baseline for non-attributed graph classification