A General Framework Based on Walsh Decomposition for Combinatorial Optimization Problems

In this paper we pursue the use of the Fourier transform for a general analysis of combinatorial optimization problems. While combinatorial optimization problems are defined by means of different notions like weights in a graph, set of numbers, distance between cities, etc., the Fourier transform allows to put all of them in the same framework, the Fourier coefficients. This permits its comparison looking for similarities and differences. Particularly, the Walsh transform has recently been used over pseudo-boolean functions in order to design new surrogate models in the black-box scenario and to generate new algorithms for the linkage discovery problem, among others, presenting very promising results. In this paper we focus on binary problems and the Walsh transform. After presenting the Walsh decomposition and some main properties, we compute the transform of the Unconstrained Binary Quadratic Problem and several particular cases of this problem such as the Max-Cut Problem and the Number Partitioning Problem. The obtained Walsh coefficients not only reinforce the similarities and differences among the problems which are known in the literature, but given a set of Walsh coefficients we can say whether or not they are produced by any of the problems analyzed. Finally, a geometrical interpretation of the space of Walsh coefficients with maximum order 2 and the subspace of each analyzed problem is presented.
by Spanish Ministry of Science and Innovation through the projects PID2019-104966GB-I00/AEI/10.13039/501100011033, PID2019-104933GBI00/ AEI/10.13039/501100011033, PID2019-106453GA-I00/AEI/10.13039/501100011033 and BCAM Severo Ochoa accreditation SEV-2017-0718; and by the Basque Government through the program BERC 2018-2021 and the projects IT1244-19 and IT-1252-19; and by UPV/EHU through the project GIU20/054. Imanol holds a grant from the Department of Education of the Basque Government (PRE_2020_2_0166).