# 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:
\begin{eqnarray*}
\begin{array}{rl}
\mbox{(SLP)} \quad \min & \langle C, X \rangle \\
\mbox{s.t.} & {\cal A}^{(i)}(X) = b^{(i)}, \quad i = 1,\ldots, N \\
& 0 \leq X \leq U, \quad X \in \mathbb{R}^{n_1\times n_2}
\end{array}
\end{eqnarray*}
where $$C,U\in\mathbb{R}^{n_1\times n_2}$$, $$b^{(i)} \in \mathbb{R}^{m_i}$$ are given data, and for each $$i$$, $${\cal A}^{(i)} : \mathbb{R}^{n_1\times n_2} \rightarrow \mathbb{R}^{m_i}$$ is a given linear map defined by
$${\cal A}^{(i)} (X) = \left[ \begin{array}{c} \langle A^{(i)}_1, X\rangle \\ \vdots \\ \langle A^{(i)}_{m_i}, X\rangle \end{array} \right]$$
and the constraint matrices $$\{ A^{(i)}_1, \ldots, A^{(i)}_{m_i} \}$$ are binary ($$0$$-$$1$$) matrices  satisfying the property that for all
$$1\leq j < k \leq m_i$$, $$A^{(i)}_j \circ A^{(i)}_k = 0$$, i.e., the non-zero patterns of $$A^{(i)}_j$$ and $$A^{(i)}_k$$ do not overlap.
The above problem includes an optimal transport LP as a special case, which is given by
\begin{eqnarray*}
\min \big\{ \langle C, X \rangle \mid Xe = b^{(1)}, \; X^\top e = b^{(2)}, \; X \geq 0 \big\}.
\end{eqnarray*}
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