Quadratic Assignment Problem

An up-to-date, verified table of best known solutions for QAPLIB, the standard benchmark library for the Quadratic Assignment Problem (QAP) by Burkard, Karisch and Rendl. The official QAPLIB tables were last updated in April 2012. Since then, several instances have been proved optimal and the record for tai100a has been improved three times. This page brings those results together, with a permutation for every value.

This is an unofficial update, not affiliated with the QAPLIB authors or maintainers. The instance data are the official files, unchanged.

136 instances · 108 proven optimal · 28 open · every best known value backed by a permutation recomputed on the official data.

Browse the instances — filter, sort and search all instances; best known values, lower bounds, gaps, and sources.
Check a permutation — paste a permutation or upload an .sln file and get its cost in the browser.
Submit an improved solution — open an issue with the permutation; it is checked and, if better, published with credit.
Download the data — instance files, verified solution files, and a JSON index with stable URLs.

What Changed Since the Official Tables

Loading…

The lower bounds of the open instances are the best ones published, mostly from H.D. Mittelmann’s improved QAPLIB lower bounds (August 2026). A 2026 paper by Sergienko et al. reports another improvement on tai100a; it will be listed once its permutation can be checked.

Conventions

An instance file (.dat) contains n, then the n×n matrix a, then the n×n matrix b. A solution is a permutation p of 1..n, where p(i) is the location of facility i, and its cost is

cost(p) = sum over i, j of  a[i][j] * b[p(i)][p(j)]

This is the QAPLIB convention. A solution file (.sln) has a first line n value, followed by the permutation. The gap of an open instance is (BKS − lower bound) / BKS.

How the Values Were Checked

Instance data: the official QAPLIB archive (qapdata.tar.gz), unchanged.
Every best known value was recomputed from its permutation. Sources: the official solution archive, the papers listed with each instance, and, for esc32a–d, esc32h and esc64a, whose official solution files are missing, new permutations found with robust tabu search.
Optimality is taken from QAPLIB or from the published proof cited with each instance; tai10a and tai10b were proved by enumerating all 10! permutations.

Known errors in other sources

Several official .sln files store the inverse permutation (esc128, kra30a, kra30b, ste36c, tai60a, tai80a, tho30, tho150), and tai40a.sln counts from 0. The files offered here all use the convention above.
The header of the official kra32.sln says 88900; its permutation costs 88700, the optimum.
Mittelmann’s page lists 7505962 as the tai60a upper bound; the best known value is 7205962.
Taillard’s instance files and grey-pattern table still carry older values for tai50a, tai80a, tai150b and tai256c.

How to Cite

Please cite QAPLIB itself, and the paper behind any best known value or proof you use:

@article{burkard1997qaplib,
  author  = {Burkard, Rainer E. and Karisch, Stefan E. and Rendl, Franz},
  title   = {{QAPLIB} -- A Quadratic Assignment Problem Library},
  journal = {Journal of Global Optimization},
  volume  = {10},
  pages   = {391--403},
  year    = {1997},
  doi     = {10.1023/A:1008293323270}
}

Contact

New best known solutions, proofs, lower bounds and corrections are welcome at tommanmaz.math@gmail.com.