iEPPA

iEPPA : a MATLAB software for solving a class of structured LPs based on an inexact entropic proximal point algorithm 
Hong T.M. Chu, Ling Liang, Kim-Chuan Toh, and Lei Yang
Corresponding author: Lei Yang (yanglei.math@gmail.com)

This is a software package for solving a class of structured linear programming problems of the form:
(SLP)minC,Xs.t.A(i)(X)=b(i),i=1,,N0XU,XRn1×n2
where C,URn1×n2, b(i)Rmi are given data, and for each i, A(i):Rn1×n2Rmi is a given linear map defined by
A(i)(X)=[A1(i),XAmi(i),X]
and the constraint matrices {A1(i),,Ami(i)} are binary (0-1) matrices  satisfying the property that for all
1j<kmi, Aj(i)Ak(i)=0, i.e., the non-zero patterns of Aj(i) and Ak(i) do not overlap.
The above problem includes an optimal transport LP as a special case, which is given by
min{C,XXe=b(1),Xe=b(2),X0}.
An inexact entropic proximal-point algorithm is developed to solve (SLP); details can be found in the following reference, where higher order tensor variable is also allowed.

  • H.T. Chu, L. Liang, K.C. Toh, and L. Yang, An efficient implementable inexact entropic proximal point algorithm for a class of linear programming problems, Computational Optimization and Applications, in print. arXiv:2011.14312
  • Codes available at here