Reference : Machine Learning to Balance the Load in Parallel Branch-and-Bound
E-prints/Working papers : First made available on ORBi
Engineering, computing & technology : Computer science
http://hdl.handle.net/2268/181086
Machine Learning to Balance the Load in Parallel Branch-and-Bound
English
Marcos Alvarez, Alejandro mailto [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation >]
Wehenkel, Louis mailto [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation >]
Louveaux, Quentin mailto [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Système et modélisation : Optimisation discrète >]
2015
No
[en] Parallel branch-and-bound ; Hardness estimation ; Machine learning ; Unit commitment
[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.
http://hdl.handle.net/2268/181086

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
mpc2014.pdfAuthor preprint305.31 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.