EURO 2025 Leeds
Abstract Submission

3093. Leveraging Fourier Analysis for Instance Characterization in Permutation-Based Combinatorial Optimization Problems

Invited abstract in session TA-15: Heuristic Search 1, stream Combinatorial Optimization.

Tuesday, 8:30-10:00
Room: Esther Simpson 1.08

Authors (first author is the speaker)

1. Leticia Hernando
Mathematics, University of the Basque Country UPV/EHU
2. Xabier Benavides
Basque Center for Applied Mathematics
3. Anne Elorza
University of the Basque Country UPV/EHU
4. Maialen Beristain
University of the Basque Country UPV/EHU
5. Josu Ceberio
University of the Basque Country UPV/EHU
6. Jose A. Lozano
University of the Basque Country (UPV/EHU), Basque Center for Applied Mathematics (BCAM)

Abstract

The Fourier transform provides an alternative perspective for addressing permutation-based combinatorial optimization problems (COPs) beyond their conventional instance representation. However, its high computational cost limits practical applications to small problem sizes. To overcome this limitation, this work explores how insights from Fourier coefficients can be leveraged to analyze instance properties without explicitly computing them.
Using the Linear Ordering Problem as a foundation, we establish direct connections between instance characteristics and the properties of their Fourier coefficients. Building on these results, we extend the approach by decomposing instances within a broader class of problems—the Multi-dimensional Quadratic Assignment Problems—relating their structure to problem complexity. Additionally, we highlight a connection between the information embedded in Fourier coefficients and the patterns observed in solution rankings of COPs. In particular, we examine the intersection of the Linear Ordering Problem and the Traveling Salesperson Problem through the lens of solution rankings.
To illustrate the practical implications of these theoretical findings, we generate instances of permutation-based COPs with varying complexity and solution ranking properties. Furthermore, we analyze how different metaheuristics perform across these diverse instances. The ultimate goal is to develop a taxonomy of problem instances based on algorithmic performance.

Keywords

Status: accepted

Back to the list of papers