Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Khung làm việc cho tối ưu hóa toàn cầu quy mô lớn song song
Tóm tắt
Bài báo mô tả thiết kế và triển khai BNB-Solver, một khung làm việc theo đối tượng cho tối ưu hóa toàn cầu song song rời rạc và liên tục. Khung làm việc hỗ trợ các thuật toán phân nhánh và giới hạn chính xác, các phương pháp heuristic và các phương pháp hỗn hợp. BNB-Solver cung cấp hỗ trợ cho các kiến trúc bộ nhớ phân tán và chia sẻ. Triển khai cho các máy bộ nhớ phân tán dựa trên MPI và do đó có thể chạy trên hầu như bất kỳ cụm tính toán nào. Để tận dụng lợi thế của các bộ xử lý đa lõi, chúng tôi cung cấp một triển khai đa luồng riêng cho các nền tảng bộ nhớ chia sẻ. Chúng tôi giới thiệu một sơ đồ hợp tác mới để kết hợp các phương pháp tìm kiếm chính xác và heuristic, cung cấp hỗ trợ cho các heuristic song song phức tạp và cân bằng thuận tiện giữa các phương pháp chính xác và heuristic. Trong phần kết quả thí nghiệm, chúng tôi thảo luận về một bộ giải lập trình phi tuyến và một bộ giải ba lô hiệu quả cao, vượt trội hơn so với các triển khai song song hiện có.
Từ khóa
#tối ưu hóa toàn cầu #phân nhánh và giới hạn #thuật toán heuristic #kiến trúc bộ nhớ phân tán #triển khai đa luồngTài liệu tham khảo
Alba E, Almeida F, Blesa M et al (2006) Efficient parallel LAN/WAN algorithms for optimization. The MALLBA project. Parall Comput 32(5-6):415–440
Ananth G, Kumar V, Pardalos P (1993) Parallel processing of discrete optimization problems. Encycl Microcomput 13:129–147
Casado L, Martínez J, García I et al (2008) Branch-and-Bound interval global optimization on shared memory multiprocessors. Optim Methods Softw 23(5):689–701
Crainic TG, Le Cun B, Roucairol C (2006) Parallel branch and bound algorithms. In: Parallel Combinatorial Optimization, Chap 1, John Wiley & Sons, Hoboken, NJ, pp 1–28
Crainic TG, Toulouse M (2002) Parallel Strategies for Metaheuristics. In: Glover F, Kochenberger G (eds) State-of-the-Art Hand-book in Metaheuristics, Kluwer Academic Publishers, Dordrecht, pp 475–513
Coello Coello CA, Mezura-Montes E (2002) Constraint-handling in genetic algorithms through the use of dominance-based tournament selection. Adv Eng Inf 16(3):193–203
Drepper U, Molnar I (2005) The Native POSIX Thread Library for Linux. http://people.redhat.com/drepper/nptl-design.pdf. Last access: 13 May 2009
Eckstein J, Philips C, Hart W (2006) PEBBL 1.0 User Guide. RUTCOR Research Report RRR 19-2006. http://rutcor.rutgers.edu/pub/rrr/reports2006/19_2006.ps. Last access: 13 May 2009
Evtushenko Y (1971) Numerical methods for finding global extreme (case of a non-uniform mesh). USSR Comput Maths Math Phys 11(6):38–54
Kellerer H, Pferschy U, Pisinger D (2004) Knapsack Problems. Springer, Berlin
Posypkin M, Sigal I (2008) A combined parallel algorithm for solving the knapsack problem. J Comput Syst Sci Int 47(4):543–551
Ralphs T (2006) Parallel branch and cut. In: Parallel Combinatorial Optimization. John Wiley & Sons, Hoboken, NJ, pp 53–103
Snir M, Otto S, Huss-Lederman S, Walker D, Dongarra J (1996) MPI: The Complete Reference. MIT Press, Boston
Tschöke S, Holthöfer N (1995) A new parallel approach to the constrained two-dimensional cutting stock problem. In: Parallel Algorithms for Irregularly Structured Problems, LNCS 980, pp 285–300, Springer, London