[pt] Este trabalho consiste da aplicação de métodos de planos de corte (euclideano acelerado e cortes disjuntivos) na solução de problemas de programação inteira pura do tipo 0- 1 e suas especializações para o problemas de particionamento, quando combinados com técnicas de penalidades para fixação de variáveis. Desenvolve-se um estudo de técnicas de penalidades, que permitem fixar variáveis a valores inteiros a partir da solução ótima da relaxação linear do problema inteiro. As variáveis fixadas são eliminadas do problema e este é reescrito, tendo suas dimensões originais reduzidas. Sugerem-se melhorias no cálculo destas penalidades, levando-se em conta a estrutura particular do problema de particionamento. Finalmente, propõe-se um novo enfoque para a solução de problemas de particionamento: um algoritmo de planos de corte que utiliza técnicas de penalidades, com a finalidade de acelerar a convergência dos métodos puros de planos de corte e de reduzir os problemas por estes apresentados. Resultados computacionais são apresentados, comparando-se o desempenho (i) do algoritmo euclideano acelerado, (ii) do algoritmo de cortes disjuntivos e (iii) do algoritmo de cortes disjuntivos utilizando-se técnicas de penalidades. Para este último algoritmo, são comparados os resultados obtidos utilizando-se técnicas de penalidades genéricas para problemas inteiros do tipo 0-1 e as melhorias destas penalidades, especificas para problemas de particionamento. Considerando-se o problemas de particionamento e as melhorias propostas no cálculo de penalidades, mostra-se que é, freqüentemente, possível fixar um maior número de variáveis ou até mesmo resolver-se diretamente o problema 0-1 original. Em alguns casos, ao aplicar-se o algoritmo de planos de corte com técnicas de penalidades não só pode- se acelerar a convergência, como também superar os problemas de degenerescência dual e erros por arredondamento apresentados pelos algoritmos puros de plano de corte. / [en] This work consists on the application of cutting plane techniques (accelerated euclidean algorithm and disjunctive cuts) for solving pure 0-1 integer problems and their specializations for the set partitioning problem, when combined to penalty techniques for fixing variables. A study on penalty techniques, which allows the fixation of variables to integer values, is also developed. These penalties are directly derived from the optimal tableau nof the linear relaxation of the integer problem. The variables fixed due to penalties are eliminated and the problem is reformulated, having its initial dimensions reduced. Some improvements on the evaluation of penalties are suggested, taking into account the special structure of the set partitioning problem. Finally, a new approach to the solution of set partitioning problems is proposed: a cutting plane algorithm which uses penalty techniques, in order to accelerate the convergence of pure cutting plane methods and overcome the problems arising from their use. Computational results are shown, allowing to compare the performance of (i) the accelerated euclidean algorithm, (ii) the disjunctive cut algorithm and (iii) the last one combined with penalty techniques. For the latter, the results obained by the use of generic penalties for 0-1 integer programs are compared with those obtained by the use of the improved penalties for ser partitioning problems. Taking into account set partitioninng problems and the improvements proposed for the evaluation of penalties, it is shown that very often it is possible to fix more variables to integer values and even to solve directly the original 0-1 problem. For some cases, by applying the cutting plane algorithm together with penalties, it is possible to accelerate the convergence and overcome dual degeneracy and round-off errors arising from the use of pure cutting plane algorithms.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-02-24T14:20:45Z No. of bitstreams: 1 rafaeldepaulagarcia.pdf: 1337243 bytes, checksum: b838edc08b3d115cfea5624cd3881538 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-02-24T15:39:22Z (GMT) No. of bitstreams: 1 rafaeldepaulagarcia.pdf: 1337243 bytes, checksum: b838edc08b3d115cfea5624cd3881538 (MD5) / Made available in DSpace on 2017-02-24T15:39:22Z (GMT). No. of bitstreams: 1 rafaeldepaulagarcia.pdf: 1337243 bytes, checksum: b838edc08b3d115cfea5624cd3881538 (MD5) Previous issue date: 2014-02-14 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A aplicação de metaheurísticas em problemas reais com restrições não é possível sem ajustes. Esta impossibilidade é devida ao fato delas serem desenvolvidas, em sua essência, para resolver problemas de otimização irrestritos. Esses ajustes são feitos por meio de técnicas que abordam as restrições apresentadas no problema. Técnicas de Penalização são comuns, transformando um problema de otimização restrito em um problema de otimização irrestrito, adicionando uma penalidade para a função aptidão das soluções infactíveis. Esta dissertação considera uma técnica que adapta o valor do coeficiente de penalização de cada restrição usando informações da população, tais como a média da função de objetivo e o nível de violação em cada restrição. Esta técnica é conhecida como Método de Penalizaçao Adaptativa (ou simplesmente APM). Existem na literatura várias variantes para o APM que podem ser sintetizadas como: APM Esporádico que mantém os coeficientes de penalização fixados em um número fixo de gerações, uma segunda abordagem semelhante à primeira, mas que acumula valores das violações; variante chamada APM Monotônico, que é semelhante ao APM original, mas que não permite que os coeficientes de penalização sejam reduzidos ao longo do processo evolutivo e variante APM Amortecida, que usa uma média ponderada dos valores atuais e anteriores dos coeficientes de penalização. Novas variantes para o APM são propostas nesta dissertação com a finalidade de buscar melhorias para o APM original. O desempenho destas novas variantes é examinado usando funções teste e problemas de engenharia mecânica e estrutural. Comparações são realizadas utilizando perfis de desempenho, que permitem identificar mais claramente a robustez dessas variantes apontando as melhores. / The application of metaheuristics on real problems with constraints is not possible without adjustments. This impossibility is due to the fact that they are developed, in their essence, to solve unconstrained optimization problems. These adjustments are made by techniques that address the constraints present in the problem. Penalty Techniques are common, transforming a constrained optimization problem into an unconstrained optimization problem, adding a penalty to the fitness function of infeasible solutions. This thesis considers a technique that adapts the value of the penalty coefficient of each constraint using the information of the population, such as the average of the objective function and the level of violation of each constraint. This technique is known as Adaptive Penalty Method (or simply APM). There are in the literature, several variants for the APM and they can be synthesized as: Sporadic APM which holds the fixed penalty coefficients for a fixed number of generations, a second approach similar to the first, but accumulating values of the violations; the variant entitled Monotonic APM, which is similar to the original APM but not allowing the penalty coefficients be reduced along the evolutionary process and the variant damped APM, which uses a weighted average of the current and previous values of the penalty coefficients. New variants for the APM are proposed in this thesis in order reach improvements in the original APM. The performance of these new variants is examined using test-functions and problems of mechanical and structural engineering. Comparisons are conducted using performance profiles, which allow to identify more clearly the robustness of these variants pointing out the best ones.