Curriculum learning for multilevel budgeted combinatorial problems
  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.
