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)
