Exact augmented Lagrangian duality for mixed integer linear programming
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.
- Exact augmented Lagrangian duality for mixed integer quadratic programming
- On the augmented Lagrangian dual for integer programming
- Augmented Lagrangian algorithms for linear programming
- Augmented Lagrangian duality for composite optimization problems
- Duality for mixed-integer linear programs
- scientific article; zbMATH DE number 1552021
- An exact augmented Lagrangian function for nonlinear programming problems with inequality constraints
- Exact augmented Lagrangian functions for nonlinear semidefinite programming
- Duality in nonlinear programs using augmented Lagrangian functions
- Partial augmented Lagrangian method and mathematical programs with complementarity constraints
- A geometric framework for nonconvex optimization duality using augmented Lagrangian functions
- A New Approach to Lagrange Multipliers
- A nonlinear Lagrangian approach to constrained optimization problems
- A Unified Augmented Lagrangian Approach to Duality and Exact Penalization
- Abstract Convexity and Augmented Lagrangians
- An Exact Penalization Viewpoint of Constrained Optimization
- Augmented Lagrange Multiplier Functions and Duality in Nonconvex Programming
- Calmness and Exact Penalization
- Decreasing Functions with Applications to Penalization
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Duality and exact penalization for general augmented Lagrangians
- scientific article; zbMATH DE number 3914081 (Why is no real title available?)
- scientific article; zbMATH DE number 3614502 (Why is no real title available?)
- scientific article; zbMATH DE number 2121575 (Why is no real title available?)
- scientific article; zbMATH DE number 1416629 (Why is no real title available?)
- Integer and mixed-integer programming models: General properties
- Lagrange-type functions in constrained non-convex optimization.
- Mathematical Programs with Equilibrium Constraints
- Nonlinear Augmented Lagrangian and Duality Theory
- On the absence of duality gap for Lagrange-type functions
- On the augmented Lagrangian dual for integer programming
- On the existence of optimal solutions to integer and mixed-integer programming problems
- Penalty functions with a small penalty parameter
- Penalty/Barrier Multiplier Methods for Convex Programming Problems
- Separation of Nonconvex Sets with General Augmenting Functions
- The exact penalty map for nonsmooth and nonconvex optimization
- The value function of a mixed integer program. II
- The value function of a mixed integer program: I
- The value function of an integer program
- The Zero Duality Gap Property and Lower Semicontinuity of the Perturbation Function
- Variational Analysis
- Dual formulations and subgradient optimization strategies for linear programming relaxations of mixed-integer programs
- A progressive hedging based branch-and-bound algorithm for mixed-integer stochastic programs
- A parallelized variable fixing process for solving multistage stochastic programs with progressive hedging
- Special issue: Global solution of integer, stochastic and nonconvex optimization problems
- Revisiting augmented Lagrangian duals
- Stochastic dual dynamic programming for multistage stochastic mixed-integer nonlinear optimization
- Non-convex nested Benders decomposition
- Stochastic Lipschitz dynamic programming
- An augmented Lagrangian proximal alternating method for sparse discrete optimization problems
- On the augmented Lagrangian dual for integer programming
- On Subadditive Duality for Conic Mixed-integer Programs
- Exact augmented Lagrangian duality for mixed integer quadratic programming
- Combining penalty‐based and Gauss–Seidel methods for solving stochastic mixed‐integer problems
- Joint tank container demurrage policy and flow optimisation using a progressive hedging algorithm with expanded time-space network
- First-order methods for convex optimization
- A study of progressive hedging for stochastic integer programming
- Decomposition methods for global solution of mixed-integer linear programs
- Exact augmented Lagrangian duality for mixed integer convex optimization
- Lagrangian dual for integer optimization with zero duality gap that admits decomposition
- Convergence analysis of primal-dual augmented Lagrangian methods and duality theory
- Stochastic dual dynamic programming and its variants: a review
- On coupling constraints in linear bilevel optimization
- Multistage stochastic optimization for mid-term integrated generation and maintenance scheduling of cascaded hydroelectric system with renewable energy uncertainty
- Sensitivity analysis for mixed binary quadratic programming
- Two-stage robust mixed integer programming problem with objective uncertainty
- Sensitivity analysis for mixed binary quadratic programming
- The augmented Lagrangian methods: overview and recent advances
- An augmented Lagrangian decomposition method for the single-source capacitated facility location problem
This page was built for publication: Exact augmented Lagrangian duality for mixed integer linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q507329)
