Lpbox-ADMM (main manuscript, supplementary material) is a generic optimization method for interger programming (IP), and it has been published in TPAMI 2018. This project provides two implementations of Lp-Box ADMM:
- Matlab: full codes and full demos to reproduce all reported results in the manuscript.
- Python: full codes and one simple demo to demonstrate the usage.
IMPORTANT: We have just provided the implementation of Lp-Box ADMM for the BQP problem. However, Lp-Box ADMM can be naturally applied to ANY IP tasks. One can easily implement Lp-Box ADMM for their own IP problems, by simply replacing the provided QP objective in our code by their own objective functions. Welcome to contribute your IP tasks and implementations to this repository.
Since any discrete constraint can be easily transformed to the binary constraint with an additional simplex constraint, in the following we focus on the following problem with binary constraints: $$ \mathop{\min}_x \ f(x) \quad \text{s.t.} \quad x \in { 0,1 }^n, x \in \mathcal{C} $$
We propose to replace the binary constraint with the intersection of two continuous constraints.
$$
{ 0,1 }^n \Leftrightarrow [0,1]^n \cap {||x-\frac{1}{2}||_p^p=\frac{n}{2^p}}
$$
where
The geometric illustration of the constraint equivalence is shown as follows. For clarity, we just show the cases when p={1,2,5}, while p can be any value in the range
We further introduce two extra variables
The above problem can be easily solved by the alternating direction method of multipliers (ADMM).
Since many important applications can be formulated as BQP, in this project we present the demo of using Lp-Box ADMM to solve the BQP problem, which is formulated as follows $$ \mathop{\min}_x \ x^\top Ax+b^\top \quad \text{s.t.} \ x \in {0,1}^n, C_1 x=d_1, C_2 x \leq d_2 $$
which includes the binary constraint, linear equality and inequality constraint.
To facilitate the usages, we provide four python functions for the BQP problems with different constraints.
To use these functions, you just need to import them to your demo, as follows
from functions.lpbox_admm import ADMM_bqp_unconstrained
from functions.lpbox_admm import ADMM_bqp_linear_eq
from functions.lpbox_admm import ADMM_bqp_linear_ineq
from functions.lpbox_admm import ADMM_bqp_linear_eq_and_ineq
We present a simple demo of image segmentation by solving unconstrained BQP problem, which calls the ADMM_bqp_unconstrained function, as follows
python demo_image_segmentation.py
The randomly initialized image and the segmentation result are shown as follows
This work has been published in CVPR 2019, "Compressing Convolutional Neural Networks via Factorized Convolutional Filters" (pdf, github)
We applied the idea of Lp-Box ADMM to deep model compression, which learns and selects the convolutional filters in a unified model. Specifically, we fitstly define a factorized convolutional filter (FCF), consisting of a standard real-valued convolutional filter and a binary selection scalar, as well as a dot-product operator between them. Then, we train CNN model with factorized convolutional filters (CNN-FCF), by updating the standard filter using back-propagation, while updating the binary scalar using the alternating direction method of multipliers (ADMM) based optimization method. The framework of the standard filter pruning (top) and the proposed CNN-FCF based pruning (bottom) are shown in the following figure.
This work has been accepted to IJCV, "MAP Inference via L2-Sphere Linear Program Reformulation" (Arxiv, the github project will be released soon).
MAP inference is a fundamental task in probabilistic graphical models, which aims to infer the most probable label configuration of a probabilistic graphical model (e.g., MRF, CRF, HMM). MAP inference can be formulated as an integer programming, based on the factor graph (any graphical model can be transformed to a corresponding factor graph), as follows $$ \text{MAP}(\boldsymbol{\theta}) = \text{ILP}(\boldsymbol{\theta}) = \mathop{\max}_{\boldsymbol{\mu}, \boldsymbol{v}} < \boldsymbol{\theta}, \boldsymbol{\mu} > ~ \quad \text{s.t.} \quad \boldsymbol{\mu} \in \mathcal{L}_G \cap {0, 1}^{|\boldsymbol{\mu}|}. $$
Inspired by the idea of Lp-Box ADMM, we firstly remove the binary constraint, while adding the
It is easily proved that $ \text{LS-LP}(\boldsymbol{\theta}) = \text{MAP}(\boldsymbol{\theta}) = \text{ILP}(\boldsymbol{\theta})$. LS-LP can be efficiently solved by ADMM, which is proved to be globally convergent to epsilon-KKT solution of the original MAP inference.
This work is presented in Arxiv, "Constrained K-means with General Pairwise and Cardinality Constraints"(Arxiv).
K-means is one of the most popular classic clustering algorithms. However, the orginal K-means is unstable. One enhanced approach is inserting some user preferences (e.g., pairwise constraints) into K-means, using some heuristic strategies. One recent work formulates K-means as an integer programming. Based on this formulation, different types of user preferences can be naturally embedded as constraints, such as cardinality constraints, must/cannot-link constraints. We adopt the Lp-Box ADMM algorithm to optimize this IP problem.
The Lp-Box ADMM method has been adopted by many researchers to solve multiple diverse applications and showing very promising performance, such as hash code learning, low-density parity-check (LDPC), feature selection, data hiding, etc.
Looking forward to more applications using Lp-Box ADMM :)
If our work is helpful to your work, please cite as follows. If any question or suggestion, plesse send email to Baoyuan Wu.
@article{wu2018lp,
title={lp-box ADMM: A versatile framework for integer programming},
author={Wu, Baoyuan and Ghanem, Bernard},
journal={IEEE Transactions on Pattern Analysis and Machine Intelligence},
year={2018},
publisher={IEEE}
}
The contents of this repository, including the codes and documents are released under an BSD 3-Clause license.