MATLAB Answers


Feasibility problem of linear programming

Asked by Edgar
on 20 Jun 2012

Like the title says, I want to determine if there exists a solution to a set of linear inequalities.


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.

Thanks in advance,



Sign in to comment.

1 Answer

Answer by Tiago Montanher on 27 Jun 2012
 Accepted Answer

 Dear Edgar,
 Once you have a small problem (20-40 lnear constraints) and I suppose you are an academic researcher,  you may try to solve feasibility problem via linear programming algorithms from CPLEX. It is much better than linprog algorithm and you just need to change the calling line with any further modification of your code. 


Sign in to comment.