  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.
