Given a linear programming problem in the form \[ \begin{array}{ll} \left\{\begin{array}{l} \mbox{maximize} \\ \mbox{minimize} \end{array}\right\} & f(\mathbf{x})=\mathbf{c}^T\mathbf{x} \\ \mbox{subject to} & \mathbf{A}\mathbf{x} \left\{\begin{array}{c} \leqslant \\ = \\ \geqslant \end{array}\right\} \mathbf{b} \\ \mbox{and} & \mathbf{x} \geqslant 0 \end{array} \] where $\mathbf{x}=\{x_1,x_2,\ldots,x_n\}$ is the vector of $n$ variables, $\mathbf{c}$ and $\mathbf{b}$ are vectors of $n$ real coefficients and $m$ (right-hand-side) numbers, respectively, $\mathbf{A}$ is a matrix of $m\times n$ real numbers, this calculator find $\mathbf{x}$ that maximize or minimize the objective function $f(\mathbf{x})$. This calculator differs from Linear Programming Calculator in that it can solve the problems efficiently when the constraints are large and sparse while the previous calculator is for small problems.

Input Data

This calculator requires from users two inputs. The first input has the same format as described in Linear Programming Calculator. The second input is for the linear constraints which are $m\times(n+2)$ sparse matrix. The non-zero entries of the sparse matrix is entered in Coordinate list with indices starting from one (one-based indices). Note that the sparse matrix for this calculator contain matrix $\mathbf{A}$, equality/inequality signs with numerical values $\{-1,0,1\}$, and vector $\mathbf{b}$. So if most of the constraints are linear equality (i.e. most $0$'s in the $(n+1)^{\mathrm{st}}$ column) or most entries of $\mathbf{b}$ are zeros, it is not necessary to enter them.

Sparse Linear Programming Calculator