Excel: Simplex vs Evolutionary Engine (Simplex wins)

In this post a simple MIP problem is posted. Basically the problem can be stated as:

\[\boxed{\begin{align} \max & \sum_i Score_i \, x_i \\ & \sum_i x_i = 6 \\ & \sum_i Salary_i \, x_i \le 50000 \\ & x_i \in \{0,1\} \end{align}}\]

We have a database of 153 players, and we want to compose the best team of 6 players with a total salary cap of $50k. This can actually be done in Excel quite easily. With some random data I get the following results using the Simplex LP based MIP solver:

The name “Simplex LP” is somewhat misleading, as we solve here a MIP.

Some comments in the post are really surprising to me:

• “the number of combinations of 6 golfers from a pool of 153 is 16,133,132,940 Note that yes, that is over 16 billion combinations. Even if Solver can do it, it will probably crash Excel”. A MIP solver (or the Evolutionary Solver) will not evaluate all possible solutions! (That would be impossible in almost all cases). There is no reason to believe Excel will crash on this problem (quite the opposite: it solves quite quickly). I see this argument more often; apparently there are lots of people around who think complete enumeration is the best we can do.
• Excel mentions “use Evolutionary engine for non-smooth problems” so one answer suggested to use the Evolutionary solver. Actually I understand why someone may think this is a wise decision: the hint can be interpreted as advice to use the Evolutionary algorithm for any discrete problem. Looking at the results below this is not such a good idea: the Evolutionary engine takes much more time and delivers a significantly sub-optimal solution. A summary comparison of the results is:
  
  
  
• “The built-in version of Solver reports, ‘This problem is too large for Solver to handle.’ [..] an alternative is the free OpenSolver add-in (see opensolver.org)“ I have no idea why this user sees this message. I had no size problems using the sizes as indicated by the poster. This problem has 153 binary variables and I believe the limit is 200 variables.

Below is the result from a run with the same data using the Evolutionary solver:

Conclusion

My advice: always try a MIP model first. The model building process forces you to understand the problem better and a MIP solver can give proven optimal solutions (or a guaranteed quality when we allow a gap between best possible and best found solutions). If the performance is not satisfactory then consider using a meta-heuristic. (The MIP model an also be used then to debug the implement the meta-heuristic and compare the quality of the objective function values).