# PACE 2024: RoundAbout solver DOI: 10.5281/zenodo.11538957 This repository contains the exact and heuristic solver RoundAbout. It was submitted to the PACE 202 Challenge on One-Sided Crossing Minimisation (OSCM). ## Description of the algorithmThe heuristic and the exact solver are built using several bricks: - a preprocessing based on preprocessing of the Kemeny Rank Aggregation problem from [1] is performed to split the input instance into several smaller sub-instances, - a DP algorithm from [2] is used when the width is small enough, directly, during the branching algorithm and in the heuristic, - the heuristic is based on a local search algorithm, - the exact algorithm is composed by branch and bound algorithm, the heuristic is used to get a good upper bound and is completed by a lower bound, when the graph is enough reduced, the DP algorithm is used to solve optimally the problem on the remaining. ## How to compile ### DependenciesThis solver is implemented in [OCaml](https://ocaml.org/) and C and uses [OPAM](https://opam.ocaml.org/) to manage its dependencies and [dune](https://dune.readthedocs.io/en/stable/) as a build system. To install `opam`:```bashbash -c "sh <(curl -fsSL https://raw.githubusercontent.com/ocaml/opam/master/shell/install.sh)"``` Opam needs to be initialised. Here, we will just initialise it without installing the ocaml compiler:```bashopam init --bare``` To install the compiler and the dependencies:```bashmake init``` ### Building and Running the solverTo build:```bashmake build``` To run the exact solver:```bash./RoundAbout-Exact < [input graph]``` To run the heuristic solver:```bash./RoundAbout-Heuristic < [input graph]``` [1] Betzler, N., Bredereck, R. and Niedermeier, R., 2014. Theoretical and empirical evaluation of data reduction for exact Kemeny rank aggregation. Autonomous Agents and Multi-Agent Systems, 28, pp.721-748. [2] Arrighi, E., Fernau, H., de Oliveira Oliveira, M. and Wolf, P., 2020, December. Width Notions for Ordering-Related Problems. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science.