| Journal: | Pesquisa operacional |
| Database: | PERIÓDICA |
| System number: | 000313025 |
| ISSN: | 0101-7438 |
| Authors: | Espejo, Luis Gonzalo Acosta1 Galvao, Roberto D1 |
| Institutions: | 1Universidade Federal do Rio de Janeiro, Instituto Alberto Luiz Coimbra de Pos-Graduacao e Pesquisa de Engenharia, Rio de Janeiro. Brasil |
| Year: | 2002 |
| Season: | Jul-Dic |
| Volumen: | 22 |
| Number: | 3 |
| Pages: | 387-402 |
| Country: | Brasil |
| Language: | Portugués |
| Document type: | Artículo |
| Approach: | Analítico, descriptivo |
| English abstract | Relaxations of an integer programming problem produce bounds on its optimal solution. The linear programming, Lagrangean, surrogate and combined Lagrangean-surrogate (L-S) relaxations are the most commonly used in the solution of an integer programming problem. We present a brief review of these relaxations, solution methods for the respective duals and theoretical relationships that exist among them. We give special emphasis to surrogate and combined L-S relaxations. The use of a combined L-S relaxation is illustrated through its application to a hierarchical covering location problem |
| Portuguese abstract | As diferentes relaxações de um problema de programação inteira permitem que se obtenham limites da solução ótima do mesmo. Entre as relaxações mais usadas destacam-se as de programação linear, Lagrangeana, surrogate e combinada Lagrangeana-surrogate (L-S). O presente trabalho contém uma revisão bibliográfica destas relaxações, de métodos de solução para os duais respectivos e de relações teóricas existentes entre os duais. É dada ênfase especial à relaxação surrogate e a relaxações combinadas Lagrangeana-surrogate. Ilustra-se o uso de uma relaxação combinada L-S através da aplicação da mesma a um problema de localização hierárquico com restrições de cobertura |
| Disciplines: | Matemáticas |
| Keyword: | Matemáticas aplicadas, Relajación lagrangiana, Programación entera |
| Keyword: | Mathematics, Applied mathematics, Lagrangian relaxation, Integer programming |
| Full text: | Texto completo (Ver HTML) |
