Simulated Annealing for TSP

This repository contains a C++ library and a set of experiments for solving the Travelling Salesman Problem (TSP) using Simulated Annealing (SA) and its generalizations. It was developed in the context of my M.Sc. in Computational Statistical Physics research. The codebase is designed to be modular, efficient, and extensible, allowing for easy experimentation with different cooling schedules, graph topologies, and proposal distributions.

The project explores concepts such as:

• Standard Simulated Annealing
• Generalized Simulated Annealing (GSA)
• Tsallis Entropy
• Correlated domains and various metric spaces

Features

• High-Performance C++17 Library: Optimized for speed and numerical stability.
• Modular Design:
  • graphs/: Efficient graph representations (Complete Weighted Graphs, Hamiltonian Cycles).
  • sampling/: MCMC implementations, Metropolis algorithm, Annealing schedules (Geometric, etc.).
  • maths/: Statistics, Stochastic processes, Topology, and basic math utilities.
  • tools/: I/O helpers, argument parsing.
• Extensible Projects: Unique experiments are organized as separate sub-projects under proj/.
• Build System: A comprehensive Makefile handles static/shared library generation, project compilation, and dependency management.
• Cluster Ready: Scripts included for running batch jobs on computer clusters (e.g., using ts Task Spooler).

Prerequisites

To build and run this project, you need:

• C++ Compiler: g++ with C++17 support.
• Make: For build orchestration.
• Eigen3: C++ template library for linear algebra.
• Python 3: For generating argument lists for batch runs.
• Task Spooler (ts): (Optional) For scheduling batch jobs via run_with_args.sh.

Alternatively, you can use Nix to set up a reproducible development environment with all dependencies pre-configured.

Installation & Build

1. Clone the repository

git clone <repository_url>
cd tsp-sa

### 2. Development Environment (Optional)

If you have [Nix](https://nixos.org/download.html) installed, you can enter a development shell with all dependencies (`gcc`, `make`, `eigen`, `python3`, `ts`) ready to go:

```sh
nix develop

This ensures you have the exact versions of tools and libraries needed.

3. Build the Library and Default Project

The Makefile provides several targets. To build everything (static library, shared library, and the active project):

make all

### 4. Build a Specific Project

To specify which project to build (projects are located in `proj/<project_name>`), edit the `PROJ` variable in the `Makefile` or pass it as an argument:

```sh
make PROJ=final_costs build

Usage

Running the Executable

After building, the binary is placed in build/proj/<project_name>/bin/. You can run it directly:

./build/proj/final_costs/bin/final_costs.out [arguments]

Or use the helper make target (runs the defined PROJ):

make run

Running Batch Experiments

The run_with_args.sh script helps run a binary multiple times with different arguments generated by a Python script.

1. Ensure you have a corresponding Python script that outputs arguments (e.g., proj/final_costs/final_costs_args.py).
2. Run the wrapper script:

./run_with_args.sh <path_to_binary> <path_to_python_args_script>

Example:

./run_with_args.sh build/proj/final_costs/bin/final_costs.out proj/final_costs/final_costs_args.py

Project Structure

.
├── Makefile             # Main build configuration
├── build/               # Compiled artifacts (lib, obj, bin)
├── datasets/            # TSP datasets
├── doc/                 # Generated documentation
├── include/             # Header files (*.hpp, *.tpp)
│   ├── graphs/          # Graph theory related headers
│   ├── maths/           # Mathematical utilities
│   ├── sampling/        # SA and MCMC headers
│   ├── tools/           # Helper tools
│   ├── core.hpp         # Core definitions
│   └── tsp_sa.hpp       # Main library include
├── proj/                # Sub-projects / Experiments
│   ├── final_costs/     # Example project: studying final costs vs params
│   ├── animation/       # Visualization projects
│   └── ...
├── src/                 # Source files (*.cpp)
└── run_with_args.sh     # Batch execution script

Key References

1. Simulated Annealing (Wikipedia)
2. Tsallis, C. "Possible generalization of Boltzmann-Gibbs statistics." Journal of Statistical Physics 52, 479–487 (1988). Link
3. Penna, T.J.P. "Generalized simulated annealing." Physica A: Statistical Mechanics and its Applications (1996). Link