Репозиторий для проекта по курсу "Численные методы оптимизации" в МФТИ.
Лектор: Гасников А.В.
Семинарист: Меркулов Д.М.
🎓 Сайт Меркулова Д.М. с материалами курса
Проект заключается в исследовании способов оценки матрицы транспорта(корреспонденций) в условии невозможности её прямого измерения с помощью линейного программирования и рандомных нейронных сетей. За основу взяты две статьи:
- Traffic matrix estimation: existing techniques and new directions,
- On the use of random neural networks for traffic matrix estimation in large-scale IP networks.
В рамках курса стояла задача повторить результаты статей и сравнить их.
В процессе работы над проектом возник вопрос поиска открытых датасетов с матрицами корреспонеденций. Ниже представлены все найденные мной источники. Стоит отметить, что в каждом их них матрицы и графы представлены в разных форматах, поэтому для каждого конкретного алгоритма нужна своя предобработка.
- Transportation Networks,
- Файл с московскими данными, любезно предоставленный Екатериной Котляровой
- Проект Totem
- 2004 Abilene data
- Генератор графов
- Обработчик для первых двух источников (Автор: Котлярова Екатерина)
- В проекте Totem есть специальный обработчик-программа. Пробовать совмещать со своим кодом не пробовала.
- Для датасета Abilene есть написанный обработчик на Perl.
- Параметры генератора описаны в коде
🚨 Обратите внимание! Не каждый датасет подходит под все задачи и все алгоритмы. Иногда нужный параметр можно получить из данных, однако не всегда это возможно. К примеру, в подходе с рандомной нейронной сетью нужно было иметь большое количество временных замеров потока по каждому ребру и так же подробное описание графа, для построения кратчайшего пути.
💻 Единственная реализованная версия для Python.
📒 Пример использования в проекте
Существует большое количество различных библиотек для решения задач линейного программирования. Я использовала PULP в своем коде.
Все полученные результаты и краткое описание проекта доступны по ссылке.