Algoritmos e modelos matemáticos para o problema da k-partição de números

Página do item simplificado
dc.contributor.advisorSouza, Sérgio Ricardo de
dc.contributor.advisor-coSilva, Carlos Alexandre
dc.contributor.advisor-coLatteshttp://lattes.cnpq.br/8465270749629421
dc.contributor.advisorLatteshttp://lattes.cnpq.br/3677015295211434
dc.contributor.authorFaria, Alexandre Frias
dc.contributor.authorLatteshttp://lattes.cnpq.br/7284035698082266
dc.contributor.refereeSouza, Sérgio Ricardo de
dc.contributor.refereeSilva, Carlos Alexandre
dc.contributor.refereeColeho, Alessandra Martins
dc.contributor.refereeCardoso, Rodrigo Tomás Nogueira
dc.date.accessioned2025-05-17T00:00:40Z
dc.date.available2025-05-17T00:00:40Z
dc.date.issued2017-02-16
dc.description.abstractEsta dissertação de mestrado apresenta uma formulação matemática e algoritmos para a versão de otimização do Problema da k-Partição de Números. Este problema consiste em distribuir os elementos de uma sequência numérica em k subconjuntos disjuntos, de modo que os resultados das somas dos elementos de cada subconjunto fiquem contidos no menor intervalo possível. A formulação matemática proposta é baseada em dois problemas semelhantes da literatura. Elimina-se a multiplicidade de soluções do modelo de programação inteira, reduzindo ao mínimo o número de variáveis. Mostra-se a NP-completude do problema estudado. Estudam-se algoritmos heurísticos, aproximados e exatos da literatura aplicáveis aos problemas relacionados. Aplica-se a meta-heurística ILS (Iterated Local Search) à solução gerada por um algoritmo aproximado. A estratégia utilizada é aplicar método guloso em todas as fases do algoritmo, tanto na inicialização quanto para a escolha de movimentos do ILS. Propõe-se uma melhoria de métodos exatos Branch-and-Bound aplicados ao problema e presentes na literatura . Esta modificação refina os limitantes do método, usando a relaxação do modelo matemático e ILS propostos. Insere-se um critério de busca para que os nós mais promissores tenham prioridade. Os resultados mostram a solução do ILS superando as soluções de heurísticas construtivas listadas na literatura. A qualidade da solução do ILS é certificada por métodos exatos, um da literatura e outro com as melhorias propostas neste trabalho. As modificações do algoritmo exato se mostram eficazes em uma comparação entre a solução alcançada sobre o número de nós explorados nas duas versões.
dc.description.abstractotherThis dissertation presents a mathematical formulation and algorithms for the optimization version of the Multi-Way Number Partitioning Problem. The problem consists in distributing the elements of a given set into k disjoint subsets such that the sum of each subset elements fits in the shortest interval. The proposed mathematical formulation is based on two similar problems in the literature. The multiplicity of solutions of the integer programming model are eliminated by reducing the number of variables to a minimum. The NP-completeness of the problem studied is shown. Heuristic, approximate and exact algorithms of the literature for related problems are studied. The ILS meta-heuristic (Iterated Local Search) is applied to the solution generated by an approximate algorithm. The strategy is to apply greedy method in all phases of the algorithm, both in initialization and in the choice of ILS movements. It is proposed to improve the exact Branch-and-Bound methods present in the literature. This modification refines the limitations of the method using the relaxation of the proposed mathematical model and ILS. A search criterion is inserted so that the most promising nodes have priority. The results show the solution of ILS overcoming the solutions of constructive heuristics listed in the literature. The quality of the solution ILS is certified by exact methods, one of the literature and another with the improvements proposed in this work. The modifications of the exact algorithm are shown to be effective in comparing the ration between solution achieved and number of nodes exploited in the two versions.
dc.description.sponsorshipCEFET-MG, FAPEMIG, CAPES.
dc.identifier.urihttps://repositorio.cefetmg.br//handle/123456789/1509
dc.language.isopt
dc.publisherCentro Federal de Educação Tecnológica de Minas Gerais
dc.publisher.countryBrasil
dc.publisher.initialsCEFET-MG
dc.publisher.programPrograma de Pós-Graduação em Modelagem Matemática e Computacional
dc.subjectProgramação matemática
dc.subjectOtimização combinatória
dc.subjectHeurística
dc.subjectAlgoritmos
dc.titleAlgoritmos e modelos matemáticos para o problema da k-partição de números
dc.typeDissertação

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Algoritmos e modelos matemáticos para o problema da k-partição de números.pdf
Tamanho:
1.03 MB
Formato:
Adobe Portable Document Format
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
1.39 KB
Formato:
Item-specific license agreed to upon submission
Descrição:
Baixar

Coleções

Mestrado em Modelagem Matemática e Computacional