Orientador: Prof. Dr. Cláudio Nogueira de Meneses / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2018. / Diversos problemas da area de otimização combinatoria podem ser convertidos, em tempo polinomial, para o problema de Programação Quadratica Binaria Irrestrita (UBQP). Neste problema, desejamos encontrar um vetor solução binario x, de dimensão n, tal que a função objetivo f(x) = x|Qx tenha valor mínimo, onde Q é uma matriz com coeficientes racionais. Em termos de complexidade computacional, o problema UBQP pertence a classe NP-difícil. A importancia deste problema, tanto pratica quanto teorica, tem motivado muitos pesquisadores a dedicarem uma quantidade razoavel de tempo tentando projetar tecnicas de resolução exatas e heuristicas para este problema. Durante o processo de resolução do problema UBQP, estas tecnicas necessitam reavaliar muitas vezes o valor da função objetivo. Dependendo da maneira como esta reavaliação é realizada, pode ser preciso executar um numero relativamente grande de operações elementares (atribuições, adições, subtrações e comparações). Isto pode consumir muito tempo de processamento quando n é grande. Nesta pesquisa, propomos formulas que requerem poucas operações para efetuar a reavaliação. Na literatura do problema UBQP, formulas de reavaliação são aplicadas, normalmente, quando há ate duas alterações nos componentes do vetor solução. As formulas que deduzimos podem ser usadas para efetuar qualquer quantidade de alterações. Analisamos uma das nossas formulas de maneira teorica e deduzimos funções que podem ser adotadas para indicar o melhor momento para aplicar essa formula. Ademais, projetamos algoritmos com estas formulas de reavaliação e verificamos a praticidade destes algoritmos conduzindo experimentos computacionais usando implementações de heurísticas de busca
local e Variable Neighborhood Search. Nesses experimentos comparamos o desempenho dessas implementações ao resolver instancias da literatura para o problema UBQP. Os resultados experimentais evidenciaram que as formulas de reavaliação, propostas, podem propiciar reduções relativamente grandes nos tempos de processamento, mesmo quando o numero de diferenças entre soluções é moderadamente grande. / Several combinatorial optimization problems can be reformulated, in polynomial time, to the
Unconstrained Binary Quadratic Programming (UBQP) problem. In this problem, we are interested in finding an n-dimensional binary solution vector, x, that minimizes the objective function f(x) = x|Qx, where Q is a matrix with rational coecients. In terms of computational complexity, the UBQP problem belongs to the NP-hard class. The practical and theoretical importance of this problem has motivated many researchers to dedicate a reasonable amount of time developing exact and heuristic solution techniques to solve this problem. During the resolution process of the UBQP problem, these techniques need to evaluate many times the objective function value.
Depending on how it is made, it may be necessary to execute a relatively large number of elementary operations, such as assignments, additions, subtractions and comparisons. For n large, this may be time consuming. In this research, we propose formulas to perform the reevaluation requiring lesser operations than the simple evaluation of the objective function. In the literature of the UBQP problem, it is common to use reevaluation formulas only when there are at most two-
ip moves that simultaneously change the values of two components. The formulas we have deduced can be used to evaluate any number of
ip moves. We analyzed one of our reevaluation formulas and deduced functions that can be used to suggest the best moment to apply this formula. In addition, we designed algorithms with these reevaluation formulas and verified the practicality of these algorithms by conducting computational experiments using implementations of local search and Variable Neighborhood Search heuristics. In these experiments, we compared the performance of these implementations by solving benchmark instances for the UBQP problem.
The experimental results showed that the reevaluation formulas we created can provide relatively large reductions in processing times, even when the number of
ip moves is moderately large.
| Identifer | oai:union.ndltd.org:IBICT/oai:BDTD:109131 |
| Date | January 2018 |
| Creators | Anacleto, Eduardo Alves de Jesus |
| Contributors | Meneses, Cláudio Nogueira de, Song, Siang Wun, Martins Junior, David Corrêa |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf, 179 f. : il. |
| Source | reponame:Repositório Institucional da UFABC, instname:Universidade Federal do ABC, instacron:UFABC |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | http://biblioteca.ufabc.edu.br/index.php?codigo_sophia=109131&midiaext=75617, http://biblioteca.ufabc.edu.br/index.php?codigo_sophia=109131&midiaext=75618, Cover: http://biblioteca.ufabc.edu.brphp/capa.php?obra=109131 |
Page generated in 0.0031 seconds