Dynamic Sparsification for Quadratic Assignment Problems

We propose an iterative algorithm that dynamically generates the quadratic part of the assignment problem and, thus, solves a sparsified linearization of the original problem in every iteration.
This procedure results in a hierarchy of lower bounds and, in addition, provides heuristic primal solutions in every iteration.
This framework was motivated by the task of the French government to design the French keyboard standard, which included solving sparse quadratic assignment problems with over $100$ special characters; a size where many commonly used approaches fail.
The design of a new standard
often involves conflicting opinions of multiple stakeholders in a committee.
Hence, there is no agreement on a single well-defined objective function that can be used for an extensive one-shot optimization.
Instead, the process is highly interactive and demands rapid prototyping, e.g., quick primal solutions, on-the-fly evaluation of manual changes, and prompt assessments of solution quality.
Particularly concerning the latter aspect, our algorithm is able to provide high-quality lower bounds for these problems in several minutes.