Busca avançada
Ano de início
Entree

Modelos e algoritmos de programação linear inteira para problemas de otimização combinatória

Processo: 01/14205-6
Linha de fomento:Bolsas no Exterior - Pesquisa
Vigência (Início): 01 de agosto de 2002
Vigência (Término): 31 de dezembro de 2002
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Matemática da Computação
Pesquisador responsável:Cid Carvalho de Souza
Beneficiário:Cid Carvalho de Souza
Anfitrião: Egon Balas
Instituição-sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
Local de pesquisa : Carnegie Mellon University (CMU), Estados Unidos  
Assunto(s):Otimização combinatória   Programação por restrições   Programação linear inteira   Combinatória poliédrica   Algoritmos

Resumo

Este projeto tem como tema principal o estudo de modelos de programação inteira (PLI) para problemas de otimização combinatória NP - difíceis. A metodologia empregada baseia-se sobretudo no estudo teórico dos problemas visando a obtenção de desigualdades lineares que melhor descrevam a envoltória convexa das soluções viáveis dos mesmos. Uma vez encontrados estes resultados teóricos, a sua eficiência computacional deverá ser avaliada através da implementação e testes de algoritmos de enumeração do tipo branch-and-cut e branch-and-price. O projeto prevê ainda o estudo de técnicas de programação por restrições (PR) como uma ferramenta auxiliar no desenvolvimento de algoritmos híbridos (PLI e PR) para o tratamento de problemas combinatórios NP - difíceis. (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)
MACAMBIRA‚ E.M.; MACULAN‚ N.; DE SOUZA‚ C.C. A column generation approach for SONET ring assignment. NETWORKS, v. 47, n. 3, p. 157-171, 2006.
BALAS‚ E.; SOUZA‚ C.C. The vertex separator problem: a polyhedral investigation. MATHEMATICAL PROGRAMMING, v. 103, n. 3, p. 583-608, 2005.
SOUZA‚ C.; BALAS‚ E. The vertex separator problem: algorithms and computations. MATHEMATICAL PROGRAMMING, v. 103, n. 3, p. 609-631, 2005.

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.
Mapa da distribuição dos acessos desta página
Para ver o sumário de acessos desta página, clique aqui.