P-NP Instance Decomposition Based on the Fourier Transform for Solving the Linear Ordering Problem
Evolutionary Computation · 02.09.2025 · 33 (3) · 395-423
DOI: 10.1162/evco_a_00368 ↗Kurz gefasst
Fachartikel in der Zeitschrift Evolutionary Computation, online erschienen am 02.09.2025. Verfasst von Xabier Benavides und 3 weiteren Autor:innen. Beteiligte Einrichtung: University of the Basque Country UPV/EHU, Donostia-San Sebastian, 20018, Spain. Hauptthemen laut MEDLINE: Algorithms, Fourier Analysis. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 58 Literaturangaben.
Abstract (Originalsprache)
The Fourier transform over finite groups has proved to be a useful tool for analyzing combinatorial optimization problems. However, few heuristic and metaheuristic algorithms have been proposed in the literature that utilize the information provided by this technique to guide the search process. In this work, we attempt to address this research gap by considering the case study of the Linear Ordering Problem (LOP). Based on the Fourier transform, we propose an instance decomposition strategy that divides any LOP instance into the sum of two LOP instances associated with a P and an NP-Hard optimization problem. By linearly aggregating the instances obtained from the decomposition, it is possible to create artificial instances with modified proportions of the P and NP-Hard components. Conducted experiments show that increasing the weight of the P component leads to a less rugged fitness landscape suitable for local search-based optimization. We take advantage of this phenomenon by presenting a new metaheuristic algorithm called P-Descent Search (PDS). The proposed method, first, optimizes a surrogate instance with a high proportion of the P component, and then, gradually increases the weight of the NP-Hard component until the original instance is reached. The multi-start version of PDS shows a promising and predictable performance that appears to be correlated to specific characteristics of the problem, which could open the door to an automatic tuning of its hyperparameters.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Stichwörter der Autor:innen
Autor:innen und Institutionen
- University of the Basque Country UPV/EHU, Donostia-San Sebastian, 20018, Spain.
- Basque Center for Applied Mathematics (BCAM), Bilbao, 48009, Spain xbenavides@bcamath.org.
- University of the Basque Country UPV/EHU, Leioa, 48940, Spain leticia.hernando@ehu.eus.
- University of the Basque Country UPV/EHU, Donostia-San Sebastian, 20018, Spain josu.ceberio@ehu.eus.
- Basque Center for Applied Mathematics (BCAM), Bilbao, 48009, Spain jlozano@bcamath.org.
ORCID-Profile: Xabier Benavides, Leticia Hernando, Josu Ceberio, Jose A Lozano
Zitieren
APA
Benavides, X., Hernando, L., Ceberio, J., & Lozano, J. A. (2025). P-NP Instance Decomposition Based on the Fourier Transform for Solving the Linear Ordering Problem. Evolutionary Computation, 33(3), 395-423. https://doi.org/10.1162/evco_a_00368
Vancouver
Benavides X, Hernando L, Ceberio J, Lozano JA. P-NP Instance Decomposition Based on the Fourier Transform for Solving the Linear Ordering Problem. Evolutionary Computation. 2025;33(3):395-423. doi:10.1162/evco_a_00368
BibTeX
@article{Benavides2025,
author = {Benavides, Xabier and Hernando, Leticia and Ceberio, Josu and Lozano, Jose A},
title = {P-NP Instance Decomposition Based on the Fourier Transform for Solving the Linear Ordering Problem},
journal = {Evolutionary Computation},
year = {2025},
volume = {33},
number = {3},
pages = {395--423},
doi = {10.1162/evco_a_00368}
}
EUVIMED