OptimalMatrixCompletion.jl: optimal noisy low-rank matrix completion in Julia

This archive is distributed in association with the INFORMS Journal on Computing under the MIT License.

The software and data in this repository are a snapshot of the software and data that were used in the research reported on in the paper Disjunctive Branch-and-Bound for Certifiably Optimal Low-Rank Matrix Completion by D. Bertsimas, R. Cory-Wright, S. Lo, and J. Pauphilet. The snapshot is based on this SHA in the development repository.

This code is being developed on an on-going basis at https://github.com/sean-lo/OptimalMatrixCompletion.jl. Please go there if you would like to get a more recent version or would like support.

Cite

To cite the contents of this repository, please cite both the paper and this repo, using their respective DOIs.

https://doi.org/10.1287/ijoc.2025.1330

https://doi.org/10.1287/ijoc.2025.1330.cd

Below is the BibTex for citing this snapshot of the repository.

@misc{
    OptimalMatrixCompletion,
    author =        {D. Bertsimas and R. Cory-Wright and S. Lo and J. Pauphilet},
    publisher =     {INFORMS Journal on Computing},
    title =         {{Disjunctive Branch-and-Bound for Certifiably Optimal Low-Rank Matrix Completion}},
    year =          {2026},
    doi =           {10.1287/ijoc.2025.1330.cd},
    url =           {https://github.com/INFORMSJoC/2025.1330},
    note =          {Available for download at https://github.com/INFORMSJoC/2025.1330},
}

Description

This repository has two purposes:

• src/OptimalMatrixCompletion.jl defines the OptimalMatrixCompletion module, which exports the matrix_completion_branchandbound() function. This function implements the branch-and-bound algorithm on a n-by-m matrix A, with target rank k, and sparsity pattern indicated by indices, and regularization parameter γ. See the development repository README for more information.
• experiments/ documents experiments from the IJOC paper, including all scripts, tables and plots.

Setup

Install Julia 1.9.2 (using juliaup is recommended):

juliaup add 1.9.2

Next, set Julia 1.9.2 as the default Julia version for this directory:

juliaup override set 1.9.2

Finally, activate the Julia environment and precompile it:

julia> using Pkg; Pkg.activate("."); Pkg.precompile()

Also ensure you have a Mosek license. This project uses Mosek 10.

Replication

Replication instructions for the suite of experiments in the paper are provided in the experiments README.

Ongoing Development

This code is being developed on an on-going basis at the author's Github site.

Support

For support in using this software, submit an issue.