Spreadsheet Evolved: Solving Non-Smooth Business Optimization Problems Using Microsoft Excel 2010+

Tallying monthly sales figures, categorizing expenses, tracking office fantasy football league stats – traditional wisdom paints Microsoft Excel as a useful, albeit unsophisticated, tool for performing ad hoc analysis around the office.  But while Excel is certainly easy to use, its simplicity belies a powerful ability to provide business users with advanced analytics in a fast and flexible way.

One example worth highlighting is a new feature in the Excel 2010 Solver tool that allows users to solve non-smooth optimization problems using evolutionary algorithms (also known as genetic algorithms because of their resemblance to the biological processes of genetic mutation and natural selection).  Whereas the standard Solver found in previous versions of Excel was capable of solving smooth linear (LP Simplex method) and smooth non-linear (GRG Nonlinear method) optimization problems, it was incapable of solving the non-smooth optimization problems that often best model complex business scenarios.

It may be helpful at this point to take a step back and consider how, exactly, Solver works.  In order to solve an optimization problem, users open the Solver add-in within Excel and define three sets of values (see Figure 1):

A)     Variable Cells – the cells that Solver will change in order to optimize (i.e., maximize or minimize) the value of the Objective Cell

B)      Objective Cell – the cell whose value is to be optimized (i.e., maximized or minimized)

  1. Note:  the value of the Objective Cell must be a function of the values of the Variable Cells in order for Solver to work

C)      Constraints – the conditions that must be satisfied in order for Solver to optimize the Objective Cell

Figure1

As noted, Solver only works if the value of the Objective Cell is a function of the values of the Variable Cells.  Furthermore, in previous versions of Excel, this functional relationship had to be smooth (for an illustrative comparison between smooth and non-smooth functions, see Figure 2).  The problem is that the relationship between the Variable Cells and the Objective Cell in many complex business optimization problems is often non smooth; for example, if it includes any Boolean operators (e.g., IF, OR, AND) or any VLOOKUP functions, these result in a non-smooth equation.  Unlike previous version of Solver, however, the Evolutionary Solver has no problem tackling non-smooth functions.

Figure2

I first harnessed the power of the Evolutionary Solver while scheduling training for several hundred ERP users across six countries.  Given a significant set of scheduling requirements (e.g., nine time zones across six countries, limited working hours, a requirement that each user be provided with at least three training sessions during home-office working hours) I set out to build a model that would optimize my training schedule to (1) meet all of the scheduling requirements and (2) maximize the average number of sessions offered to users during their home-office working hours.

To do this, I built my constraints and assumptions, as well as a full training schedule (Figure 3), into an Excel workbook.  I then built out a scoring function using a series of formulas (Cells B30:S54 in my workbook) to “score” the set of training session times based on (1) their adherence to my constraints, and (2) the average number of sessions made available to users during home-office working hours.

Figure3

In the language of Solver, the session times were my Variable Cells, and the output of the scoring function was my Objective Cell.  Because some of the constraints were incorporated into my scoring function as Boolean operators (e.g., “IF a session time begins at midnight CST, award it zero points”) the optimization problem was non smooth and therefore required me to use the Evolutionary Solver.

The actual algorithms underlying the Evolutionary Solver are complex (perhaps the topic of another blog), but it basically works by assigning random numbers to the Variable Cells in the model (training session times) and then testing the outcome of the Objective Cell, repeating itself  tens of thousands of times and only keeping a subsequent solution if it improves upon the previous one.  After approximately 10,000 iterations (this can be customized) without any improvement in the optimization of the Objective Cell, Solver considers the Objective Cell maximized and keeps the current values of the Variable Cells.

What is so powerful about the Evolutionary Solver, however, is that it does not simply “brute force” the problem; instead, it applies complex principles mimicking genetic mutation and natural selection to drive efficient optimization of the scoring function.  They key is that the process of selecting the “random” variables during each iteration isn’t really random.  Behind the scenes, the Evolutionary Solver is actually merging traits – think breeding – of previously-generated sets of Variable Cells (in my case, training session times) that have been marginally successful at maximizing the value of the Objective Cell.  The end result is a highly-optimized Objective Cell value.

In this particular example, this means a schedule that (1) adheres to all of my scheduling constraints and (2) does a very good job of maximizing the average number of sessions available to users during their home-office working hours.  It may be complicated and require more than a little tinkering to perfect, but the Evolutionary Solver provides an excellent example of the power that Excel places in the hands of non-technical users.

Instructions for accessing demo workbook:

  1. click the following link: Evolutionary Solver
  2. ensure that you have added the Solver Add-in (link to instructions: http://office.microsoft.com/en-us/excel-help/load-the-solver-add-in-HP001127725.aspx)
  3. click on the ‘Optimize Schedule’ button
  4. send any questions or feedback to ftidwell@westmonroepartners.com

Your email address will not be published. Required fields are marked *

Phone: 312-602-4000
Email: marketing@westmonroepartners.com
222 W. Adams
Chicago, IL 60606
Show Buttons
Share On Facebook
Share On Twitter
Share on LinkedIn
Hide Buttons