Revista: | Pesquisa operacional |
Base de datos: | PERIÓDICA |
Número de sistema: | 000313045 |
ISSN: | 0101-7438 |
Autores: | Lorena, Luiz A.N1 Pereira, Marcos A Salomao, Silvely N.A2 |
Instituciones: | 1Instituto Nacional de Pesquisas Espaciais, Laboratorio Associado de Computacao e Matematica Aplicada, Sao Jose dos Campos, Sao Paulo. Brasil 2Universidade Estadual Paulista "Julio de Mesquita Filho", Faculdade de Ciencias e Tecnologia, Presidente Prudente, Sao Paulo. Brasil |
Año: | 2003 |
Periodo: | Ene-Abr |
Volumen: | 23 |
Número: | 1 |
Paginación: | 29-47 |
País: | Brasil |
Idioma: | Portugués |
Tipo de documento: | Artículo |
Enfoque: | Analítico, descriptivo |
Resumen en inglés | Column generation and Dantzig-Wolfe decomposition are very successful methods for large-scale linear programming problems. It is also well known the instability of the overall process. Stabilizing methods work constraining the norm of the dual vector arising from restricted masters. This work shows how to combine the Lagrangean/surrogate relaxation and column generation aiming a stabilized method |
Resumen en portugués | Os métodos de geração de colunas e o de decomposição de Dantzig-Wolfe ficaram conhecidos como métodos eficientes para o tratamento de problemas de programação linear com grande número de variáveis. Um problema mestre restrito é identificado e novas colunas são geradas através de um subproblema. Também é bem conhecido que estes métodos sofrem de problemas de estabilização. Para amenizar estes problemas, as variáveis duais tem sido controladas de várias maneiras, em geral, restringindo sua norma para evitar grandes variações. A relaxação Lagrangeana/surrogate foi proposta recentemente para estabilização de métodos subgradientes. Considera-se neste trabalho a combinação do método de geração de colunas e a relaxação Lagrangeana/surrogate como uma proposta de estabilização. Alguns resultados computacionais são apresentados para problemas de p-medianas e várias aplicações são sugeridas. Algumas questões em aberto são levantadas para futura pesquisa |
Disciplinas: | Matemáticas |
Palabras clave: | Matemáticas aplicadas, Métodos de estabilización, Relajación lagrangiana, Generación de columnas |
Keyword: | Mathematics, Applied mathematics, Stabilizing methods, Lagrangian relaxation, Column generation |
Texto completo: | Texto completo (Ver HTML) |