Which algorithm for this type of problem?
3 views (last 30 days)
Show older comments
Hi!
I would like to solve a problem, where I have run many optimization problems by using a loop. That problem has already been solved by another person, however the results that I get in each step of the loop are very different from the result of the other person who solved this problem. That is why, I would like to make sure that Matlab uses the best algorithm available for this type of problem.
The problem:
A =
174726 187180 -1
196094 171660 -1
87100 110042 -1
182625 157808 -1
188196 233574 -1
b =
91832600
165805408
51750400
113998496
158685200
f =
-110429 -120153 1
problem: min f^T*x
st Ax<=b, x>=0
--------------------
My code:
options=optimset('display','off');
[x,fval,exitflag,output]=linprog(f,A,b,[],[],zeros(1,3),[],[],options);
As previously mentioned, I have to run this code a number of times by using a loop. In each step only the two first elements of f change - otherwise the problem is exactly the same.
So, by not changing the algorithm Matlab uses "interior point" by default. I have tried to change something (largescale on/off, simplex, actice-set). But sometimes even though I change it in optimset it does not give me any error, and I can see in the output that the algorithm is stille the same. My question is, which algorithm is best for this type of problem and how do I tell Matlab to use it?
Thank you very much for your time and consideration!
Alex
1 Comment
Matt J
on 29 Sep 2013
Why do you think it matter which one you use? Your tests show that all the different alternatives are giving you the correct result.
Accepted Answer
Matt J
on 29 Sep 2013
Edited: Matt J
on 29 Sep 2013
If you add upper bounds to your problem, you can compute the vertices of the feasible region using LCON2VERT (Available Here). Then you can simply evaluate f.'*V(i,:) for all the different vertices V(i,:) and all different f and find the minimum.
>> A,b
A =
174726 187180 -1
196094 171660 -1
87100 110042 -1
182625 157808 -1
188196 233574 -1
-1 0 0
0 -1 0
0 0 -1
1 0 0
0 1 0
0 0 1
b =
91832600
165805408
51750400
113998496
158685200
0
0
0
10000000
10000000
10000000
>> V=lcon2vert(A,b);
>> [~,i]=min(V*f(:)); x=V(i,:)
x =
143.2383 356.9032 0
0 Comments
More Answers (0)
See Also
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!