Solving unconstrained binary polynomial programs with limited reach: Application to low autocorrelation binary sequences

Computers & Operations Research, vol. 165, pp. 106586

Abstract

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.

Authors 5

1. Jens Clausen

   Technical University of Denmark

   Affiliation as printed

   Department of Technology Management and Economics, Technical University of Denmark, Anker Engelunds Vej 1 Bygning 101A, 2800 Kgs. Lyngby, Denmark

2. Yves Crama

   University of Liège

   Affiliation as printed

   HEC Liège - Management School, University of Liège, Rue Louvrex 14 (N1), 4000 Liège, Belgium

3. Richard Martin Lusby

   Technical University of Denmark

   Affiliation as printed

   Department of Technology Management and Economics, Technical University of Denmark, Anker Engelunds Vej 1 Bygning 101A, 2800 Kgs. Lyngby, Denmark

4. Elisabeth Rodríguez-Heck Aachen Chair of Operations Research

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, The Chair of Operations Research, Kackertstraße 7, 52072 Aachen, Germany

5. Stefan Røpke corresponding

   Technical University of Denmark

   Affiliation as printed

   Department of Technology Management and Economics, Technical University of Denmark, Anker Engelunds Vej 1 Bygning 101A, 2800 Kgs. Lyngby, Denmark