Learning to Prune Instances of k-median and Related Problems

In a large number of industrial applications, combinatorial optimization problems are repeatedly solved with datasets from similar distribution. In recent years, machine learning techniques have been shown to be quite effective in speeding up such computations. However, black-box end-to-end machine learning approaches suffer from poor interpretability and the requirement for a large amount of labelled data. In this paper, we demonstrate a simple and highly effective way to incorporate the insights from the algorithmic and optimization literature on these problems into a machine learning framework to speed-up the solutions of these problems. We study the k-median problem and the following closely related combinatorial optimization problems: set cover, max coverage and uncapacitated facility location. These problems are well studied and a large number of approximation algorithms have been designed for these problems. We look at the kind of quantities these approximation algorithms employ and use these to derive useful features for training a classifier that helps quickly reduce the problem size by identifying the difficult core of the problem and pruning the remainder. The difficult core is then solved using an ILP solver. A prime advantage of using such features is that we do not require much data to train the classifier. This results in a much faster algorithm than just using the Integer Linear Programming solver. Several of the features we used for the classifier were derived from approximation algorithms that were designed for the metric instances of the k-median and the uncapacitated facility location problem. However, remarkably, the use of these features also leads to significant speed up in the non-metric instances of these problems and even the other two related problems.