# Feasibility of Linear Program

I have a set of (real) linear equations/inequalities and I want to know whether they have a solution, and to find at least one. The goal is to do this quickly. FindInstance seems rather slow -- it is possible that it's just the size of my problem, but I thought it could be done faster. In particular, since all my equations are linear, I thought I might try to see if LinearProgramming would be faster. Unfortunately, the function doesn't seem to take parameters the way I want it to: I have 0-1 matrices $M_1$, $M_2$, and seek a vector $x$ such that $M_1x = 0$ and $M_2x \geq 1$. The vector $x$ is however allowed to have negative entries. Any help for how to solve this problem is appreciated.

Edit: on request, here is an example of $M_1$ (in fact, it always looks like three identity matrices, though its size varies) and of $M_2$ (which has, to the best of my knowledge no nice pattern except that it has precisely 3 ones per row):

M1 = {{1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0},
{0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0},
{0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0},
{0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1}};

M2 = {{0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1},
{0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0},
{0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0}};


I am looking for a real vector $x$ of length 12 (in this case) such that $M_1x = 0$ and each entry of $M_2x$ is at least 1.

• "I have a set of (real) linear equations/inequalities..." - where are they? – J. M.'s torpor Jun 5 '13 at 14:21
• It's not a single specific set; different (but similar) equations arise depending on some parameters, which I want to be able to vary. The problem itself is rather obscure and I don't think attempting to explain it would help anyone to understand the question. I think I have put all the notable information about the constraints in the question. – jona Jun 5 '13 at 14:26
• Okay, but gives us some code/examples to work with; it's hard to help if you've nothing definite to supply. – J. M.'s torpor Jun 5 '13 at 14:28
• I find there are no solutions to this particular problem. – b.gates.you.know.what Jun 5 '13 at 15:36

## 1 Answer

To ensure ${\boldsymbol{\mathrm M}}_1 \cdot {\boldsymbol{x}} = \boldsymbol{0}$, $\boldsymbol x$ must lies in the null space of ${\boldsymbol{\mathrm M}}_1$:

ns = NullSpace[M1];
x = MapIndexed[c[#2[]] #1 &, ns] // Total


For the constraint $\left({\boldsymbol{\mathrm M}}_2 \cdot {\boldsymbol{x}}\right)_k \geq 1, (k=1,2,3)$, we can use Reduce to invesgate it:

Reduce[And @@ Thread[M2.x >= 1]]


False

So there is no solution for your example.

# Edit

For cases where there do exist solutions, we can get instances as following. Here we take the M1 in original question and

M2 = {{1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1},
{0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0}};


for example.

After obtaining x as described above, we continue with

cond = Reduce[And @@ Thread[M2.x >= 1]]
coeffSet = FindInstance[cond, Union[Cases[x, c[_], ∞]], Reals, 5]
x /. coeffSet To verify the solutions we found:

SetAttributes[c, NHoldAll]
Column[{M1.x, N[M2.x]}] /. coeffSet 