Optimization Online


Machine Learning to Balance the Load in Parallel Branch-and-Bound

Alejandro Marcos Alvarez(amarcos***at***ulg.ac.be)
Louis Wehenkel(l.wehenkel***at***ulg.ac.be)
Quentin Louveaux(q.louveaux***at***ulg.ac.be)

Abstract: 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.

Keywords: Parallel branch-and-bound; Hardness estimation; Machine learning; Unit commitment

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Applications -- Science and Engineering (Data-Mining )

Citation: Department of Electrical Engineering and Computer Science, University of Liege, Liege, Belgium, March 2015

Download: [PDF]

Entry Submitted: 03/20/2015
Entry Accepted: 03/20/2015
Entry Last Modified: 03/20/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society