Info
This question is closed. Reopen it to edit or answer.
You are now following this question
- You will see updates in your followed content feed.
- You may receive emails, depending on your communication preferences.
Why does linprog generate a 7D optimal solution for 6D simplex problem
1 view (last 30 days)
Show older comments
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.
10 Comments
Thomas Kirven
on 18 Mar 2019
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
on 18 Mar 2019
Edited: Thomas Kirven
on 18 Mar 2019
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
on 20 Mar 2019
Edited: Matt J
on 20 Mar 2019
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
on 20 Mar 2019
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
on 20 Mar 2019
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
on 20 Mar 2019
Edited: Thomas Kirven
on 20 Mar 2019
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!
Answers (1)
See Also
Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!An Error Occurred
Unable to complete the action because of changes made to the page. Reload the page to see its updated state.
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
You can also select a web site from the following list
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
Americas
- América Latina (Español)
- Canada (English)
- United States (English)
Europe
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)
Asia Pacific
- Australia (English)
- India (English)
- New Zealand (English)
- 中国
- 日本Japanese (日本語)
- 한국Korean (한국어)