Arrêt de service lundi 11 juillet de 12h30 à 13h : tous les sites du CCSD (HAL, Epiciences, SciencesConf, AureHAL) seront inaccessibles (branchement réseau à modifier)
Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

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.
Type de document :
Communication dans un congrès
Liste complète des métadonnées
Contributeur : Laurence Porte Connectez-vous pour contacter le contributeur
Soumis le : lundi 14 septembre 2020 - 15:57:44
Dernière modification le : mercredi 3 novembre 2021 - 06:30:01


  • HAL Id : hal-02938000, version 1



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⟩



Consultations de la notice