# Algorithms for Boolean Matrix Factorization using Integer Programming

arXiv: https://arxiv.org/abs/2305.10185 · HTML: https://mlsanity.com/paper/2305.10185/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 23 references that are in the map.
- First posted on arXiv 17 May 2023.

## Builds on (most cited first, 5 of 5)

- [Generalized Low Rank Models](https://mlsanity.com/paper/1410.0342/) (2014)
- [Recent Developments in Boolean Matrix Factorization](https://mlsanity.com/paper/2012.03127/) (2020)
- [Bayesian Boolean Matrix Factorisation](https://mlsanity.com/paper/1702.06166/) (2017)
- [Boolean Matrix Factorization via Nonnegative Auxiliary Optimization](https://mlsanity.com/paper/2106.04708/) (2021)
- [Binary Matrix Factorisation and Completion via Integer Programming](https://mlsanity.com/paper/2106.13434/) (2021)

## Built on by (most cited first, 1 of 1)

- [Algorithms for Boolean Matrix Factorization using Integer Programming and Heuristics](https://mlsanity.com/paper/2512.03807/) (2025)

## Abstract (arXiv)

Boolean matrix factorization (BMF) approximates a given binary input matrix as the product of two smaller binary factors. As opposed to binary matrix factorization which uses standard arithmetic, BMF uses the Boolean OR and Boolean AND operations to perform matrix products, which leads to lower reconstruction errors. BMF is an NP-hard problem. In this paper, we first propose an alternating optimization (AO) strategy that solves the subproblem in one factor matrix in BMF using an integer program (IP). We also provide two ways to initialize the factors within AO. Then, we show how several solutions of BMF can be combined optimally using another IP. This allows us to come up with a new algorithm: it generates several solutions using AO and then combines them in an optimal way. Experiments show that our algorithms (available on gitlab) outperform the state of the art on medium-scale problems.