Machine Learning for Subproblem Selection

Abstract

Subproblem generation, solution, and recombination is a standard approach to combinatorial optimization problems. In many settings identifying suitable subproblems is itself a significant component of the technique. 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 e#cacy of our technique for problem decomposition on a particular wellknown combinatorial optimization problem, graph coloring for geometric graphs. 1. Introduction Subproblem generation, solution, and recombination is a standard technique in combinatorial optimization. Often this "divide and conquer" method involves a search for one or several suitable subproblems, and the outcome of this search can critically a#ect the performance of the overall algorithm. For example, in a classical vehic...