TY - JOUR
T1 - Solving unconstrained binary polynomial programs with limited reach
T2 - Application to low autocorrelation binary sequences
AU - Clausen, Jens Vinther
AU - Crama, Yves
AU - Lusby, Richard
AU - Rodríguez-Heck, Elisabeth
AU - Ropke, Stefan
N1 - Publisher Copyright:
© 2024 The Authors
PY - 2024
Y1 - 2024
N2 - Unconstrained Binary Polynomial Programs (UBPs) are a class of optimization problems relevant in a broad array of fields. In this paper, we examine an example from communication engineering, namely low autocorrelation binary sequences and propose a new dynamic programming approach that is particularly effective on UBP instances that have a limited so-called reach, which is a metric that states the maximum difference between any two variable indices across all monomials in the UBP. Based on the reach, the dynamic programming approach decomposes the problem into a number of overlapping stages that can be solved in parallel. On a set of publicly available low autocorrelation binary sequence problems, we demonstrate the superiority of the approach by showing that the method solves to optimality for the first time several previously unsolved instances. In particular, we provide a direct comparison between the proposed method and a modern version of a previously proposed dynamic program for UBPs. We give a detailed analysis of the connection between the two different algorithms and demonstrate that the advantage of the proposed dynamic program is in its ability to implicitly identify the multilinear polynomials that are required in the recursive steps of the two dynamic programs. For perspective, a comparison to several other methods is also provided.
AB - Unconstrained Binary Polynomial Programs (UBPs) are a class of optimization problems relevant in a broad array of fields. In this paper, we examine an example from communication engineering, namely low autocorrelation binary sequences and propose a new dynamic programming approach that is particularly effective on UBP instances that have a limited so-called reach, which is a metric that states the maximum difference between any two variable indices across all monomials in the UBP. Based on the reach, the dynamic programming approach decomposes the problem into a number of overlapping stages that can be solved in parallel. On a set of publicly available low autocorrelation binary sequence problems, we demonstrate the superiority of the approach by showing that the method solves to optimality for the first time several previously unsolved instances. In particular, we provide a direct comparison between the proposed method and a modern version of a previously proposed dynamic program for UBPs. We give a detailed analysis of the connection between the two different algorithms and demonstrate that the advantage of the proposed dynamic program is in its ability to implicitly identify the multilinear polynomials that are required in the recursive steps of the two dynamic programs. For perspective, a comparison to several other methods is also provided.
KW - Dynamic programming
KW - Low autocorrelated binary sequences
KW - Unconstrained binary polynomial program
U2 - 10.1016/j.cor.2024.106586
DO - 10.1016/j.cor.2024.106586
M3 - Journal article
AN - SCOPUS:85186641438
SN - 0305-0548
VL - 165
JO - Computers and Operations Research
JF - Computers and Operations Research
M1 - 106586
ER -