OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

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

Mossina, Luca and Rachelson, Emmanuel and Delahaye, Daniel Application of Multi-label Classification to the Generation of Sub-problems in Combinatorial Optimization. (2018) In: International Workshop on Optimization and Learning: Challenges and Applications (OLA 2018), 26 February 2018 - 28 February 2018 (Alicante, Spain).

[img] (Document in English)

PDF (Author's version) - Depositor and staff only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader


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.

Item Type:Conference or Workshop Item (Other)
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:Université de Toulouse > Ecole Nationale de l'Aviation Civile - ENAC (FRANCE)
Université de Toulouse > Institut Supérieur de l'Aéronautique et de l'Espace - ISAE-SUPAERO (FRANCE)
Laboratory name:
This research benefited from the support of the “FMJH Program Gaspard Monge in optimization and operation research”, and from the support to this program from EDF.
Deposited On:16 Feb 2018 14:07

Repository Staff Only: item control page