B-n-B algorithms for PCGTSP

Here come source code, input data and results of numerical experiments for solving Precedence Constrained General Traveling Salesman Problem (PCGTSP) referred to in Problem-Specific Branch-and-Bound Algorithms for the Precedence Constrained Generalized Traveling Salesman Problem.

Prerequisites

One needs modern installation of Python as well as modules in requirements.txt:

pip install -r requirements.txt

For DP version to run, working installation of Gurobi along with appropriate license (the academic one is just fine) is recommended.

Test data

Problem instances are in Salman/input in PCGLNS format.

Corresponding solutions by PCGLNS heuristic are in Salman/heuristic.

Logs of B-n-B flavour of the algorithm are in logs/s, of DP flavour - in logs/salman.

Running algorithms

Branch-and-Bound flavour

Source code for B-n-B design is in playground/. To run:

python path/to/walk.py instance

Use instance name (eg e3x_1) without path or extension. Result of PCGLNS evaluation will be used automagically.

Logs will fall into logs/.

Dynamic Programming flavour

Source code for DP design is in dp/. To run:

python path/to/DP_pcglns.py -i=path/to/instance.pcglns -UB=NNNN -w=1

Specify path to PCGLNS file (with extension), best solution by PCGLNS and optionally number of parallel workers to run.

Logs will go to standard output / error.