  


Machine Learning to Balance the Load in Parallel BranchandBound
Alejandro Marcos Alvarez(amarcosulg.ac.be) Abstract: We describe in this paper a new approach to parallelize branchandbound 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 branchandbound; Hardness estimation; Machine learning; Unit commitment Category 1: Combinatorial Optimization (Branch and Cut Algorithms ) Category 2: Applications  Science and Engineering (DataMining ) Citation: Department of Electrical Engineering and Computer Science, University of Liege, Liege, Belgium, March 2015 Download: [PDF] Entry Submitted: 03/20/2015 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  