  This paper introduces two decomposition-based methods for two-block
mixed-integer linear programs (MILPs), which aim to take advantage of separable
structures of the original problem by solving a sequence of lower-dimensional
MILPs. The first method is based on the $\ell_1$-augmented Lagrangian method
(ALM), and the second one is based on a modified alternating direction method
of multipliers (ADMM). In the presence of certain block-angular structures,
both methods create parallel subproblems in one block of variables, and add
nonconvex cuts to update the other block; they converge to globally optimal
solutions of the original MILP under proper conditions. Numerical experiments
on three classes of MILPs demonstrate the advantages of the proposed methods on
structured problems over the state-of-the-art MILP solvers.
