Оптимальные связывающие сети: нижние оценки, алгоритмы и приложения
| Номер гранта: | 18-07-01240 |
| Область научного знания: | инфокоммуникационные технологии и вычислительные системы |
| Тип конкурса: | (а)(а) конкурс проектов фундаментальных научных исследований |
| Год выполнения: | 2018г. |
| Руководитель: | Губко Михаил Владимирович |
| Статус заявки: | поддержана |
Аннотация к заявке:
В классической квадратичной задаче о назначениях (КЗН) в постановке Купманса-Бекманна ищется размещение терминалов в вершинах некоторого графа (сети связи) для минимизации расстояния, которое в среднем проходит по ребрам сети единица потока (информационного или материального) между парами терминалов. В настоящем проекте оптимизируется не только размещение терминалов, но и топология сети с учетом практических ограничений на количество ребер, промежуточных вершин (коммутаторов), количество соседей вершин в сети и т.п.Эта постановка - т.н. задача об оптимальной связывающей сети (ОСС) - обобщает не только КЗН, но и многие задачи кластеризации на графах, задачи разрезания графов и восстановления сетевой структуры системы по данным, и находит применение при проектировании интегральных микросхем и пользовательских интерфейсов, разработке топологии транспортных сетей и сетей связи, построении филогенетических деревьев в биоинформатике и декомпозиции бизнес-процессов в менеджменте, определении схем аварийного деления электрических сетей, получении материалов с экстремальными свойствами и др.Актуальность проекта определяется тем, что, несмотря на обилие исследований и полезных результатов в рамках частных постановок, до сих пор нет точных алгоритмов и нижних оценок для сколь бы то ни было общего случая задачи ОСС.С использованием инструментария алгебраической теории графов и задела в области оптимизации топологических индексов (в частности, индекса Винера для графов со взвешенными вершинами) получается семейство нижних оценок затрат связывающего дерева с заданными степенями вершин. Оценки основаны на понижении ранга матрицы потоков между терминалами. Они эффективно вычисляются путем решения задач выпуклой оптимизации с ограничениями в форме линейных матричных неравенств и позволяют анализировать эффективность приближенных алгоритмов поиска ОСС, также основанных на сведении задачи ОСС к задаче оптимизации индекса Винера для деревьев со взвешенными вершинами.Улучшение этих нижних оценок связано с исследованием других частных случаев задачи ОСС, в частности, задач минимизации топологических индексов типа степенного расстояния, предложенного Добрыниным и Кочетовой (1994). В дальнейшем нижние оценки и приближенные алгоритмы обобщаются и на сети с циклами, что позволяет расширить область их приложений.На основе полученных результатов будут решаться прикладные задачи оптимизации структуры систем: деления электрических сетей, иерархической декомпозиции бизнес-процессов, оптимизации коммуникаций в мультиагентных системах. Будет исследована возможность применения разработанных алгоритмов поиска ОСС для решения задач идентификации структуры электрических и транспортных сетей по зашумленным неполным измерениям.Аннотация к заявке приведена в авторской редакции. По состоянию на 05.08.2025
Поделиться:
