Banca de QUALIFICAÇÃO: EDUARDO ALVES DE JESUS ANACLETO

Uma banca de QUALIFICAÇÃO de DOUTORADO foi cadastrada pelo programa.
DISCENTE : EDUARDO ALVES DE JESUS ANACLETO
DATA : 05/06/2019
HORA: 14:00
LOCAL: sala 301, 3º andar do Bloco B, no campus Santo André
TÍTULO:

Methods for Solving Pseudo-Boolean Optimization Problems

PÁGINAS: 174
GRANDE ÁREA: Ciências Exatas e da Terra
ÁREA: Ciência da Computação
SUBÁREA: Matemática da Computação
RESUMO:

In this work, we investigate the Unconstrained Pseudo-Boolean Programming problem (UPBP), Unconstrained Binary Quadratic Programming problem (UBQP) and the Boolean Quadratic Programming problem with Generalized Upper Bound constraints (BQP-GUB), which belong to the computational complexity class NP-hard. Due to practical demands, researchers have shown interest in developing methods to solve these problems. To make relevant contributions, we intend to: (a) create an exact algorithm for the UPBP and UBQP; (b) design a polynomial time algorithm for solving instance classes of the UBQP; (c) propose a parallel version of the methods indicated in items (a) and (b); (d) develop a formula to generate bounds on the optimal solution values for solving instances of the UBQP; (e) develop formulas for evaluating flip-moves that simultaneously change the values of components of a solution vector for the BQP-GUB; (f) reformulate combinatorial optimization problems to the form of UBQP and BQP-GUB. Despite the objectives are ambitious, in the last six months, we proved original results with respect to the items (a), (b), (d) and (e). We also have conducted computational experiments for the methods related to the items (a), (b) and (e). It is worth to say that these preliminary results, theoretical and computational, are encouraging.

MEMBROS DA BANCA:
Presidente - 2616839 - CLAUDIO NOGUEIRA DE MENESES
Interno - 1722875 - DAVID CORREA MARTINS JUNIOR
Externo à Instituição - SIANG WUN SONG - USP