Short Paper - The Binary Linearization Complexity of Pseudo-Boolean Functions
Walter, Matthias1
1Department of Applied Mathematics, University of Twente, The Netherlands
Open Journal of Mathematical Optimization, Tome 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.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/ojmo.34
Keywords: Pseudo-Boolean optimization, multilinear optimization

Walter, Matthias  1

1 Department of Applied Mathematics, University of Twente, The Netherlands
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits
@article{OJMO_2024__5__A6_0,
     author = {Walter, Matthias},
     title = {Short {Paper} - {The} {Binary} {Linearization} {Complexity} of {Pseudo-Boolean} {Functions}},
     journal = {Open Journal of Mathematical Optimization},
     eid = {6},
     pages = {1--12},
     year = {2024},
     publisher = {Universit\'e de Montpellier},
     volume = {5},
     doi = {10.5802/ojmo.34},
     mrnumber = {4811411},
     language = {en},
     url = {https://www.numdam.org/articles/10.5802/ojmo.34/}
}
TY  - JOUR
AU  - Walter, Matthias
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://www.numdam.org/articles/10.5802/ojmo.34/
DO  - 10.5802/ojmo.34
LA  - en
ID  - OJMO_2024__5__A6_0
ER  - 
%0 Journal Article
%A Walter, Matthias
%T Short Paper - The Binary Linearization Complexity of Pseudo-Boolean Functions
%J Open Journal of Mathematical Optimization
%] 6
%D 2024
%P 1-12
%V 5
%I Université de Montpellier
%U https://www.numdam.org/articles/10.5802/ojmo.34/
%R 10.5802/ojmo.34
%G en
%F OJMO_2024__5__A6_0
Walter, Matthias. Short Paper - The Binary Linearization Complexity of Pseudo-Boolean Functions. Open Journal of Mathematical Optimization, Tome 5 (2024), article  no. 6, 12 p.. doi: 10.5802/ojmo.34

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

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

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

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

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

[6] Billionnet, Alain; Elloumi, Sourour 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 | Zbl | DOI | MR

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[24] Hammer, Peter L.; Rosenberg, Ivo G.; Rudeanu, Sergiu 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] Hammer, Peter L.; Rudeanu, Sergiu Boolean Methods in Operations Research and Related Areas, Ökonometrie und Unternehmensforschung, 7, Springer, 2012 | DOI

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

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

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

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

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

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

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

[33] Rodríguez-Heck, Elisabeth 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] Sherali, Hanif D.; Tuncbilek, Cihan H. A global optimization algorithm for polynomial programming problems using a Reformulation-Linearization Technique, J. Glob. Optim., Volume 2 (1992) no. 1, pp. 101-112 | Zbl | DOI | MR

[35] Zhang, Xiaojie; Siegel, Paul H. 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

Cité par Sources :