Busca avançada
Ano de início
Entree

Contribuições para a integração de técnicas de programação inteira e de programação por restrições

Processo: 12/09566-4
Linha de fomento:Auxílio à Pesquisa - Pesquisador Visitante - Internacional
Vigência: 15 de setembro de 2012 - 26 de outubro de 2012
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Cid Carvalho de Souza
Beneficiário:Cid Carvalho de Souza
Pesquisador visitante: John Norman Hooker
Inst. do pesquisador visitante: Carnegie Mellon University (CMU), Estados Unidos
Instituição-sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
Assunto(s):Otimização combinatória  Programação por restrições  Programação linear inteira  Combinatória poliédrica  Intercâmbio de pesquisadores 

Resumo

A pesquisa feita na última década mostra que a integração dos métodos de programação inteira (IP) e de programação por restrições (CP) pode levar a benefícios substanciais na solução de problemas de otimização combinatória. Isto inclui reduções em ordens de grandeza no tempo de computação de importantes problemas da área, bem como formas mais poderosas de modelagem. Neste projeto nós propomos estudar um elemento central para os métodos de integração, a saber, o desenvolvimento de relaxações poliedrais para as "restrições globais" usadas em CP. As restrições globais são a chave do sucesso da CP. Elas representam subconjuntos de restrições altamente estruturadas. Ao processar cada restrição global através de um algoritmo de "filtragem", o resolvedor pode explorar a subestrutura de modo a excluir valores inviáveis para as variáveis. Um próximo passo natural é combinar as vantagens das restrições globais com a metodologia de relaxação da IP, por meio do estudo da estrutura poliedral das restrições globais. O estudo descrito nesta proposta se insere neste contexto. (AU)