Some relationships between lagrangian and surrogate duality in integer programming |
| |
Authors: | Mark H. Karwan Ronald L. Rardin |
| |
Affiliation: | (1) Industrial Engineering, State University of New York at Buffalo, Amherst, NY, USA;(2) Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA |
| |
Abstract: | Lagrangian dual approaches have been employed successfully in a number of integer programming situations to provide bounds for branch-and-bound procedures. This paper investigates some relationship between bounds obtained from lagrangian duals and those derived from the lesser known, but theoretically more powerful surrogate duals. A generalization of Geoffrion's integrality property, some complementary slackness relationships between optimal solutions, and some empirical results are presented and used to argue for the relative value of surrogate duals in integer programming. These and other results are then shown to lead naturally to a two-phase algorithm which optimizes first the computationally easier lagrangian dual and then the surrogate dual. |
| |
Keywords: | Integer Programming Surrogate Duality Lagrangian Relaxation Lagrangian Duality Surrogate Constraint |
本文献已被 SpringerLink 等数据库收录! |
|