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?

Answer 1

[Matt J]

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.

[Matt J]

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

[Devin]

Hi Matt

Thank for your help.

I did not use interior-point-legacy. What I used is just interior-point.

Is interior-point same as interior-point-legacy?

[Matt J]

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]

Thank you Matt.

The version I am using is R2018a. Does "interior-point" method of R2018a have crossover?

Thank you

[Matt J]

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]

Thank you very much! The reason why I ask, because I find interior-point of CPLEX by BIM is much slower than linprog of Matlab even I used same tolerance and constraints.

[Devin]

A = [1 1; 1 2];
b = [4 5]';
z = -[2 4];
%% Matlab interior
LPoptions = optimset('Algorithm','interior-point','MaxIter',2000,'TolFun',1e-6,'display','iter');
[MBarrier,fval,exitflag,output,lambda] = linprog(z, A, b, [], [], [0 0], [], LPoptions);

%% Matlab interior legacy
LPoptions = optimset('Algorithm','interior-point-legacy','MaxIter',2000,'TolFun',1e-6,'display','iter');
[MBarrier_legacy,fval,exitflag,output,lambda] = linprog(z, A, b, [], [], [0 0], [], LPoptions);

%% Matlab dual simplex
LPoptions = optimset('Algorithm','dual-simplex','Display','final','MaxIter',2000,'TolFun',1e-6);
[MDual,fval,exitflag,output,lambda] = linprog(z, A, b, [], [], [0 0], [], LPoptions);

You are right. I did this test, it is very clear that there is no crossover process in both interior-point and interior-point-legacy. I got a non-basic solution. The basic solution should be [0; 2.5].

I have a new question. Do you know from what version of matlab, new interior-point is used to replace old interior-point (interior-point-legacy)? Because I need to repeat the results simulated by old interior-point. And these two methods give different resultes when there are multiple optimal solutions.

Thank you very much!

[Matt J]

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.