Curriculum learning for multilevel budgeted combinatorial problems
This addresses complex sequential decision-making problems in combinatorial optimization, offering a scalable solution for NP-hard generalizations, though it is incremental as it builds on existing graph neural network and reinforcement learning methods.
The paper tackled multilevel budgeted combinatorial problems by proposing a curriculum learning approach with multi-agent reinforcement learning, achieving results close to optimality on graphs up to 100 nodes and a 185x speedup compared to the quickest exact solver for the Multilevel Critical Node problem.
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 $Σ_2^p$-hard.