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