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:

Avaliação Rápida de Soluções para o Problema de Programação Quadrática Binária Irrestrita

PÁGINAS: 88
RESUMO:

O prolema de Programação Binária Quadrática Irrestrita (UBQP) é considerado como uma formulação que unifica a modelagem de uma ampla gama de problems de otimização combinatória, e tem sido objeto de pesquisa intensa nos últimos 50 anos. Com o intuito de resolver instâncias do problema UBQP, ambos métodos exatos e heurísticos têm sido desenvolvidos. Tais métodos frequentemente exploram o espaço de soluções de uma instâncias por meio de flip moves, isto é, a transição de uma solução para outra invertendo os valores dos componentes do vetor solução. A avaliação de soluções resultantes de flip moves consome uma grande porção do tempo gasto por métodos de resolução do UBQP.
Assim, é importante que sejam feitas o mais rápido possível.
Nossas contribuções neste trabalho tratam da avaliação de múltiplos simultâneos flip moves. Na literatura atual, existem algoritmos para avaliação rápida de quantidades arbitrárias de flip moves simultâneos. Porém, dependendo das características do vetor solução, um algoritmo de avaliação pode apresentar performance melhor que outro. Assim, nossa primeira contribução consiste no desenvolvimento de algoritmos de avaliação híbridos. Com este intuito,
primeiramente encontramos fórmulas que estimam a quantidade de operações básicas que cada algoritmo de avaliação reaiza. Então, elaboramos algoritmos que consistem
em avaliar soluções que requerem a menor quantidade estimada de operações. Nossa segunda contribuição trata da avaliação de f-flip moves, isto é, flip moves onde valores fracionários são permitidos no vetor solução. Nós apresentamos duas fórmulas fechadas para computar o valor de soluções resultantes de múltiplos f-flip moves simultâneos.
Então, elaboramos algoritmos de avaliação baseados em cada fórmula. Nosso melhor algoritmo tem complexidade de tempo assintótica menor que a de algoritmos existentes na literatura
para avaliação de 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