Eprint first made available on ORBi (E-prints, working papers and research blog)
Machine Learning to Balance the Load in Parallel Branch-and-Bound
Marcos Alvarez, Alejandro; Wehenkel, Louis; Louveaux, Quentin
2015
 

Files


Full Text
mpc2014.pdf
Author preprint (312.64 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Parallel branch-and-bound; Hardness estimation; Machine learning; Unit commitment
Abstract :
[en] We describe in this paper a new approach to parallelize branch-and-bound on a certain number of processors. We propose to split the optimization of the original problem into the optimization of several subproblems that can be optimized separately with the goal that the amount of work that each processor carries out is balanced between the processors, while achieving interesting speedups. The main innovation of our approach consists in the use of machine learning to create a function able to estimate the difficulty (number of nodes) of a subproblem of the original problem. We also present a set of features that we developed in order to characterize the encountered subproblems. These features are used as input of the function learned with machine learning in order to estimate the difficulty of a subproblem. The estimates of the numbers of nodes are then used to decide how to partition the original optimization tree into a given number of subproblems, and to decide how to distribute them among the available processors. The experiments that we carry out show that our approach succeeds in balancing the amount of work between the processors, and that interesting speedups can be achieved with little effort.
Disciplines :
Computer science
Author, co-author :
Marcos Alvarez, Alejandro ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation
Wehenkel, Louis  ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation
Louveaux, Quentin ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Système et modélisation : Optimisation discrète
Language :
English
Title :
Machine Learning to Balance the Load in Parallel Branch-and-Bound
Publication date :
2015
Available on ORBi :
since 03 May 2015

Statistics


Number of views
402 (14 by ULiège)
Number of downloads
289 (7 by ULiège)

Bibliography


Similar publications



Contact ORBi