Major error in Excel Simplex-LP solver

Wow.  I had no idea that Open Solver would have found a solution so quickly.

Thanks for the feedback.

Hi Dana,

I appeciate you taking the time to analyze the problem.

OpenSolver takes 0.06s and SAS 0.01s to solve this mixed integer linear programming problem.

I would expect from a commercial linear solver that it can solve a MILP problem of this size. If this is not the case for the Excel solver, then it should probably not pretend that it can. The solver says "Solver found a solution. (...) When Simplex LP is used, this means Solver has found a global optimal solution." This is wrong and therefore a bug.

Best,

Jost

Hi.  Just two cents on the Excel issue.

I would be curious to learn how long it took Open Solver to solve this as written.

As written, Excel's Solver would have to check every combination, which is astronomically large.

It doesn't lend itself to a fast Simplex solution.

Picture the solution plane as a surface with lots of hills and valleys.  Solver is asking to check every valley and then do a comparison of two cells.  Not very efficient.  Solver really can't do Global optimization well, unless it uses the  Evolutionary method, which would take forever in this case.

The usual solution in this case is to write a macro that generates a better table that Solver can use.

However, in this case, it may be better to do the following.

Take each column of your data table, and multiply it by the columns constraint.

It is now a simple task for vba to compare two rows at a time, and pick the minimum from each column.  There are only 45 row comparisons to make.  The solution is almost immediate.  I think this is a better way to go than have Solver compare billions of combinations.   Here, it immediately picked the same rows 4&5, and the sum of the green values are the same as what you had:  2,426,047,900

If we look at just the 45 possible combinations, we see just how un-smooth the solution set is.   Solver would have to do a Global search, and it wouldn't be very efficient.:

Here, the 25th comparison was your rows 4 & 5.

Again, Excel got this solution immediately be changing the model.