Quadratic Assignment Problem (QAP)

Introduction

The Quadratic Assignment Problem (QAP) is one of the fundamental optimization problems in operations research and has long been challenging to solve, particularly for dynamic, fast-changing scenarios. In this blog post, we demonstrate how we formulated the QAP as a QUBO problem, ran it on the LightSolver platform and benchmarked it against two solvers from the Google OR-Tools suite.

The Challenge: Real-time Assignments

Imagine you are the logistics manager of a bustling e-commerce warehouse, where hundreds of orders flood in every hour and new shipments of goods arrive continuously. Your challenge is to ensure that each item is stored in an optimal location to minimize the time and effort needed for picking and packing. As customer demands fluctuate and new products are introduced, the complexity of assigning storage locations dynamically increases.

This is where the QAP comes into play, helping you determine the best arrangement of products to enhance efficiency, reduce operational costs, and accelerate order fulfillment in real-time.

Considered one of the most challenging NP-hard problems, the QAP has been used in fields like facility layout design, electronic design, and logistics, traditionally. It involves assigning a set of facilities to a set of locations in such a way that the total cost, influenced by both the distance between locations and the interaction between facilities, is minimized. Imagine trying to determine the best positions for machines in a factory or servers in a data center, where the objective is to reduce the total cost of transporting materials or data between them. The QAP captures this real-world problem, seeking an optimal solution among the many possible layouts. Despite its practical importance, solving QAP efficiently is notoriously difficult due to the combinatorial explosion of possible assignments as the number of facilities and locations increases.

This challenge becomes intractable with conventional computing platforms for dynamic use cases such as the above-mentioned e-commerce warehouse optimization, where solutions must be obtained within seconds or minutes to deliver optimal value. Additional dynamic QAP applications include network design in telecommunications (real-time allocation of transmitters to frequencies to adapt to traffic patterns), dynamic hospital layout (assigning rooms and facilities in function of needs and emergencies), path planning and task assignment for robot arms in manufacturing settings, dynamic electronic component placement for PCB assembly, emergency response resource allocation, and traffic flow management in smart cities. Delivering optimized solutions for such fast-paced scenarios demands advanced solving algorithms and highly efficient computing platforms.

Putting QUBO to work

Skip the mathematical part and go directly to the results

Let’s start by putting down the mathematical definition of the QAP:
 
MATHEMATICAL DEFINITION
 

• 𝑛 facilities to be assigned to 𝑛 locations.

 

• $d_{i,j}$ is the distance between location i and location j.

 

• $f_{i,j}$ is the flow between facility i and facility j

 

• A solution is a bijective function σ:{1,…,n}→{1,…,n} which assigns facility i to location σ(i)

 

• For a given solution σ, the objective value of QAP is:
  $\sum _{\mathrm{i},\mathrm{j}}^{}{\mathrm{f}}_{i,j}{d}_{\sigma \left(i\right),\sigma \left(j\right)}$

 
Our goal is to find an assignment σ that minimizes the cost defined above.
 
QUBO FORMULATION
 
Here is how we created the QUBO:
 

• We introduce the binary variables ${\mathrm{x}}_{\mathrm{ij}}$ that represent the assignment of the ith facility to the jth location.

 

• For σ to be bijective we must have each facility assigned to exactly one factory. To achieve this, we add a penalty term if these conditions are violated:
   
  $Penalty\left(x\right)=\lambda \sum _i^{}{\left(\sum _j^{}{x}_{ij}–1\right)}^2+\lambda \sum _j^{}{\left(\sum _i^{}{x}_{ij}–1\right)}^2$

 

• The objective value introduced before can be expressed in terms of the variables $x_{ij}$ as follows:
   
  $\mathrm{Obj}\left(\mathrm{x}\right)=\sum _{i,j,k,l}^{}{\mathrm{f}}_{\mathrm{ij}}{\mathrm{d}}_{\mathrm{kl}}{\mathrm{x}}_{\mathrm{ik}}{\mathrm{x}}_{\mathrm{jl}}$

 

• Finally, the QUBO formulation for a QAP problem is:
   
  $\underset{{\mathrm{\chi }}_{\mathrm{i},\mathrm{j}}\in \left\{0,1\right\}}{min} Obj\left(x\right)+\mathrm{Penalty}\left(x\right)$

Benchmark against Google OR-Tools Solvers

To evaluate the feasibility of our platform for dynamic QAP use cases, we decided to limit the run time for this benchmark to 60 seconds. We chose data sets from the COR@L library, starting with instances of 12 locations and increasing the problem size until the solvers were unable to provide solutions. Our evaluation criterium was the solution quality, expressed by the size of the gap from the best-known objective value, with the smallest gap being the best result. Here is how the LightSolver platform performed against CP-SAT and GSCIP from the Google-OR package 9.9.3963:

LightSolver constantly delivered higher solution quality (smaller gaps from the optimal known solution) than the two Google OR-Tools solvers, regardless of the problem size. Within the set runtime, CP-SAT could not generate solutions for instances with 50+ facilities, nor could GSCIP for problems of 60+ facilities.

Conclusion

Since its initial introduction in the 1950s, the QAP continues to challenge the operations research community. Despite the amount of data available in real time today, many solvers cannot generate solutions for dynamic scenarios due to the explosion of combinatorial possibilities. LightSolver’s platform delivers accurate and ultra-fast solutions that enable organizations to optimize their operations, saving valuable time, resources, and in the case of emergency response resource allocation, even lives.

Would you like to see how LightSolver can tackle YOUR optimization challenge? Contact us at info@lightsolver.com