Busca avançada
Ano de início
Entree

Reformulações de problemas de otimização binária: algoritmos e complexidade

Processo: 14/23269-8
Linha de fomento:Bolsas no Brasil - Pós-Doutorado
Vigência (Início): 01 de março de 2015
Vigência (Término): 28 de fevereiro de 2017
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Matemática da Computação
Pesquisador responsável:Carlos Eduardo Ferreira
Beneficiário:Aritanan Borges Garcia Gruber
Instituição-sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
Vinculado ao auxílio:13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação, AP.TEM
Assunto(s):Otimização matemática

Resumo

Problemas de otimização binária não linear de larga escala ocorrem frequentemente em uma variedade de aplicações. Ao longo dos anos, várias técnicas exatas e heurísticas foram desenvolvidas para lidar com tais problemas no caso em que a função objetivo é um polinômio quadrático - e elas se mostraram extremamente efetivas em tal caso. Quando a função objetivo é um polinômio de grau maior que dois, no entanto, muito menos sucesso foi obtido. Com a crescente necessidade de se encontrar soluções para problemas de otimização de polinômios de alto grau, pois muitas aplicações oriundas das áreas de visão computacional e aprendizado de máquina encaixam-se neste quadro, várias técnicas com o intuito de reduzir o caso geral para o caso quadrático foram recentemente desenvolvidas. Todas elas se dão ao custo de um aumento no número de variáveis descrevendo o problema. O foco deste projeto de pós-doutorado é no avanço do estudo e desenvolvimento de tais abordagens, chamadas na literatura de quadratizações, tanto do ponto de vista teórico (estrutura e complexidade) quando do prático (algoritmos e aplicações). Pretende-se também investigar possíveis relações com outras estratégias existentes, como hierarquias de relaxamento / formulações estendidas e somas-de-quadrados de polinômios. (AU)

Publicações científicas
(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)
ANTHONY, MARTIN; BOROS, ENDRE; CRAMA, YVES; GRUBER, ARITANAN. Quadratic reformulations of nonlinear binary optimization problems. MATHEMATICAL PROGRAMMING, v. 162, n. 1-2, p. 115-144, MAR 2017. Citações Web of Science: 2.
ANTHONY, MARTIN; BOROS, ENDRE; CRAMA, YVES; GRUBER, ARITANAN. Quadratization of symmetric pseudo-Boolean functions. DISCRETE APPLIED MATHEMATICS, v. 203, p. 1-12, APR 20 2016. Citações Web of Science: 5.

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.