Skip to content

TSP Solver v20250822-9135d78

Latest
Latest

Choose a tag to compare

View all tags
@github-actions github-actions released this 22 Aug 12:02
v20250822-9135d78
9135d78

TSP Solver Release v20250822-9135d78

Commit: 9135d78
Branch: master
Commit Message: update README.md with claude sonnet 4

no, the point of this is to demonstrate the problem and serve as a platform for others to take up on the challenge of working on a solution. for now, can you please integrate the findings here with the readme below? remember that it is critical that you do NOT hallucinate and do not remove the AI disclaimer in this repository. please return the complete readme in plain text

$ time cargo run --release 21 42

Finished release profile [optimized] target(s) in 0.00s

Running target/release/tsp_solver 21 42

Note: For 21 cities, only running optimized solution.

Use --all flag to run all implementations (warning: may take very long!)

=== Traveling Salesman Problem Solver ===

Cities: 21

Seed: 42

Mode: Optimized solution only

City Positions:

City 0: (0.00, 0.01)

City 1: (78.56, 60.47)

City 2: (81.05, 1.19)

City 3: (70.41, 37.51)

City 4: (28.28, 37.96)

City 5: (63.30, 31.49)

City 6: (41.54, 8.58)

City 7: (99.72, 80.97)

City 8: (29.60, 45.77)

City 9: (0.91, 96.23)

City 10: (24.66, 76.52)

City 11: (24.11, 45.28)

City 12: (22.73, 63.63)

City 13: (94.25, 18.45)

City 14: (3.18, 97.01)

City 15: (47.72, 72.36)

City 16: (24.17, 4.92)

City 17: (94.32, 29.94)

City 18: (96.39, 48.30)

City 19: (54.78, 14.33)

City 20: (94.31, 84.46)

=== Optimized Solution (Distance Matrix + Branch & Bound + Bitmask DP) ===

Best path: [0, 14, 10, 15, 12, 11, 8, 4, 16, 6, 19, 5, 3, 1, 20, 7, 18, 17, 13, 2, 9]

Route: 0 -> 14 -> 10 -> 15 -> 12 -> 11 -> 8 -> 4 -> 16 -> 6 -> 19 -> 5 -> 3 -> 1 -> 20 -> 7 -> 18 -> 17 -> 13 -> 2 -> 9 -> 0

Total distance: 351.83

Time taken: 2704.067 seconds

real 45m4.104s

user 44m54.371s

sys 0m0.444s

readme:

Traveling Salesman Problem Solver in Rust

A zero-dependency TSP solver with three distinct implementations showcasing algorithmic optimizations and parallel computing in Rust.

Features

  • Three Implementations: Single-threaded, multithreaded, and optimized with advanced algorithms
  • Exact Solutions: All implementations find the mathematically optimal solution (not heuristic)
  • Performance Benchmarking: Randomized execution order and detailed performance comparisons
  • Scalable: Handles 1-20+ cities with different algorithmic approaches based on problem size

Algorithms

Implementation Approach Best For
Single-threaded Brute force permutation Baseline comparison, 1-10 cities
Multi-threaded Parallel brute force CPU-bound improvement, 4-12 cities
Optimized Distance matrix + Branch & Bound + Bitmask DP Performance critical, 1-20+ cities

Performance

The optimized implementation demonstrates dramatic improvements through algorithmic optimization:

# 14 cities benchmark results:
1. Optimized:      0.008s  (baseline)
2. Multi-threaded: 59.084s (7,580x slower)
3. Single-threaded: 432.124s (55,444x slower)

Key optimizations:

  • Pre-computed distance matrix (eliminates repeated sqrt calculations)
  • Branch-and-bound pruning (reduces search space exponentially)
  • Bitmask dynamic programming (O(n²2ⁿ) vs O(n!) for ≤20 cities)

Usage

cargo run --release <num_cities> [seed] [threads]

Examples:

cargo run --release 10 42        # 10 cities, seed 42, auto-detect threads
cargo run --release 15 123 8     # 15 cities, seed 123, 8 threads

Recommendations:

  • 1-10 cities: All implementations work well
  • 11-15 cities: Use optimized implementation for best performance
  • 16-20 cities: Only optimized implementation practical
  • 20+ cities: Consider heuristic algorithms for larger problems

Sample Output

=== Traveling Salesman Problem Solver ===
Cities: 13, Seed: 42, Available CPU threads: 16

=== Performance Summary ===
Implementation order: ["Multi", "Optimized", "Single"]

Performance Ranking:
  1. Optimized: 0.004s (distance: 403.93)
  2. Multi-threaded: 4.400s (distance: 403.93, 1,243x slower)
  3. Single-threaded: 32.522s (distance: 403.93, 9,190x slower)

✓ All implementations found the same optimal solution!

Building & Testing

# Build optimized binary
cargo build --release

# Run tests
cargo test

# Run with custom parameters
./target/release/tsp_solver 12 42 4

Technical Details

  • Language: Rust (zero external dependencies)
  • Algorithms: Exact solutions only - guaranteed optimal results
  • Threading: Work-stealing parallel permutation generation
  • Memory: Efficient distance matrix caching and memory pooling
  • Verification: All implementations cross-validated for correctness

Complexity Analysis

Cities Brute Force Optimized (Bitmask DP) Practical Runtime
10 10! ≈ 3.6M 10²×2¹⁰ ≈ 102K milliseconds
15 15! ≈ 1.3T 15²×2¹⁵ ≈ 7.4M seconds
20 20! ≈ 2.4×10¹⁸ 20²×2²⁰ ≈ 419M minutes

