Solving unconstrained binary polynomial programs with limited reach: Application to low autocorrelation binary sequences
提出一种新的动态规划方法，专门求解具有有限可达范围的无约束二元多项式规划问题，首次在低自相关二元序列问题上求解了多个此前未解实例。
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.