Thanks to Eric Patterson for putting together this post.
In Excel 2010, we have made a number of improvements to Solver that make it easy for beginners to get started and more advanced ones to find solutions to all types of problems. The purpose of this post is to review the improvements to Solver, and so assumes some familiarity with the tool. If you are not familiar with Solver, you can learn more about Solver from Office Online. The help topic applies to the Solver that ships in Excel 2007 and earlier, but the concepts are very much the same.
In short, Solver is a what-if analysis tool for optimization. It is an add-in licensed from Frontline Systems that has shipped with Excel for many years. Solver helps to find an optimal value in one cell, called the target cell, on your worksheet. It works by changing a group of cells related to the target cell to find an optimal value subject to the constraints that you set. You can use Solver, for example, to determine the most efficient shipping routes, maximize income/sales/etc., or discover the best product mix. To see an example of (the Excel 2007) Solver in use, check out this earlier blog post where Solver is used to maximize the number of hikes on a vacation road trip. I hope to write more posts in the future about examples of using Solver to solve optimization problems.
In this post I am going to cover the new user interface for the Solver app, the new solving methods and constraints that can be used, and the new reports that can be generated.
One of the changes that we have made is to the interface used for setting the Solver Parameters. The Solver Parameters dialog Box has been streamlined to make it easier to define a model. The most common features are now surfaced at the top level making it easier for both beginning and advanced Excel users to be successful. For example, the solving method (Simplex, GRG Nonlinear, Evolutionary) can now easily be chosen based on the type of model being solved. Also, a checkbox for making unconstrained variables non-negative (on by default) is bubbled up to the Solver Parameters dialog.
Also updated is the Solving Options dialog. The Options dialog has now been divided into 3 tabs with settings based on Solving Method. Now it will be easier for people to associate settings with the solving method that they are using.
The Excel 2010 Solver has 3 Solving methods used for solving spreadsheet optimization problems.
The Simplex method is used for solving linear problems. The Simplex solving method has several performance enhancements in Excel 2010 resulting in greatly improved performance for some problem types.
The GRG solver is used for solving smooth nonlinear problems. There is a new Multi-start search setting which when used in conjunction with the GRG solver results in better solutions, escaping locally optimal solutions in favor of globally optimal ones.
The new Evolution solver accepts Solver models defined in exactly the same way as the Simplex and GRG Solvers, but uses genetic algorithms to find its solutions. While the Simplex and GRG solvers are used for linear and smooth nonlinear problems, the Evolutionary Solver can be used for any Excel formulas or functions, even when they are not linear or smooth nonlinear. Spreadsheet functions such as IF and VLOOKUP fall into this category.
All Different Constraint
There is a new type of integer constraint known as AllDifferent that form a permutation of integers, making it easy to define models with ordering or sequencing. The well-known travelling salesman problem is hard to define in the current solver, but it can be defined with just an objective and one AllDifferent constraint.
In Excel 2010, we’ve added a number of new report types that provide additional detail about the problem being solved.
If you try to solve a model that is not linear, Solver will indicate that linearity conditions were not satisfied:
A new Linearity Report is available that uses numerical tests to help you find the constraints that are not linear and/or the variables that do not occur linearly in the model:
If you try to solve a model that has no feasible solution, Solver will display the message “Solver could not find a feasible solution” in the Solver Results dialog. There now two new Report choices:
The Feasibility Report uses a procedure that involves automatically adding and dropping constraints and re-solving the model, to identify an “Irreducibly Infeasible Subset” of the constraints. (The Feasibility-Bounds report uses the same procedure but doesn’t add or drop variable bounds, to save time.) These reports can help you find the source of infeasibility in your model.
Where the Simplex and GRG Solvers find a single solution, the Evolutionary Solver creates a population of candidate solutions. When this Solver Engine stops, the best solution from the population is displayed on the worksheet, but a new report is available in the Solver Results dialog:
The Population Report provides statistics about the entire final population of candidate solutions, which can yield insights into how the Evolutionary Solver performed on this model, and whether a true optimal solution has been found.