Application of Multi-label Classification to the Generation of Sub-problems in Combinatorial Optimization - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année :

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

(1) , (1) , (2)
1
2
Luca Mossina
• Fonction : Auteur
• PersonId : 1040418
Emmanuel Rachelson
• Fonction : Auteur
• PersonId : 1034574
Daniel Delahaye

#### Résumé

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.

### Dates et versions

hal-02938000 , version 1 (14-09-2020)

### Identifiants

• HAL Id : hal-02938000 , version 1

### Citer

Luca Mossina, Emmanuel Rachelson, Daniel Delahaye. Application of Multi-label Classification to the Generation of Sub-problems in Combinatorial Optimization. OLA 2018, International Workshop on Optimization and Learning: Challenges and Applications, Feb 2018, Alicante, Spain. ⟨hal-02938000⟩

### Exporter

BibTeX TEI Dublin Core DC Terms EndNote Datacite

### Collections

32 Consultations
0 Téléchargements