Open Journal of Mathematical Optimization

Short paper - The Binary Linearization Complexity of Pseudo-Boolean Functions
Matthias Walter1
1 Department of Applied Mathematics, University of Twente, The Netherlands
Open Journal of Mathematical Optimization, Volume 5 (2024), article no. 6, 12 p.

We consider the problem of linearizing a pseudo-Boolean function f:{0,1} n →ℝ by means of k Boolean functions. Such a linearization yields an integer linear programming formulation with only k auxiliary variables. This motivates the definition of the linearization complexity of f as the minimum such k. Our theoretical contributions are the proof that random polynomials almost surely have a high linearization complexity and characterizations of its value in case we do or do not restrict the set of admissible Boolean functions. The practical relevance is shown by devising and evaluating integer linear programming models of two such linearizations for the low auto-correlation binary sequences problem. Still, many problems around this new concept remain open.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/ojmo.34
Keywords: Pseudo-Boolean optimization, multilinear optimization
Matthias Walter 1

1 Department of Applied Mathematics, University of Twente, The Netherlands
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{OJMO_2024__5__A6_0,
     author = {Matthias Walter},
     title = {Short paper - {The} {Binary} {Linearization} {Complexity} of {Pseudo-Boolean} {Functions}},
     journal = {Open Journal of Mathematical Optimization},
     eid = {6},
     pages = {1--12},
     publisher = {Universit\'e de Montpellier},
     volume = {5},
     year = {2024},
     doi = {10.5802/ojmo.34},
     language = {en},
     url = {https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.34/}
}
TY  - JOUR
AU  - Matthias Walter
TI  - Short paper - The Binary Linearization Complexity of Pseudo-Boolean Functions
JO  - Open Journal of Mathematical Optimization
PY  - 2024
SP  - 1
EP  - 12
VL  - 5
PB  - Université de Montpellier
UR  - https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.34/
DO  - 10.5802/ojmo.34
LA  - en
ID  - OJMO_2024__5__A6_0
ER  - 
%0 Journal Article
%A Matthias Walter
%T Short paper - The Binary Linearization Complexity of Pseudo-Boolean Functions
%J Open Journal of Mathematical Optimization
%D 2024
%P 1-12
%V 5
%I Université de Montpellier
%U https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.34/
%R 10.5802/ojmo.34
%G en
%F OJMO_2024__5__A6_0
Matthias Walter. Short paper - The Binary Linearization Complexity of Pseudo-Boolean Functions. Open Journal of Mathematical Optimization, Volume 5 (2024), article  no. 6, 12 p. doi : 10.5802/ojmo.34. https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.34/

[1] Warren P. Adams; Hanif D. Sherali A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems, Manage. Sci., Volume 32 (1986) no. 10, pp. 1274-1290 | DOI | Zbl

[2] Warren P. Adams; Hanif D. Sherali Linearization Strategies for a Class of Zero-One Mixed Integer Programming Problems, Oper. Res., Volume 38 (1990) no. 2, pp. 217-226 | DOI | Zbl

[3] Warren P. Adams; Hanif D. Sherali Mixed-integer bilinear programming problems, Math. Program., Volume 59 (1993) no. 1, pp. 279-305 | DOI | Zbl

[4] Martin Anthony; Endre Boros; Yves Crama; Aritanan Gruber Quadratic reformulations of nonlinear binary optimization problems, Math. Program., Volume 162 (2017) no. 1, pp. 115-144 | DOI | Zbl

[5] Jakob Bernasconi Low autocorrelation binary sequences: statistical mechanics and configuration space analysis, J. Phys., Volume 141 (1987) no. 48, pp. 559-567 | DOI

[6] Alain Billionnet; Sourour Elloumi Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem, Math. Program. Comput., Volume 109 (2007) no. 1, pp. 55-68 | DOI | Zbl

[7] Suresh Bolusani; Mathieu Besançon; Ksenia Bestuzheva; Antonia Chmiela; João Dionísio; Tim Donkiewicz; Jasper van Doornmalen; Leon Eifler; Mohammed Ghannam; Ambros Gleixner et al. The SCIP Optimization Suite 9.0 (2024) | arXiv

[8] Endre Boros; Peter L. Hammer Pseudo-Boolean optimization, Discrete Appl. Math., Volume 123 (2002) no. 1, pp. 155-225 | DOI | Zbl

[9] Christoph Buchheim; Yves Crama; Elisabeth Rodríguez-Heck Berge-acyclic multilinear 0–1 optimization problems, Eur. J. Oper. Res., Volume 273 (2019) no. 1, pp. 102-107 | DOI | Zbl

[10] Jens Vinther Clausen; Yves Crama; Richard Lusby; Elisabeth Rodríguez-Heck; Stefan Røpke Solving unconstrained binary polynomial programs with limited reach: Application to low autocorrelation binary sequences, Comput. Oper. Res., Volume 165 (2024), 106586 | DOI | Zbl

[11] Yves Crama; Elisabeth Rodríguez-Heck A class of valid inequalities for multilinear 0–1 optimization problems, Discrete Optim., Volume 25 (2017), pp. 28-47 | DOI | Zbl

[12] Alberto Del Pia; Silvia Di Gregorio Chvátal Rank in Binary Polynomial Optimization, INFORMS J. Optim., Volume 3 (2021) no. 4, pp. 315-443 | DOI

[13] Alberto Del Pia; Aida Khajavirad A Polyhedral Study of Binary Polynomial Programs, Math. Oper. Res., Volume 42 (2017) no. 2, pp. 389-410 | DOI | Zbl

[14] Alberto Del Pia; Aida Khajavirad The Multilinear Polytope for Acyclic Hypergraphs, SIAM J. Optim., Volume 28 (2018) no. 2, pp. 1049-1076 | DOI | Zbl

[15] Alberto Del Pia; Aida Khajavirad On decomposability of Multilinear sets, Math. Program., Volume 170 (2018) no. 2, pp. 387-415 | DOI | Zbl

[16] Alberto Del Pia; Aida Khajavirad The Running Intersection Relaxation of the Multilinear Polytope, Math. Oper. Res., Volume 46 (2021) no. 3, pp. 1008-1037 | DOI | Zbl

[17] Alberto Del Pia; Matthias Walter Simple Odd β-Cycle Inequalities for Binary Polynomial Optimization, Integer Programming and Combinatorial Optimization (Karen Aardal; Laura Sanità, eds.), Springer (2022), pp. 181-194 | DOI | Zbl

[18] Sourour Elloumi; Amélie Lambert; Arnaud Lazare Solving unconstrained 0-1 polynomial programs through quadratic convex reformulation, J. Glob. Optim., Volume 80 (2021) no. 2, pp. 231-248 | DOI | Zbl

[19] Robert Fortet Applications de l’algebre de Boole en recherche opérationelle, Rev. Franc. Rech. Operat., Volume 4 (1960) no. 14, pp. 17-26

[20] Robert Fortet L’algebre de Boole et ses applications en recherche operationnelle, Trab. Estad., Volume 4 (1960), pp. 17-26 | DOI

[21] Fabio Furini; Emiliano Traversi Extended linear formulation for binary quadratic problems, Optimization Online (2013) (https://optimization-online.org/?p=12481)

[22] Fred Glover Improved Linear Integer Programming Formulations of Nonlinear Integer Problems, Manage. Sci., Volume 22 (1975) no. 4, pp. 455-460 | DOI | Zbl

[23] Marcel J. E. Golay The merit factor of long low autocorrelation binary sequences, IEEE Trans. Inf. Theory, Volume 28 (1982) no. 3, pp. 543-549 | DOI

[24] Peter L. Hammer; Ivo G. Rosenberg; Sergiu Rudeanu On the Determination of the Minima of Pseudo-Boolean Functions, Stud. Cercet. Ştiinţ., Ser. Mat., Univ. Bacău, Volume 14 (1963) no. 3, pp. 359-364 (in Rumanian)

[25] Peter L. Hammer; Sergiu Rudeanu Boolean Methods in Operations Research and Related Areas, Ökonometrie und Unternehmensforschung, 7, Springer, 2012 | DOI

[26] Robert Jeroslow On defining sets of vertices of the hypercube by linear inequalities, Discrete Math., Volume 11 (1975) no. 2, pp. 119-124 | DOI | Zbl

[27] Richard M. Karp Reducibility among Combinatorial Problems, Springer (1972), pp. 85-103 | DOI

[28] Frauke Liers; Enzo Marinari; Ulrike Pagacz; Federico Ricci-Tersenghi; Vera Schmitz A non-disordered glassy model with a tunable interaction range, J. Stat. Mech. Theory Exp., Volume 2010 (2010) no. 05, L05003 | DOI

[29] Stephan Mertens Exhaustive search for low-autocorrelation binary sequences, J. Phys. A. Math. Gen., Volume 29 (1996) no. 18, L473 | DOI | Zbl

[30] Stephan Mertens; Christine Bessenrodt On the ground states of the Bernasconi model, J. Phys. A. Math. Gen., Volume 31 (1998) no. 16, pp. 3731-3749 | DOI | Zbl

[31] MINLPLib A Library of Mixed-Integer and Continuous Nonlinear Programming Instances, 2020 (http://www.minlplib.org)

[32] Tom Packebusch; Stephan Mertens Low autocorrelation binary sequences, J. Phys. A. Math. Theor., Volume 49 (2016) no. 16, 165001 | DOI

[33] Elisabeth Rodríguez-Heck Linear and quadratic reformulations of nonlinear optimization problems in binary variables, Ph. D. Thesis, Université de Liège, Liège, Belgique (2018) https://hdl.handle.net/2268/227242

[34] Hanif D. Sherali; Cihan H. Tuncbilek A global optimization algorithm for polynomial programming problems using a Reformulation-Linearization Technique, J. Glob. Optim., Volume 2 (1992) no. 1, pp. 101-112 | DOI | Zbl

[35] Xiaojie Zhang; Paul H. Siegel Adaptive cut generation for improved linear programming decoding of binary linear codes, 2011 IEEE International Symposium on Information Theory Proceedings, IEEE (2011), pp. 1638-1642 | DOI

Cited by Sources: