EFFICIENT IMPLEMENTATION OF BRANCH-AND-BOUND METHOD ON DESKTOP GRIDS

Jul 2, 2014, 4:50 PM
20m
407 (LIT JINR)

407

LIT JINR

Russia, 141980 Moscow region, Dubna, JINR
sectional reports Section 7 - Desktop grid technologies and volunteer computing Desktop grid technologies and volunteer computing

Speaker

Mr Bo Ye Tian (Lomonosov Moscow State University)

Description

Many problems from the areas of operations research and artificial intelligence can be defined as combinatorial optimization problems. Branch-and-bound method (B&B)is a universal and well known algorithmic technique for solving problems of that type.The root of the tree is the original problem, and the other nodes represent subproblems to be solved. Though algorithm considerably decreases the computational time required to explore the entire solution space, the running time remains unbearable.Using parallel or distributed processing is one of the most popular ways to resolve this issue. The implementation of B&B algorithms on parallel machines was studied in numerous papers. All these solvers are based on parallel computation frameworks that are flexible and only useful for tightly coupled or shared memory distributed systems. Over the last decade we observe an emergent growth of a new HPC platform volunteer computing grids or desktop grids (DGs). Unlike conventional parallel computers this platform has not been sufficiently explored as a target for branch-andbound methods. DGs are highly dynamic and heterogeneous distributed computing platform. BOINC [5] is one of typical DGs platforms, which been developed by a team based at the Space Sciences Laboratory (SSL) at the University of California. It was originally developed to support the SETI@home [6] project before it became useful as a platform for other distributed applications in areas as diverse as mathematics, medicine, molecular biology, climatology, and astrophysics. BOINC has become widely popular recently, in both theory and practice. Devising an efficient B&B implementation for BOINC is a challenging and practically important problem. The approach proposed in our paper addresses this issue. We implemented a branch-and-bound solver for the NP-hard 0-1 knapsack problem. The classical knapsack problem is defined as follows. Given a set of n items, each item j having an integer profit j and an integer weight one need to choose a subset of items such that their overall profit is maximized, while the overall weight does not exceed the given capacity c. It worth noting that our approach is not specific to the knapsack problem, after functional verification, we will use our distributed branch and bound method to solve practical problems. The knapsack problem was chosen as one of the most basic and well-studied optimization problems for illustrative purposes.

Primary author

Mr Bo Ye Tian (Lomonosov Moscow State University)

Co-author

Dr Mikhail Posypkin (ITTP RAS)

Presentation materials