Geodesic
Application of parallel heuristic algorithms for speeding up parallel implementations of the branch-and-bound method
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 47 (2007) no. 9, pp. 1524-1537 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

A scheme for the parallel implementation of the combined branch-and-bound method and heuristic algorithms is proposed. Results of computations for the one-dimensional Boolean knapsack problem are presented that demonstrate the efficiency of the proposed approach. The main factors that affect the speedup of the solution when local optimization is used are discussed. 
@article{ZVMMF_2007_47_9_a7,
     author = {M. A. Posypkin and I. Kh. Sigal},
     title = {Application of parallel heuristic algorithms for speeding up parallel implementations of the branch-and-bound method},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1524--1537},
     year = {2007},
     volume = {47},
     number = {9},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2007_47_9_a7/}
}
TY  - JOUR
AU  - M. A. Posypkin
AU  - I. Kh. Sigal
TI  - Application of parallel heuristic algorithms for speeding up parallel implementations of the branch-and-bound method
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2007
SP  - 1524
EP  - 1537
VL  - 47
IS  - 9
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2007_47_9_a7/
LA  - ru
ID  - ZVMMF_2007_47_9_a7
ER  - 
%0 Journal Article
%A M. A. Posypkin
%A I. Kh. Sigal
%T Application of parallel heuristic algorithms for speeding up parallel implementations of the branch-and-bound method
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2007
%P 1524-1537
%V 47
%N 9
%U http://geodesic.mathdoc.fr/item/ZVMMF_2007_47_9_a7/
%G ru
%F ZVMMF_2007_47_9_a7
M. A. Posypkin; I. Kh. Sigal. Application of parallel heuristic algorithms for speeding up parallel implementations of the branch-and-bound method. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 47 (2007) no. 9, pp. 1524-1537. http://geodesic.mathdoc.fr/item/ZVMMF_2007_47_9_a7/

[1] Voevodin V. V., Voevodin Vl. V., Parallelnye vychisleniya, BKhV-Peterburg, SPb., 2002

[2] Barskii A. B., Parallelnye informatsionnye tekhnologii, INTUIT, M., 2007

[3] Emelyanov C. B., Afanasev A. P., “Problemy vychislenii v raspredelennoi srede: organizatsiya vychislenii v globalnykh setyakh”, Tr. In-ta sistemnogo analiza RAN, ROKhOS, M., 2004

[4] Posypkin M. A., Sigal I. Kh., “Issledovanie algoritmov parallelnykh vychislenii v zadachakh diskretnoi optimizatsii rantsevogo tipa”, Zh. vychisl. matem. i matem. fiz., 45:10 (2005), 1801–1809 | MR

[5] Posypkin M. A., Sigal I. Kh., Galimyanova H. H., Parallelnye algoritmy v zadachakh diskretnoi optimizatsii: vychislitelnye modeli, biblioteka, rezultaty eksperimentov, Soobsch. po prikl. matem., VTs RAN, M., 2006

[6] Ananth G. Y., Kumar V., Pardalos P., “Parallel processing of discrete optimization problems”, Encyclopedia of Microcomputers, 13 (1993), 129–147

[7] Trienekens H., Bruin A., Towards a taxonomy of parallel branch and bound algorithms, Report EUR-CS-92-01, Erasmus Univ., Rotterdam, 1992

[8] Gendron B., Grainic T. G., “Parallel branch-and-bound survey and synthesis”, Operat. Res., 42:6 (1994), 1042–1066 | DOI | MR | Zbl

[9] Sigal I. Kh., Ivanova A. P., Vvedenie v prikladnoe diskretnoe programmirovanie, Fizmatlit, M., 2002

[10] Kochetov Yu., Mladenovich N., Khansen P., “Lokalnyi poisk s chereduyuschimisya okrestnostyami”, Diskretnyi analiz i issl. operatsii. Seriya 2, 10:1 (2003), 11–43 | MR | Zbl

[11] Martello S., Toth P., Knapsack problems: Algorithms and computer implementations, John Wiley Sons, 1990 | MR | Zbl

[12] Posypkin M. A., “Arkhitektura i programmnaya organizatsiya biblioteki dlya resheniya zadach optimizatsii metodom vetvei i granits na mnogoprotsessornykh vychislitelnykh kompleksakh”, Probl. vychisl. v raspredelennoi srede: raspredelennye prilozheniya, kommunikatsionnye sistemy, matem. modeli i optimizatsiya, Tr. ISA RAN, KomKniga, M., 2006, 18–25

[13] Sigal I. Kh., Babinskaya Ya. L., Posypkin M. A., “Parallelnaya realizatsiya metoda vetvei i granits v zadache kommivoyazhera na baze biblioteki BNB-Solver”, Probl. vychislenii v raspredelennoi srede: raspredelennye prilozheniya, kommunikatsionnye sistemy, matem. modeli i optimizatsiya, Tr. ISA RAN, KomKniga, M., 2006, 26–36

[14] Mezhvedomstvennyi superkompyuternyi tsentr RAN http://www.jscc.ru

[15] Kellerer H., Pferschy U., Pisinger D., Knapsack problems, Springer, Berlin, 2004 | MR

[16] Iskhodnye dannye dlya zadachi o rantse http://dcs.isa.ru/posypkin/knapdata/index.html

[17] Finkelshtein Yu. Yu., Priblizhennye metody i prikladnye zadachi diskretnogo programmirovaniya, Nauka, M., 1976

[18] Crainic T., Toulouse M., Parallel-strategies for metaheuristics. State-of-the-Art Handbook in Metaheuristics, Kluwer Acad. Pubs., 2002 | Zbl

[19] Hoff A., Løkketangen A., Mittet I., Genetic Algorithms for 0/1 multidimensional knapsack problems, Norsk Informatikkonferanse, 1996, 291–302 pp.

[20] Glover F., Kochenberger G., “Critical event tabu search for multidimensional knapsack problems”, Meta-Heuristics: Theory Applic., 1996, 407–427 | Zbl

[21] Matsumura T., Nakamura M., Okech J., Onaga K., “A paralel and distributed genetic algorithm on loosely-coupled multiprocessor systems”, IEICE Trans. Fundam. Electron. Communs Comput. Sci. (Japan), E81-A:4 (1998), 540–546

[22] Niar S., Freville A., “A parallel tabu search algorithm for the 0-1 multidimensional khapsack problem”, 11th Internat. Parallel Processing Symposium (IPPS'97), 1997, 512–516

[23] Denzinger J., Offermann T., “On cooperation between evolutionary algorithims and other search paradigms”, Proc. CEC-99, IEEE Press, Washington, 1999, 2317–2324