| Full text | |
| Author(s): |
Liang, Ricardo N.
;
Anacleto, Eduardo A. J.
;
Meneses, Claudio N.
Total Authors: 3
|
| Document type: | Journal article |
| Source: | Computers & Operations Research; v. 159, p. 16-pg., 2023-06-27. |
| Abstract | |
We consider the general case of pseudo-Boolean optimization (PBO). This problem belongs to the NP-hard class of computational complexity and generalizes the well-known quadratic unconstrained binary optimization (QUBO) problem, which is able to model a wide range of combinatorial optimization problems and also has applications in quantum computing. Several state-of-the-art methods in the literature for solving specific classes of PBO problems rely on the ability to quickly evaluate changes in objective function value upon a flip move, i.e., after changing the value of a Boolean variable in a given solution from 0 to 1 or from 1 to 0. In this work, we propose closed-form formulae, and develop algorithms and auxiliary data structures for quickly evaluating 1-flip move neighborhoods in PBO problems. We work with the objective function represented as a posiform, i.e., a sum of terms that may contain Boolean variables or negations thereof. This representation is interesting for solving large-scale instances, since converting a posiform to an expression containing no variable negations may take exponential time and space in the number of variables. We also provide implementations of our algorithms and data structures as a library written in C programming language. This library can be used to implement methods with fast flip move evaluations for solving PBO problem instances. We conducted computational experiments with implementations of a Iterated Tabu Search (ITS) metaheuristic, when solving randomly-generated instances, and also instances of the Hypergraph Maximum Cut problem, which can be easily recast as a PBO problem. The results showed that our best evaluation algorithms provided relatively large speedups as instance sizes increased, and became more competitive as a consequence of speedup. (AU) | |
| FAPESP's process: | 18/03819-4 - Methods for Solving Quadratic Binary Optimization Problems |
| Grantee: | Eduardo Alves de Jesus Anacleto |
| Support Opportunities: | Scholarships in Brazil - Doctorate |