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

Bo Tian; Mikhail Posypkin

doi:10.7494/csci.2014.15.3.239

Authors

Bo Tian Lomonosov Moscow State University
Mikhail Posypkin Lomonosov Moscow State University

DOI:

https://doi.org/10.7494/csci.2014.15.3.239

Keywords:

BOINC, branch-and-bound method, distributed computing, volunteer computing, desktop grid

Abstract

The Berkeley Open Infrastructure for Network Computing (BOINC) is an opensource middleware system for volunteer and desktop grid computing. In this paper we propose BNBTEST, a BOINC version of distributed branch and bound method. The crucial issues of distributed branch-and-bound method are traversing the search tree and loading balance. We developed subtaskspackaging method and three dierent subtasks' distribution strategies to solve these.

Downloads

Download data is not yet available.

Author Biographies

Bo Tian, Lomonosov Moscow State University

Faculty of Computational Mathematics and Cybernetics

Mikhail Posypkin, Lomonosov Moscow State University

Faculty of Computational Mathematics and Cybernetics

References

Afanasiev A., Evtushenko Y., and Posypkin M.: The Layered Software Infrastructure for Solving Large-scale Optimization Problems on the Grid. Horizons in Computer Science Research, vol. 4, pp. 129-144, 2012.

Aida K., Futaka Y., and Osumi T.: Parallel Branch and Bound Algorithm with the Hierarchical Master-Worker Paradigm on the Grid. IPSJ Digital Courier, vol. 2, pp. 584-597, 2006.

Aida K., Natsume W., and Futakata Y.: Distributed computing with hierarchical master-worker paradigm for parallel branch and bound algorithm. Cluster Computing and the Grid, 2003. Proceedings. CCGrid 2003. 3rd IEEE/ACM International Symposium on pp. 156-163, 2003.

Alba E., Almeida F., Blesa M., Cabeza J., Cotta C., Daz M., Dorta I., Gabarr J., Len C., Luna J., Moreno L., Pablos C., Petit J., Rojas A., and Xhafa F.: MALLBA: A Library of Skeletons for Combinatorial Optimisation (Research Note). pp. 927-932. 2002.

Anstreicher K., Brixius N., Goux J.P., and Linderoth J.: Solving large quadratic assignment problems on computational grids. Mathematical Programming, vol. 91, pp. 563-588, 2002.

Budiu M., Delling D., and Werneck R.F.: DryadOpt: Branch-and-Bound on Distributed Data-Parallel Execution Engines. In IPDPS, pp. 1278-1289, 2011.

Crainic T.G., Cun B.L., and Roucairol C.: Parallel Combinatorial Optimization. John Wiley & Sons, Inc., 2006.

David P.: Where are the hard knapsack problems? Computers & Operations Research, vol. 32, pp. 2271-2284, 2005.

David P.A.: BOINC: a system for public-resource computing and storage. in Proceedings of the 5th IEEE/ACM International GRID Workshop, 2004.

David P.A., Cobb J., Korpela E., Lebofsky M., and Werthimer D.: SETI@home: an experiment in public-resource computing. Communications of the ACM, vol. 45, pp. 56-61, 2002.

Djerrah A., Cun L.B., Cung V.D., and Roucairol C.: Bob++: Framework for solving optimization problems with branch-and-bound methods. in Proceedings of the 15th IEEE International Symposium on High Performance Distributed Computing (HPDC), pp. 369-370, 2006.

Donald E.K.: The Art of Computer Programming. Addison-Wesley, Boston, 1968. ISBN 0-201-89683-4.

Drummond L.M.A., Uchoa E., Goncalves A.D., Silva J.M.N., Santos M.C.P., and Castro M.C.S.: A grid-enabled distributed branch-and bound algorithm with application on the Steiner problem in graphs. Parallel Computing, vol. 32, pp.629-642, 2006.

Durstenfeld R.: Algorithm 235: random permutation. Communications of the ACM, vol. 7, p. 420, 1964.

Eckstein J., Phillips C.A., and Hart W.E.: PICO: An object-oriented framework for parallel branch and bound. Studies in Computational Mathematics, vol. 8, pp. 219-265, 2001.

Glankwamdee W. and Linderoth J.: Parallel Combinatorial Optimization. John Wiley & Sons, Inc., 2006.

Kacsuk P., Kovacs J., Farkas Z., Marosi A.C., and Balaton Z.: Towards a Powerful European DCI Based on Desktop Grids. J Grid Computing, vol. 9, pp. 219-239, 2011.

Land A.H. and Doig A.G.: An automatic method of solving discrete programming problems. Econometrica, vol. 28, pp. 497-520, 1960.

Litzkow M.J., Livny M., and Mutka M.W.: Condor-a hunter of idle workstations. 8th International Conference on Distributed Computing Systems, pp. 104-111, 1988.

Lling R. and Monien B.: Load balancing for distributed branch and bound algorithms. Parallel Processing Symposium, 1992. Proceedings., Sixth International, pp. 543-548, 1992.

Martello S. and Toth P.: A new algorithm for the 0-1 knapsack problem. Management Science, vol. 34, pp. 633-644, 1988.

Martello S. and Toth P.: Upper bounds and algorithms for hard 0-1 knapsack problems. Operations Research, vol. 45, pp. 768-778, 1997.

Nakada H., Tanaka Y., Matsuoka S., and Sekiguchi S.: Grid Computing: Making the Global Infrastructure a Reality. John Wiley & Sons Ltd, 2003.

Quinn M.: Analysis and implementation of branch-and-bound algorithms on a hypercube multicomputer. IEEE Transactions on Computers, vol. 39, pp. 384-387, 1990.

Shinano Y., Higaki M., and Hirabayashi R.: A generalized utility for parallel branch and bound algorithms. p. 392. Los Alamitos, CA, USA: IEEE Computer Society, 1995.

Tschke S., Lling R., and Monien B.: Solving the traveling salesman problem with a distributed branch-and-bound algorithm on a 1024 processor network. in Proceedings of the 9th Parallel Processing Symposium, pp. 182-189, 1995.