Box ADMM: A Versatile Framework for Integer Programming

Baoyuan Wu*, Bernard Ghanem

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

66 Scopus citations

Abstract

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, since many of these methods are designed to solve specific IP forms, they cannot adequately satisfy the simultaneous requirements of accuracy, feasibility, and scalability. To this end, we propose a novel and versatile framework called $\ell-p$â.,"p-box ADMM, which is based on two main ideas. (1) The discrete constraint is equivalently replaced by the intersection of a box and an $\ell-p$â.,"p-norm sphere. (2) We infuse this equivalence into the Alternating Direction Method of Multipliers (ADMM) framework to handle the 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 apply it to an optimization form that occurs often in computer vision and machine learning, namely binary quadratic programming (BQP). In this case, the ADMM steps are simple, computationally efficient. Moreover, we present the theoretic analysis about the global convergence of the $\ell-p$â.,"p-box ADMM through adding a perturbation with the sufficiently small factor $\epsilon$ϵ to the original IP problem. Specifically, the globally converged solution generated by $\ell-p$â.,"p-box ADMM for the perturbed IP problem will be close to the stationary and feasible point of the original IP problem within $O(\epsilon)$O(ϵ). We demonstrate the applicability of $\ell-p$â.,"p-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 to state-of-the-art methods designed specifically for these applications.

Original languageEnglish (US)
Article number8378001
Pages (from-to)1695-1708
Number of pages14
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Volume41
Issue number7
DOIs
StatePublished - Jul 1 2019

Bibliographical note

Publisher Copyright:
© 1979-2012 IEEE.

Keywords

  • ADMM
  • Integer programming
  • computer vision
  • machine learning
  • nonconvex optimization

ASJC Scopus subject areas

  • Software
  • Artificial Intelligence
  • Applied Mathematics
  • Computer Vision and Pattern Recognition
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Box ADMM: A Versatile Framework for Integer Programming'. Together they form a unique fingerprint.

Cite this