[pt] ANÁLISE CONVEXA E MÉTODOS LIFT-AND-PROJECT PARA PROGRAMAÇÃO INTEIRA

• Ano de defesa: 2001
• Autor(a) principal: PABLO ANDRES REY
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: MAXWELL
• Palavras-chave em Português: [pt] LIFT-AND-PROJECT; [pt] SISTEMA DE TRIPLA DE STEINER; [pt] SIMETRIA; [pt] OTIMIZACAO NAO-DIFERENCIAVEL; [pt] METODO DE FEIXE PROXIMAL; [pt] FUNCAO GAUGE; [pt] FUNCAO SUPORTE; [pt] PROGRAMACAO INTEIRA 0-1; [pt] CORTE DIJUNTIVO; [en] LIFT-AND-PROJECT; [en] STEINER TRIPLE SYSTEM; [en] SIMETRY; [en] NON SMOOTH OPTIMIZATION; [en] PROXIMAL BUNDLE METHOD; [en] GAUGE FUNCTIONS; [en] SUPPORT FUNCTION; [en] 0-1 INTEGER PROGRAMMING; [en] DISJUNCTIVE CUT
• Link de acesso: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=1794&idi=1; https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=1794&idi=2; https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=1794&idi=4; http://doi.org/10.17771/PUCRio.acad.1794

[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.