[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.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:10249 |
| Date | 06 August 2007 |
| Creators | MARCELO PRAIS |
| Contributors | CELSO DA CRUZ CARNEIRO RIBEIRO, CELSO DA CRUZ CARNEIRO RIBEIRO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | English |
| Type | TEXTO |
Page generated in 0.0029 seconds