Métodos para Resolução de Problemas de Otimização Quadráticos Binários

• Processo: 18/03819-4
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Data de Início da vigência: 01 de junho de 2018
• Data de Término da vigência: 31 de maio de 2022
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Matemática da Computação
• Pesquisador responsável: Cláudio Nogueira de Meneses
• Beneficiário: Eduardo Alves de Jesus Anacleto
• Instituição Sede: Centro de Matemática, Computação e Cognição (CMCC). Universidade Federal do ABC (UFABC). Ministério da Educação (Brasil). Santo André , SP, Brasil
• Vinculado ao auxílio: 16/01860-1 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento, localização e suas integrações em contextos industriais e logísticos, AP.TEM
• Assunto(s): Programação dinâmica Otimização combinatória
• Palavra(s)-Chave do Pesquisador: Algoritmos de Tempo Polinomial | Limitantes Inferiores e Superiores | Problemas Quadráticos Binários | Programação Dinâmica | Reavaliação Rápida de Funções | Redução de Problemas em Tempo Polinomial | Otimização Combinatória

Resumo

Neste projeto, investigamos os problemas de Programação Quadrática Binária Irrestrita (UBQP) e Programação Quadrática Booleana com Restrições de Limitantes Superiores Generalizados (BQP-GUB), que pertencem à classe de complexidade NP-difícil. Em virtude de apelos práticos, há grande interesse no desenvolvimento de métodos para resolver esses problemas. Com o intuito de contribuir de maneira significativa para esta área de pesquisa, pretendemos: (a) desenvolver um método exato para o problema UBQP; (b) projetar um algoritmo de tempo polinomial para resolver classes de instâncias do problema UBQP; (c) propor uma versão paralela dos métodos indicados nos itens (a) e (b); (d) desenvolver uma fórmula para gerar limitantes aos valores de soluções ótimas para resolver instâncias do problema UBQP; (e) desenvolver fórmulas para calcular rapidamente o valor da função objetivo do problema BQP-GUB; e (f) converter problemas de otimização para a forma dos problemas UBQP e BQP-GUB. Embora estes objetivos sejam ambiciosos, ressaltamos que nos últimos seis meses obtivemos resultados originais com relação aos itens (a), (b), (d), (e) e realizamos experimentos computacionais quanto aos itens (a) e (b). Estes resultados preliminares, teóricos e computacionais, são animadores.

Publicações científicas

(4)

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

ANACLETO, EDUARDO A. J.; MENESES, CLAUDIO N.; RAVELO, SANTIAGO V.. Closed-form formulas for evaluating r-flip moves to the unconstrained binary quadratic programming problem. Computers & Operations Research, v. 113, JAN 2020. (18/03819-4)

RAVELO, SANTIAGO, V; MENESES, CLAUDIO N.; ANACLETO, EDUARDO A. J.; IEEE. NP-hardness and evolutionary algorithm over new formulation for a Target Set Selection problem. 2020 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC), v. N/A, p. 8-pg., 2020-01-01. (18/03819-4)

LIANG, RICARDO N.; ANACLETO, EDUARDO A. J.; MENESES, CLAUDIO N.. Data structures for speeding up Tabu Search when solving sparse quadratic unconstrained binary optimization problems. Journal of Heuristics, v. 28, n. 4, p. 47-pg., 2022-04-27. (18/03819-4)

LIANG, RICARDO N.; ANACLETO, EDUARDO A. J.; MENESES, CLAUDIO N.. Fast 1-flip neighborhood evaluations for large-scale pseudo-Boolean optimization using posiform representation. Computers & Operations Research, v. 159, p. 16-pg., 2023-06-27. (18/03819-4)