exact-tsp-solver-rs

• Two modes, one binary — exact for correctness, heuristic for scale
• Honest status reporting — optimality is either proven or explicitly not claimed
• Reference lower bound — Held-Karp 1-tree bound with subgradient descent is computed at the root and reported as a quality metric
• Timeout support — exact mode can be limited by wall-clock time
• Progress reporting — periodic output during long exact runs
• Reproducible — deterministic point generation from a single seed
• Structured output — result files are written to the results/ directory, created automatically on the first run
• Single dependency — only rand for RNG
• Single binary — compiles to one executable, dynamic linking by default

Exact mode

1. Upper bound — multi-start greedy nearest-neighbor followed by 2-opt.
2. Reference lower bound at root — Held-Karp 1-tree bound with subgradient descent (informational; not used for pruning).
3. Branch & Bound — depth-first search over partial tours. At every node:
   • Lower bound = partial_distance + MST(unvisited) + 2 × min_edge_to_path.
   • If lower_bound ≥ best_known, prune the subtree.
   • Otherwise expand to the nearest unvisited vertex first.
4. Termination — either the search tree is exhausted (OPTIMAL (proven)) or the timeout fires (TIMEOUT).

The MST-based lower bound is mathematically correct: the length of a minimum spanning tree over a set of vertices never exceeds the length of any Hamiltonian cycle over the same set. Therefore pruning never removes a subtree that could contain a better tour, and the algorithm is exact.

Heuristic mode

1. Same greedy + 2-opt upper bound.
2. Same Held-Karp reference lower bound at the root.
3. Iterative threshold search:
   • Start with threshold T = 0.90 × greedy.
   • Run B&B looking for any tour shorter than T.
   • If found — update best and lower T further.
   • If not found — raise T and try again.
   • Stop when no improvement is found after a raise.
4. Return the best tour found and the gap to the reference bound.

Heuristic mode never claims optimality. The result is a feasible tour whose quality is bounded above by the reported gap.

git clone https://github.com/smartlegionlab/exact-tsp-solver-rs
cd exact-tsp-solver-rs
cargo build --release

Binary: target/release/exact-tsp-solver.

Result files are written to the results/ directory, which is created automatically on the first run.

Requires a recent stable Rust toolchain (edition 2021).

exact-tsp-solver [OPTIONS]

Mode selection

• -m exact — force exact mode. Recommended for n ≤ 20. Combine with -t for safety.
• -m heuristic — force heuristic. No proof of optimality.
• -m auto (default) — exact for n ≤ 20, heuristic for larger n.

Examples

# Exact, small instance
cargo run --release -- -n 18 -seed 123 -m exact

# Exact with a time limit
cargo run --release -- -n 24 -seed 123 -m exact -t 60

# Heuristic, larger instance
cargo run --release -- -n 30 -seed 123 -m heuristic

# Auto mode
cargo run --release -- -n 30 -seed 123

==================================================
TSP SOLVER v1.1.0 (Rust)
Points: 18
Seed:   123
Mode:   EXACT (requested: EXACT)
Timeout: none
==================================================

Coordinates of points:
   Dot  0: (173.25, 152.30)
   ...

1. Multi-start greedy + 2-opt (upper bound)...
   Upper bound: 3308.57
2. Held-Karp root reference lower bound (informational)...
   Reference LB: 2856.35 (took 0ns)
3. Branch & Bound (proves optimality via MST+2-edge bound)...
   Timeout will stop safely if configured.

RESULTS
==================================================
Status:            OPTIMAL (proven)
Number of points:  18
Seed:              123
Total possible:    so many
Checked paths:     0
                   (zero leaves reached: optimality was proven
                    at internal nodes by the lower bound alone)
Pruned nodes:      3.0k
Execution time:    0.004 seconds

Greedy + 2-opt:    3308.573811
Held-Karp ref LB:  2856.353899
Best found:        3308.573811
Optimality:        PROVEN by exhaustive B&B
Improvement vs greedy: 0.000000 (0.000%)
Note:              Best path is the same cycle as greedy.

Greedy way (normalized to 0):  [0, 15, 9, 7, 5, 2, 17, 6, 4, 8, 16, 10, 13, 1, 14, 11, 12, 3]
Best path  (normalized to 0):  [0, 15, 9, 7, 5, 2, 17, 6, 4, 8, 16, 10, 13, 1, 14, 11, 12, 3]

Results saved to results/tsp_result_n18_seed123.txt

Status codes

Checked paths: 0 note

In exact mode the solver may report zero checked leaves. This is not a bug: it means the lower bound at the root or at shallow nodes was already high enough to prune the entire search tree without descending to a complete tour. Optimality was proven by bounds alone.

Measured on a single-threaded x86-64 machine, --release profile (opt-level = 3, lto = true). Times are the solver's own reported Execution time (excludes process startup and output). All runs use -seed 123 and random uniform points in [0, 1000)².

Exact mode

Heuristic mode

Notes

• Exact mode was verified up to n = 24 on this seed. The exact threshold depends on the instance; beyond n = 25, use a timeout or heuristic mode.
• Heuristic timings vary with instance difficulty. The n = 35 run took longer than n = 40 on the same seed because the greedy upper bound was weaker relative to the optimum, forcing more search.
• Gap is measured against the Held-Karp reference bound at the root, which is itself a lower bound. The true gap is never larger than reported.

The solver is deterministic given -n and -seed.

# Small exact instances — expect OPTIMAL (proven)
cargo run --release -- -n 15 -seed 123 -m exact
cargo run --release -- -n 20 -seed 123 -m exact
cargo run --release -- -n 24 -seed 123 -m exact -t 60

# Timeout case — expect TIMEOUT
cargo run --release -- -n 25 -seed 123 -m exact -t 5

# Heuristic — expect BEST FOUND
cargo run --release -- -n 30 -seed 123 -m heuristic

• Target range: n ≤ 25 for exact mode, n ≤ 40 for heuristic mode.
• Not designed for: n > 50. For larger instances, use a dedicated heuristic solver (e.g. LKH or an Or-opt / 3-opt-based implementation).
• Random uniform instances only in the published benchmarks. Structured instances may behave differently.
• No parallelism. Single-threaded by design; adding threads is possible but out of scope for v1.1.0.

• NP Problem Ecosystem — exact and heuristic solvers for the TSP, grounded in the Position-Candidate-Hypothesis (PCH) paradigm.
• exact-tsp-solver (Go) — original implementation; this project is its Rust port.
• smart-pch-tsp-rs — Universal TSP path improver using the PCH paradigm.
• smart-dynamic-gravity-tsp-rs — Rust library using the novel Dynamic Gravity algorithm.
• smart-tsp-oracle — Python implementation of the same Branch & Bound approach.
• smart-tsp-benchmark — professional algorithm testing infrastructure.
• smart-tsp-solver — spatial intelligence algorithms for large-scale TSP routing.
• Position-Candidate-Hypothesis Paradigm — structural-statistical approach to NP-complete problems.

By using this software, you agree to the full disclaimer terms.

Software provided "AS IS" without warranty. You assume all risks.

Full legal disclaimer: See DISCLAIMER.md

License: BSD 3-Clause License