  This paper revisits the integer programming (IP) problem, which plays a
fundamental role in many computer vision and machine learning applications. The
literature abounds with many seminal works that address this problem, some
focusing on continuous approaches (e.g. linear program relaxation) while others
on discrete ones (e.g., min-cut). However, a limited number of them are
designed to handle the general IP form and even these methods cannot adequately
satisfy the simultaneous requirements of accuracy, feasibility, and
scalability. To this end, we propose a novel and versatile framework called
$\ell_p$-box ADMM, which is based on two parts. (1) The discrete constraint is
equivalently replaced by the intersection of a box and a $(n-1)$-dimensional
sphere (defined through the $\ell_p$ norm). (2) We infuse this equivalence into
the ADMM (Alternating Direction Method of Multipliers) framework to handle
these continuous constraints separately and to harness its attractive
properties. More importantly, the ADMM update steps can lead to manageable
sub-problems in the continuous domain. To demonstrate its efficacy, we consider
an instance of the framework, namely $\ell_2$-box ADMM applied to binary
quadratic programming (BQP). Here, the ADMM steps are simple, computationally
efficient, and theoretically guaranteed to converge to a KKT point. We
demonstrate the applicability of $\ell_2$-box ADMM on three important
applications: MRF energy minimization, graph matching, and clustering. Results
clearly show that it significantly outperforms existing generic IP solvers both
in runtime and objective. It also achieves very competitive performance vs.
state-of-the-art methods specific to these applications.
