Resumen de P-NP instance decomposition based on the fourier transform for solving the linear ordering problem

Xabier Benavides, Leticia Hernando Rodríguez , Josu Ceberio Uribe , José Antonio Lozano Alonso

• Despite recent developments on the application of the Fourier transform in com- binatorial optimization, few meta-heuristic algorithms have been proposed in the literature that exploit the information provided by this technique. In this work, we address this research gap by considering the case of the Linear Ordering Problem (LOP). Based on the Fourier transform of the problem’s objective function, 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. We take advantage of this decomposition to design a meta-heuristic algo- rithm called P-Descent Search (PDS). The proposed method intelligently adjusts the proportion of the P and NP-Hard components in the decomposition to define a sequence of surrogate instances suitable for optimization. By iteratively solv- ing those instances, PDS is able to find better solutions than classical algorithms operating on the original problem.