  This paper introduces two decomposition-based methods for two-block
mixed-integer linear programs (MILPs), which break the original problem into a
sequence of smaller MILP subproblems. The first method is based on the
l1-augmented Lagrangian. The second method is based on the alternating
direction method of multipliers. When the original problem has a block-angular
structure, the subproblems of the first block have low dimensions and can be
solved in parallel. We add reverse-norm cuts and augmented Lagrangian cuts to
the subproblems of the second block. For both methods, we show asymptotic
convergence to globally optimal solutions and present iteration upper bounds.
Numerical comparisons with recent decomposition methods demonstrate the
exactness and efficiency of our proposed methods.
