QAPLIB Instances
Data checked: …
Every best known value (BKS) below is the cost of a stored permutation, recomputed on the official instance data. Rows highlighted in green are proven optimal; for the others, the lower bound is the best one published and the gap is (BKS − lower bound) / BKS. Instances marked updated differ from the official 2012 tables. Click an instance for its permutation, sources and history.
Loading instance data…
Families
Data Access
Static files with stable URLs, relative to https://tommanmaz.github.io:
| URL | Content |
|---|---|
/data/qap_instances.json |
Index of all instances: name, family, n,
bks, status, lower_bound, gap_pct,
the value and status in the official 2012 tables (qaplib_2012), the
changes since then, record history, and the
references behind each value, proof and bound. |
/downloads/qap/instances/<name>.dat |
Official QAPLIB instance file, unchanged. |
/downloads/qap/solutions/<name>.sln |
Verified best known solution: n value, then the permutation (1-based,
p(i) = location of facility i). |
import json, urllib.request
BASE = "https://tommanmaz.github.io"
data = json.load(urllib.request.urlopen(f"{BASE}/data/qap_instances.json"))
open_instances = [(e["name"], e["bks"], e["lower_bound"]) for e in data["instances"] if e["status"] == "open"]
print(len(open_instances), "open instances")
To check permutations in bulk, load the computation core in Node.js:
require('./js/qap_core.js').
Reporting a New Best Solution
Found a permutation that beats a listed BKS, or a proof of optimality or a better lower bound? Check the permutation with the online checker, then open a submission issue or email tommanmaz.math@gmail.com. It is published here with credit once the permutation has been checked.