Using Excel for an Optimization Problem

The astute reader will note that I didn’t (and won’t) write a book called Advanced Excel. Not because there aren’t a number of advanced Excel topics I could’ve written about but more because that becomes the realm of people who really get in the weeds on Excel and I’d also have to find a way to make it comprehensive and that just seemed a little too…much.

But yesterday on Facebook a friend of mine asked for Excel help so I thought I’d share the question and what I came up with here.

Here’s the scenario she gave: It’s career day. You have fifty students. Ten lecturers. There are four sessions, so each student can attend up to four lectures. Students have provided a ranking of their preferences from 1 to 10 with 1 being their top choice. Is there a way to have Excel tell you which students should be paired with which lecturers?

Short answer: Yes. Slightly longer answer: Not in the basic version of Excel. At least not at the scale we’re talking about here. (It can handle up to 200 decision variables but what I gave you above would have 500.)

So if you actually wanted to do this you’d have to get access to a more robust version of Solver. But you can use Excel to build a mini version of the problem.

I used four students and eight lecturers and rigged my data so that I knew there’d be a solution.

Here’s how it goes.

Start with your student data:

Student Data Data Optimization

Here you can see I’ve built a table with one student per row and their ranking of each lecturer across the different columns. (See how I rigged it so that two students want the first four lecturers and the other two want the last four?)

Next, create a “decision grid”. It’s the exact same as the first table except instead of student rankings all the values in the table are set to 1. (Could be set to zero, too. Either way works.)

Decision Grid Data Optimization

You also want to have the total lectures given by each lecturer (the last row) and the total lectures attended by each student (Column V). This is because these will have constraints that need to be met for our final solution.

Finally, create an “outcome grid” which takes the student ranking in the first grid and multiplies it by the value in the second grid. So if you put 1s in the second grid this will look just like the first grid, but it’s using a formula.

Outcome grid data optimization

At the end of the outcome grid you want a total value for each student (Column AE) and then at the bottom of that column of values you want the average of those student scores.

Now, to do this next part you need to enable Solver, which comes installed in Excel but isn’t automatically activated. Go to File->Options->Add-Ins and at the bottom where it says Manage Excel Add-Ins click on Go. This will bring up the Add-Ins dialogue box. Click the box for Solver Add-In and say OK.

Once you do that you will have the Solver option in the Analysis section of the Data tab. Click on it.

This will bring up the Solver Parameters dialogue box.

solver screen

Here’s where all the fun happens. In this case we want to minimize the average student score. So we’re minimizing the value in Cell AE7 which is where we have the average student score after they’ve been assigned to their lecturer. (This is because in this scenario 1 is the best outcome, 10 is the worst, so the lower the score per student the better.) So our Set Objective is Min AE7.

To do this, we need Excel to say yes/no to which lectures a student will attend. That is done by adjusting the 1s we placed in Cells N2:U5 to either be 1’s (for yes, go to that lecture) or 0’s (for no, don’t go to that lecture). That’s what we specify in the “By Changing Variable Cells” box. When Excel solves the problem it will do that for us.

But Excel needs to know our constraints. For example, that students can only attend 4 lectures. That’s why we tell it V2:V5 must equal 4. (Only make four entries per student equal to 1.)

And we need to make sure that Excel doesn’t do something wacky like decide you can attend half a lecture. So we have to say N2:U5 must be binary. (That means an integer that is either 1 or 0.)

And in this scenario, I had to limit the number of students each lecturer gave a lecture to to 2 so there could be a possible solution. (In the real life example this would be a minimum of number of students per session times the number of sessions and a maximum number of students per session times the number of sessions.) That’s the N6:U6>=2 part.

Finally, I wanted each student to at least be marginally happy with the outcome so I made it so that AE2:AE5 were all less than 12. (We don’t want one kid having a terrible outcome while everyone else has a good outcome.)

And that was it. Then you just tell Excel to solve it. Excel will run scenarios until it finds one that meets all of those criteria. (Or it will tell you it doesn’t have a solution which happened a few times to me when I was building this because I’d built it so it wasn’t solvable.)

If you let it implement its solution, you get something like this for that second grid:

Solver solution

In this case, each student attends four lectures, each lecturer lectures to two students, and (you can’t see it) all students have a score of 10.

As you can see, your constraints are crucial on something like this. And you really need to look at the outcome when it’s all done and see if makes sense and to confirm you didn’t miss some crucial constraint or set it wrong. (If that happens, change it, reset the grid, and run the solver again.)

Also, the model type you choose can have an impact. (It tells you when to use each type but I just try each one to see which one works.)

Now, one final caution. Solver will stop on the first feasible solution. I originally had student scores set to a possible value of 20 instead of 12 and it gave me a solution that worked, but wasn’t the ideal solution you see above.

Anyway. This is why I didn’t do much writing yesterday, because, sadly enough, I find this kind of thing fun so I was happy to set aside my current project to puzzle it out. And I thought it might be fun to see for those looking for more advanced uses for Excel.

Author: M.L. Humphrey

I have spent close to twenty years as a regulator and consultant in the financial services industry. I am also a former stockbroker with degrees in Economics, Anthropology, and Psychology from Stanford and an MBA from Wharton and I have self-published more than a hundred titles across non-fiction, fantasy, and romance. This website is where I tend to talk self-publishing with a small smattering of business, life, and Excel mixed in.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s