QAPLIB, open instances

# QAPLIB, open instances ## Goal The quadratic assignment problem: `n` facilities, `n` locations, a flow matrix `A` (flow between facilities) and a distance matrix `B` (distance between locations). Assign each facility `i` to a location `p[i]`, one facility per location, minimising cost(p) = sum over i, j in 0..n-1 of A[i][j] * B[p[i]][p[j]] This is exactly QAPLIB's convention (`min sum_ij a_ij b_p(i)p(j)`, Burkard, Karisch, Rendl); the eval reproduces every best-known value in the table below from QAPLIB's own published `.sln` permutation under this formula (for `tai60a` and `tai80a` the `.sln` file lists the inverse permutation, which is the same problem with `A` and `B` swapped and has the same cost). `solve.py` exposes solve(name: str, flow: list[list[int]], dist: list[list[int]], time_budget: float, seed: int) -> list[int] `flow` is `A`, `dist` is `B` (both `n x n` lists of ints, `n = len(flow)`), `name` is the instance label (use it to pick a strategy, `tai*b` instances are structured and `tai*a` are uniform random). Return `p`: a permutation of `0..n-1`, `p[i]` the location of facility `i`. The instance files live in `instances/<name>.dat` (QAPLIB format: `n`, then `A`, then `B`); the eval parses them and passes the matrices in. They are not mutable and the eval recomputes the cost itself, so nothing the solver reports is trusted. ## Metric metric = mean over the 12 instances of best_known(name) / cost(p) A ratio of 1.0 matches the best-known value; above 1.0 beats it, and the eval lists those instances in `records_beaten`. An invalid permutation (wrong length, repeated location, out of range, non-integer) on any instance is a failed run, as is exceeding the time budget. Environment knobs the eval honours: - `ZT_EVAL_SEED`: only seeds the `seed` handed to your solver. The instance set is fixed. - `ZT_EVAL_PER_INSTANCE_SECONDS`: the `time_budget` per instance (default 8; the full run takes about 100 s). - `ZT_EVAL_INSTANCES`: comma-separated subset of the names below, for quick local runs (`ZT_EVAL_INSTANCES=tai35a,sko49 python eval.py`). ## Records Best-known values from the QAPLIB table (Lehigh mirror, fetched 2026-09-07; "found by" is the method label QAPLIB prints: Ro-TS is Taillard's robust tabu search, ITS is Misevičius' iterated tabu search, SIM-2 is simulated annealing). QAPLIB marks none of these optimal. Instances that have since been solved to optimality are excluded: tai30a and sko42 (Fujii, Ito, Kim, Kojima, Shinano, Toh 2021, arXiv:2101.09629), tai35b and tai40b (Date and Nagi, arXiv:1510.02065) and tho40 (Fujii, Mittelmann, Kojima, Kim, Shinano, ISMP 2024). | instance | n | best-known | found by (QAPLIB) | instance source | optimal? | |---|---|---|---|---|---| | tai35a | 35 | 2 422 002 | Ro-TS | Taillard 1991, uniform random | no | | tai40a | 40 | 3 139 370 | Ro-TS | Taillard 1991, uniform random | no | | tai50a | 50 | 4 938 796 | ITS | Taillard 1991, uniform random | no | | tai60a | 60 | 7 205 962 | TS-2 | Taillard 1991, uniform random | no | | tai80a | 80 | 13 499 184 | ITS | Taillard 1991, uniform random | no | | tai100a | 100 | 21 052 466 | ITS | Taillard 1991, uniform random | no | | sko49 | 49 | 23 386 | Ro-TS | Skorin-Kapov 1990, grid distances | no | | sko56 | 56 | 34 458 | Ro-TS | Skorin-Kapov 1990, grid distances | no | | sko64 | 64 | 48 498 | Ro-TS | Skorin-Kapov 1990, grid distances | no | | wil50 | 50 | 48 816 | SIM-2 | Wilhelm and Ward 1987 | no | | tai50b | 50 | 458 821 517 | Ro-TS | Taillard 1995, structured, asymmetric B | no | | tai60b | 60 | 608 215 054 | Ro-TS | Taillard 1995, structured, asymmetric B | no | The `tai*a` values have stood since Misevičius (2005-2008) and are widely believed to be very close to optimal but not proven; `sko*` and `wil50` values are matched routinely by good metaheuristics; `tai*b` values are reached by tabu and memetic searches in seconds. So 1.0 is the realistic target on every instance, and anything above it is a record candidate that QAPLIB's maintainers would want to hear about. ## Constraints - Standard library only. No numpy, no scipy. The eval rejects other imports. - Respect `time_budget` (seconds, per call). The eval fails a call that runs more than 25 % over. - Deterministic given `seed`: use `random.Random(seed)`. - `flow` and `dist` are copies; mutate them if you like, the eval scores against its own. ## Ideas that are known to matter (check the journal before repeating one) - Pairwise swap (2-exchange) neighbourhood with delta evaluation: the change in cost from swapping facilities `r` and `s` is `O(n)` to compute (Taillard 1991, general formula covers the asymmetric `tai*b` distance matrices). After a swap, the deltas for all other pairs can be updated in `O(1)` each from the stored delta matrix (Taillard 1991), which makes a full neighbourhood scan `O(n^2)` instead of `O(n^3)`. The baseline recomputes deltas from scratch; fixing that alone gives it ten times the iterations. - Robust tabu search (Taillard 1991, "Robust taboo search for the quadratic assignment problem"): best-swap moves with a tabu tenure drawn uniformly from about `[0.9n, 1.1n]`, an aspiration criterion, and a long-term "force a move not tried in 5n^2 iterations" rule. It still matches the `sko*` and `tai*b` records and is the reference point every QAP paper compares against. - Simulated annealing (Connolly 1990; Wilhelm and Ward 1987 is where `wil50` comes from) with a slow geometric cooling and the same delta evaluation. - Iterated local search / iterated tabu search (Stützle 2006; Misevičius 2005): perturb the best solution with `k` random swaps, re-optimise, accept if better or occasionally worse. Misevičius' ITS is what set the current `tai*a` records. - The `tai*a` instances are random and flat (many near-equal local optima): diversification matters more than intensification. The `tai*b` instances are clustered: memetic / genetic recombination that preserves good sub-assignments works well there. - Pure Python is slow; spend your budget on a fast inner loop (bind rows to locals, precompute symmetric cases, avoid per-swap allocations) before tuning the metaheuristic. Write one honest line in `NOTES.md`: the idea, and which instances it helped. Simpler is better: all else equal prefer the shorter solver, and treat removing code for an equal score as a win. Log every experiment, including discards, in your results.tsv.