Efficient implementation of branch-and-bound method on desktop grids

• Autorzy: Tlan B. , Posypkin M.

Identyfikatory

DOI

10.7494/csci.2014.15.3.239

• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

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

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2014
• Tom: Vol. 15 (3)
• Strony: 239--252
• Opis fizyczny: Bibliogr. 26 poz., rys., tab.

Twórcy

autor

Tlan B.

• Lomonosov Moscow State University

autor

Posypkin M.

• Lomonosov Moscow State University

Bibliografia

• [1] Afanasiev A., Evtushenko Y., 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.
• [2] Aida K., Futaka Y., 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.
• [3] Aida K., Natsume W., Futakata Y.: Distributed computing with hierarchical master-worker paradigm for parallel branch and bound algorithm. In: Proc. 3rd IEEE/ACM International Symposium on Cluster Computing and the Grid (CCGrid 2003), pp. 156–163, 2003.
• [4] Alba E., Almeida F., Blesa M., Cabeza J., Cotta C., D ́ıaz M., Dorta I., Gabarr ́o J., Le ́on C., Luna J., Moreno L., Pablos C., Petit J., Rojas A., Xhafa F.: MALLBA: A Library of Skeletons for Combinatorial Optimisation (Research Note). In: Proceedings of the 8th international Euro-Par Conference on Parallel Processing, pp. 927–932, 2002.
• [5] Anstreicher K., Brixius N., Goux J. P., Linderoth J.: Solving large quadratic assignment problems on computational grids. Mathematical Programming, vol. 91, pp. 563–588, 2002.
• [6] Budiu M., Delling D., Werneck R. F.: DryadOpt: Branch-and-Bound on Distributed Data-Parallel Execution Engines. In: IPDPS, pp. 1278–1289, 2011.
• [7] Crainic T. G., Cun B. L., Roucairol C.: Parallel Combinatorial Optimization. John Wiley & Sons, Inc., 2006. 2014/10/24; 19:53 str. 12/14 250
• [8] David P.: Where are the hard knapsack problems? Computers & Operations Research, vol. 32, pp. 2271–2284, 2005.
• [9] David P. A.: BOINC: a system for public-resource computing and storage. In: Proceedings of the 5th IEEE/ACM International GRID Workshop, 2004.
• [10] David P. A., Cobb J., Korpela E., Lebofsky M., Werthimer D.: SETI@home: an experiment in public-resource computing. Communications of the ACM, vol. 45, pp. 56–61, 2002.
• [11] Djerrah A., Cun L. B., Cung V. D., 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.
• [12] Knuth D. E.: The Art of Computer Programming. Addison-Wesley, Boston, 1968.
• [13] Drummond L. M. A., Uchoa E., Goncalves A. D., Silva J. M. N., Santos M. C. P., Castro M. C. S.: A grid-enabled distributed branch-andbound algorithm with application on the Steiner problem in graphs. Parallel Computing, vol. 32, pp. 629–642, 2006.
• [14] Durstenfeld R.: Algorithm 235: random permutation. Communications of the ACM, vol. 7, p. 420, 1964.
• [15] Eckstein J., Phillips C. A., Hart W. E.: PICO: An object-oriented framework for parallel branch and bound. Studies in Computational Mathematics, vol. 8, pp. 219–265, 2001.
• [16] Glankwamdee W., Linderoth J.: Parallel Combinatorial Optimization. John Wiley & Sons, Inc., 2006.
• [17] Kacsuk P., Kovacs J., Farkas Z., Marosi A. C., Balaton Z.: Towards a Powerful European DCI Based on Desktop Grids. J Grid Computing, vol. 9, pp. 219–239, 2011.
• [18] Land A. H., Doig A. G.: An automatic method of solving discrete programming problems. Econometrica, vol. 28, pp. 497–520, 1960.
• [19] Litzkow M. J., Livny M., Mutka M. W.: Condor-a hunter of idle workstations. 8th International Conference on Distributed Computing Systems, pp. 104–111, 1988.
• [20] L ̈uling R., Monien B.: Load balancing for distributed branch and bound algorithms. In: Parallel Processing Symposium, 1992. Proceedings., Sixth International, pp. 543–548, 1992.
• [21] Martello S., Toth P.: A new algorithm for the 0-1 knapsack problem. Management Science, vol. 34, pp. 633–644, 1988.
• [22] Martello S., Toth P.: Upper bounds and algorithms for hard 0-1 knapsack problems. Operations Research, vol. 45, pp. 768–778, 1997.
• [23] Nakada H., Tanaka Y., Matsuoka S., Sekiguchi S.: Grid Computing: Making the Global Infrastructure a Reality. John Wiley & Sons Ltd., 2003.
• [24] Quinn M.: Analysis and implementation of branch-and-bound algorithms on a hypercube multicomputer. IEEE Transactions on Computers, vol. 39, pp. 384–387, 1990.
• [25] Shinano Y., Higaki M., Hirabayashi R.: A generalized utility for parallel branch and bound algorithms. In: IEEE Symposium on Parallel and Distributed Processing, p. 392, 1995.
• [26] Tschoke S., L ̈uling R., 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.