This repository contains the source code of a solver for the PACE 2024 challenge. See a short description of the solver.
Bob came third🥉on the exact track, second🥈on the heuristic track, and got the maximum score on the parameterized track.
Your machine needs to have a C++ compiler with C++17 support. We use GNU Make to build the executables.
The solver has been developed and thoroughly tested with LLVM (release_17.0.4). Use the corresponding versions of clang/lld for reproducible results.
To build the executable, run one of the following commands at the root of the repository:
make heuristic
make exact
make cutwidth
This creates an executable named pace_* and can be run as follows:
| Track | Command |
|---|---|
| heuristic | ./pace_heuristic < path/to/input_file.gr |
| exact | ./pace_exact < path/to/input_file.gr |
| cutwidth | ./pace_cutwidth < path/to/input_file.gr |
dev (make) |
./pace < path/to/input_file.gr or ./pace -verbose=1 -help for supported options |
lite (make lite) |
./pace_lite < path/to/input_file.gr |
Important
Release pace-2024 contains statically built binaries (for Linux) for the three tracks: pace_heuristic, pace_exact, and pace_cutwidth
The lite version of the solver, pace_lite (not part of the competition), is able to process very large instances within seconds
at the cost of slightly worsened results. For example, every instance from the public dataset (containing up to 100K vertices) is processed
within 10 seconds producing less than extra 0.5% of crossings than the known optimum.
