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)