Towards strong duality in integer programming

Towards strong duality in integer programming

0.00 Avg rating0 Votes
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: ,
Keywords: duality
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.

Reviews

Required fields are marked *. Your email address will not be published.