125 lines
12 KiB
TeX
125 lines
12 KiB
TeX
\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} |