PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

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

Autorzy
Treść / Zawartość
Identyfikatory
Warianty tytułu
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.
Wydawca
Czasopismo
Rocznik
Strony
239--252
Opis fizyczny
Bibliogr. 26 poz., rys., tab.
Twórcy
autor
  • Lomonosov Moscow State University
autor
  • 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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-7d4e4193-ec98-4882-b1a8-d4a1840197df
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.