Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/330906
Type: TESE DIGITAL
Degree Level: Doutorado
Title: Uma heurística híbrida para resolução de problemas de programação não linear inteira mista
Title Alternative: A hybrid heuristic for solving mixed integer nonlinear programming problems
Author: Ferreira, Daiane Gonçalves, 1988-
Advisor: Ruggiero, Márcia Aparecida Gomes, 1956-
Abstract: 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

Abstract: The aim of this work is to address problems formulated as MINLP (Mixed Integer Nonlinear Programming). We propose a heuristic resolution method based on Inexact Restoration methods combined with the Feasibility Pump heuristic. The Inexact Restoration methods were proposed for solving nonlinear problems with continuous variables. These methods involve two phases, Restoration (viability phase) and Optimality. The Feasibility Pump heuristic was proposed to obtain feasible solutions for optimization problems with integer variables, MILPs (Mixed Integer Linear Programming) and MINLPs. In this work we adapt the two phases of the Inexact Restoration method in the context of problems with integer variables, MINLP, seeking advances in feasibility (Restoration phase) through the Feasibility Pump heuristic. In the optimality phase, two subproblems are solved, in the first the integrality constraints are relaxed and we construct a NLP (Nonlinear Programming), in the second the nonlinear constraints are relaxed and we construct a MILP. A master process coordinates the subproblems to be solved at each stage. The performance of the final algorithm was analised in a set of classical problems
Subject: Programação não-linear inteira mista
Métodos de restauração inexata
Feasibility pump - Técnica
Language: Português
Editor: [s.n.]
Citation: FERREIRA, Daiane Gonçalves. Uma heurística híbrida para resolução de problemas de programação não linear inteira mista. 2017. 1 recurso online (123 p.). Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica, Campinas, SP. Disponível em: <http://www.repositorio.unicamp.br/handle/REPOSIP/330906>. Acesso em: 3 set. 2018.
Date Issue: 2017
Appears in Collections:IMECC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Ferreira_DaianeGoncalves_D.pdf1.73 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.