exact-tsp-solver

• 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
• Standard library only — no external dependencies
• Single binary — go build produces a self-contained executable

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
cd exact-tsp-solver
go build -o exact-tsp-solver .

Binary: ./exact-tsp-solver.

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

Requires Go 1.21 or newer.

./exact-tsp-solver [OPTIONS]

Mode selection

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

Examples

# Exact, small instance
go run . -n 20 -seed 1222 -mode exact

# Exact with a time limit
go run . -n 35 -seed 1222 -mode exact -timeout 60

# Heuristic, larger instance
go run . -n 30 -seed 1222 -mode heuristic

# Auto mode
go run . -n 30 -seed 123

==================================================
TSP SOLVER v1.1.0 (Go)
Points: 20
Seed:   1222
Mode:   EXACT (requested: EXACT)
Timeout: none
==================================================

Coordinates of points:
   Dot  0: (521.84, 998.65)
   ...

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

RESULTS
==================================================
Status:            OPTIMAL (proven)
Number of points:  20
Seed:              1222
Total possible:    so many
Checked paths:     19
Pruned nodes:      10.6k
Execution time:    0.047 seconds
Speed:             407 paths/sec

Greedy + 2-opt:    3443.440958
Held-Karp ref LB:  2995.706383
Best found:        3200.422724
Optimality:        PROVEN by exhaustive B&B
Improvement vs greedy: 243.018234 (7.057%)

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

Results saved to results/tsp_result_n20_seed1222.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. Times are the solver's own reported Execution time (excludes process startup and output). All runs use -seed 1222 and random uniform points in [0, 1000)².

Exact mode

Heuristic mode

Notes

• Exact mode was verified up to n = 35 on this seed. The exact threshold depends heavily on the instance: for the same n but a different seed (123), n = 35 takes minutes instead of seconds. Use -timeout to bound runtime when trying new seeds.
• Heuristic timings vary with instance difficulty. On some seeds, the greedy upper bound is close enough to the optimum that the first threshold is immediately pruned; on others, the search tree explodes.
• 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)
go run . -n 15 -seed 1222 -mode exact
go run . -n 20 -seed 1222 -mode exact
go run . -n 24 -seed 1222 -mode exact

# Larger exact with a time limit — expect OPTIMAL or TIMEOUT
go run . -n 35 -seed 1222 -mode exact -timeout 60

# Heuristic — expect BEST FOUND
go run . -n 30 -seed 1222 -mode heuristic
go run . -n 40 -seed 1222 -mode 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).
• Instance-dependent runtime. The same n on different seeds can differ by orders of magnitude. Always use -timeout in exact mode when trying unknown instances.
• 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 (Rust) — Rust port with identical semantics.
• 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.
• Angular-Radial & Dynamic Gravity — 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