TSP Solver v20250822-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 Runti...

TSP Solver v20250821-74d849a

TSP Solver Release v20250821-74d849a

Commit: 74d849a
Branch: master
Commit Message: run cargo fmt

kushal@kusfedora2024:~/src/rustlang/tsp_rust$ cargo fmt --all -- --check
Diff in /home/kushal/src/rustlang/tsp_rust/src/main.rs:538:
let should_run_all = run_all || num_cities < 15;

 if num_cities >= 15 && !run_all {

•    println!("Note: For {} cities, only running optimized solution.", num_cities);
  

•    println!(
  

•        "Note: For {} cities, only running optimized solution.",
  

•        num_cities
  

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

  }
  kushal@kusfedora2024:/src/rustlang/tsp_rust$ cargo fmt --all
  kushal@kusfedora2024:/src/rustlang/tsp_rust$

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]

TSP Solver v20250820-9e9df11

TSP Solver Release v20250820-9e9df11

Commit: 9e9df11
Branch: master
Commit Message: mark pre release as false

the whole repo is pre release
nothing here is production

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]

TSP Solver v20250820-d14f218

TSP Solver Release v20250820-d14f218

Commit: d14f218
Branch: master
Commit Message: ask claude and gemini for input to fix releases

good response from both

Prompt:
There is something seriously wrong with this github action
error:

Run if [[ "ubuntu-latest" == "windows-latest" ]]; then
if [[ "ubuntu-latest" == "windows-latest" ]]; then
cp target/x86_64-unknown-linux-gnu/release/tsp_solver.exe tsp_solver
else
cp target/x86_64-unknown-linux-gnu/release/tsp_solver tsp_solver
fi

Make binary executable on Unix systems

if [[ "ubuntu-latest" != "windows-latest" ]]; then
chmod +x tsp_solver
fi
shell: /usr/bin/bash --noprofile --norc -e -o pipefail {0}
env:
CARGO_TERM_COLOR: always
BINARY_NAME: tsp_solver
CARGO_HOME: /home/runner/.cargo
CARGO_INCREMENTAL: 0
cp: cannot stat 'target/x86_64-unknown-linux-gnu/release/tsp_solver': No such file or directory
Error: Process completed with exit code 1.
context

name: Release

on:
  push:
    branches:
      - main
      - master
  pull_request:
    branches:
      - main
      - master
  workflow_dispatch:

env:
  CARGO_TERM_COLOR: always
  BINARY_NAME: tsp_solver

permissions:
  contents: write

