Título: A dimensionality reduction algorithm for optimizing pseudo-Boolean functions

Palestrante: Eduardo Alves de Jesus Anacleto (Doutorando em Ciência da Computação – UFABC)

Data e local: Quarta, 08 de junho de 2022 às 16:00, Campus Santo André, Bloco A, sala S-204-0

Resumo: The general case of Pseudo-Boolean Optimization (PBO) problems belongs to the NP-hard computational class. To the best of our knowledge, there exist only two exact methods for solving PBO problems via variable elimination. One such method, known as the Basic Algorithm (BA), consists of eliminating one decision variable at a time until the problem is solved. There is no evidence in the literature that the BA has been implemented, perhaps due to the intricacies of pseudo-Boolean function manipulation. The other method is a Branch-and-Bound based approach that also performs variable elimination. In this work, motivated by the challenge of providing an implementable algorithm based on the BA and seeking to reduce the scarcity of exact techniques for solving PBO problems, we developed an easy-to-implement Dimensionality Reduction Algorithm (DRA) and conducted computational experiments. The asymptotic time complexity of our DRA is O(k(2n-k)2^{k-1}), where n is the dimension of a solution and k indicates the width of a tree associated with the pseudo-Boolean function. We also developed mechanisms to facilitate algebraic manipulations of pseudo-Boolean functions and used them to prove the correctness of our DRA.