Exact augmented Lagrangian duality for mixed integer linear programming

详细信息    查看全文

• 作者：Mohammad Javad Feizollahi ; Shabbir Ahmed ; Andy Sun
• 关键词：Mixed integer linear programming ; Lagrangian duality ; Penalty functions
• 刊名：Mathematical Programming
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：161
• 期：1-2
• 页码：365-387
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Calculus of Variations and Optimal Control; Optimization; Mathematics of Computing; Numerical Analysis; Combinatorics; Theoretical, Mathematical and Computational Physics; Mathematical Methods in Phys
• 出版者：Springer Berlin Heidelberg
• ISSN：1436-4646
• 卷排序：161

文摘

We investigate the augmented Lagrangian dual (ALD) for mixed integer linear programming (MIP) problems. ALD modifies the classical Lagrangian dual by appending a nonlinear penalty function on the violation of the dualized constraints in order to reduce the duality gap. We first provide a primal characterization for ALD for MIPs and prove that ALD is able to asymptotically achieve zero duality gap when the weight on the penalty function is allowed to go to infinity. This provides an alternative characterization and proof of a recent result in Boland and Eberhard (Math Program 150(2):491–509, 2015, Proposition 3). We further show that, under some mild conditions, ALD using any norm as the augmenting function is able to close the duality gap of an MIP with a finite penalty coefficient. This generalizes the result in Boland and Eberhard (2015, Corollary 1) from pure integer programming problems with bounded feasible region to general MIPs. We also present an example where ALD with a quadratic augmenting function is not able to close the duality gap for any finite penalty coefficient.