Using statistical measures and machine learning for graph reduction to solve maximum weight clique problems

Yuan Sun, Xiaodong Li, Andreas Ernst

Research output: Contribution to journalArticleResearchpeer-review

18 Citations (Scopus)

Abstract

In this article, we investigate problem reduction techniques using stochastic sampling and machine learning to tackle large-scale optimization problems. These techniques heuristically remove decision variables from the problem instance, that are not expected to be part of an optimal solution. First we investigate the use of statistical measures computed from stochastic sampling of feasible solutions compared with features computed directly from the instance data. Two measures are particularly useful for this: 1) a ranking-based measure, favoring decision variables that frequently appear in high-quality solutions; and 2) a correlation-based measure, favoring decision variables that are highly correlated with the objective values. To take this further we develop a machine learning approach, called Machine Learning for Problem Reduction (MLPR), that trains a supervised learning model on easy problem instances for which the optimal solution is known. This gives us a combination of features enabling us to better predict the decision variables that belong to the optimal solution for a given hard problem. We evaluate our approaches using a typical optimization problem on graphs - the maximum weight clique problem. The experimental results show our problem reduction techniques are very effective and can be used to boost the performance of existing solution methods.

Original languageEnglish
Pages (from-to)1746-1760
Number of pages15
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Volume43
Issue number5
DOIs
Publication statusPublished - May 2021

Keywords

  • Combinatorial optimization
  • data mining
  • machine learning
  • problem reduction
  • statistics

Cite this