Towards Strong Duality in Integer Programming |
| |
Authors: | D Li X L Sun |
| |
Institution: | (1) Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, NT, Hong Kong;(2) Department of Mathematics, Shanghai University, Baoshan, Shanghai, 200444, P. R. China |
| |
Abstract: | 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 pth power to the constraints. We prove that this reformulation possesses an asymptotic strong duality property. Primal feasibility
and primal optimality of the Lagrangian relaxation problems can be achieved in this reformulation when the parameter p is larger than a threshold value, thus ensuring the existence of an optimal primal-dual pair. We further show that duality
gap for this partial pth power reformulation is a strictly decreasing function of p in the case of a single constraint.
Dedicated to Professor Alex Rubinov on the occasion of his 65th birthday. Research supported by the Research Grants Council
of Hong Kong under Grant CUHK 4214/01E, and the National Natural Science Foundation of China under Grants 79970107 and 10571116. |
| |
Keywords: | asymptotic strong duality integer programming Lagrangian duality pth power reformulation |
本文献已被 SpringerLink 等数据库收录! |
|