Learning to Prune Instances of k-median and Related Problems

Dena Tayebi, Saurabh Ray, Deepak Ajwani

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationSIAM Symposium on Algorithm Engineering and Experiments, ALENEX 2022
PublisherSociety for Industrial and Applied Mathematics Publications
Pages184-194
Number of pages11
ISBN (Electronic)9781713844204
StatePublished - 2022
Event2022 SIAM Symposium on Algorithm Engineering and Experiments, ALENEX 2022 - Alexandria Old Town, United States
Duration: Jan 9 2022Jan 10 2022

Publication series

NameProceedings of the Workshop on Algorithm Engineering and Experiments
Volume2022-January
ISSN (Print)2164-0300

Conference

Conference2022 SIAM Symposium on Algorithm Engineering and Experiments, ALENEX 2022
Country/TerritoryUnited States
CityAlexandria Old Town
Period1/9/221/10/22

ASJC Scopus subject areas

  • Engineering(all)
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Learning to Prune Instances of k-median and Related Problems'. Together they form a unique fingerprint.

Cite this