[en] 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 UBP. 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.
Research center :
HEC Recherche. Supply Chain Management and Business Analytics - ULiège
Disciplines :
Quantitative methods in economics & management Mathematics
Author, co-author :
Clausen, Jens Vinther; Technical University of Denmark > Department of Technology Management and Economics
Crama, Yves ; Université de Liège - ULiège > HEC Liège : UER > UER Opérations ; Université de Liège - ULiège > HEC Liège Research > HEC Liège Research: Business Analytics & Supply Chain Mgmt
Lusby, Richard; Technical University of Denmark > Department of Technology Management and Economics
Rodriguez-Heck, Elisabeth
Ropke, Stefan; Technical University of Denmark > Department of Technology Management and Economics
Language :
English
Title :
Solving unconstrained binary polynomial programs with limited reach: Application to low autocorrelation binary sequences
Adjiman, C., Dallwig, S., Floudas, C., Neumaier, A., A global optimization method, αBB, for general twice-differentiable constrained NLPs-I. Theoretical advances. Comput. Chem. Eng. 22:9 (1998), 1137–1158.
Anstee, R., Hypergraphs with no special cycles. Combinatorica 3:2 (1983), 141–146.
Anthony, M., Boros, E., Crama, Y., Gruber, A., Quadratization of symmetric pseudo-Boolean functions. Discrete Appl. Math. 203 (2016), 1–12.
Anthony, M., Boros, E., Crama, Y., Gruber, A., Quadratic reformulations of nonlinear binary optimization problems. Math. Program. 162:1–2 (2017), 115–144.
Beeri, C., Fagin, R., Maier, D., Yannakakis, M., On the desirability of acyclic database schemes. J. ACM 30:3 (1983), 479–513.
Berge, C., Graphs and Hypergraphs. 1976, North-Holland Publishing Company, Amsterdam.
Bernasconi, J., Low autocorrelation binary sequences: statistical mechanics and configuration space analysis. J. Physique 48:4 (1987), 559–567.
Bodlaender, H.L., A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci. 209:1–2 (1998), 1–45.
Boros, E., Crama, Y., Rodríguez-Heck, E., Compact quadratizations for pseudo-Boolean functions. J. Combin. Optim. 39 (2020), 1–21.
Buchheim, C., Crama, Y., Rodríguez-Heck, E., Berge-acyclic multilinear 0–1 optimization problems. European J. Oper. Res. 273:1 (2019), 102–107.
Buchheim, C., Rinaldi, G., Efficient reduction of polynomial zero-one optimization to the quadratic case. SIAM J. Optim. 18:4 (2007), 1398–1413.
Clausen, J.V., Automatic Dantzig-Wolfe Reformulation of Mixed Integer Linear Programs. (Ph.D. thesis), 2021, The Technical University of Denmark.
Conway, A.R., The design of efficient dynamic programming and transfer matrix enumeration algorithms. J. Phys. A, 50, 2017, 353001.
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., Introduction to Algorithms. third ed., 2009, MIT Press, Cambridge.
Crama, Y., Elloumi, S., Lambert, A., Rodriguez-Heck, E., Quadratization and Convexification in Polynomial Binary Optimization: Technical Report., 2022, HEC Liège - Management School, University of Liège, Belgium URL: https://hdl.handle.net/2268/295296.
Crama, Y., Hammer, P.L., Boolean Functions: Theory, Algorithms, and Applications. 2011, Cambridge University Press, New York, N.Y.
Crama, Y., Hansen, P., Jaumard, B., The basic algorithm for pseudo-boolean programming revisited. Discrete Appl. Math. 29:2–3 (1990), 171–185.
Crama, Y., Rodríguez-Heck, E., A class of valid inequalities for multilinear 0-1 optimization problems. Discrete Optim. 25 (2017), 28–47.
De Simone, C., The cut polytope and the Boolean quadric polytope. Discrete Math. 79:1 (1990), 71–75.
Dearing, P.M., Hammer, P.L., Simeone, B., Boolean and graph theoretic formulations of the simple plant location problem. Transp. Sci. 26:2 (1992), 138–148.
Del Pia, A., Di Gregorio, S., 2022. On the complexity of binary polynomial optimization over acyclic hypergraphs. In: Proceedings of SODA 2022.
Del Pia, A., Khajavirad, A., A polyhedral study of binary polynomial programs. Math. Oper. Res. 42:2 (2016), 389–410.
Del Pia, A., Khajavirad, A., The multilinear polytope for acyclic hypergraphs. SIAM J. Optim. 28:2 (2018), 1049–1076.
Del Pia, A., Khajavirad, A., On decomposability of multilinear sets. Math. Program. 170:2 (2018), 387–415.
Del Pia, A., Khajavirad, A., Sahinidis, N.V., On the impact of running intersection inequalities for globally solving polynomial optimization problems. Math. Program. Comput. 12 (2020), 165–191.
Elloumi, S., Lambert, A., Lazare, A., Solving unconstrained 0-1 polynomial programs through quadratic convex reformulation. J. Global Optim. 80:2 (2021), 231–248.
Fagin, R., Degrees of acyclicity for hypergraphs and relational database schemes. J. ACM 30:3 (1983), 514–550.
Fischer, A., Fischer, F., McCormick, S.T., Matroid optimisation problems with nested non-linear monomials in the objective function. Math. Program. 169:2 (2018), 417–446.
Fix, A., Gruber, A., Boros, E., Zabih, R., A hypergraph-based reduction for higher-order binary Markov random fields. IEEE Trans. Pattern Anal. Mach. Intell. 37:7 (2015), 1387–1395.
Fortet, R., L'algèbre de boole et ses applications en recherche opérationnelle. Cah. Cent. d’Études Rec. Opér. 4 (1959), 5–36.
Freedman, D., Drineas, P., 2005. Energy minimization via graph cuts: settling what is possible. In: IEEE Conference on Computer Vision and Pattern Recognition. Vol. 2, pp. 939–946.
Glover, F., Kochenberger, G., Du, Y., Quantum bridge analytics I: a tutorial on formulating and using QUBO models. 4OR 17:4 (2019), 335–371.
Glover, F., Woolsey, E., Further reduction of zero-one polynomial programming problems to zero-one linear programming problems. Oper. Res. 21:1 (1973), 156–161.
Glover, F., Woolsey, E., Technical note: converting the 0-1 polynomial programming problem to a 0-1 linear program. Oper. Res. 22:1 (1974), 180–182.
Goldengorin, B., Ghosh, D., Sierksma, G., Branch and peg algorithms for the simple plant location problem. Comput. Oper. Res. 30:7 (2003), 967–981.
Goldengorin, B., Krushinsky, D., Complexity evaluation of benchmark instances for the p-median problem. Math. Comput. Modelling 53:9 (2011), 1719–1736.
Hammer, P.L., Plant location - A pseudo-Boolean approach. Israel J. Technol. 6 (1968), 330–332.
Hammer, P.L., Rosenberg, I., Rudeanu, S., Application of discrete linear programming to the minimization of Boolean functions. Rev. Math. Pures Appl. 8 (1963), 459–475 in Russian.
Hammer, P.L., Rosenberg, I., Rudeanu, S., On the determination of the minima of pseudo-Boolean functions. Stud. Cercet. Mat. 14 (1963), 359–364 in Romanian.
Hammer, P.L., Rudeanu, S., Boolean Methods in Operations Research and Related Areas. 1968, Springer-Verlag, Berlin.
Ishikawa, H., Transformation of general binary MRF minimization to the first-order case. IEEE Trans. Pattern Anal. Mach. Intell. 33:6 (2011), 1234–1249.
Khajavirad, A., On the strength of recursive McCormick relaxations for binary polynomial optimization. Oper. Res. Lett. 51 (2023), 146–152.
Kolmogorov, V., Zabih, R., What energy functions can be minimized via graph cuts?. IEEE Trans. Pattern Anal. Mach. Intell. 26:2 (2004), 147–159.
Liers, F., Marinari, E., Pagacz, U., Ricci-Tersenghi, F., Schmitz, V., A non-disordered glassy model with a tunable interaction range. J. Stat. Mech. Theory Exp., 2010(5), 2010, L05003.
Mertens, S., Exhaustive search for low-autocorrelation binary sequences. J. Phys. A: Math. Gen., 29(18), 1996, L473.
MINLPLib, S., A library of mixed-integer and continuous nonlinear programming instances. 2020 http://www.minlplib.org/.
Padberg, M., The Boolean quadric polytope: some characteristics, facets and relatives. Math. Program. 45:1–3 (1989), 139–172.
Papadimitriou, C.H., The NP-completeness of the bandwidth minimization problem. Computing 16:3 (1976), 263–270.
POLIP, C.H., Library for polynomially constrained mixed-integer programming. 2020 http://polip.zib.de/polip.php.
Rosenberg, I.G., Reduction of bivalent maximization to the quadratic case. Cah. Cent. d’Études Rec. Opér. 17 (1975), 71–74.
Verma, A., Lewis, M., Optimal quadratic reformulations of fourth degree pseudo-Boolean functions. Optim. Lett. 14 (2020), 1557–1569.
Watters, L.J., Reduction of integer polynomial programming problems to zero-one linear programming problems. Oper. Res. 15 (1967), 1171–1174.
Zangwill, W.I., Media selection by decision programming. J. Advert. Res. 5 (1965), 30–36.
