Article ID: | iaor2007412 |
Country: | Netherlands |
Volume: | 35 |
Issue: | 2 |
Start Page Number: | 255 |
End Page Number: | 282 |
Publication Date: | Jun 2006 |
Journal: | Journal of Global Optimization |
Authors: | Li D., Sun X.L. |
Keywords: | duality |
We consider in this paper the Lagrangian dual method for solving general integer programming. New properties of Lagrangian duality are derived by a means of perturbation analysis. In particular, a necessary and sufficient condition for a primal optimal solution to be generated by the Lagrangian relaxation is obtained. The solution properties of Lagrangian relaxation problem are studied systematically. To overcome the difficulties caused by duality gap between the primal problem and the dual problem, we introduce an equivalent reformulation for the primal problem via applying a