SiliconSpire QAP Solver (Rust)

A Rust command-line heuristic for the Quadratic Assignment Problem. It combines Grey Wolf Optimization (GWO), a continuous-position-to-permutation decoder, and swap-based Tabu Search.

The bundled cleanroom instance is illustrative. This repository does not demonstrate a deployed semiconductor-layout system, industrial savings, or benchmark performance.

Build and run

cargo build --release
cargo run --release -- --input-file silicon_spire.txt
cargo run --release -- --input-file silicon_spire.txt --seed 42

An instance file starts with a positive integer n, then contains an n × n distance matrix and an n × n flow matrix. Each matrix row must contain exactly n integers.

The parser rejects missing matrix values, malformed rows, and non-whitespace data after the flow matrix. Assignments are checked as permutations of 0..n-1; objective costs that overflow signed 64-bit arithmetic return an error.

The objective for an assignment p is:

sum(i = 0..n-1) sum(j = 0..n-1) flow[i][j] * distance[p[i]][p[j]]

Options

Option	Default	Meaning
--input-file FILE	silicon_spire.txt	QAP instance path
--pack-size N	30	GWO population; at least three candidates are required
--max-iterations N	100	GWO iterations; must be positive
--ts-iterations N	50	Tabu iterations per invocation
--tabu-tenure N	10	Tabu-list length; must be positive
--seed N	generated	Optional unsigned 64-bit seed; the selected seed is printed for repeat runs

For a brief usage summary, run cargo run -- --help.

Checks

cargo fmt --check
cargo test --locked
cargo clippy --all-targets --locked -- -D warnings

Small QAPLIB evaluation

The standard-library Python runner downloads three small instances from QAPLIB and verifies each file's SHA-256 before use. It runs seeds 1–30 with pack size 30, 100 GWO iterations, 50 Tabu iterations and tenure 10:

python3 benchmarks/run_qaplib.py --solver ./target/release/silconspire

Observed with this Rust release build:

Instance	Published optimum	Exact runs	Best	Median	Mean gap
Nug12	578	29/30	578	578	0.046%
Nug14	1,014	18/30	1,014	1,014	0.158%
Tai12a	224,416	30/30	224,416	224,416	0.000%

The per-seed CSV can be saved with --csv results.csv. These are small-instance checks, not evidence of performance on larger or industrial QAPs. The C++ and Rust programs use different random-number implementations, so equal seed values do not make their runs a paired algorithm comparison. Re-run the script for results from a different build or platform.

Scope and limitations

• GWO and Tabu Search are randomized heuristics; they do not guarantee an optimal assignment.
• The best assignment is retained across generations. After Tabu Search changes it, the solver re-encodes its continuous position before the next GWO iteration.
• Pass --seed N to repeat a run with the same build and input. Without it, the solver generates and prints a seed that can be reused. Reproducibility across different dependency versions or platforms is not guaranteed.
• The included small instance is a demonstration, not evidence of performance on larger QAP benchmark suites.
• No industrial data or comparison against exact solvers on larger instances is included.

Attribution

This is an educational optimization prototype. The cleanroom narrative and included data are illustrative. See the source and Git history for implementation details.

Recovery

See RECOVERY.md for rebuilding an offloaded checkout and restoring its dependencies/data.