Return to search

Modelos matemáticos e algoritmos para problemas combinatórios

Submitted by Erika Demachki (erikademachki@gmail.com) on 2016-03-17T17:31:58Z
No. of bitstreams: 2
Dissertação - Santiago Valdés Ravelo - 2011.pdf: 730949 bytes, checksum: 92c89c8c1f240082004834898896b9ba (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Erika Demachki (erikademachki@gmail.com) on 2016-03-17T17:35:15Z (GMT) No. of bitstreams: 2
Dissertação - Santiago Valdés Ravelo - 2011.pdf: 730949 bytes, checksum: 92c89c8c1f240082004834898896b9ba (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2016-03-17T17:35:15Z (GMT). No. of bitstreams: 2
Dissertação - Santiago Valdés Ravelo - 2011.pdf: 730949 bytes, checksum: 92c89c8c1f240082004834898896b9ba (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)
Previous issue date: 2011-02-18 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work considers three relevant NP-hard problems. The firstone is the one-dimensional
cutting stock problem in which the non-used material in the cutting patterns may be used
in the future. For this problem we analyze the existing mathematical models, propose new
models, design a heuristic and two metaheuristic approaches, being their performances
improved by using parallel programming, and solve instances, practical and randomly
generated, from the literature. The computational experiments were quite good for all
tested instances. The second problem we consider is the stable roommates problem (a
variant of the stable matching problem). For this we give two mathematical programming
models, sequential and parallel implementations of a Tabu Search, and a Branch-andBound. Also, we report computational experiments to instances of the problem. The
last problem we consider is the compartmentalized knapsack problem (a generalization
of the knapsack problem) for which we analyze a quadratic integer model and give a
linear integer model. We design a greedy heuristic and a GRASP algorithm, that uses
path-relinking, and solve randomly generated instances. All parallel implementations use
Graphics Processing Units (GPUs). / Este trabalho considera três problemas, NP-difíceis, relevantes de estudo em otimização
combinatória. O primeiro deles é o problema de corte uni-dimensional de objetos,
onde o material não usado pelos padrões de corte pode ser usado no futuro. Para este
problema analisamos os modelos matemáticos existentes, propomos novos modelos,
projetamos uma heurística construtiva e duas metaheurísticas, sendo seus desempenhos
melhorados com programação paralela, e resolvemos instâncias, práticas e aleatórias,
encontradas na literatura; sendo os experimentos computacionais muito bons para todas as
intânciastestadas.Osegundoproblemaqueconsideramoséoproblemadoscompanheiros
estáveis (stable roommates problem), uma variante do problema de emparelhamento
estável (stable matching problem). Para este propomos dois modelos matemáticos, uma
implementação sequencial e uma paralela de uma Tabu Search, e um Branch-andBound. Também reportamos experimentos computacionais para instâncias do problema.
O último problema considerado é o da mochila compartimentada (uma generalização do
problema clássico da mochila), para o qual analisamos uma modelagem quadrática inteira
e propomos um modelo linear inteiro; também projetamos uma heurística gulosa, um
algoritmo GRASP, que usa path-relinking, e resolvemos intâncias geradas aleatóriamente.
Todas as implementações em paralelo usam unidades de processamento gráfico (Graphics
Processing Units, GPUs).

Identiferoai:union.ndltd.org:IBICT/oai:repositorio.bc.ufg.br:tede/5354
Date18 February 2011
CreatorsRavelo, Santiago Valdes
ContributorsMeneses, Claudio Nogueira de, Meneses, Cláudio Nogueira de, Longo, Humberto José, Morabito, Reinaldo
PublisherUniversidade Federal de Goiás, Programa de Pós-graduação em Ciência da Computação (INF), UFG, Brasil, Instituto de Informática - INF (RG)
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguagePortuguese
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis
Formatapplication/pdf
Sourcereponame:Biblioteca Digital de Teses e Dissertações da UFG, instname:Universidade Federal de Goiás, instacron:UFG
Rightshttp://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess
Relation-3303550325223384799, 600, 600, 600, 600, -7712266734633644768, 3671711205811204509, 2075167498588264571

Page generated in 0.0028 seconds