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 1


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.

  • $\begingroup$ 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? $\endgroup$
    – xandrella
    Sep 25, 2015 at 3:15
  • $\begingroup$ 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. $\endgroup$ Sep 25, 2015 at 3:23
  • $\begingroup$ 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. $\endgroup$ Sep 25, 2015 at 3:27
  • $\begingroup$ @BrianBorchers, I posted a related question here, and, if you get the time, I would appreciate your thoughts on it. Thank you very much. $\endgroup$
    – xandrella
    Oct 1, 2015 at 19:56
  • $\begingroup$ @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.) $\endgroup$
    – xandrella
    Oct 1, 2015 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.