Построение надёжной электрической цепи минимальной стоимости(SNDP)

Оглавление

• Введение
• Системные требования
• Сборка проекта
• Использование
  • Примеры
  • Формат ввода
  • Формат вывода
  • Отрисовка графа
• Математическая модель
  • Первое приближение
  • Эвристика для отказоустойчивости
  • Эвристика для связности графа
• Структура проекта
  • Диаграмма классов
• Анализ
• Источники

Введение

Цель проекта - разработка эвристического алгоритма, который находит ограничения с помощью вещественной модели. Далее все найденные ограничения передаются в точную смешано-целочисленную модель. Как показывают опыты это помогает ускорить нахождение оптимального решения для графов небольших размерностей и улучшить нижнюю оценку для графов больших размерностей(задача NP-трудная).

Системные требования

• Компилятор g++ (GCC) 15.2.1 или новее
• Python 3.14 или новее
• Лицензия CPLEX 12.6.1 или новее
• GNU Make 4.4.1 или новее

Сборка проекта

Чтобы собрать проект вам нужно владеть лицензией программного пакета "CPLEX".

Чтобы собрать проект, в Makefile нужно изменить значения:

...
CPLEXDIR      = ../../path-to-cplex/cplex/cplex/
CONCERTDIR    = ../../path-to-cplex/cplex/concert/
...

Затем собрать проект командой:

make

Использование

Примеры

Можно запустить тестовый пример командами:

make run

./build/network < ./input/main.txt

Можно запустить точный решатель (без эвристики), добавив флаг -e

./build/network -e < ./input/main.txt

Результаты вычислений записываются в директории output с именем output.txt.

Далее, после запуска виртуального окружения, можно отрисовать граф командой:

python draw.py

Подробнее про отрисовку тут.

Формат ввода

Первое число n - количество узлов в сети.

Далее в n строках передаются значения x, y, d, t, где x - координата узла по x, y - координата узла по y, d - потребление/прозводство узла, t - тип узла(0 - электростанция, 1 - город).

Типы переменных:

• x - вещественная
• y - вещественная
• d - вещественная
• t - бинарная

Примеры можно найти в директории input.

Формат вывода

В первой строке через пробел передаются значения узлов. Значения узла разделяются символом ";" и содержит:

• x - Координата по оси x
• y - Координата по оси y
• demand - Потребление/производство узла
• type - тип узла

Далее в i строке передаются значения дуг от узла i. Значения дуги содержат параметры:

• j - Номер узла в который ведёт дуга
• y - Значение y
• flow - Значения потока

Все выходные данные сохраняются в директории output с названием output.txt.

Отрисовка графа

Чтобы нарисовать граф нужно:

Создать виртуальное окружение

python -m venv venv

Активировать виртуальное окружение

. venv/bin/activate

Установить требуемые зависимости

pip install -r requirements.txt

Запустить скрипт draw.py:

python draw.py

python draw.py <название-файла-в-output> # например output.txt, а не output/output.txt

Математическая модель

ЕСЛИ LATEX НЕ ОТОБРАЖАЕТСЯ: ДИПЛОМ

Первое приближение

$min \sum_{i = 0}^{N}\sum_{j = 0}^{N} C_{ij} y_{ij}$

$\forall k \in S\space\sum_{i \in in(k)} f_{ik} - \sum_{j \in out(k)} f_{kj} = d_k$

$\forall i,j \in I f_{ij} \leqslant u_{ij}\cdot y_{ij}$

$\sum y_{ij} \geqslant 2$

Эвристика для добавления отказоустойчивости

$\forall S \subset V\space\sum\limits_{\substack{i \in S\j \in V \backslash S}} y_{ij}\geqslant \left\lceil - \dfrac{\sum\limits_{k \in S} P_{k} - \sum\limits_{k \in S} d_{k} - P_{k}^{}}{u^{}} \right\rceil$

Эвристика для связности графа

$\forall S \in V \sum\limits_{\substack{i \in S\ j \in V\backslash S}} y_{ij} \geqslant 1$

Структура проекта

Диаграмма классов