A Customized Augmented Lagrangian Method for Block-Structured Integer Programming
- 19 June 2024
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Pattern Analysis and Machine Intelligence
- Vol. 46 (12) , 9439-9455
Abstract
Integer programming with block structures has received considerable attention recently and is widely used in many practical applications such as train timetabling and vehicle routing problems. It is known to be NP-hard due to the presence of integer variables. We define a novel augmented Lagrangian function by directly penalizing the inequality constraints and establish the strong duality between the primal problem and the augmented Lagrangian dual problem. Then, a customized augmented Lagrangian method is proposed to address the block-structures. In particular, the minimization of the augmented Lagrangian function is decomposed into multiple subproblems by decoupling the linking constraints and these subproblems can be efficiently solved using the block coordinate descent method. We also establish the convergence property of the proposed method. To make the algorithm more practical, we further introduce several refinement techniques to identify high-quality feasible solutions. Numerical experiments on a few interesting scenarios show that our proposed algorithm often achieves a satisfactory solution and is quite effective.Keywords
Funding Information
- National Natural Science Foundation of China (12331010, 72150001, 72225009, 72394360, 72394365)
This publication has 40 references indexed in Scilit:
- The blockwise coordinate descent method for integer programsMathematical Methods of Operations Research, 2019
- On Block-Structured Integer Programming and Its Applications2019
- Alternating direction method of multipliers as a simple effective heuristic for mixed-integer nonlinear optimizationStructural and Multidisciplinary Optimization, 2018
- Exact augmented Lagrangian duality for mixed integer linear programmingMathematical Programming, 2016
- Integer Programming2014
- Proximal alternating linearized minimization for nonconvex and nonsmooth problemsMathematical Programming, 2013
- Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methodsMathematical Programming, 2011
- An Automatic Method for Solving Discrete Programming Problems2009
- Lagrangean relaxation for integer programming1974
- Partitioning procedures for solving mixed-variables programming problemsNumerische Mathematik, 1962