A Python library for the Quadratic Assignment Problem. 29 optimization methods, reproducible benchmarks, and a complete SA multistart pipeline that confirmed optimal solutions across seven instance families.
Every QAPLIB instance (n ≤ 50) mapped by family and optimality status. SA multistart confirmed gap = 0% on 30 instances across seven families.
A unified OptimizationMethod interface across eight solver families. Mix and compose for hybrid strategies.
50 seeds × 2–3M iterations per seed. Gap = (best − BKS) / BKS. Verified by cost-function recomputation.
| Instance | n | BKS | Best Cost | Gap | Seeds | Iter / Seed | Status |
|---|---|---|---|---|---|---|---|
| rou20 | 20 | 725,522 | 725,522 | +0.000% | 50 | 2 M | ✓ OPT |
| tai35a | 35 | 2,422,002 | 2,453,548 | +1.302% | 50 | 3 M | Near-OPT |
We introduce EGO (Equilibrium-Guided Optimization), a unified framework for continuous relaxation of combinatorial assignment problems. By combining Nesterov momentum, entropy regularization, reverse-time saddle escape, and SA multistart on the Birkhoff polytope, we confirm proven-optimal solutions on 30 of 31 tractable QAPLIB instances and achieve +1.302% on tai35a.
Install from PyPI, load any QAPLIB instance by name, and run the full SA multistart pipeline with a single call.
# Install from PyPI pip install qaplibria # Optional visualisation support pip install "qaplibria[viz]"
from qaplibria import solve_qap, load_instance inst = load_instance("nug20") result = solve_qap(inst, method="fast_sa", seed=42) print(f"Cost: {result.cost:,}") print(f"Gap: {result.gap_pct:+.3f}%")
from qaplibria import SAMultistart, load_instance inst = load_instance("rou20") runner = SAMultistart(n_seeds=50, max_iter=2_000_000) result = runner.run(inst) # Reproducible: seed=31 always finds BKS print(f"OPT: {result.gap_pct == 0}") # True
Solve a small QAP instance (n ≤ 10) using the NesterovSolver.
Click to run...