🌍 Advanced TSP Solver: Integer Linear Programming & Branch-and-Cut

📖 Overview

This project provides a comprehensive framework for solving the Traveling Salesman Problem (TSP) using Integer Linear Programming (ILP).

Unlike simple heuristic solvers, this project explores the evolution of exact algorithms, demonstrating why standard mathematical formulations fail on large datasets and how modern techniques (like Lazy Constraints and Branch-and-Cut) solve instances with hundreds or thousands of nodes to optimality.

The repository includes implementations of:

1. Naive Formulation (Full Dantzig-Fulkerson-Johnson).
2. Miller-Tucker-Zemlin (MTZ) compact formulation.
3. Iterative Constraint Generation (Row Generation).
4. Branch-and-Cut using Solver Callbacks (State-of-the-Art).
5. k-NN Graph Sparsification for handling large-scale instances.

---

🧮 Mathematical Formulation

The TSP can be modeled as finding the minimum-weight Hamiltonian Cycle in a complete weighted graph $G=(V, A)$.

Let $V = {1, \dots, n}$ be the set of cities and $c_{ij}$ be the distance between city $i$ and city $j$. We introduce binary decision variables:

$$ x_{ij} = \begin{cases} 1 & \text{if the path goes directly from city } i \text{ to } j \\ 0 & \text{otherwise} \end{cases} $$

The Objective Function

We strictly minimize the total travel distance:

$$ \text{Minimize} \quad Z = \sum_{i=1}^{n} \sum_{j=1, j \neq i}^{n} c_{ij} x_{ij} $$

Assignment Constraints

To ensure every city is visited exactly once, we enforce that exactly one edge enters and one edge leaves every node:

$$ \begin{aligned} \sum_{j=1, j \neq i}^{n} x_{ij} = 1, \quad \forall i \in V \quad (\text{Out-degree}) \\ \sum_{i=1, i \neq j}^{n} x_{ij} = 1, \quad \forall j \in V \quad (\text{In-degree}) \end{aligned} $$

---

🚀 Implemented Strategies

This repository implements four distinct strategies to handle subtour elimination.

1. The Naive Approach (Full DFJ)

We explicitly forbid subtours for every possible subset of cities $S$. $$\sum_{i \in S} \sum_{j \in S} x_{ij} \leq |S| - 1, \quad \forall S \subset V, 2 \leq |S| \leq n-1$$

• The Issue: The number of subsets is $2^n$. For $N=50$, it requires $10^{15}$ constraints.

2. Miller-Tucker-Zemlin (MTZ)

Uses auxiliary variables $u_i$ representing the order of visits. $$u_i - u_j + n x_{ij} \leq n - 1$$

• Complexity: Polynomial $O(n^2)$.
• Drawback: Weak linear relaxation (Big-M), leading to slow convergence for $N > 60$.

3. Iterative Constraint Generation

Solves the problem without subtour constraints, detects disconnected loops, adds specific cuts, and restarts the solver.

• Benefit: Only adds necessary constraints.
• Drawback: Restarting the solver repeatedly discards the search tree.

4. Lazy Constraints (Branch-and-Cut)

State-of-the-Art. Uses Solver Callbacks.

1. Solver pauses when an integer solution is found.
2. We inject cuts dynamically.
3. Solver continues exploring the existing tree.

---

📊 Performance Benchmarks

The table below compares the execution time (in seconds) and the objective cost of the solution across different methods. It also highlights the impact of Graph Sparsification (Pruning).

Key Observation: At $N=600$, we observe the trade-off of the heuristic approach.

• The Full method (Exact) finds the optimal cost of 616.
• The Pruned method (Heuristic) finds a slightly suboptimal cost of 617, but solves it in 0.12s compared to 25s.

Nodes	Edges (F/P)	Iter. Full (Time/Cost)	Iter. Pruned (Time/Cost)	MTZ Full (Time/Cost)	MTZ Pruned (Time/Cost)	Lazy Full (Time/Cost)	Lazy Pruned (Time/Cost)
10	71 / 71	0.007s (251)	0.011s (251)	0.007s (251)	0.029s (251)	0.002s (251)	0.002s (251)
20	304 / 200	0.006s (187)	0.008s (187)	0.011s (187)	0.008s (187)	0.002s (187)	0.002s (187)
50	1946 / 500	0.357s (245)	0.439s (245)	0.116s (245)	0.059s (245)	0.063s (245)	0.030s (245)
100	7940 / 1k	0.208s (251)	0.047s (251)	0.553s (251)	0.099s (251)	0.019s (251)	0.022s (251)
200	31k / 2k	1.974s (303)	0.365s (303)	1.912s (303)	0.143s (303)	0.433s (303)	0.114s (303)
300	71k / 3k	3.725s (372)	2.072s (372)	6.318s (372)	0.283s (372)	0.802s (372)	0.038s (372)
400	127k / 4k	37.69s (446)	12.86s (446)	1033s (446)	2.416s (446)	2.116s (446)	0.164s (446)
500	199k / 5k	52.71s (521)	20.60s (521)	1425s (521)	11.52s (521)	20.47s (521)	0.126s (521)
600	287k / 6k	500.9s (616)	15.44s (617)	Timeout	3.63s (617)	25.42s (616)	0.122s (617)

---

🛠 Installation & Setup

Prerequisites

• Python 3.10+
• CPLEX Optimization Studio (Recommended for Lazy Constraints) or generic CBC solver.

Dependencies

pip install pulp docplex networkx