\section{Описание программной реализации}
\label{sec:5_alg_description} \index{5_alg_description}

\subsection{Запуск решателя при выполнении экспериментов}
\label{sec:solver_run}



При выполнении серий экспериментов было введено ограничение по времени на
выполнение решателя, так как есть задачи (например, с треугольным графом из 55
вершин и 90 ребер), на которых решатель не завершил работу в течение
суток. Ограничение задается в виде параметра эксперимента.

В связи с существенной зависимостью времени работы решателя от упорядочения и наличия/отсутствия транзитивности, для основной серии экспериментов (см. раздел \ref{sec:7_experiments}) была выбрана следующая схема выполнения эксперимента с каждым конкретным набором входных данных (графом работ):
\begin{itemize}
    \item на 10 процессорных ядрах параллельно запускаются 10 экземпляров
решателя, с 5 разными упорядочениями переменных и линейных
ограничений в каждой секции входного файла решателя, как при наличии так и при отсутствии добавленных в граф транзитивных ребер;
    \item на выполнение каждого экземпляра решателя установлен лимит по
времени, являющийся параметром эксперимента;
    \item по достижении лимита времени, все экземпляры решателя, не завершившиеся до
этого момента, останавливаются искусственно;
    \item если хотя бы один экземпляр решателя завершился с обнаружением оптимального решения (статус «optimal solution found» для SCIP), то принудительно завершается выполнение остальных экземпляров.
\end{itemize}

В набор упорядочений входили: default, down\_left, up\_right, tiers, reverse\_tiers (см. подраздел \ref{sec:input_generation}). 

Эксперимент для конкретного графа считается успешным, если хотя бы один из
экземпляров решателя завершился с обнаружением оптимального решения. Если
такого экземпляра нет, то некоторые решения задачи (без гарантии
оптимальности) могут быть получены от экземпляров решателя, завершившихся по лимиту времени, но нашедших в ходе работы допустимые решения.

Выдача решателя содержит верхние оценки отклонения целевой функции на полученных промежуточных решениях от оптимального значения. В подразделе \ref{sec:gap} на отдельных примерах рассмотрено, какую экономию по времени можно получить, ограничившись поиском решений с наперед заданным отклонением значения целевой функции от оптимального.

Решатель SCIP запускался при помощи команды вида:
\begin{verbatim}
scip -s only_time.set -l <выходной файл> -f <входной файл>
\end{verbatim}

Решатель CBC запускался при помощи команды вида:
\begin{verbatim}
cbc <входной файл> sec <лимит в секундах> solve solu <выходной файл>
\end{verbatim}

Решатель GLPK запускался при помощи команды вида:
\begin{verbatim}
time timeout <лимит в секундах> glpsol --cpxlp --first <входной файл> 
-o <выходной файл>
\end{verbatim}

Здесь <лимит в секундах> был установлен в 1800, это же значение было записано в файл only\_time.set

\subsection{Разработанные программы}
\label{programs}

Исходные тексты реализации, а также комплекты входных данных, доступны в репозитории на сервисе Github \cite{GITHUB}.

\textbf{Транслятор входных данных во входной язык решателя}

Программа make\_input.py, написанная на языке Python 3.9. Получает на вход
файл с описанием графа работ и транслирует его в 5 файлов на входном
языке решателя, соответствующих 5 различным упорядочениям вершин и
ребер графа (а, следовательно, переменных и ограничений задачи ЦЛП). Упорядочения описаны в подразделе \ref{sec:input_generation}.

Параметры командной строки:

\texttt{-i, --input}: Путь к входному файлу или каталогу с файлами. Обязательный параметр.

\texttt{-o, --output}: Путь к каталогу для сохранения выходных файлов. По умолчанию используется подкаталог outputs/ в текущем каталоге.

\texttt{-tr, --transitive}: Флаг, указывающий на добавление транзитивных ребер при генерации ограничений.

\newpage
Пример запуска:
\begin{verbatim}
make_input.py -i input.txt -o outdir/ -tr
\end{verbatim}

