JG
Jianjun Gao
Author with expertise in Scheduling Problems in Manufacturing Systems
Achievements
This user has not unlocked any achievements yet.
Key Stats
Upvotes received:
0
Publications:
3
(33% Open Access)
Cited by:
0
h-index:
16
/
i10-index:
22
Reputation
Biology
< 1%
Chemistry
< 1%
Economics
< 1%
Show more
How is this calculated?
Publications
0

A Customized Augmented Lagrangian Method for Block-Structured Integer Programming

Rui Wang et al.Jan 1, 2024
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.