Escolha Adiada de Parâmetros em Métodos de Pontos Interiores para Programação Linear

• Processo: 08/09685-8
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Data de Início da vigência: 01 de agosto de 2009
• Data de Término da vigência: 31 de dezembro de 2012
• Área de conhecimento: Engenharias - Engenharia de Produção - Pesquisa Operacional
• Pesquisador responsável: Aurelio Ribeiro Leite de Oliveira
• Beneficiário: Luiz Rafael dos Santos
• Instituição Sede: Instituto de Matemática, Estatística e Computação Científica (IMECC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Métodos de pontos interiores Programação linear
• Palavra(s)-Chave do Pesquisador: Métodos de Pontos Interiores | programação linear | Sistemas Lineares de Grande Porte | Programação Linear

Resumo

A técnica de escolha atrasada dos parâmetros de perturbação e tamanho do passo será utilizada com o objetivo de reduzir o número de iterações necessárias para a convergência dos métodos de pontos interiores do tipo primal-dual. Esta técnica procura reduzir o número de iterações adiando a escolha destes parâmetros obtendo assim pontos com melhores propriedades. Para obter os parâmetros é necessário resolver sistemas lineares adicionais com a mesma matriz. No entanto, na grande maioria das iterações o parâmetro de perturbação ótimo é nulo e identificar a priori esta situação pode levar a implementações muito eficientes, pois seria necessário resolver somente um sistema linear nestas iterações. O objetivo deste projeto consiste em detectar iterações onde uma ou duas resoluções de sistemas lineares são suficientes para obter uma boa direção através tanto de heurísticas quanto propriedades teóricas. Desta forma pretende-se desenvolver uma implementação que reduza o tempo computacional total através da combinação de iterações mais baratas com um menor número de iterações para obtenção da convergência.

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)

SANTOS, LUIZ-RAFAEL; VILLAS-BOAS, FERNANDO; OLIVEIRA, AURELIO R. L.; PERIN, CLOVIS. Optimized choice of parameters in interior-point methods for linear programming. COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, v. 73, n. 2, p. 535-574, JUN 2019. (08/09685-8, 10/06822-4)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

SANTOS, Luiz Rafael dos. Escolha otimizada de parâmetros em métodos de pontos interiores para programação linear. 2014. Tese de Doutorado - Universidade Estadual de Campinas (UNICAMP). Instituto de Matemática, Estatística e Computação Científica Campinas, SP.