Operations Research 2 Project – University of Padua

TL;DR: A comprehensive optimization engine in C, orchestrated with Bash and GNU Make/CMake, implementing constructive heuristics (Nearest‑Neighbor, Extra‑Mileage), local search (2‑OPT), metaheuristics (GRASP, VNS, Tabu Search, Genetic Algorithms), exact methods (Benders Decomposition, Branch‑and‑Cut with CPLEX), and matheuristics (Local Branching, Hard Fixing) for the Traveling Salesman Problem. The code uses pthread, manual memory management, and profiling/debug scripts.

1. Motivation and Context
2. Repository Architecture
3. Algorithms
4. Building (CMake → GNU Make/Ninja)
5. Quick Run
6. Profiling & Benchmark
7. Testing & Continuous Integration
8. Report
9. License

This project started as a homework assignment for Operations Research 2 and turns syllabus content (mathematical programming algorithms, modeling, combinatorial optimization) into code by applying it to a prototype problem: the Traveling Salesman Problem. The outcome is a modular solver in C99, accompanied by POSIX shell scripts for building, testing and measurement, suitable for systems programming scenarios typical of the Linux kernel.

cflaglib/                 # Command‑line option parser           (C)
common/                  # Generic utilities, hashmap, timing  (C)
tsp_algo_lib/            # Algorithmic core and TSP structures  (C)
tsp_solver/              # Executable, algorithms, plotting    (C)
profiler/                # Bash scripts for experiments        (sh)
build.sh                 # Build helper                        (sh)
CMakeLists.txt           # Root build definition               (cmake)

The solver implements a comprehensive suite of algorithms organized into four categories:

• Nearest Neighbor – greedy tour construction
• Extra‑Mileage – insertion-based construction

• 2‑OPT – edge-swap refinement

• GRASP (Greedy Randomized Adaptive Search Procedure)
• Variable Neighborhood Search (VNS)
• Tabu Search
• Genetic Algorithms

• Benders Decomposition
• Branch‑and‑Cut

• Local Branching
• Hard Fixing

The project is managed with CMake, but can generate GNU Makefiles or use Ninja:

# Production build with GNU Makefiles
cmake -G "Unix Makefiles" -DCMAKE_BUILD_TYPE=RelWithDebInfo -B build
make -C build -j$(nproc)

# Debug build with sanitizers
cmake -G Ninja -DCMAKE_BUILD_TYPE=Debug -DENABLE_ASAN=ON -B build_dbg
ninja -C build_dbg

Note: The build.sh wrapper automates the steps above.

• GCC ≥ 12 / Clang ≥ 16
• CMake ≥ 3.25 (generates Makefile or Ninja)
• GNU Make (if using the “Unix Makefiles” generator)
• Bash ≥ 5, coreutils
• gnuplot (for plots)

# Random instance with 1000 nodes, 60s time limit, Nearest‑Neighbor heuristic
./build/tsp_solver/tsp_solver \
    --nodes 1000 --seconds 60 --nearest-neighbor

For the full list of options:

./tsp_solver --help

See the Algorithms section for the full list of implemented methods.

The profiler/ directory contains two scripts:

• profiler.sh – runs experiments in parallel (NN, VNS, TS) over a range of parameters
• analyzer.sh – analyzes CSVs and produces averages/plots

Output:

profiler/
├── results-*.csv       # raw data
├── *_avg.csv           # averages per configuration
└── *-plot.png          # cost vs. time graphs

Unit tests written in C (using <assert.h>) reside in */tests/.
Run them with CTest:

cd build && ctest --output-on-failure

Suggested CI pipeline (GitHub Actions):

- uses: actions/checkout@v4
- uses: rnorth/try-actions/setup-cmake@v1
- run: cmake -G Ninja -B build -DCMAKE_BUILD_TYPE=Debug
- run: ninja -C build
- run: ctest --test-dir build --output-on-failure

A detailed technical report is available in PDF format describing the theoretical background, implementation details, and experimental evaluation of all algorithms:

📄 report.pdf

The report includes:

• Mathematical formulation of the TSP
• Algorithm pseudocode and complexity analysis
• Experimental results on TSPLIB instances
• Dolan‑Moré performance profiles

This project is released under the MIT license (see LICENSE).

Author: Lorenzo Croce and Alberto Bottari – April 2025