Skip to main content

tsp-fast-solver: High-Performance TSP Solver in Pure Python & C++ (Cython)

Python 3.8+ License: MIT

A high-performance library solving the Traveling Salesperson Problem (TSP) using brute-force search implemented in both Pure Python and Native C++ wrapped with Cython.


📌 Problem Overview & Real-World Context

The Traveling Salesperson Problem (TSP) is an NP-hard problem in combinatorial optimization:

Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?

Because the number of unique tours starting from a fixed origin scales factorially with $(N-1)!$, brute-force exploration in dynamic languages like pure Python rapidly encounters performance bottlenecks.

By offloading the inner combinatorial search loop (std::next_permutation) to compiled C++ and exposing it via a zero-overhead Cython C-extension, we achieve up to ~100x speedups.


🚀 Performance Benchmarks

Benchmarks were performed on random symmetric Euclidean/metric distance matrices using Python's timeit module.

Graph Size (Nodes) Possible Routes $(N-1)!$ Pure Python Time (s) Cython C++ Time (s) Speedup Minimum Tour Cost
N = 8 5,040 0.0034s 0.00005s 71.5x 229
N = 10 362,880 0.3384s 0.0033s 101.7x 191
N = 11 3,628,800 3.8315s 0.0418s 91.6x 268

Key Takeaways

  • N = 8: Cython execution is virtually instantaneous ($< 0.1\text{ ms}$).
  • N = 10: Over $362,000$ permutations evaluated in only $3.3\text{ ms}$ (vs. $338\text{ ms}$ in Python).
  • N = 11: Evaluates over $3.6\text{ million}$ complete candidate tours in just $41.8\text{ ms}$ (under $0.05$ seconds), delivering a massive ~92x to 102x speedup over pure Python.

📂 Project Architecture

CPython/
├── pyproject.toml              # Modern PEP 517/518 build specification
├── setup.py                    # Setuptools build configuration with Cython C++ extension
├── MANIFEST.in                 # Source distribution manifest ensuring all C++ & Cython files are packaged
├── .gitignore                  # Git ignore rules for build artifacts, compiled .pyd/.so, etc.
├── README.md                   # Complete documentation and benchmark analysis
├── WORKFLOW_STEPS.txt          # Detailed step-by-step workflow of work performed
├── benchmark.py                # Benchmarking suite comparing Pure Python vs Cython
├── test_solvers.py             # Unit tests verifying correctness and equivalence across topologies
├── src/
│   ├── python_solver/
│   │   ├── __init__.py
│   │   └── solver.py           # Pure Python implementation (tsp_python) using itertools.permutations
│   ├── cpp/
│   │   ├── tsp.h               # C++ header declaring tsp_solver(const std::vector<int>&, int)
│   │   └── tsp.cpp             # Native C++ solver using std::next_permutation
│   └── cython_wrapper/
│       ├── __init__.py
│       ├── tsp_c.pxd           # Cython declaration bridging C++ header
│       └── tsp_wrapper.pyx     # Cython implementation converting list-of-lists to std::vector<int>
└── tsp_fast_solver/            # Python package entry point
    ├── __init__.py             # Exports tsp_python and tsp_cython
    └── python_solver.py        # Packaged pure Python fallback

🛠️ Installation & Building

1. Requirements

  • Python 3.8 or higher
  • C++11 compliant compiler (GCC/MinGW-w64 on Windows, GCC/Clang on Linux/macOS, or MSVC)
  • Cython, setuptools, and build:
    pip install cython setuptools build twine pytest
    

2. In-place Compilation (Local Development)

To compile the C++ extension locally:

python setup.py build_ext --inplace

3. Build Source Distribution (sdist)

To generate the distribution tarball for PyPI:

python -m build --sdist

The resulting .tar.gz archive will be located in the dist/ directory.


💻 Usage Example

from tsp_fast_solver import tsp_python, tsp_cython

# Define an N x N distance matrix (e.g. 4 cities)
distance_matrix = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

# 1. Pure Python Solver
py_cost = tsp_python(distance_matrix)
print("Pure Python Minimum Cost:", py_cost)

# 2. Cython C++ Solver
cy_cost = tsp_cython(distance_matrix)
print("Cython C++ Minimum Cost:", cy_cost)

assert py_cost == cy_cost

🧪 Running Tests & Benchmarks

Run Unit Tests

pytest test_solvers.py -v

Run Benchmarks

python benchmark.py

📦 Publishing to GitHub and PyPI

Step 1: Initialize Git and Push to GitHub

git init
git add .
git commit -m "Initial commit: Pure Python and Cython C++ TSP solvers"
git branch -M main
git remote add origin https://github.com/<your-username>/tsp-fast-solver.git
git push -u origin main

Step 2: Upload to PyPI using Twine

# Upload distribution archive to PyPI
python -m twine upload dist/*

When prompted:

  • Username: __token__
  • Password: <Your-PyPI-API-Token>

Step 3: Verify Installation from PyPI

pip install tsp-fast-solver
python -c "import tsp_fast_solver; print('Successfully installed and imported!')"

📄 License

This project is licensed under the MIT License.

Metadata

Release files for tsp-fast-solver-raghav15048 0.1.2

For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.

Source distribution (sdist)

Source distribution for tsp-fast-solver-raghav15048 0.1.2
File Size Uploaded Provenance Actions
tsp_fast_solver_raghav15048-0.1.2.tar.gz 73.4 kB Without provenance Details for tsp_fast_solver_raghav15048-0.1.2.tar.gz

Built distribution (wheel)

Table of built distributions (wheels) for tsp-fast-solver-raghav15048 0.1.2
File Interpreter ABI Platform Actions
tsp_fast_solver_raghav15048-0.1.2-cp312-cp312-win_amd64.whl CPython 3.12 CPython 3.12 Windows x86-64 Details for tsp_fast_solver_raghav15048-0.1.2-cp312-cp312-win_amd64.whl

Total release size: 168.8 kB

Release files / tsp_fast_solver_raghav15048-0.1.2.tar.gz

Download URL tsp_fast_solver_raghav15048-0.1.2.tar.gz
Size 73.4 kB
Tags Source
SHA-256 checksum
How to use checksums
b57a3025008908e7f2feded994ee4a91eef9c4fd689f0704af29ed45a1aca7d8
BLAKE2b-256 checksum
How to use checksums
d78c702862b5b199b1823b33e78c3079e52ad50793f745f9872ed22acf353820
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/7.0.0 CPython/3.12.1

Release files / tsp_fast_solver_raghav15048-0.1.2-cp312-cp312-win_amd64.whl

Download URL tsp_fast_solver_raghav15048-0.1.2-cp312-cp312-win_amd64.whl
Size 95.4 kB
Tags CPython 3.12 Windows x86-64
SHA-256 checksum
How to use checksums
eaceb7a4072073713a23e032208e0caffa4ab6f8dafd698b9b8ea8e9298e3bde
BLAKE2b-256 checksum
How to use checksums
434d3a2dcfabb7bfb373825351011dfb9c0a630b5b8575f0db132bc194adde3f
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/7.0.0 CPython/3.12.1

Security for tsp-fast-solver-raghav15048 0.1.2

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

No provenance found

None of the files in this release were uploaded with provenance metadata.

A note on package security

PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.

To learn more about protecting yourself from malicious actors, visit our package security documentation.

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page