Опыт многоуровневого распараллеливания метода ветвей и границ в задачах дискретной оптимизации

Обсуждаются различные схемы параллельной реализации метода ветвей и границ применительно к многопроцессорным вычислительным системам (кластерам) с распределенной памятью. На языке неформальных автоматов излагаются вопросы организации обмена данными и сигналами внутри кластера, обеспечивающими асинхронную работу его процессоров. Общие идеи иллюстрируются на примере классической задачи коммивояжера, приводятся данные численных экспериментов, проведенных на МВС-100.