Fourier transform-based instance decomposition for Multi-dimensional Quadratic Assignment Problems

X. Benavides Canta, L. Hernando Rodriguez, J. Ceberio Uribe, J. A. Lozano Alonso

The Fourier transform over finite groups has shown to be a promising tool for decomposing the objective function of combinatorial optimization problems (COPs), providing a multi-objectivization framework that may be beneficial for optimization purposes. However, working with this technique is very costly, limiting its practical application to small problem sizes.

To address this issue, the literature has recently proposed an alternative approach. Instead of applying the Fourier transform to break down the objective function, they suggested using it to decompose the problem instance itself. This new, more efficient framework was proposed in the context of the Linear Ordering Problem (LOP), so this work further generalizes this methodology to a wider family of problems called Multi-dimensional Quadratic Assignment Problems (MQAP). By doing so, we aim to prove that the Fourier transform-based instance decomposition can be applied to many of the most well-known COPs in the literature.

Keywords: Fourier transform, Multi-dimensional Quadratic Assignment Problem, Instance decomposition

Heuristics and Metaheuristics I
June 10, 2025  3:30 PM
MR 1

J. Serrano Roig, A. Martinez Gavara, M. Reula Martin

J. Sánchez Díaz, S. Cavero, E. G. Pardo

M. Malagón, H. F. Iñigo, E. Irurozki, J. A. Lozano Alonso, J. Ceberio

M. Robles Rodríguez, S. Cavero, E. G. Pardo