New Knowledge about the Elementary Landscape Decomposition for Solving the Quadratic Assignment Problem

Xabier Benavides, Josu Ceberio, Leticia Hernando, José Antonio Lozano

Introduction

The Quadratic Assignment Problem (QAP) remains one of the most formidable NP-hard challenges in combinatorial optimization. It involves assigning $n$ facilities to $n$ locations to minimize the total cost, defined by the product of flow and distance. To navigate the complex "fitness landscapes" of these problems, researchers have historically relied on Elementary Landscape Decomposition (ELD). ELD partitions the landscape into three orthogonal components ($f^1, f^2, f^3$), providing a cleaner mathematical framework for analysis. However, these components have long been treated as "black boxes," lacking clear interpretability regarding actual facility placement. This paper bridges that gap by decomposing ELD into intuitive sub-functions, explaining why certain heuristics succeed or fail across different problem instances.

Interpretable Sub-functions: The $\chi, \omega, \tau$ Framework

To demystify ELD, the authors introduce a "decomposition of the decomposition." They break the three standard ELD functions into three new sub-functions based on facility-location pairs:

  1. $\chi$ (Both in place): Evaluates pairs where both facilities are in their "correct" locations for a specific term.
  2. $\omega$ (One in place): Evaluates pairs where only one facility is in a "correct" location.
  3. $\tau$ (Neither in place): Evaluates pairs where neither facility is in the "correct" location.

By analyzing the expected value and variance of these sub-functions, the researchers can identify which specific placement dynamics drive each ELD component.

Theoretical Insights: Decoding $f^2$ and $f^3$

The analysis yielded a significant "Aha!" moment regarding the $f^2$ component. Theoretical calculations revealed that $f^2$ is almost entirely driven by the $\chi$ sub-function. This implies that $f^2$ essentially mirrors the core information found in the original objective function.

Expected values of sub-functions for the $f^2$ component, showing the dominance of $f^2_\chi$.

In contrast, $f^3$ is driven primarily by the $\omega$ and $\tau$ sub-functions. It captures "extra" information about potential moves that the standard objective function ignores. This characteristic makes $f^3$ a powerful tool for diversification, allowing algorithms to escape local optima by considering moves that do not immediately appear beneficial under the primary objective.

Experimental Evaluation and the Correlation Tug-of-War

The study validated these insights using 112 benchmark instances from the Drezner and Taixxeyy sets, ranging in size from $n=15$ to $n=175$. The researchers compared a standard Tabu Search (TS) against a Variable Function Search (VFS)—an algorithm specifically designed to use ELD components to guide its search.

The results highlighted a critical "Correlation Tug-of-War." The success of ELD-based algorithms depends on the correlation between $f^2$ and $f^3$. In Drezner instances, these functions are negatively correlated; improving one often degrades the other. Consequently, the extra information provided by $f^3$ acts as noise, and standard TS remains superior. However, in Taixxeyy instances, the lack of negative correlation allows $f^3$ to act as a "ladder," helping the search climb out of local traps in $f^2$.

Simplex plots comparing Tabu Search (TS) and Variable Function Search (VFS) performance on Drezner and Taixxeyy instances.

As shown in the simplex plots, VFS demonstrated a 0.77 probability of being the top performer on Taixxeyy instances, whereas TS maintained dominance on the Drezner set with a 0.55 probability.

Conclusion and Future Directions

This research provides a roadmap for designing more efficient optimization heuristics by making ELD interpretable. Beyond performance insights, the authors noted that certain sub-functions (like $f^3_\omega$) can be calculated in $O(n^3)$ time, offering a path toward "lite" ELD algorithms that bypass the standard $O(n^4)$ complexity.

Future work will focus on developing adaptive algorithms capable of detecting $f^2/f^3$ correlation in real-time to toggle ELD usage dynamically. Additionally, the researchers aim to extend this sub-function decomposition approach to other combinatorial problems, such as the Traveling Salesman Problem (TSP).

Summary updated

Abstract

Previous works have shown that studying the characteristics of the Quadratic Assignment Problem (QAP) is a crucial step in gaining knowledge that can be used to design tailored meta-heuristic algorithms. One way to analyze the characteristics of the QAP is to decompose its objective function into a linear combination of orthogonal sub-functions that can be independently studied. In particular, this work focuses on a decomposition approach that has attracted considerable attention: the Elementary Landscape Decomposition (ELD).The main drawback of the ELD is that it does not allow an understandable characterization of what is being measured by each component of the decomposition. Thus, it turns out difficult to design new efficient meta-heuristic algorithms for the QAP based on the ELD. To address this issue, in this work, we delve deeper into the ELD by means of an additional decomposition of its elementary components. Conducted experiments show that the performed analysis may be used to explain the behaviour of ELD-based methods, providing critical information about their potential applications.
BibTeX
@inproceedings{benavides2023new,
  author = {Xabier Benavides and Josu Ceberio and Leticia Hernando and José Antonio Lozano},
  title = {{New Knowledge about the Elementary Landscape Decomposition for Solving the Quadratic Assignment Problem}},
  booktitle = {GECCO},
  year = {2023},
  doi = {10.1145/3583131.3590369},
}
Figure