Learned Subproblem Selection Techniques for Combinatorial Optimization
Subproblem generation, solution, and recombination is a standard solution method for combinatorial optimization problems. In many settings identifying suitable subproblems is itself a significant component of the method. Such subproblems are often identified using a heuristic rule. Here we show how to use machine learning to make this identification. In particular we use a learned objective function to direct search in an appropriate space of subproblem decompositions. We demonstrate the efficacy of our technique for problem decomposition on two examples: graph coloring for geometric graphs, a deterministic optimization problem, and the Multiple Uninhabited Air Vehicle Surveillance Control Problem, or MUAV, a stochastic optimization problem that is related to vehicle routing problems in operations research.