Why does linprog generate a 7D optimal solution for 6D simplex problem

When running linprog with 6x18 constraint matrix (m=6,n=18) and 6x1 b vector, the "optimal" solution generated has 7 nonzero elements when it should only be 6. Why is this the case? I have my own implementation of simplex which comes up with a different solution (6 as apposed to 7 nonzero entries) but both have the same objective function value when evaluated at the solution point.

[Matt J]

Well, provide us with code to reproduce what you obtain and we'll see if there's anything unusual in its behavior.

[Thomas Kirven]

Sure! here's the code

A =[150   150   150   150     0     0     0     0  -150  -150     0     0     0     0     0     0     0     0;
      0   -50     0    50     0     0   120  -120  -100   100     0    30     0   -30     0     0     0     0;
     50     0   -50     0  -120   120     0     0     0     0   -30     0    30     0   -60    60    60   -60;
      0     0     0     0     0     0     0     0     0     0     0     0     0     0    60    60   -60   -60;
    350     0  -350     0  -120   120     0     0     0     0  -120     0   120     0   -60    60    60   -60;
      0   350     0  -350     0     0  -120   120  -150   150     0  -120     0   120     0     0     0     0];

  b = [63, -23, -43, 29, -54, 20];

f = [1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1];

lb = zeros(1,18);

linprog(f,[],[],A,b,lb)
%% result
ans =

    0.1028
    0.0838
    0.1395
    0.0938
    0.1014
    0.0000
    0.0000
    0.1958
    0.0000
    0.0000
    0.0000
    0.0000
    0.0000
    0.0000
    0.4833
    0.0000
    0.0000
    0.0000

The (non-matlab) solution I get has non zero elements 1,3,4,5,8,15 as follows

0.186667, 0.223333, 0.010000, 0.101389, 0.195833, 0.483333

[Thomas Kirven]

Actually upon second look the solutions have the same objective function value, but different soution values... interesting. I guess it isn't really specified that matlab should use only 6 entries of the solution vector, I guess my question is then: Is there a way to specify this constraint?

[Matt J]

Strange. The solution I get when I run your code is as below. What Matlab version are you running?

xlp =

         0
    0.1867
    0.0367
    0.1967
    0.1014
         0
         0
    0.1958
         0
         0
         0
         0
         0
         0
    0.4833
         0
         0
         0

[Walter Roberson]

I get the same as Matt J

[Thomas Kirven]

I'm running 2016b... which might be the problem

[Matt J]

Actually upon second look the solutions have the same objective function value, but different soution values

Your solution with 7 non-zeros doesn't really even seem to be a solution. It doesn't satisfy the equlaity constraints very well. Are you sure it comes from the exact code that you have posted?

[Mary Fenelon]

The default algorithm in R2016b is the interior-point-legacy solver; it was changed to dual-simplex in 17a. Simplex algorithms move from vertex to vertex of the feasible region but interior point algorithms move through the middle. When there are multiple optimal x vectors, the interior point algorithm may return a point in the middle. It will be a linear combination of some of the optimal vertex points.

[Thomas Kirven]

Matt J, yep this is the exact code and the solution. Also I checked the solution and it does seem to be correct:

A*linprog(f,[],[],A,b,lb)

gives

ans =

   63.0000
  -23.0000
  -43.0000
   29.0000
  -54.0000
   20.0000

which is b.

[Thomas Kirven]

Thank you very much Mary! I think this makes sense now! A linear combination of vertices on the simplex would totally explain why there are 7 non-zero values. In fact it looks like the solution the interior point comes up with is a linear combination of my independently obtained solution and the matlab dual simplex solution Matt provided. Cool!

Answer 1

[Thomas Kirven]

See Mary's comment https://www.mathworks.com/matlabcentral/answers/450806-why-does-linprog-generate-a-7d-optimal-solution-for-6d-simplex-problem#comment_683388