jobs:
  create-release:
    name: Create Release
    runs-on: ubuntu-latest
    outputs:
      upload_url: ${{ steps.create_release.outputs.upload_url }}
      release_id: ${{ steps.create_release.outputs.id }}
      release_tag: ${{ steps.get_tag.outputs.tag }}
    steps:
      - name: Get tag name
        id: get_tag
        run: |
          # Generate tag based on date and commit SHA
          TAG="v$(date +'%Y%m%d')-${GITHUB_SHA::7}"
          echo "tag=${TAG}" >> $GITHUB_OUTPUT

      - name: Create Release
        id: create_release
        uses: ncipollo/release-action@v1
        with:
          tag: ${{ steps.get_tag.outputs.tag }}
          name: TSP Solver ${{ steps.get_tag.outputs.tag }}
          body: |
            # TSP Solver Release ${{ steps.get_tag.outputs.tag }}

            **Commit:** ${{ github.sha }}
            **Branch:** ${{ github.ref_name }}
            **Commit Message:** ${{ github.event.head_commit.message }}

            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
            ```bash
            ./tsp_solver <num_cities> [seed] [threads]
            ```
          draft: false
          prerelease: true
          allowUpdates: true
          token: ${{ secrets.GITHUB_TOKEN }}

  build-and-upload:
    name: Build - ${{ matrix.name }}
    needs: create-release
    runs-on: ${{ matrix.os }}
    continue-on-error: true
    strategy:
      fail-fast: false
      matrix:
        include:
          # Windows x64
          - os: windows-latest
            name: Windows x64
            target: x86_64-pc-windows-msvc
            artifact_name: tsp_solver.exe
            asset_name: tsp_solver-windows-x64.exe

          # macOS x64 (Intel)
          - os: macos-latest
            name: macOS x64
            target: x86_64-apple-darwin
            artifact_name: tsp_solver
            asset_name: tsp_solver-macos-x64

          # macOS ARM64 (Apple Silicon)
          - os: macos-latest
            name: macOS ARM64
            target: aarch64-apple-darwin
            artifact_name: tsp_solver
            asset_name: tsp_solver-macos-arm64

          # Linux x64
          - os: ubuntu-latest
            name: Linux x64
            target: x86_64-unknown-linux-gnu
            artifact_name: tsp_solver
            asset_name: tsp_solver-linux-x64

          # Linux ARM64
          - os: ubuntu-latest
            name: Linux ARM64
            target: aarch64-unknown-linux-gnu
            artifact_name: tsp_solver
            asset_name: tsp_solver-linux-arm64
            use_cross: true

    steps:
      - name: Checkout code
        uses: actions/checkout@v4

      - name: Setup Rust
        uses: dtolnay/rust-toolchain@stable
        with:
          targets: ${{ matrix.target }}

      - name: Install Cross (for Linux ARM64)
        if: matrix.use_cross == true
        run: |
          # Use prebuilt binary instead of building from source
          curl -L https://github.com/cross-rs/cross/releases/latest/download/cross-x86_64-unknown-linux-gnu.tar.gz | tar xz
          sudo mv cross /usr/local/bin/

      - name: Build (Standard)
        if: matrix.use_cross != true
        run: |
          cargo build --release --target ${{ matrix.target }}

      - name: Build (Cross)
        if: matrix.use_cross == true
        run: |
          cross build --release --target ${{ matrix.target }}

      - name: Prepare binary
        shell: bash
        run: |
          if [[ "${{ matrix.os }}" == "windows-latest" ]]; then
            cp target/${{ matrix.target }}/release/${{ env.BINARY_NAME }}.exe ${{ matrix.artifact_name }}
          else
            cp target/${{ matrix.target }}/release/${{ env.BINARY_NAME }} ${{ matrix.artifact_name }}
          fi

          # Make binary executable on Unix systems
          if [[ "${{ matrix.os }}" != "windows-latest" ]]; then
            chmod +x ${{ matrix.artifact_name }}
          fi

      - name: Upload Release Asset
        uses: ncipollo/release-action@v1
        with:
          tag: ${{ needs.create-release.outputs.release_tag }}
          artifacts: ${{ matrix.artifact_name }}
          artifactContentType: application/octet-stream
          allowUpdates: true
          updateOnlyUnreleased: false
          replacesArtifacts: false
          token: ${{ secrets.GITHUB_TOKEN }}
          omitBodyDuringUpdate: true
          omitNameDuringUpdate: true
          omitPrereleaseDuringUpdate: true

      - name: Upload Artifact (for debugging)
        uses: actions/upload-artifact@v4
        with:
          name: ${{ matrix.asset_name }}
          path: ${{ matrix.artifact_name }}

  test-builds:
    name: Test Build - ${{ matrix.name }}
    needs: build-and-upload
    runs-on: ${{ matrix.os }}
    continue-on-error: true
    strategy:
      fail-fast: false
      matrix:
        include:
          - os: windows-latest
            name: Windows x64
            asset_name: tsp_solver-windows-x64.exe
            binary_name: tsp_solver.exe

          - os: macos-latest
            name: macOS x64
            asset_name: tsp_solver-macos-x64
            binary_name: tsp_solver

          - os: ubuntu-latest
            name: Linux x64
            asset_name: tsp_solver-linux-x64
            binary_name: tsp_solver

    steps:
      - name: Download artifact
        uses: actions/download-artifact@v4
        with:
          name: ${{ matrix.asset_name }}

      - name: Test binary
        shell: bash
        run: |
          # List files for debugging
          ls -la

          # Make executable on Unix
          if [[ "${{ matrix.os }}" != "windows-latest" ]]; then
            chmod +x ${{ matrix.binary_name }}
          fi

          # Test with 5 cities
          ./${{ matrix.binary_name }} 5 42 2

  summary:
    name: Build Summary
    needs: [create-release, build-and-upload, test-builds]
    runs-on: ubuntu-latest
    if: always()
    steps:
      - name: Summary
        run: |
          echo "# Build Summary" >> $GITHUB_STEP_SUMMARY
          echo "" >> $GITHUB_STEP_SUMMARY
          echo "## Release Tag: ${{ needs.create-release.outputs.release_tag }}" >> $GITHUB_STEP_SUMMARY
          echo "" >> $GITHUB_STEP_SUMMARY
          echo "| Platform | Build Result |" >> $GITHUB_STEP_SUMMARY
          echo "|----------|--------------|" >> $GITHUB_STEP_SUMMARY

          # Note: This shows overall job status, not individual matrix results
          echo "| All Platforms | ${{ needs.build-and-upload.result }} |" >> $GITHUB_STEP_SUMMARY
          echo "" >> $GITHUB_STEP_SUMMARY

          if [[ "${{ needs.build-and-upload.result }}" == "success" ]]; then
            echo "✅ All builds completed successfully!" >> $GITHUB_STEP_SUMMARY
          else
            echo "⚠️ Some builds may have failed, but artifacts for successful builds are available." >> $GITHUB_STEP_SUMMARY
          fi
          echo "" >> $GITHUB_STEP_SUMMARY
          echo "Check the release page for available binaries: https://github.com/${{ github.repository }}/releases/tag/${{ needs.create-release.outputs.release_tag }}" >> $GITHUB_STEP_SUMMARY

