Application of Multi-label Classification to the Generation of Sub-problems in Combinatorial Optimization

Abstract

The ubiquitous presence of combinatorial optimization (CO) problems in fields such as Operations Research and Artificial Intelligence as well the great wealth of recent results in Machine Learning (ML) have contributed to a recent surge in interest for applications of ML to CO. ML has been employed, for example, to automate the application of decomposition methods to mixed integer programs, to guide the branching in branch-and-bound algorithms and used to improve greedy heuristics for hard CO problems over graphs. Our work focuses on the resolution of recurrent CO problems for which similar instances need to be solved repeatedly over time, with some modifications in the model parameters. We couple multi-label classification (MLC) techniques with branch-and-bound and stochastic solvers, operating under a limited time budget. Assuming problems are the realization of a generative process, historical data are collected and used to train a classification model. When solving a new instance P, this model will select a subset x_B of ``blocked" decision variables to be set heuristically to some reference values, becoming fixed parameters. The remaining variables x_SP are left free and form the smaller sub-problem SP whose solution, while yielding an approximation of the optimum, can be obtained sensibly faster. Subsequently, if some of the time allocated is available, an iterative process of blocking/unblocking variables takes place, allowing to further explore the solution space. This approach is of particular interest for problems where perturbations on the instance parameters can occur unexpectedly, requiring a rapid re-optimization of a complex model.