Short Paper - The Binary Linearization Complexity of Pseudo-Boolean Functions
We consider the problem of linearizing a pseudo-Boolean function $f : \lbrace 0,1\rbrace ^n \rightarrow \mathbb{R}$ 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 lineari...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Université de Montpellier
2024-10-01
|
| Series: | Open Journal of Mathematical Optimization |
| Subjects: | |
| Online Access: | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.34/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1825205159432552448 |
|---|---|
| author | Walter, Matthias |
| author_facet | Walter, Matthias |
| author_sort | Walter, Matthias |
| collection | DOAJ |
| description | We consider the problem of linearizing a pseudo-Boolean function $f : \lbrace 0,1\rbrace ^n \rightarrow \mathbb{R}$ 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. |
| format | Article |
| id | doaj-art-7eeb38dbd35248a1ad654d09d3f09c10 |
| institution | Kabale University |
| issn | 2777-5860 |
| language | English |
| publishDate | 2024-10-01 |
| publisher | Université de Montpellier |
| record_format | Article |
| series | Open Journal of Mathematical Optimization |
| spelling | doaj-art-7eeb38dbd35248a1ad654d09d3f09c102025-02-07T14:01:17ZengUniversité de MontpellierOpen Journal of Mathematical Optimization2777-58602024-10-01511210.5802/ojmo.3410.5802/ojmo.34Short Paper - The Binary Linearization Complexity of Pseudo-Boolean FunctionsWalter, Matthias0Department of Applied Mathematics, University of Twente, The NetherlandsWe consider the problem of linearizing a pseudo-Boolean function $f : \lbrace 0,1\rbrace ^n \rightarrow \mathbb{R}$ 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.https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.34/Pseudo-Boolean optimizationmultilinear optimization |
| spellingShingle | Walter, Matthias Short Paper - The Binary Linearization Complexity of Pseudo-Boolean Functions Open Journal of Mathematical Optimization Pseudo-Boolean optimization multilinear optimization |
| title | Short Paper - The Binary Linearization Complexity of Pseudo-Boolean Functions |
| title_full | Short Paper - The Binary Linearization Complexity of Pseudo-Boolean Functions |
| title_fullStr | Short Paper - The Binary Linearization Complexity of Pseudo-Boolean Functions |
| title_full_unstemmed | Short Paper - The Binary Linearization Complexity of Pseudo-Boolean Functions |
| title_short | Short Paper - The Binary Linearization Complexity of Pseudo-Boolean Functions |
| title_sort | short paper the binary linearization complexity of pseudo boolean functions |
| topic | Pseudo-Boolean optimization multilinear optimization |
| url | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.34/ |
| work_keys_str_mv | AT waltermatthias shortpaperthebinarylinearizationcomplexityofpseudobooleanfunctions |