Projects per year
Abstract
In this article, we investigate problem reduction techniques using stochastic sampling and machine learning to tackle largescale 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 rankingbased measure, favoring decision variables that frequently appear in highquality solutions; and 2) a correlationbased 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 language  English 

Pages (fromto)  17461760 
Number of pages  15 
Journal  IEEE Transactions on Pattern Analysis and Machine Intelligence 
Volume  43 
Issue number  5 
DOIs  
Publication status  Published  May 2021 
Keywords
 Combinatorial optimization
 data mining
 machine learning
 problem reduction
 statistics
Projects
 1 Finished

Hybrid methods with decomposition for large scale optimization
Li, X., Ernst, A. & Kalyanmoy, D.
16/04/18 → 31/12/20
Project: Research