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? Jun 5, 2013 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, 2013 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. Jun 5, 2013 at 14:28
• I find there are no solutions to this particular problem. Jun 5, 2013 at 15:36

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]]] #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