\textbf{Командный сценарий запуска серии экспериментов}

Программа run\_scip.sh, написанная на языке bash, выполняет параллельные запуски решателя SCIP для различных упорядочений и наличия/отсутствия транзитивности и принудительно завершает выполнение всех экземпляров решателя, если хотя бы один экземпляр успешно завершился. Программы run\_glpk.sh и run\_cbc.sh выполняют последовательные запуски решателей GLPK и CBC для различных упорядочений и наличия/отсутствия транзитивности.

Для каждого файла из каталога translator\_inputs/ предварительно должен быть вызван транслятор входных данных во входной язык решателя. Входные данные решателя должны быть в каталогах inputs/new\_tr/order/ и inputs/new\_no\_tr/order/ (суффиксы «\_tr» и «no\_tr» соответствуют наличию и отсутствию транзитивности). Результаты записываются в каталоги outs/new\_tr/ и outs/new\_no\_tr/.

Формат вызова программ:
\begin{verbatim}
run_scip.sh
run_glpk.sh
run_cbc.sh
\end{verbatim}

\textbf{Сборщик результатов экспериментов}

Программы get\_stats\_scip.py, get\_stats\_glpk.py, get\_stats\_cbc.py, написанные на языке Python 3.9, получают на вход каталог с файлами с результатами экспериментов соответствующего решателя и записывают в файлы SCIP\_res, GLPK\_res, CBC\_res соответственно три словаря: с количеством вершин для каждого графа, временем выполнения эксперимента и статусом завершения эксперимента. Программа get\_percents.py, написанная на языке Python 3.9, получает на вход список файлов с результатами экспериментов решателя SCIP и записывает в файл SCIP\_percents словари соответствия для каждого графа: времени и процентного отклонения лучшего найденного решения от теоретической оценки оптимального.

Формат вызова программ:
\begin{verbatim}
get_stats_scip.py <каталог c результатами экспериментов>
get_stats_glpk.py <каталог c результатами экспериментов>
get_stats_cbc.py <каталог c результатами экспериментов>
get_percents.py <путь к файлу1> <путь к файлу2> ...
\end{verbatim}

\textbf{Программы отображения результатов экспериментов}

Программы show\_res\_scip.py (результат см. рис. \ref{fig:default60}, \ref{fig:default65}), show\_sorts\_scip.py (см. рис. \ref{fig:sorts}, \ref{fig:sorts_tr}) принимают на вход файл SCIP\_res, полученный с помощью программы \\get\_stats\_scip.py, и строят диаграммы в формате, описанном в подразделе \ref{sec:input_generation}. 

Программа show\_all.py (результат см. рис. \ref{fig:solvers_default} -- \ref{fig:solvers_dag}) принимает на вход три файла с результатами экспериментов трех решателей SCIP\_res, GLPK\_res, CBC\_res и строит диаграммы, описанные в подразделе \ref{sec:solvers_benchmark}.

Программы plot\_triang.py (результат см. рис. \ref{fig:trianglog}), plot\_layered.py (см. рис. \ref{fig:layeredlog}), plot\_dag.py (см. рис. \ref{fig:dagpie}) получают на вход файл SCIP\_res и строят диаграммы по серии экспериментов в формате, описанном в подразделе \ref{sec:results}.

Программа plot\_percents.py (см. рис. \ref{fig:percents_gap}) принимает на вход файл SCIP\_percents и строит диаграммы в формате, описанном в подразделе \ref{sec:gap}. 

Все вышеперечисленные программы написаны на языке Python 3.9 с использованием библиотеки matplotlib.

Формат вызова программ:
\begin{verbatim}
show_res_scip.py SCIP_res
show_sorts_scip.py SCIP_res
show_all.py SCIP_res GLPK_res CBC_res
plot_triang.py SCIP_res
plot_layered.py SCIP_res
plot_dag.py SCIP_res
plot_percents.py SCIP_percents
\end{verbatim}