Does function linprog by interior point method have crossover process to obtain a basic solution?
2 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
Categories
Find more on Get Started with Optimization Toolbox in Help Center and File Exchange
Products
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!