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 An Enhanced ADMM-based Interior Point Method for Linear and Conic Optimization by Qi Deng, Qing Feng, Wenzhi Gao, Dongdong Ge, Bo Jiang, Yuntian Jiang, Jingsong Liu, Tianhao Liu, Chenyu Xue, Yinyu Ye and Chuwen Zhang.

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.2023.0017

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

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

@article{deng2023new,
  title  =    {New Developments of ADMM-based Interior Point Methods for Linear Programming and Conic Programming}, 
  author =    {Qi Deng and Qing Feng and Wenzhi Gao and Dongdong Ge and Bo Jiang and Yuntian Jiang and Jingsong Liu and Tianhao Liu and Chenyu Xue and Yinyu Ye and Chuwen Zhang},
  publisher = {INFORMS Journal on Computing},
  year =      {2024},
  doi =       {10.1287/ijoc.2023.0017.cd},
  url =       {https://github.com/INFORMSJoC/2023.0017},
  note =      {Available for download at https://github.com/INFORMSJoC/2023.0017},
}  

ADMM-based Interior Point Method for Linear and Conic Programming (ABIP) is a new framework that applies alternating direction method of multipliers (ADMM) to implement interior point method (IPM) for solving large-scale linear programs (LP) and conic programs (QCP).

ABIP (LP part) was initially developed by Tianyi Lin (https://github.com/tyDLin) and is currently maintained by LEAVES optimization software platform.

The original ABIP follows the following paper:

@article{lin_admm-based_2021,
	title = {An {ADMM}-based interior-point method for large-scale linear programming},
	volume = {36},
	number = {2-3},
	journal = {Optimization Methods and Software},
	author = {Lin, Tianyi and Ma, Shiqian and Ye, Yinyu and Zhang, Shuzhong},
	year = {2021},
	note = {Publisher: Taylor \& Francis},
	pages = {389--424},
}

Current version of ABIP is 2.0

We provide the Matlab interface. The C interface is planned for 3.0 release. To install ABIP, install Intel OneAPI MKL first.

We suggest that the user set the environment variables by using the script provided by OneAPI. It is typically located at path-to-oneapi/setvars.sh.

For example, on Ubuntu, the root path of OneAPI is /opt/intel/oneapi, then you can run the following,

cd to_the_root_directory_of_abip
source /opt/intel/oneapi/setvars.sh       

When you finish the setups, use install.m script in the root directory

ABIP operates on the standard form LP, i.e.,

$$ \begin{aligned} \min ~ &c^Tx \\ \text{s.t.} ~&Ax = b\\ &x\ge 0 \end{aligned} $$

and accepts standard sedumi format defined using $A, b, c, K$.

To call it, use

[x, y, s, info] = abip(data, K, params)

For convenience, we provide scripts to proceed the standard form LP, reformulates the problem to the appropriate format, see Replicating.

ABIP operates on the following quadratic cone programming (QCP), i.e.,

$$ \begin{aligned} \min ~ &\frac{1}{2}x^TQx + c^Tx \\ \text{s.t.} ~&Ax = b\\ &x\in \mathcal{K} \end{aligned} $$

where $Q \in \mathbb{S}_{+}^n, c \in \mathbb{R}^n, b \in \mathbb{R}^m, A \in \mathbb{R}^{m \times n}$, and $\mathcal{K}$ is a closed convex cone.

To call it, use

[x, y, s, info] = abip(data, K, params)

ABIP-QCP shares most of the parameters with ABIP-LP, except for the convex cone K, currently we support following cones:

Note: columns of data matrix A must be specified in the order above.

The result files can be found in results

To replicate the results in the paper, please refer to the README here

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

For support in using this software, submit an issue.

This project is licensed under the MIT License, as detailed in the LICENSE file.

All external dependencies are consolidated in src/external/, with each dependency's license:

• AMD (SuiteSparse): BSD license allows broad usage with minimal restrictions. The license file is included in its respective directory.
• LDL & CSparse (SuiteSparse): Under GNU LGPL, permitting use and modification provided changes are shared under LGPL. License files are placed within their specific directories.
• QDLDL (OSQP): Apache License 2.0 supports use and modification, requiring clear documentation of changes and the original copyright notice. The license file is located in the relevant directory.

Contributors agree that their contributions will be licensed under the MIT License. We encourage contributors to review the licenses of external dependencies housed in src/external/ to ensure compliance with their terms.

This README section is provided for informational purposes only and does not constitute legal advice. If you have any questions or concerns about the licensing terms or compliance, especially regarding third-party dependencies, please consult with a legal expert.