Uma heurística híbrida para resolução de problemas de programação não linear inteira mista

Autor(es)

Daiane Gonçalves Ferreira

• Tipo de documento: Tese de Doutorado
• Instituição: Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica
• Data de defesa: 2017

Resumo

O objetivo neste trabalho é abordar problemas formulados como MINLP (Mixed Integer Nonlinear Programming). Propomos um método de resolução heurístico baseado em ideias de métodos do tipo Restauração Inexata combinado com a heurística denominada Feasibility Pump. Os métodos de Restauração Inexata foram propostos para resolução de problemas não lineares com variáveis contínuas. As iterações envolvem duas fases, Restauração (fase da viabilidade) e Otimalidade. A heurística Feasibility Pump foi proposta para obter soluções factíveis para problemas de otimização com variáveis inteiras, MILPs (Mixed Integer Linear Programming) e MINLPs. Neste trabalho adaptamos as duas fases dos métodos de Restauração Inexata ao contexto de problemas com variáveis inteiras, MINLP, buscando avanços na viabilidade (fase da Restauração) através da heurística Feasibility Pump. Na fase de otimalidade resolvemos dois subproblemas, no primeiro a condição de integralidade sobre as variáveis é relaxada e construímos um PNL (Problema de Programação Não Linear), no segundo as restrições não lineares são relaxadas e construímos um MILP. Um processo mestre coordena os subproblemas que são resolvidos em cada fase. O desempenho do algoritmo foi analisado e validado através da resolução de um conjunto clássico de problemas (AU)

• Processo FAPESP: 13/21515-9 - Modelos e elaboração de algoritmos para problemas de programação não linear inteira mista (MINLP)
• Beneficiário: Daiane Gonçalves Ferreira
• Linha de fomento: Bolsas no Brasil - Doutorado