local build and run looks good.
I even tried it on a second machine. I think the code is fine. It is the yaml that is screwed up.

kushal@kusfedora2024:~$ cd ~/src/rustlang/
kushal@kusfedora2024:~/src/rustlang$ time git clone [email protected]:kusl/tsp_rust.git
Cloning into 'tsp_rust'...
remote: Enumerating objects: 98, done.
remote: Counting objects: 100% (98/98), done.
remote: Compressing objects: 100% (48/48), done.
remote: Total 98 (delta 41), reused 87 (delta 30), pack-reused 0 (from 0)
Receiving objects: 100% (98/98), 36.09 KiB | 3.28 MiB/s, done.
Resolving deltas: 100% (41/41), done.

real	0m0.602s
user	0m0.017s
sys	0m0.013s
kushal@kusfedora2024:~/src/rustlang$ cd ~/src/rustlang/tsp
tsp_rust/   tsp-solver/
kushal@kusfedora2024:~/src/rustlang$ cd ~/src/rustlang/tsp_rust/
kushal@kusfedora2024:~/src/rustlang/tsp_rust$ cd ~/src/rustlang/tsp_rust/; time git remote show origin --verbose
error: unknown option `verbose'
usage: git remote show [<options>] <name>

    -n                    do not query remotes

real	0m0.002s
user	0m0.001s
sys	0m0.001s
kushal@kusfedora2024:~/src/rustlang/tsp_rust$ cd ~/src/rustlang/tsp_rust/; time git remote show origin
* remote origin
  Fetch URL: [email protected]:kusl/tsp_rust.g...

TSP Solver v20250820-b161fd4

TSP Solver Release v20250820-b161fd4

Commit: b161fd4
Branch: master
Commit Message: add cargo fmt fixes

kushal@kusfedora2024:~/src/rustlang/tsp_rust$ cargo fmt --all -- --check
Diff in /home/kushal/src/rustlang/tsp_rust/src/main.rs:1:
+use std::collections::VecDeque;
use std::env;
use std::process;
use std::sync::{Arc, Mutex};
Diff in /home/kushal/src/rustlang/tsp_rust/src/main.rs:4:
use std::thread;
-use std::collections::VecDeque;

#[derive(Debug, Clone)]
struct City {
Diff in /home/kushal/src/rustlang/tsp_rust/src/main.rs:215:

     // Pre-calculate all distances (optimization 1: distance matrix caching)
     for i in 0..n {

•        for j in i+1..n {
  

•        for j in i + 1..n {
             let dist = cities[i].distance_to(&cities[j]);
             distance_matrix[i][j] = dist;
             distance_matrix[j][i] = dist;
  

Diff in /home/kushal/src/rustlang/tsp_rust/src/main.rs:237:
for i in 0..path.len() {
let from = path[i];
let to = path[(i + 1) % path.len()];

•        total += self.distance_matrix[from][to];  // O(1) lookup instead of calculation
  

•        total += self.distance_matrix[from][to]; // O(1) lookup instead of calculation
     }
     total
  

  }
  Diff in /home/kushal/src/rustlang/tsp_rust/src/main.rs:264:
  let new_dist = if l == 0 {
  0.0
  } else {

•                current_dist + self.distance_matrix[path[l-1]][path[l]]
  

•                current_dist + self.distance_matrix[path[l - 1]][path[l]]
             };
  
             self.permute_with_bound(path, l + 1, r, new_dist);
  

Diff in /home/kushal/src/rustlang/tsp_rust/src/main.rs:311:

     for mask in 1..(1 << n) {
         for u in 0..n {

•            if (mask & (1 << u)) == 0 { continue; }
  

•            if (mask & (1 << u)) == 0 {
  

•                continue;
  

•            }
  
             for v in 0..n {
  

•                if u == v || (mask & (1 << v)) != 0 { continue; }
  

•                if u == v || (mask & (1 << v)) != 0 {
  

•                    continue;
  

•                }
  
                 let new_mask = mask | (1 << v);
                 let new_dist = dp[u][mask] + self.distance_matrix[u][v];
  

Diff in /home/kushal/src/rustlang/tsp_rust/src/main.rs:344:
self.reconstruct_path(parent, final_mask, last_city);
}

• fn reconstruct_path(&mut self, parent: Vec<Vec<Option>>, mut mask: usize, mut current: usize) {

• fn reconstruct_path(

•    &mut self,
  

•    parent: Vec<Vec<Option<usize>>>,
  

•    mut mask: usize,
  

•    mut current: usize,
  

• ) {
  let mut path = Vec::new();

  while let Some(prev) = parent[current][mask] {
  

Diff in /home/kushal/src/rustlang/tsp_rust/src/main.rs:553:
order.swap(i, j);
}

• let mut results = vec![(String::new(), f64::INFINITY, std::time::Duration::ZERO, Vec::new()); 3];

• let mut results = vec![

•    (
  

•        String::new(),
  

•        f64::INFINITY,
  

•        std::time::Duration::ZERO,
  

•        Vec::new()
  

•    );
  

•    3
  

• ];

  for &implementation in &order {
  match implementation {
  Diff in /home/kushal/src/rustlang/tsp_rust/src/main.rs:579:
  println!("Time taken: {:.3} seconds", elapsed_single.as_secs_f64());
  println!();

•            results[0] = ("Single-threaded".to_string(), solver_single.best_distance, elapsed_single, solver_single.best_path);
  

•        },
  

•            results[0] = (
  

•                "Single-threaded".to_string(),
  

•                solver_single.best_distance,
  

•                elapsed_single,
  

•                solver_single.best_path,
  

•            );
  

•        }
         1 => {
             // Multithreaded implementation (only if we have enough cities)
             if num_cities >= 4 {
  

Diff in /home/kushal/src/rustlang/tsp_rust/src/main.rs:604:
println!("Time taken: {:.3} seconds", elapsed_parallel.as_secs_f64());
println!();

•                results[1] = ("Multi-threaded".to_string(), solver_parallel.best_distance, elapsed_parallel, solver_parallel.best_path);
  

•                results[1] = (
  

•                    "Multi-threaded".to_string(),
  

•                    solver_parallel.best_distance,
  

•                    elapsed_parallel,
  

•                    solver_parallel.best_path,
  

•                );
             } else {
                 println!("=== Multi-threaded Solution (Skipped for < 4 cities) ===");
                 println!();
  

Diff in /home/kushal/src/rustlang/tsp_rust/src/main.rs:611:

•                results[1] = ("Multi-threaded (Skipped)".to_string(), f64::INFINITY, std::time::Duration::ZERO, Vec::new());
  

•                results[1] = (
  

•                    "Multi-threaded (Skipped)".to_string(),
  

•                    f64::INFINITY,
  

•                    std::time::Duration::ZERO,
  

•                    Vec::new(),
  

•                );
             }
  

•        },
  

•        }
         2 => {
             // Optimized implementation
  

•            println!("=== Optimized Solution (Distance Matrix + Branch & Bound + Bitmask DP) ===");
  

•            println!(
  

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

•            );
             let mut solver_optimized = OptimizedTSPSolver::new(cities.clone());
  
             let start_time = std::time::Instant::now();
  

Diff in /home/kushal/src/rustlang/tsp_rust/src/main.rs:633:
println!("Time taken: {:.3} seconds", elapsed_optimized.as_secs_f64());
println!();

•            results[2] = ("Optimized".to_string(), solver_optimized.best_distance, elapsed_optimized, solver_optimized.best_path);
  

•        },
  

•            results[2] = (
  

•                "Optimized".to_string(),
  

•                solver_optimized.best_distance,
  

•                elapsed_optimized,
  

•                solver_optimized.best_path,
  

•            );
  

•        }
         _ => unreachable!(),
     }
  

  }
  Diff in /home/kushal/src/rustlang/tsp_rust/src/main.rs:641:

  // Summary comparison
  println!("=== Performance Summary ===");

• println!("Implementation order: {:?}", order.iter().map(|&i| match i {

•    0 => "Single",
  

•    1 => "Multi",
  

•    2 => "Optimized",
  

•    _ => "Unknown"
  

• }).collect::<Vec<_>>());

• println!(

•    "Implementation order: {:?}",
  

•    order
  

•        .iter()
  

•        .map(|&i| match i {
  

•            0 => "Single",
  

•            1 => "Multi",
  

•            2 => "Optimized",
  

•            _ => "Unknown",
  

•        })
  

•        .collect::<Vec<_>>()
  

• );
  println!();

  // Find best distance across all implementations
  Diff in /home/kushal/src/rustlang/tsp_rust/src/main.rs:653:

• let best_distance = results.iter()

• let best_distance = results

•    .iter()
     .filter(|(_, dist, _, _)| *dist != f64::INFINITY)
     .map(|(_, dist, _, _)| *dist)
     .fold(f64::INFINITY, f64::min);
  

Diff in /home/kushal/src/rustlang/tsp_rust/src/main.rs:672:
println!("Performance Ranking:");
for (rank, (name, distance, time, _)) in perf_results.iter().enumerate() {
if *distance != f64::INFINITY {

•        let speedup = if rank == 0 { 1.0 } else {
  

•        let speedup = if rank == 0 {
  

•            1.0
  

•        } else {
             time.as_secs_f64() / perf_results[0].2.as_secs_f64()
         };
  

•        println!("  {}. {}: {:.3}s (distance: {:.2}, {}x slower)",
  

•                 rank + 1, name, time.as_secs_f64(), distance,
  

•                 if rank == 0 { "baseline".to_string() } else { format!("{:.2}", speedup) });
  

•        println!(
  

•            "  {}. {}: {:.3}s (distance: {:.2}, {}x slower)",
  

•            rank + 1,
  

•            name,
  

•            time.as_secs_f64(),
  

•            distance,
  

•            if rank == 0 {
  

•                "baseline".to_string()
  

•            } else {
  

•                format!("{:.2}", speedup)
  

•            }
  

•        );
     } else {
         println!("  {}. {}: skipped", rank + 1, name);
     }
  

Diff in /home/kushal/src/rustlang/tsp_rust/src/main.rs:684:
}

 // Verify all implementations found the same optimal solution

• let valid_results: Vec<_> = results.iter()

• let valid_results: Vec<_> = results

•    .iter()
     .filter(|(_, dist, _, _)| *dist != f64::INFINITY)
     .collect();
  

Diff in /home/kushal/src/rustlang/tsp_rust/src/main.rs:691:
if valid_results.len() > 1 {

•    let all_same = valid_results.iter()
  

•    let all_same = valid_results
  

•        .iter()
         .all(|(_, dist, _, _)| (dist - best_distance).abs() < 0.001);
  
     if all_same {
  

kushal@kusfedora2024:/src/rustlang/tsp_rust$ cargo fmt --all
kushal@kusfedora2024:/src/rustlang/tsp_rust$ cargo fmt --all
kushal@kusfedora2024:~/src/rustlang/tsp_rust$

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]

TSP Solver v20250820-88866b0

TSP Solver Release v20250820-88866b0

Commit: 88866b0
Branch: master
Commit Message: ask claude what this method is for

what is this method for?
is it used?
is it for the future?

    fn calculate_total_distance(&self, path: &[usize]) -> f64 {
        let mut total = 0.0;
        for i in 0..path.len() {
            let from = path[i];
            let to = path[(i + 1) % path.len()];
            total += self.distance_matrix[from][to];  // O(1) lookup instead of calculation
        }
        total
    }

kushal@kusfedora2024:~/src/rustlang/tsp_rust$ time cargo build --release
   Compiling tsp_solver v0.1.0 (/home/kushal/src/rustlang/tsp_rust)
warning: method `calculate_total_distance` is never used
   --> src/main.rs:234:8
    |
211 | impl OptimizedTSPSolver {
    | ----------------------- method in this implementation
...
234 |     fn calculate_total_distance(&self, path: &[usize]) -> f64 {
    |        ^^^^^^^^^^^^^^^^^^^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: `tsp_solver` (bin "tsp_solver") generated 1 warning
    Finished `release` profile [optimized] target(s) in 0.47s

real	0m0.506s
user	0m0.750s
sys	0m0.120s
kushal@kusfedora2024:~/src/rustlang/tsp_rust$

Looking at the code, this calculate_total_distance method in OptimizedTSPSolver is currently unused - as the compiler warning correctly indicates.

What it's for:

This method calculates the total distance for a complete tour by:

1. Taking a path (sequence of city indices)
2. Summing up distances between consecutive cities in the path
3. Including the return trip from the last city back to the first city (the % path.len() handles this wraparound)

Key optimization:

It uses the pre-computed distance matrix (self.distance_matrix[from][to]) for O(1) distance lookups instead of recalculating distances with sqrt() operations.

Why it's unused:

The optimized solver uses different approaches that don't need this method:

1. For bitmask DP (≤20 cities): It builds solutions incrementally using the distance matrix directly
2. For branch-and-bound (>20 cities): The permute_with_bound method calculates distances incrementally as it explores the search tree, rather than calculating complete tour distances

Should you remove it?

You have a few options:

1. Remove it - since it's genuinely unused
2. Keep it - it's a useful utility method that could be handy for:
   • Debugging (verify a known path's distance)
   • Future features (like local search improvements)
   • Testing (validate that different algorithms produce the same distance)

I'd suggest keeping it and adding #[allow(dead_code)] above it:

#[allow(dead_code)]
fn calculate_total_distance(&self, path: &[usize]) -> f64 {
    // ... existing code
}

It's a clean, optimized utility method that follows the single responsibility principle and could be useful for future enhancements or debugging.

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]

TSP Solver v20250820-1299936

TSP Solver Release v20250820-1299936

Commit: 1299936
Branch: master
Commit Message: ignore clippy

based on claude recommendations

kushal@kusfedora2024:~/src/rustlang/tsp_rust$ cargo clippy -- -D warnings
Checking tsp_solver v0.1.0 (/home/kushal/src/rustlang/tsp_rust)
error: the loop variable i is used to index dp
--> src/main.rs:339:18
|
339 | for i in 1..n {
| ^^^^
|
= help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#needless_range_loop
= note: -D clippy::needless-range-loop implied by -D warnings
= help: to override -D warnings add #[allow(clippy::needless_range_loop)]
help: consider using an iterator and enumerate()
|
339 - for i in 1..n {
339 + for (i, ) in dp.iter().enumerate().take(n).skip(1) {
|

error: could not compile tsp_solver (bin "tsp_solver") due to 1 previous error
kushal@kusfedora2024:~/src/rustlang/tsp_rust$

use std::collections::VecDeque;
use std::env;
use std::process;
use std::sync::{Arc, Mutex};
use std::thread;

#[derive(Debug, Clone)]
struct City {
id: usize,
x: f64,
y: f64,
}

impl City {
fn distance_to(&self, other: &City) -> f64 {
let dx = self.x - other.x;
let dy = self.y - other.y;
(dx * dx + dy * dy).sqrt()
}
}

struct TSPSolver {
cities: Vec,
best_path: Vec,
best_distance: f64,
}

impl TSPSolver {
fn new(cities: Vec) -> Self {
let initial_path: Vec = (0..cities.len()).collect();
TSPSolver {
cities,
best_path: initial_path,
best_distance: f64::INFINITY,
}
}

fn calculate_total_distance(&self, path: &[usize]) -> f64 {
    let mut total = 0.0;
    for i in 0..path.len() {
        let from = &self.cities[path[i]];
        let to = &self.cities[path[(i + 1) % path.len()]];
        total += from.distance_to(to);
    }
    total
}

#[allow(dead_code)]
fn permute(&mut self, path: &mut Vec<usize>, l: usize, r: usize) {
    if l == r {
        let distance = self.calculate_total_distance(path);
        if distance < self.best_distance {
            self.best_distance = distance;
            self.best_path = path.clone();
        }
    } else {
        for i in l..=r {
            path.swap(l, i);
            self.permute(path, l + 1, r);
            path.swap(l, i);
        }
    }
}

#[allow(dead_code)]
fn solve(&mut self) {
    let n = self.cities.len();
    if n <= 1 {
        return;
    }

    let path: Vec<usize> = (0..n).collect();

    // Keep first city fixed to avoid duplicate rotations
    if n > 2 {
        self.permute(&mut path[1..].to_vec(), 0, n - 2);

        // Reconstruct full path with fixed first city
        let mut full_path = vec![0];
        full_path.extend_from_slice(&self.best_path[..n - 1]);
        self.best_path = full_path;
    } else {
        self.best_distance = self.calculate_total_distance(&path);
    }
}

fn solve_all_permutations(&mut self) {
    let n = self.cities.len();
    if n <= 1 {
        return;
    }

    let mut path: Vec<usize> = (1..n).collect();

    // Generate all permutations of cities 1…n (keeping city 0 fixed)
    self.check_all_permutations(&mut path, 0);

    // Add city 0 at the beginning
    self.best_path.insert(0, 0);
}

fn check_all_permutations(&mut self, path: &mut Vec<usize>, start: usize) {
    if start == path.len() {
        let mut full_path = vec![0];
        full_path.extend_from_slice(path);
        let distance = self.calculate_total_distance(&full_path);
        if distance < self.best_distance {
            self.best_distance = distance;
            self.best_path = path.clone();
        }
        return;
    }

    for i in start..path.len() {
        path.swap(start, i);
        self.check_all_permutations(path, start + 1);
        path.swap(start, i);
    }
}

fn solve_parallel(&mut self, num_threads: usize) {
    let n = self.cities.len();
    if n <= 1 {
        return;
    }

    if n <= 4 {
        // For very small problems, just use single-threaded
        self.solve_all_permutations();
        return;
    }

    // We'll fix city 0 at position 0, then distribute the work
    // by having each thread handle different starting cities at position 1
    let cities_to_permute: Vec<usize> = (1..n).collect();

    // Shared state for best solution
    let best_distance = Arc::new(Mutex::new(f64::INFINITY));
    let best_path = Arc::new(Mutex::new(Vec::new()));
    let cities = Arc::new(self.cities.clone());

    // Create threads
    let mut handles = Vec::new();
    let chunk_size = cities_to_permute.len().div_ceil(num_threads);

    for chunk in cities_to_permute.chunks(chunk_size) {
        let chunk = chunk.to_vec();
        let all_cities = cities_to_permute.clone();
        let best_distance = Arc::clone(&best_distance);
        let best_path = Arc::clone(&best_path);
        let cities = Arc::clone(&cities);

        let handle = thread::spawn(move || {
            let mut local_best_distance = f64::INFINITY;
            let mut local_best_path = Vec::new();

            // For each starting city in our chunk
            for &start_city in &chunk {
                // Create a path starting with 0 and this city
                let mut path = vec![0, start_city];

                // Add remaining cities
                let mut remaining: Vec<usize> = all_cities
                    .iter()
                    .filter(|&&c| c != start_city)
                    .cloned()
                    .collect();

                // Generate all permutations with this fixed start
                permute_and_check(
                    &cities,
                    &mut path,
                    &mut remaining,
                    0,
                    &mut local_best_distance,
                    &mut local_best_path,
                );
            }

            // Update global best if we found something better
            let mut global_best = best_distance.lock().unwrap();
            if local_best_distance < *global_best {
                *global_best = local_best_distance;
                let mut global_path = best_path.lock().unwrap();
                *global_path = local_best_path;
            }
        });

        handles.push(handle);
    }

    // Wait for all threads to complete
    for handle in handles {
        handle.join().unwrap();
    }

    // Update solver's best solution
    self.best_distance = *best_distance.lock().unwrap();
    self.best_path = best_path.lock().unwrap().clone();
}

}

// New optimized solver with distance matrix and branch-and-bound
struct OptimizedTSPSolver {
cities: Vec,
distance_matrix: Vec<Vec>,
best_path: Vec,
best_distance: f64,
}

impl OptimizedTSPSolver {
fn new(cities: Vec) -> Self {
let n = cities.len();
let mut distance_matrix = vec![vec![0.0; n]; n];

    // Pre-calculate all distances (optimization 1: distance matrix caching)
    for i in 0..n {
        for j in i + 1..n {
            let dist = cities[i].distance_to(&cities[j]);
            distance_matrix[i][j] = dist;
            distance_matrix[j][i] = dist;
        }
    }

    let initial_path: Vec<usize> = (0..cities.len()).collect();
    OptimizedTSPSolver {
        cities,
        distance_matrix,
        best_path: initial_path,
        best_distance: f64::INFINITY,
    }
}

#[allow(dead_code)]
fn calculate_total_distance(&self, path: &[usize]) -> f64 {
    let mut total = 0.0;
    for i in 0..path.len() {
        let from = path[i];
        let to = path[(i + 1) % path.len()];
        total += self.distance_matrix[from][to]; // O(1) lookup instead of calculation
    }
    total
}

// Optimization 2: Branch and bound with early termination
fn permute_with_bound(&mut self, path: &mut Vec<usize>, l: usize, r: usize, current_dist: f64) {
    // Early termination if partial distance already exceeds best
    if current_dist >= self.best_distance {
        return;
    }

    if l == r {
        // Complete the cycle by adding distance back to start
        let total_distance = current_dist + self.distance_matrix[path[r]][path[0]];
        if total_distance < self.best_distance {
            self.best_distance = total_distance;
            self.best_path = path.clone();
        }
    } else {
        for i in l..=r {
            path.swap(l, i);

            // Calculate incremental distance for branch and bound
            let new_dist = if l == 0 {
                0.0
            } else {
                current_dist + self.distance_matrix[path[l - 1]][path[l]]
            };

            self.permute_with_bound(path, l + 1, r, new_dist);
            path.swap(l, i);
        }
    }
}

fn solve_optimized(&mut self) {
    let n = self.cities.len();
    if n <= 1 {
        return;
    }

    if n <= 20 {
        // Use dynamic programming with bitmask for small problems (optimization 3)
        self.solve_with_bitmask();
    } else {
        // Use branch and bound for larger problems
        let mut path: Vec<usize> =...

TSP Solver v20250819-c3f141b

TSP Solver Release v20250819-c3f141b

Commit: c3f141b
Branch: master
Commit Message: update all actions

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]

TSP Solver v20250819-6cfd729

TSP Solver Release v20250819-6cfd729

Commit: 6cfd729
Branch: master
Commit Message: update dependencies

actions/upload-artifact
and
actions/download-artifact

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]

TSP Solver v20250819-1b9b670

TSP Solver Release v20250819-1b9b670

Commit: 1b9b670
Branch: master
Commit Message: remove prereleae tag

the whole repo is a pre release
I mean the whole thing is experimental
there will never be a "production" release on this repository
it is for educational purpoises only

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]