Modelos e elaboração de algoritmos para problemas de programação não linear inteira mista (MINLP)

• Processo: 13/21515-9
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Data de Início da vigência: 01 de janeiro de 2014
• Data de Término da vigência: 30 de junho de 2017
• Área de conhecimento: Engenharias - Engenharia de Produção - Pesquisa Operacional
• Pesquisador responsável: Marcia Aparecida Gomes Ruggiero
• Beneficiário: Daiane Gonçalves Ferreira
• 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): Programação não linear Convexidade Heurística Algoritmos Programação linear inteira
• Palavra(s)-Chave do Pesquisador: Algoritmos heurísticos | Feasibility Pump | programação inteira | programação não linear | Restauração inexata | Programação Linear, Nao Linear, Inteira, Mista

Resumo

Modelos matemáticos de problemas reais de diversas áreas envolvem a otimização de uma função com variáveis de decisão inteiras e contínuas e as funções que representam o objetivo e restrições podem ser lineares (MILP: Mixed Integer Linear Programming) ou não lineares (MINLP: Mixed Integer Nonlinear Programming). As variáveis inteiras representam itens que não podem ser fracionados, tais como, máquinas, equipamentos médicos, padrões de corte, profissionais e/ou máquinas alocados em tarefas. Em problemas de tomada de decisão, a formulação envolve também variáveis binárias que assumem valor 0 ou 1 dependendo se uma decisão é ou não concretizada. Caso o modelo envolva somente variáveis contínuas, temos um problema de programação não linear, denotado aqui por NLP: Nonlinear Programming. Os primeiros processos de resolução para tais problemas eram baseados na resolução de subproblemas MILP gerados a partir da linearização das funções envolvidas. Tais subproblemas permitem a obtenção de limites para o valor ótimo do problema original que são então apropriadamente usados em técnicas Branch-and-Bound. É evidente que tal procedimento só é numericamente possível para problemas de pequeno e médio porte. Contudo, o crescente avanço em métodos para modelos MILP e de Programação Não Linear (NLP) tem contribuído para despertar o interesse em novas propostas de métodos para problemas com maior número de variáveis e restrições. Assim como ocorre com os modelos NLP, os problemas nos quais as funções envolvidas são convexas são de resolução mais fácil que os não convexos. A razão é bastante simples uma vez que a versão relaxada do modelo, obtida ao supor que todas as variáveis são contínuas, resulta em um NLP convexo e uma grande variedade de métodos exatos são fundamentados neste fato, tais como, decomposição de Benders, branch-and-bound, branch-and-cut, outer approximation, entre outros. O objetivo neste trabalho é abordar problemas formulados como MINLP, com e sem suposição de convexidade sobre as funções envolvidas. A expectativa é elaborar um algoritmo eficiente e robusto para resolução de problemas MINLP. O processo de resolução que propomos é um algoritmo heurístico baseado em ideias de métodos do tipo Restauração Inexata combinado com a técnica 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 técnica Feasibility Pump foi proposta para obter soluções factíveis para problemas de otimização com variáveis inteiras, MILPs e MINLPs. A proposta neste trabalho é adaptar as duas fases dos métodos Restauração Inexata ao contexto de problemas com variáveis inteiras, MINLP, buscando avanços na viabilidade (fase da Restauração) através da estratégia Feasibility Pump. Na fase de otimalidade, a condição de integralidade sobre as variáveis é relaxada e uma função de mérito é construída e em empregada na resolução de um Problema Não Linear com variáveis contínuas. Um processo mestre deverá coordenar os subproblemas que serão resolvidos em cada fase. A versão final do algoritmo empregará softwares específicos para os vários subproblemas, tais como MINOS e CPLEX além dos programas que serão elaborados relacionados às heurísticas e etapas da resolução. Todo este projeto computacional requer o uso de plataformas adequadas para modelagem, tais como: AIMMS ou AMPL. O desempenho do algoritmo será analisado e validado através da resolução de um conjunto clássico de problemas. Após estes testes, aplicaremos a analisaremos o algoritmo na resolução de modelos MINLP para projetos de redes de cadeia de suprimento. (AU)

Publicações acadêmicas

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

FERREIRA, Daiane Gonçalves. Uma heurística híbrida para resolução de problemas de programação não linear inteira mista. 2017. Tese de Doutorado - Universidade Estadual de Campinas (UNICAMP). Instituto de Matemática, Estatística e Computação Científica Campinas, SP.