P-NP Decomposition of the Linear Ordering Problem: Landscape Analysis and Applications

X. Benavides Canta, J. Ceberio, J. A. Lozano, L. Hernando

The Linear Ordering Problem (LOP) is an NP-Hard combinatorial optimization problem that arises in many real-world situations. Due to its complexity, many different meta-heuristic approaches have been developed over the years to efficiently solve the LOP. In this line, recent studies have concluded that decomposing the objective function of the LOP using the Fourier Transform may create a suitable framework for optimization. In fact, one of the components of this decomposition has been shown to belong to the P complexity class.

In this work, we prove that the Fourier Transform can be used for decomposing not only the objective function but also the instance itself. We show that this decomposition may be useful for analyzing the complexity of an LOP instance, and we propose a novel local search-based algorithm called the P-Descent based on the performed analysis. Experimental results show that the proposed method may be more efficient than other classical local search strategies.

Keywords: "Linear Ordering Problem" "Complexity" "Fourier Transform"

Scheduled

Heuristics and Metaheuristics
November 10, 2023  4:00 PM
CC3: Room 1

Matheurística basada en la búsqueda local aplicada a un problema de ruteo de vehículos de recogida y entrega en el contexto de salud en casa.

I. Pemberthy, J. C. Rivera, C. Jussien Guéret, H. Al Hasan

On the Use of Second Order Neighbors to Escape from Local Optima

E. Contreras-Torres, L. Hernando, M. Torralbo, J. A. Lozano