Feasibility problem of linear programming
2 views (last 30 days)
Show older comments
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.
Thanks in advance,
-edgar
0 Comments
Accepted Answer
Tiago Montanher
on 27 Jun 2012
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.
0 Comments
More Answers (0)
See Also
Categories
Find more on Linear Programming and Mixed-Integer Linear Programming in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!