## Feasibility problem of linear programming

on 20 Jun 2012

### Tiago Montanher (view profile)

Like the title says, I want to determine if there exists a solution to a set of linear inequalities.
A*x<=b
I am very concerned about speed because I will have to do this several times. I expect to have about 20-40 linear constraints each time I try to solve this problem.
My questions are:
1) is linprog() the fastest way to do this in Matlab? [~,~,EXITFLAG] = linprog([],A,b).
2) If I do use linprog() should I set the maximum number of iterations to 1 since I don't care about the solution?
3) If I do use linprog(), does it matter if I use 'simplex', large-scale', etc. algorithms? If so, what should I be using? I have read that interior-point algorithms determine if the problem has a solution "automatically" but I don't really know what that means.
*Edit: So I thought I'd give a little more detail about why I want to do this.
What I really want to do is to determine whether two shapes intersect: a hyperrectangle and a simplex (both in n dimensions). I've been converting the shapes into linear constraints and using linprog to see if a solution exists. This approach works but it is too slow. It takes about 0.3 seconds to compute. This is way too long because of the amount of times I have to solve this problem. Any advice on how to do this much faster would be greatly appreciated.
-edgar