# PBO#

Pseudo-Boolean Optimization (PBO) problem set, which contains 25 test functions taking their domain on {0, 1}^n, where n is the length of bitstrings.

In PBO, we cover some theory-motivated function, e.g., OneMax and LeadingOnes as well as others with more practical relevance, e.g., the NK Landscape [DoerrYHWSB20]. We also utilized the so-called W-model for generating/enriching the problem set [WeiseW18].

## Problems#

### Classes#

 `ConcatenatedTrap`(self, instance, n_variables) Concatenated Trap (CT) is defined by partitioning a bit-string into segments of length k and concatenating m = n/k trap functions that takes each segment as input. `IsingRing`(self, instance, n_variables) The Ising Spin Glass model arose in solid-state physics and statistical mechanics, aiming to describe simple interactions within many-particle systems. `IsingTorus`(self, instance, n_variables) The Ising Spin Glass model arose in solid-state physics and statistical mechanics, aiming to describe simple interactions within many-particle systems. `IsingTriangular`(self, instance, n_variables) The Ising Spin Glass model arose in solid-state physics and statistical mechanics, aiming to describe simple interactions within many-particle systems. `LABS`(self, instance, n_variables) Low Autocorrelation Binary Sequences (LABS): x ↦ n^2 / 2∑_{k=1}^{n-1}(∑_{i=1}^{n−k}s_is_{i+k})^2, where s_i = 2x_i − 1 `LeadingOnes`(self, instance, n_variables) LeadingOnes: {0,1}^n → [0..n], x ↦ max{i∈[0..n] ∣ ∀j≤i: x_j=1} `LeadingOnesDummy1`(self, instance, n_variables) A variant of LeadingOnes applying the Dummy transformation of W-model. `LeadingOnesDummy2`(self, instance, n_variables) A variant of LeadingOnes applying the Dummy transformation of W-model. `LeadingOnesEpistasis`(self, instance, n_variables) A variant of LeadingOnes applying the Epistasis transformation of W-model. `LeadingOnesNeutrality`(self, instance, ...) A variant of LeadingOnes applying the Neutrality transformation of W-model. `LeadingOnesRuggedness1`(self, instance, ...) A variant of LeadingOnes applying the first Ruggnedness transformation in https://doi.org/10.1016/j.asoc.2019.106027. `LeadingOnesRuggedness2`(self, instance, ...) A variant of LeadingOnes applying the second Ruggnedness transformation in https://doi.org/10.1016/j.asoc.2019.106027. `LeadingOnesRuggedness3`(self, instance, ...) A variant of LeadingOnes applying the third Ruggnedness transformation in https://doi.org/10.1016/j.asoc.2019.106027. `Linear`(self, instance, n_variables) A Linear Function with Harmonic Weights: {0,1}^n → ℝ, x ↦ ∑_i i * x_i `MIS`(self, instance, n_variables) The maximum independent vertex set (MIVS) formulated as x ↦ ∑_i x_i - n ∑_{i,j} x_i x_j e_{i,j}, where e_{i,j} = 1 if {i,j} in E, otherwise e_{i,j} = 0. `NQueens`(self, instance, n_variables) The N-queens problem (NQP) is defined as the task to place N queens on an N*N chessboard in such a way that they cannot attack each other. `OneMax`(self, instance, n_variables) OneMax: {0,1}^n → [0..n], x ↦ ∑_{i=1}^n x_i. `OneMaxDummy1`(self, instance, n_variables) A variant of OneMax applying the Dummy transformation of W-model. `OneMaxDummy2`(self, instance, n_variables) A variant of OneMax applying the Dummy transformation of W-model. `OneMaxEpistasis`(self, instance, n_variables) A variant of OneMax applying the Epistasis transformation of W-model. `OneMaxNeutrality`(self, instance, n_variables) A variant of OneMax applying the Neutrality transformation of W-model. `OneMaxRuggedness1`(self, instance, n_variables) A variant of OneMax applying the first Ruggnedness transformation in https://doi.org/10.1016/j.asoc.2019.106027. `OneMaxRuggedness2`(self, instance, n_variables) A variant of OneMax applying the second Ruggnedness transformation in https://doi.org/10.1016/j.asoc.2019.106027. `OneMaxRuggedness3`(self, instance, n_variables) A variant of OneMax applying the third Ruggnedness transformation in https://doi.org/10.1016/j.asoc.2019.106027. `PBO` Pseudo-Boolean Optimization (PBO) problem set.

### Class Inheritance Diagram# ## Reference#

[DoerrYHWSB20] Carola Doerr, Furong Ye, Naama Horesh, Hao Wang, Ofer M. Shir, and Thomas Bäck. “Benchmarking discrete optimization heuristics with IOHprofiler.” Applied Soft Computing 88 (2020): 106027.

[WeiseW18] Thomas Weise and Zijun Wu. “Difficult features of combinatorial optimization problems and the tunable w-model benchmark problem for simulating them.” In Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 1769-1776. 2018.