Banca de QUALIFICAÇÃO: RICARDO NANTES LIANG

Uma banca de QUALIFICAÇÃO de MESTRADO foi cadastrada pelo programa.
DISCENTE : RICARDO NANTES LIANG
DATA : 20/12/2019
HORA: 14:00
LOCAL: sala 301, 3º andar, Bloco B, Campus SA da Fundação Universidade Federal do ABC, localizada na Avenida dos Estados, 5001, Santa Terezinha, Santo André, SP
TÍTULO:

Fast Evaluation of Solutions to the Unconstrained Binary Quadratic Programming Problem

PÁGINAS: 88
GRANDE ÁREA: Ciências Exatas e da Terra
ÁREA: Ciência da Computação
RESUMO:

The Unconstrained Binary Quadratic Programming (UBQP) problem is considered a unifying formulation for modeling a wide range of combinatorial optimization problems, and has been the subject of intense research over the last 50 years.
For the purpose of solving instances of the UBQP problem, both exact and heuristic methods have been developed. Such methods often explore an instance's solution space through flip moves, i.e. the transition from a solution to another by changing the value of the components in the solution vector. The evaluation of solutions resulting from flip moves represents a relatively large portion of the time spent by UBQP resolution methods when solving instances. Thus, it is important that they are performed as quickly as possible. Our contributions in this work regard
the evaluation of multiple simultaneous flip moves.
In current literature, there exist algorithms for quickly
evaluating arbitrary amounts of simultaneous flip moves.
However, depending on the characteristics of the solution vector, one evaluation algorithm may perform better than another. Thus, our first contribution consists in the development of hybrid evaluation algorithms. For that purpose, first we find formalae for estimating the amount of basic operations each evaluation algorithm takes.
Then, we propose algorithms which consist in evaluating solutions through the algorithm that would take the least estimated amount of operations. Our second contribution regards the evaluation of f-flip moves, that is, flip moves where fractional values are allowed in a solution vector.
We present two closed-form formulae for efficiently evaluating solutions resulting from multiple simultaneous f-flip moves.
Furthermore, we present evaluation algorithms based on each formula. As a result, our best algorithm has lower asymptotic time complexity than those in existing literature for evaluating f-flip moves. 

MEMBROS DA BANCA:
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 à Instituição - HUMBERTO JOSÉ LONGO - UFG
Membro Suplente - Examinador(a) Interno ao Programa - 1934625 - JESUS PASCUAL MENA CHALCO
Membro Suplente - Examinador(a) Interno ao Programa - 1675615 - LUIZ CARLOS DA SILVA ROZANTE