Exact augmented Lagrangian duality for mixed integer linear programming (Q507329): Difference between revisions

This paper deals with mixed integer linear programming problems of the form \[ z^{IP}:=\inf \left\{ c^{T}x:Ax=b,x\in X\right\}, \] where \(X=\left\{ x\in \mathbb{Z}^{p}\times \mathbb{R}^{q}:Ex\leq f\right\} ,\) with \(p+q=n,\) \(A\in \mathbb{Q}^{m\times n},\) \(E\in \mathbb{Q}^{r\times n},\) \( b\in \mathbb{Q}^{m},\) and \(f\in \mathbb{Q}^{r}.\;\)The linear system \(Ax=b\) contains the complicating constraints to be dualized. The augmented Lagrangian dual has the form \[ z_{\rho }^{LD_{+}}:=\sup_{\lambda \in \mathbb{R}^{n}}\inf_{x\in X}\left\{ c^{T}x+\lambda ^{T}\left( b-Ax\right) +\rho \psi \left( b-Ax\right) \right\}, \] where the \textit{penalty coefficient} \(\rho \) is a given positive scalar and the \textit{augmenting function} \(\psi \) satisfies \(\psi \left( 0_{m}\right) =0 \) and \(\psi \left( u\right) >0\) for all \(u\neq 0_{m}.\) The purpose of the summand \(\rho \psi \left( b-Ax\right) \) is to reduce the duality gap in the non-convex setting. Under certain conditions, depending on the choice of \( \psi ,\) a zero duality gap can be reached asymptotically by making \(\rho \longrightarrow +\infty \) or even it can be attained by taking a sufficient large \(\rho ,\) in which case \(z_{\rho }^{LD_{+}}\) is said to be \textit{exact}. In this paper, inspired in [\textit{N. L. Boland} and \textit{A. C. Eberhard}, Math. Program. 150, No. 2 (A), 491--509 (2015; Zbl 1346.90607), Proposition 3], the authors assume that \(z^{IP}\in \mathbb{R}\)\ and \(\psi \) belongs to the class of the so-called non-negative level bounded augmenting functions. The main contributions of the paper are improvements of results in the inspiring paper: 1. It is shown that \(z_{\rho }^{LD_{+}}\) can be seen as a classical Lagrangian dual in some lifted space. 2. A new proof is given of the known fact that the zero duality gap can be reached asymptotically. 3. It is proven, without assuming that \(X\) is a bounded subset of \(\mathbb{Z} ^{n},\) that \(z_{\rho }^{LD_{+}}\) is exact when \(\psi \) is an arbitrary norm. 4. An example of \(z_{\rho }^{LD_{+}}\)\ is given showing that a quadratic augmenting function is not able to close the duality gap for any finite penalty coefficient.