298 lines
11 KiB
TeX
298 lines
11 KiB
TeX
%************************************************
|
|
\chapter{Experiment Resources}%
|
|
\label{ch:benchmarks}
|
|
%************************************************
|
|
|
|
\noindent{}All experiments included in this thesis were conducted on a dedicated node in a computational cluster.
|
|
The machine operates using an \textbf{Intel Xeon 8260} \glsxtrshort{cpu}, which has 24 non-hyperthreaded cores, and has access to \textbf{268.55 GB} of \glsxtrshort{ram}.
|
|
Each experimental test was given exclusive access to a single \glsxtrshort{cpu} core and access to sufficient \glsxtrshort{ram}.
|
|
|
|
\section{Experimental Design}%
|
|
\label{sec:bench-env}
|
|
|
|
To promote the verification and recreation of our experiments, we have published our experimental design in the form of several bundles.
|
|
Each bundle contains the exact versions of the software, models, and data that were used.
|
|
They are accompanied by instructions to perform the experiments.
|
|
|
|
The experiments are split into three bundles, each testing a different system.
|
|
Each part is published as a Git repository on GitHub.
|
|
|
|
\paragraph{MiniZinc Prototype} The design for the experiments of the \minizinc{} prototype implementation can be found on the following webpage.
|
|
|
|
\begin{center}
|
|
\url{https://github.com/Dekker1/bytecode-benchmarks}
|
|
\end{center}
|
|
|
|
This repository contains the \gls{rewriting} and recursive function benchmarks.
|
|
|
|
\paragraph{Half-Reification} The design for all the \gls{half-reif} experiments is located on the following webpage.
|
|
|
|
\begin{center}
|
|
\url{https://github.com/Dekker1/half-reif-benchmarks}
|
|
\end{center}
|
|
|
|
This repository contains both the benchmark for the \gls{chuffed} \glspl{propagator} of \gls{half-reif} \constraints{} and the \minizinc{} Challenge 2019 \& 2020 benchmark.
|
|
|
|
\paragraph{Restart Based Meta-Optimization} Finally, the design of the experiments for restart based \gls{meta-optimization} can be found on the following webpage.
|
|
|
|
\begin{center}
|
|
\url{https://github.com/Dekker1/on-restart-benchmarks}
|
|
\end{center}
|
|
|
|
This repository contains the benchmarks for both \gls{gecode} and \gls{chuffed}.
|
|
|
|
|
|
\section{Software}%
|
|
\label{sec:bench-soft}
|
|
|
|
Central to the experiments in this thesis are two kinds of programs: programs that rewrite a \constraint{} model into a \gls{slv-mod} and the \solvers{} that search for \glspl{sol}.
|
|
We generally test the rewriting programs, in particular to rewrite \minizinc{} \instances{} to \flatzinc{}, but use the \solvers{} to evaluate the effect of changes to these rewriting programs.
|
|
|
|
\subsection{MiniZinc Rewriting}
|
|
|
|
In this thesis we use three different programs to rewrite \minizinc{} to \flatzinc{}.
|
|
|
|
\begin{itemize}
|
|
|
|
\item The official release of MiniZinc, version 2.5.5 \autocite{minizinc-2021-minizinc}.
|
|
The source code for this version can be found on the following webpage.
|
|
\begin{center}
|
|
\url{https://github.com/MiniZinc/libminizinc/tree/2.5.5}
|
|
\end{center}
|
|
|
|
\item A prototype for the language architecture designed as part of this thesis.
|
|
The source code for this version can be found on the following webpage.
|
|
\begin{center}
|
|
\url{https://github.com/Dekker1/libminizinc/tree/feature/bytecode}
|
|
\end{center}
|
|
|
|
\item The official MiniZinc release, version 2.5.5, adjusted to support \gls{rbmo}.
|
|
The source code for this version can be found on the following webpage.
|
|
\begin{center}
|
|
\url{https://github.com/Dekker1/libminizinc/tree/feature/on_restart}
|
|
\end{center}
|
|
|
|
\end{itemize}
|
|
|
|
\subsection{MiniZinc Solvers}
|
|
|
|
In this thesis we use the following \solvers{}.
|
|
|
|
\paragraph{Chuffed} is an open source \gls{lcg} \solver{} \autocite{chuffed-2021-chuffed,chu-2011-chuffed}.
|
|
In this thesis we use three different versions of the \gls{chuffed} \solver{}.
|
|
|
|
\begin{itemize}
|
|
|
|
\item The official development version of \gls{chuffed}.
|
|
The source code for this version can be found on the following webpage.
|
|
\begin{center}
|
|
\url{https://github.com/chuffed/chuffed/tree/develop}
|
|
\end{center}
|
|
|
|
\item An extension of \gls{chuffed} that includes \glspl{propagator} for \glspl{half-reif} of the \mzninline{all_different} and \mzninline{element} \constraints{}.
|
|
The source code for this version can be found on the following webpage.
|
|
\begin{center}
|
|
\url{https://github.com/Dekker1/chuffed/tree/feature/imp_globals}
|
|
\end{center}
|
|
|
|
\item An extension of \gls{chuffed} that includes \glspl{propagator} for restart-based \gls{meta-optimization}.
|
|
The source code for this version can be found on the following webpage.
|
|
\begin{center}
|
|
\url{https://github.com/Dekker1/chuffed/tree/feature/on_restart}
|
|
\end{center}
|
|
|
|
\end{itemize}
|
|
|
|
\paragraph{Coin-OR Branch-and-Cut} is an open source \gls{mip} \solver{} \autocite{forrest-2020-cbc}.
|
|
In this thesis we use version 2.10.5 of this solver.
|
|
Its source code is available on the following webpage.
|
|
|
|
\begin{center}
|
|
\url{https://github.com/coin-or/Cbc/tree/releases/2.10.5}
|
|
\end{center}
|
|
|
|
\paragraph{Gecode} is an open source \gls{cp} solver \autocite{schulte-2019-gecode}.
|
|
In this thesis we use four different versions of the \gls{gecode} solver.
|
|
\begin{itemize}
|
|
|
|
\item The official release of \gls{gecode}, version 6.3.0.
|
|
The source code for this version can be found on the following webpage.
|
|
\begin{center}
|
|
\url{https://github.com/Gecode/gecode/tree/release-6.3.0}
|
|
\end{center}
|
|
|
|
\item An extension of \gls{gecode} that includes \glspl{propagator} for restart-based \gls{meta-optimization}.
|
|
The source code for this version can be found on the following webpage.
|
|
\begin{center}
|
|
\url{https://github.com/Dekker1/gecode/tree/feature/on_restart}
|
|
\end{center}
|
|
|
|
\item An extension of \gls{gecode} that is able to record the search process of restart-based \gls{meta-optimization}.
|
|
The source code for this version can be found on the following webpage.
|
|
\begin{center}
|
|
\url{https://github.com/Dekker1/gecode/tree/feature/on_restart_record}
|
|
\end{center}
|
|
|
|
\item An extension of \gls{gecode} that is able to replay the search process of restart-based \gls{meta-optimization}.
|
|
The source code for this version can be found on the following webpage.
|
|
\begin{center}
|
|
\url{https://github.com/Dekker1/gecode/tree/feature/on_restart_replay}
|
|
\end{center}
|
|
|
|
\end{itemize}
|
|
|
|
\paragraph{IBM CPLEX} is a proprietary \gls{mip} \solver{} \autocite{ibm-2020-cplex}.
|
|
In this thesis we use \gls{cplex} version 20.1 under an academic licence in our experiments.
|
|
|
|
\paragraph{OpenWBO} is an open source \gls{maxsat} \solver{} \autocite{martins-2014-openwbo}.
|
|
In this thesis we use version 2.1 in our experiments.
|
|
The source code for this version can be found on the following webpage.
|
|
|
|
\begin{center}
|
|
\url{https://github.com/sat-group/open-wbo}
|
|
\end{center}
|
|
|
|
|
|
\section{MiniZinc Models}%
|
|
\label{sec:bench-models}
|
|
|
|
In the following paragraphs, we introduce the origins of the models used in the experiments of this thesis.
|
|
|
|
\paragraph{MiniZinc Challenge} Most of the models used in the experiments in this thesis stem from the \minizinc{} Challenge \autocite{stuckey-2010-challenge,stuckey-2014-challenge}.
|
|
The \minizinc{} Challenge is a yearly competition, held since 2008, in which \minizinc{} \solvers{} compete against each other in solving 100 \minizinc{} instances.
|
|
\Glspl{solver} are scored based on their performance solving each instance: time to \gls{sol}, quality of \gls{sol}, and proof of optimality.
|
|
The 100 instances stem from 20 \minizinc{} models, 10 of which are guaranteed to have never been used in earlier challenges.
|
|
|
|
A repository of all \minizinc{} models previously used in the challenges and accompanying data files can be found on the following webpage.
|
|
|
|
\begin{center}
|
|
\url{https://github.com/minizinc/minizinc-benchmarks}
|
|
\end{center}
|
|
|
|
The \gls{rewriting} experiment presented in \cref{sec:rew-experiments} use a selection of seventeen models originating from the \minizinc{} challenge.
|
|
These models can be identified using the following labels.
|
|
|
|
\begin{multicols}{3}
|
|
\ttfamily
|
|
\begin{itemize}
|
|
\item accap
|
|
\item amaze
|
|
\item city-position
|
|
\item {\scriptsize{} community-detection}
|
|
\item depot-placement
|
|
\item freepizza
|
|
\item groupsplitter
|
|
\item kidney-exchange
|
|
\item multi-knapsack
|
|
\item nonogram
|
|
\item nside
|
|
\item rcpsp-wet
|
|
\item road-cons
|
|
\item roster
|
|
\item {\scriptsize{} stack-cuttingstock}
|
|
\item steelmillslab
|
|
\item triangular
|
|
\end{itemize}
|
|
\end{multicols}
|
|
|
|
The large scale \gls{half-reif} experiment presented in \cref{sec:half-experiments} uses the \minizinc{} instances from 2019 and 2020.
|
|
The 2019 \minizinc{} Challenge included the models identified by the following labels.
|
|
|
|
\begin{multicols}{3}
|
|
\ttfamily
|
|
\begin{itemize}
|
|
\item accap
|
|
\item amaze
|
|
\item code-generator
|
|
\item fox-geese-corn
|
|
\item groupsplitter
|
|
\item hrc
|
|
\item kidney-exchange
|
|
\item {\scriptsize{} liner-sf-repositioning}
|
|
\item lot-sizing
|
|
\item median-string
|
|
\item multi-knapsack
|
|
\item nside
|
|
\item ptv
|
|
\item rcpsp-wet-diverse
|
|
\item {\scriptsize{} rotating-workforce}
|
|
\item {\scriptsize{} stack-cuttingstock}
|
|
\item steelmillslab
|
|
\item stochastic-vrp
|
|
\item triangular
|
|
\item zephyrus
|
|
\end{itemize}
|
|
\end{multicols}
|
|
|
|
\noindent{}The 2020 \minizinc{} Challenge included the models identified by the following labels.
|
|
|
|
\begin{multicols}{3}
|
|
\ttfamily
|
|
\begin{itemize}
|
|
\item bnn-planner
|
|
\item cable\_tree\_wiring
|
|
\item code-generator
|
|
\item {\tiny{} collaborative-construction}
|
|
\item gbac
|
|
\item hoist-benchmark
|
|
\item is
|
|
\item lot-sizing
|
|
\item {\scriptsize{} minimal-decision-sets}
|
|
\item p1f-pjs
|
|
\item pentominoes
|
|
\item pillars-and-planks
|
|
\item racp
|
|
\item radiation
|
|
\item sdn-change
|
|
\item skill-allocation
|
|
\item {\scriptsize{} soccer-computational}
|
|
\item stable-goods
|
|
\item tower\_challenge
|
|
\item whirlpool
|
|
\end{itemize}
|
|
\end{multicols}
|
|
|
|
The incremental experiments presented in \cref{sec:inc-experiments} are based on four models from the \minizinc{} Challenge, identified by the following labels.
|
|
|
|
\begin{multicols}{2}
|
|
\ttfamily
|
|
\begin{itemize}
|
|
\item gbac
|
|
\item radiation
|
|
\item steelmillslab
|
|
\item rcpsp-wet
|
|
\end{itemize}
|
|
\end{multicols}
|
|
|
|
|
|
\paragraph{Prize Collecting Path} This problem was introduced in by \textcite{feydy-2011-half-reif} in the original paper on \gls{half-reif}.
|
|
In this thesis it is used to benchmark the implementation of a \gls{propagator} for the \gls{half-reif} of the \mzninline{element} \constraint{}.
|
|
This experiment is shown in \cref{sec:half-experiments}.
|
|
\Cref{lst:bench-prize} shows a \minizinc{} model that can be used to solve the problem.
|
|
The data and original model are available on the following webpage.
|
|
|
|
\begin{center}
|
|
\url{https://people.eng.unimelb.edu.au/pstuckey/half/}
|
|
\end{center}
|
|
|
|
\begin{listing}
|
|
\mznfile{assets/listing/prize.mzn}
|
|
\caption{\label{lst:bench-prize} A \minizinc{} model for the Prize Collecting Path problem.}
|
|
\end{listing}
|
|
|
|
\paragraph{QCP-Max} This problem was introduced in by \textcite{feydy-2011-half-reif} in the original paper on \gls{half-reif}.
|
|
In this thesis it is used to benchmark the implementation of a \gls{propagator} for the \gls{half-reif} of the \mzninline{all_different} \constraint{}.
|
|
This experiment is shown in \cref{sec:half-experiments}.
|
|
\Cref{lst:bench-qcpmax} shows a \minizinc{} model that can be used to solve the problem.
|
|
The data and original model are available on the following webpage.
|
|
|
|
\begin{center}
|
|
\url{https://people.eng.unimelb.edu.au/pstuckey/half/}
|
|
\end{center}
|
|
|
|
\begin{listing}
|
|
\mznfile{assets/listing/qcp_max.mzn}
|
|
\caption{\label{lst:bench-qcpmax} A \minizinc{} model for the QCP-Max problem.}
|
|
\end{listing}
|
|
|