COVERING CODES: BOUNDS AND HEURISTICS / CÓDIGOS DE ABERTURA: LIMITES E HEURÍSTICAS
AUTOR(ES)
CARLOS RAONI DE ALENCAR MENDES
DATA DE PUBLICAÇÃO
2009
RESUMO
Data compression, speech coding, móbile telecommunications and error-corretion are some of the practical apllications of the covering codes study, an important field of coding theory. This work addresses two problems of covering codes: the classic code covering problem and the recent short code covering problem. It presents an application of Reactive Tabu Search (RTS) metaheuristic for the problems cited, the RTS is an important variation of the classic Tabu Search. Moreover, it presents a new heuristic technique for solving combinatorial optimization problems named Column Generation Improbement Heuristic (CGIH). It also presents an application of CGIH for the covering codes problems. The CGIH combines the delayed column generation, technique used to solve problems with a large number of decision variables (columns), and local search heuristics. A comparison of results obtained by the Reactive Tabu Search, the Tabu Search without the reaction mechanism and the CGIH is also presented in order to assess the effectivenss of the presented heuristics.
ASSUNTO(S)
combinatorial optimization geracao de colunas metaheuristic otimizacao combinatoria metaeuristica column generation
