Does function linprog by interior point method have crossover process to obtain a basic solution?
6 views (last 30 days)
Show older comments
Greetings,
Currently, I am working on a linear programming problem. I used function linprog to solve it. However, I found if I specified either using interior point method or dual simplex method, I would get totally different solutions. The reason is the existence of multiple optimal solutions.
As we know, dual simplex method gives a vertex solution. How about interior point method? If interior point method has crossover process, I should get a vertex solution (basic solution). If it has not, I will get a inner point of the hyperplane of constraints.
Does function linprog by interior point method have crossover process to obtain a basic solution?
0 Comments
Accepted Answer
Matt J
on 1 Feb 2019
Definitely not if your Matlab version is old enough, in which case the interior-point method offered is presumably the same as what is R2018a calls interior-point-legacy. I draw this conclusion from this test,
f=-[1,1];
A=-f;
b=5;
lb=[0,0];
ub=[1,1]*b;
opts=optimoptions('linprog','Algorithm','interior-point-legacy');
x_ipl=linprog(f,A,b,[],[],lb,ub,opts)
which yields the non-basic solution,
x_ipl =
2.5000
2.5000
With the interior-point algorithm of R2018a, I always seem to get a basic solution, but don't know why.
8 Comments
Matt J
on 19 Feb 2019
Edited: Matt J
on 19 Feb 2019
When there are multiple optimal solutions to a linear program there is no way to ensure reproducibility of one solution on a different computer or software version. Such optimization problems are numerically unstable and so there is no way, through algorithm implementation, that you can hope to guarantee a particular output.
More Answers (0)
See Also
Products
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!