⚠️ AI Disclosure: This project includes code generated with assistance from Large Language Models (LLMs).

Traveling Salesman Problem Solver in Rust

A zero-dependency TSP solver with three distinct implementations showcasing algorithmic optimizations and parallel computing in Rust.

Features

  • Three Implementations: Single-threaded, multithreaded, and optimized with advanced algorithms
  • Exact Solutions: All implementations find the mathematically optimal solution (not heuristic)
  • Performance Benchmarking: Randomized execution order and detailed performance comparisons
  • Scalable: Handles 1-20+ cities with different algorithmic approaches based on problem size

Algorithms

Implementation Approach Best For
Single-threaded Brute force permutation Baseline comparison, 1-10 cities
Multi-threaded Parallel brute force CPU-bound improvement, 4-12 cities
Optimized Distance matrix + Branch & Bound + Bitmask DP Performance critical, 1-20+ cities

Performance

The optimized implementation demonstrates dramatic improvements through algorithmic optimization:

# 14 cities benchmark results:
1. Optimized:      0.008s  (baseline)
2. Multi-threaded: 59.084s (7,580x slower)
3. Single-threaded: 432.124s (55,444x slower)

Key optimizations:

  • Pre-computed distance matrix (eliminates repeated sqrt calculations)
  • Branch-and-bound pruning (reduces search space exponentially)
  • Bitmask dynamic programming (O(n²2ⁿ) vs O(n!) for ≤20 cities)

The Performance Cliff at 21 Cities

This solver demonstrates a dramatic algorithmic complexity cliff that serves as an educational example of why algorithm selection is critical:

# 20 cities - uses bitmask DP:
Time taken: 0.665 seconds

# 21 cities - falls back to branch-and-bound:
Time taken: 2704.067 seconds (45 minutes!)

What happens at the threshold:

  • ≤20 cities: Uses efficient bitmask dynamic programming (O(n²×2ⁿ))
  • >20 cities: Switches to branch-and-bound with factorial worst-case complexity (O(n!))
  • Performance impact: 21!/20! = 21× more permutations, but poor pruning leads to ~4000× slowdown

This performance cliff exists because:

  1. Bitmask DP becomes memory-prohibitive beyond 2²⁰ states
  2. The fallback branch-and-bound algorithm lacks sufficient pruning for problems this size
  3. The transition point (n=20) creates a computational complexity gap

Challenge for contributors: Improve the solver to handle 21+ cities efficiently while maintaining exact solutions.

Usage

cargo run --release <num_cities> [seed] [threads]

Examples:

cargo run --release 10 42        # 10 cities, seed 42, auto-detect threads
cargo run --release 15 123 8     # 15 cities, seed 123, 8 threads
cargo run --release 21 42        # 21 cities - demonstrates the performance cliff

Recommendations:

  • 1-10 cities: All implementations work well
  • 11-15 cities: Use optimized implementation for best performance
  • 16-20 cities: Only optimized implementation practical
  • 21+ cities: Current implementation becomes impractical - optimization challenge!

Sample Output

=== Traveling Salesman Problem Solver ===
Cities: 13, Seed: 42, Available CPU threads: 16

=== Performance Summary ===
Implementation order: ["Multi", "Optimized", "Single"]

Performance Ranking:
  1. Optimized: 0.004s (distance: 403.93)
  2. Multi-threaded: 4.400s (distance: 403.93, 1,243x slower)
  3. Single-threaded: 32.522s (distance: 403.93, 9,190x slower)

✓ All implementations found the same optimal solution!

Building & Testing

# Build optimized binary
cargo build --release

# Run tests
cargo test

# Run with custom parameters
./target/release/tsp_solver 12 42 4

# Demonstrate the performance cliff
./target/release/tsp_solver 20 42  # Fast (< 1 second)
./target/release/tsp_solver 21 42  # Slow (45+ minutes)

Technical Details

  • Language: Rust (zero external dependencies)
  • Algorithms: Exact solutions only - guaranteed optimal results
  • Threading: Work-stealing parallel permutation generation
  • Memory: Efficient distance matrix caching and memory pooling
  • Verification: All implementations cross-validated for correctness

Complexity Analysis

Cities Brute Force Optimized (Bitmask DP) Branch & Bound Practical Runtime
10 10! ≈ 3.6M 10²×2¹⁰ ≈ 102K Variable milliseconds
15 15! ≈ 1.3T 15²×2¹⁵ ≈ 7.4M Variable seconds
20 20! ≈ 2.4×10¹⁸ 20²×2²⁰ ≈ 419M Variable < 1 second
21 21! ≈ 5.1×10¹⁹ Memory prohibitive Up to 21! 45+ minutes

⚠️ AI Disclosure: This project includes code generated with assistance from Large Language Models (LLMs).

A zero-dependency Traveling Salesman Problem solver in Rust with both single-threaded and multi-threaded implementations.

Available Binaries

  • Windows (x64): tsp_solver-windows-x64.exe
  • macOS (x64 Intel): tsp_solver-macos-x64
  • macOS (ARM64 Apple Silicon): tsp_solver-macos-arm64
  • Linux (x64): tsp_solver-linux-x64
  • Linux (ARM64): tsp_solver-linux-arm64

Usage

./tsp_solver <num_cities> [seed] [threads]
Assets 4
Loading