# Linear system solution with inequality constraints - methods?

First of all, I hope I am posting this in the correct place. If not, I'm sorry and could you please direct me to where I should post this?

Problem: You are given a set of vectors, $\{\mathbf{a}^i\}_{i=1}^{24}$, and matrices $D_1$ and $D_2$ (both of dimension $[10\times6]$. Let the following be true:

• $\sum_{i=1}^{24} \mathbf{a}^i = \mathbf{1}\;,$
• $\mathbf{a}^i \geq \mathbf{0}\;,\forall i\;,$ (i.e. all elements positive),
• $(D_1 + D_2)\mathbf{1} = \mathbf{1}\;.$

Then, find vectors $\{\mathbf{b}^i\}_{i=1}^{24}$ and $\{\mathbf{c}^i\}_{i=1}^{24}$ that satisfy the equation, $$\mathbf{c}^i - D_1 \mathbf{b}^i = D_2 \mathbf{a}^i\;,\quad \forall i\in \{1,2,\dots,24\}\;,$$

and the following constraints:

• $\sum_{i=1}^{24} \mathbf{c}^i = \mathbf{1}\;,$
• $\sum_{i=1}^{24} \mathbf{b}^i = \mathbf{1}\;,$
• $\mathbf{c}^i \geq \mathbf{0}\;,\forall i\;,$ (i.e. all elements positive),
• $\mathbf{b}^i \geq \mathbf{0}\;,\forall i\;,$ (i.e. all elements positive).

Could anyone please give me any pointers on how I could go about tackling this problem? I would be interested in finding a solution (if there are multiple), or even finding out that there are none. I think that this is a kind of optimization problem, but I have no idea about any methods I could use to solve this problem computationally.

Also, this is NOT homework.

Thanks a lot.

## 1 Answer

This is a linear programming feasibility problem (since you don't have an objective function to minimize or maximize.) You can simply use an objective function of $0$ and hand this off to any reasonable LP solver. You'll either get back a solution or the bad news that the problem is infeasible.

• Thanks, Brian. Like I said, I have no idea about how to solve these things. Could you suggest a reasonable LP solver you believe will have the capability to handle this kind of a problem? Sep 25, 2015 at 3:15
• Try Gurobi, CPLEX, SCIP, or Clp; the order is (approximately) fastest to slowest. The first two are commercially licensed, but academics can get free research licenses. The third is open-source and freely downloadable, but again has a commercial license and is free for research use. The last package is open-source. Sep 25, 2015 at 3:23
• Geoff's suggestions are all good. I'd add the GNU Linear Programming Kit GLPK to the end of his list. Your problems are so small that any of these codes should be able to solve them with no difficulty. Sep 25, 2015 at 3:27
• @BrianBorchers, I posted a related question here, and, if you get the time, I would appreciate your thoughts on it. Thank you very much. Oct 1, 2015 at 19:56
• @GeoffOxberry, I posted a related question here, and, if you get the time, I would appreciate your thoughts on it. Thank you very much. (I can only add one user at a time, hence the double comment for you and Brian.) Oct 1, 2015 at 19:58