[pt] Algoritmos para a resolução de problemas de programação
mista 0-1 gerais baseados em cortes derivados dos métodos
lift-and-project, tem se mostrado bastante eficientes na
prática. Estes cortes são gerados resolvendo um problema
que depende de uma certa normalização. Desde um ponto de
vista teórico, o bom comportamento destes algoritmos não
foi completamente compreendido, especialmente no que diz
respeito à normalização. Neste trabalho consideramos
normalizações gerais definidas por um conjunto convexo
fechado arbitrário, estendendo assim a análise teórica
desenvolvida nos anos noventa. Apresentamos um marco
teórico que abarca todas as normalizações previamente
estudadas e introduzimos novas normalizações, analisando
as propriedades dos cortes associados.Introduzimos também
uma nova fórmula de atualização do parâmetro proximal
para uma variante dos métodos de feixes. Estes métodos
são bem conhecidos pela sua eficiência na resolução de
problemas de otimização não diferenciável. Por último,
propomos uma metodologia para eliminr soluções
redundantes de programas inteiros combinatórios. Nossa
proposta baseia-se na utilização da informação de
simetria do problema, eliminam a simetria sem prejudicar
a solução do problema inteiro. / [en] Algorithms for general 0-1 mixed integer programs can be
successfully developed by using lift-and-project methods to
generate cuts. Cuts are generated by solving a cut-
generation-program that depends on a certain normalization.
From a theoretical point of view, the good numerical
behavior of these cuts is not completely understood yet,
specially, concerning to the normalization chosen. We
consider a general normalization given by an arbitrary
closed convex set, extending the theory developed in the
90's. We present a theoretical framework covering a wide
group of already known normalizations. We also introduce
new normalizations and analyze the properties of the
associated cuts. In this work, we also propose a new
updating rule for the prox parameter of a variant of the
proximal bundle methods, making use of all the information
available at each iteration. Proximal bundle methods are
well known for their efficiency in nondifferentiable
optimization. Finally, we introduce a way to eliminate
redundant solutions ( due to geometrical symmetries ) of
combinatorial integer program. This can be done by using
the information about the problem symmetry in order to
generate inequalities, which added to the formulation of
the problem, eliminate this symmetry without affecting
solution of the integer problem. / [es] Los algoritmos para la resolución de problemas de programación mixta 0-1 generales que utilizan
cortes derivados de los métodos lift-and-project, se han mostrado bastante eficientes en la práctica.
Estos cortes se generan resolviendo un problema que depende de una cierta normalización. Desde el
punto de vista teórico, el buen comportamiento de estos algoritmos no fue completamente
comprendido, especialmente respecto a la normalización. En este trabajo consideramos
normalizaciones generales definidas por un conjunto convexo cerrado arbitrario, extendiendo así el
análisis teórico desarrollado en los años noventa. Presentamos un marco teórico que abarca todas las
normalizaciones previamente estudiadas e introducimos nuevas normalizaciones, analizando las
propiedades de los cortes asociados. Introducimos una nueva fórmula de actualización del parámetro
de. Estoss métodos son bien conocidos por su eficiencia en la resolución de problemas de
optimización no diferenciable. Por último, proponemos una metodología para eliminar soluciones
redundantes de programas enteros combinatorios. Nuestra propuesta se basa en la utilización de la
información de simetría del problema, eliminan la simetría sin perjudicar la solución del problema
entero.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:1794 |
| Date | 06 August 2001 |
| Creators | PABLO ANDRES REY |
| Contributors | OSCAR PORTO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Spanish |
| Type | TEXTO |
Page generated in 0.003 seconds