Институт вычислительной математики и математической геофизики СОРАН

Тезисы докладов

Многие известные алгоритмы решения оптимизационных задач могут быть получены в рамках единого подхода, который был предложен в классической работе Джеффриона. Исследуемый класс задач преобразуют с помощью одной или нескольких операций, например, дуализации, проектирования, внешней или внутренней линеаризации и др. В результате получается новая задача, которую можно назвать координирующей. Она обычно в том или ином смысле эквивалентна исходной задаче. Применяя к координирующей задаче одну из известных стратегий решения: сужение, релаксацию, допустимых направлений, штрафных функций и некоторые другие, получаем алгоритм решения исходной задачи. В работе подробно рассматривается данный подход. Приводится обзор результатов в этой области. Излагаются новые результаты, полученные для комбинаторных задач двухуровневого программирования, в частности, для задачи о $(r, p)$-центроиде, которая является полной на втором уровне полиномиальной иерархии. Идея построения таких методов, имеет, несомненно, большой потенциал. Пополняя запас преобразований, разрабатывая новые стратегии решения, можно получить более эффективные алгоритмы. В последние годы большое внимание уделяется применению метаэвристик для решения $NP$-трудных и более сложных задач. Если рассматривать метаэвристики в качестве новых стратегий, то данное направление исследований получает новые интересные перспективы.

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 2009, Институт Вычислительной Математики и Математической Геофизики СО РАН, Новосибирск
© 1996-2009, Сибирское отделение Российской академии наук, Новосибирск
    Дата последней модификации: 06-Jul-2012 (11:52:52)