Does function linprog by interior point method have crossover process to obtain a basic solution?
显示 更早的评论
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?
采纳的回答
Matt J
2019-2-1
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 个评论
But even if the current or legacy interior-point algorithm does not have a "cross-over process", you should hardly ever see a non-basic solution. Linear programming problems with multiple solutions are numerically unstable. Small perturbations of the data will give you a basic solution, and you can never control which solution you are going to get. As an example,
opts=optimoptions('linprog','Algorithm','interior-point-legacy');
x_ipl_perturbed=linprog(f+randn(size(f))*1e-7,A,b,[],[],lb,ub,opts)
almost always gives the basic solution
x_ipl_perturbed =
5.0000
0.0000
or
x_ipl_perturbed =
0.0000
5.0000
Is interior-point same as interior-point-legacy?
interior-point-legacy is the same as what old versions of Matlab called "interior-point".(That's what "legacy" means).
So, if you have selected "interior-point" in an old version of Matlab, you might see non-basic solutions.
Devin
2019-2-4
I do not know. I have yet to see a non-basic solution, however, in interior-point-R2018a.
But again, I'm not sure what you hope to achieve, even if you could confirm that interior-point has a cross-over process. Linear programming problems with multiple solutions are unstable. Even if the interior-point method did have a cross-over process, there can be no gaurantee that you would get the same basic solution that the dual simplex method (or any other solver) gives you.
Devin
2019-2-4
Devin
2019-2-19
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.
更多回答（0 个）
类别
在 帮助中心 和 File Exchange 中查找有关 Linear Programming and Mixed-Integer Linear Programming 的更多信息
Translated by 
