ИСТИНА

В рамках проекта предполагается разработка простых и эффективных рекурсивных процедур параллелизации решения комбинаторных задач методом ветвей и границ. Основным преимуществом данных процедур должна быть минимизация объема данных, передаваемых между процессорами в процессе решения задач, при сохранении необходимой для масштабируемости задачи сбалансированности разбиения задачи на подзадачи, решаемые процессорами. Данное преимущество позволяет уменьшить время решения задачи за счет сокращения времени обмена данными между процессорами. Планируется программная реализация этих методов на многоядерных вычислительных системах и проведение экспериментальных исследований. Предполагается также уделить существенное внимание получению теоретических оценок сложности данных алгоритмов. Для этого будут развиты полученные исполнителями ранее оценки сложности последовательных и параллельных вариантов метода ветвей и границ.

The project goal is the development of a simple and efficient recursive procedures of parallelization of solving combinatorial problems by a branch-and-bound method. The main advantage of these procedures is the small amount of data transferred between the processors during the problem resolution, while maintaining the balanced partitioning of a task into subtasks solved by the processors which is necessary for scalability of the problem. This feature allows to reduce the time of solving the problem by reducing the time of communication between processors. We plan to develope the software implementation of these methods on multicore computer systems and to conduct experimental studies. It is also expected to devote an considerable attention to the theoretical estimates of the complexity of these algorithms. We plain to employ the previously obtained estimations of complexity of sequential and parallel variants of the branch-and-bound method.

Разработка теоретической базы для исследования эффективности параллельных методов оптимизации, рассматриваемых в проекте. Планируется создание модели параллельного выполнения и определение основных характеристик производительности на ее базе. Также будет разработан рекурсивный параллельный вариант метода ветвей и границ и получены базовые проблемно-независимые оценки параллельной вычислительной сложности.

Коллектив исполнителей проекта имеет существенный задел в тематике проекта. В направлении решения задач оптимизации различного типа получен ряд важных результатов, нашедших отражение в опубликованных работах. В частности, разработаны новые комбинированные методы решения задач дискретной оптимизации на параллельных вычислительных системах. Разработана оригинальная методика оценки сложности задач дискретной оптимизации.

1. Эффективные параллельные детерминированные методы решения задач дискретной оптимизации, основанные на схеме ветвей и границ. 2. Теория параллельного решения задач дискретной оптимизации. Строгие определения понятий параллельной эффективности и масштабируемости, оценки параллельной вычислительной сложности для общей параллельной схемы ветвей и границ. Конкретизация полученных оценок для конкретных задач ранцевого типа и задач об оптимальной упаковке. 3. Программная реализация разработанных методов с использованием современных средств разработки параллельных программ. 4. Программа и методика проведения экспериментальных исследований, направленных на выяснение эффективности разработанных подходов. Результаты экспериментальных исследований, их сопоставление с теоретическими оценками. 5. Общие выводы о выборе оптимальных процедур распаралелливания при реализации детерминированных методов, основанных на концепции ветвей и границ. Будут даны как общие рекомендации, так и выполнена их конкретизация для задач ранцевого типа и задач об оптимальной упаковке.