Banca de DEFESA: RICARDO NANTES LIANG

Uma banca de DEFESA de DOUTORADO foi cadastrada pelo programa.
STUDENT : RICARDO NANTES LIANG
DATE: 06/05/2024
TIME: 14:30
LOCAL: https://meet.google.com/syy-hqze-uyi
TITLE:

Fast Evaluation of Solutions to Pseudo-Boolean Optimization Problems

PAGES: 180
BIG AREA: Ciências Exatas e da Terra
AREA: Ciência da Computação
SUBÁREA: Teoria da Computação
SPECIALTY: Análise de Algoritmos e Complexidade de Computação
SUMMARY:

We consider the Pseudo-Boolean Optimization (PBO) problem. It belongs to the NP-hard class of
computational complexity and is able to model a wide range of combinatorial optimization problems.
The well-known Quadratic Unconstrained Binary Optimization (QUBO) problem is a specific case of
pseudo-Boolean optimization. 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 variable in a given solution from 0 to 1 or from 1 to 0.
Consequently, research on fast flip move evaluation has benefitted many existing exact and heuristic methods.
In this work, we seek to expand the literature surrounding fast flip move evaluation. Our first three
contributions regard the QUBO problem. First, we consider two existing algorithms for evaluating
multiple simultaneous flip moves. Depending on the values of their parameters, one may execute faster than the other. Thus, we propose what we call hybrid evaluation algorithms, that consist in estimating and using the
fastest one for some given parameters. In our second contribution, we prove closed-form formulae and derive algorithms for fast evaluation of multiple simultaneous flip moves, considering the case where fractional values
may be allowed in solution vectors. In our third contribution, we propose data structures to speed up
1-flip move evaluation within the context of a Tabu Search heuristic, and when the QUBO problem instance is sparse. Our last contribution regards the general PBO problem. We work with its objective function represented as a so-called posiform, i.e. an expression which may contain variable negations in its terms. Based on that, we prove closed-form formulae, derive algorithms, and propose data structures to speed up 1-flip move evaluations. For all of our contributions, we show, by means of extensive computational experiments, that our results can benefit existing methods in the literature for solving the respective problems.

COMMITTEE MEMBERS:
Presidente - Interno ao Programa - 2616839 - CLAUDIO NOGUEIRA DE MENESES
Membro Titular - Examinador(a) Interno ao Programa - 1722875 - DAVID CORREA MARTINS JUNIOR
Membro Titular - Examinador(a) Externo ao Programa - 2123345 - CRISTIANE MARIA SATO
Membro Titular - Examinador(a) Externo à Instituição - HUMBERTO JOSÉ LONGO - UFG
Membro Titular - Examinador(a) Externo à Instituição - SANTIAGO VALDÉS RAVELO - UNICAMP
Membro Suplente - Examinador(a) Interno ao Programa - 1934625 - JESUS PASCUAL MENA CHALCO
Membro Suplente - Examinador(a) Interno ao Programa - 1932365 - FABRICIO OLIVETTI DE FRANCA
Membro Suplente - Examinador(a) Externo à Instituição - MARISTELA OLIVEIRA DOS SANTOS - USP
Membro Suplente - Examinador(a) Externo à Instituição - THIERSON COUTO ROSA