QuadraticAssignmentProblem.jl

Algorithms for solving the quadratic assignment problem (QAP) implemented in Julia.
Author flixpar
Popularity
2 Stars
Updated Last
2 Years Ago
Started In
April 2021

Quadratic Assignment Problem

Algorithms for (approximately) solving the quadratic assignment problem (QAP) implemented in Julia.

Exact algorithms:

  • Quadratic integer programming
  • Linearization

Approximation algorithms:

  • "On the Maximum Quadratic Assignment Problem" by Nagarajan and Sviridenko (NS)
  • "Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm" by Makarychev, Manokaran, and Sviridenko (MMS)

Heuristic algorithms:

  • Fast Approximate QAP
  • Random search
  • LP + LAP rounding