**UPDATE (1/15/2013):** *Cliff Ragsdale was kind enough to include the modification I describe below in the 7th edition of his book (it’s now problem 32 in Chapter 6). He even named a character after me! Thanks, Cliff!*

When I teach the OR class to MBA students, I adopt Cliff Ragsdale’s textbook entitled “Spreadsheet Modeling and Decision Analysis“, which is now in its sixth edition. I like this book and I’m used to teaching with it. In addition, it has a large and diverse collection of interesting exercises/problems that I use both as homework problems and as inspiration for exam questions.

One of my favorite problems to assign as homework is problem number 30 in the *Integer Linear Programming* chapter (Chapter 6). (This number refers to the 6th edition of the book; in the 5th edition it’s problem number 29, and in the 4th edition it’s problem number 26.) Here’s the statement:

The emergency services coordinator of Clarke County is interested in locating the county’s two ambulances to maximize the number of residents that can be reached within four minutes in emergency situations. The county is divided into five regions, and the average times required to travel from one region to the next are summarized in the following table:

The population in regions 1, 2, 3, 4, and 5 are estimated as 45,000, 65,000, 28,000, 52,000, and 43,000, respectively. In which two regions should the ambulances be placed?

I *love* this problem. It exercises important concepts and unearths many misconceptions. It’s challenging, but not impossible, and it forces students to think about connecting distinct—albeit related—sets of variables; a common omission in models created by novice modelers. *BUT, *in its present form, in my humble opinion, it falls short of the masterpiece it can be. There are two main issues with the current version of this problem (think about it for a while and you’ll see what I mean):

- It’s easy for students to eyeball an optimal solution. So they come back to my office and say: “I don’t know what the point of this problem is; the answer is obviously equal to …” Many of them don’t even try to create a math model.
- Even if you model it incorrectly, that is, by choosing the wrong variables which will end up double-counting the number of people covered by the ambulances, the solution that you get is still equal to the correct solution. So when I take points off for the incorrect model, the students come back and say “But I got the right answer!”

After a few years of facing these issues, I decided I had had enough. So I changed the problem data to achieve the following (“evil”) goals:

- It’s not as easy to eyeball an optimal solution as it was before.
- If you write a model assuming every region has to be covered (which is not a requirement to begin with), you’ll get an infeasible model. In the original case, this doesn’t happen. I didn’t like that because this isn’t an explicit assumption and many students would add it in.
- If you pick the wrong set of variables and double-count the number of people covered, you’ll end up with an incorrect (sub-optimal) solution.

These improvements are obtained by adding a sixth region, changing the table of distances, and changing the population numbers as follows:

The new population numbers (in 1000’s) for regions 1 through 6 are, respectively, 21, 35, 15, 60, 20, and 37.

I am now much happier with this problem and my students are getting a lot more out of it (I think). At least I can tell you one thing: they’re spending a lot more time thinking about it and asking me intelligent questions. Isn’t that the whole purpose of homework? Maybe they hate me a bit more now, but I don’t mind practicing some tough love.

Feel free to use my modification if you wish. I’d love to see it included in the 7th edition of Cliff’s book.

*Note to instructors: if you want to have the solution to the new version of the problem, including the Excel model, just drop me a line: tallys at miami dot edu.*

*Note to students: to preserve the usefulness of this problem, I cannot provide you with the solution, but if you become an MBA student at the University of Miami, I’ll give you some hints.*

A bit off-topic but the price of the textbook ($217) shocked me a bit.

Adamo: $217 is indeed expensive. But if you buy a used copy of the previous edition (5th), it’s not that bad.

One of the things I like to do after covering a similar fire station max covering location problem is to revisit the problem as a p-center problem. The resulting discussions about equity, fairness, covered/uncovered, etc. have always turned out to be quite interesting.

I agree. I go through a similar discussion in my class and let the students go wild on all sorts of what-if scenarios and how to change the model accordingly.

To achieve goal 2 (but not alleviate the issue remedied by goal 3), I’ve always simply reduced the response requirement to 2 minutes rather than 4. This sounds like a better fix overall. Thanks!

I am offering to anyone who has questions, I have this morning, independently solved Dr. Yunes’ nice variant on the optimization problem. Send me a note to mrcoder_ga at hot mail dot com and I will happily discuss it. I like to share and tutor people if they are interested in OR. I won’t even charge you anything but I won’t share my findings unless you can prove to my satisfaction you are not a student. For sure this problems was challenging — about 16 hours to design and code in AMPL (actually GLPK) is what it took me to solve it. But the problem is not overly challenging judging by the fact that I have no graduate school coursework of any kind, just a BA in math. I am not a student, and I did not read anyone else’s solution. I designed my solution and coded it from scratch entirely independently.

Sure, it makes a little bit of sense why academics would not want to share the information on how to solve this except if you take their course. They get paid for sharing their knowledge which I understand. I am OK with it. Now, by contrast I don’t get paid for sharing my knowledge though, so I am happy to share knowledge for nothing except a real interest in the subject. I am a software engineer by trade, unemployed for now on purpose. I get my money by selling software that I create, by the way.

I expect that the excellent professor will not mind if I share my solution vector right here and now, because after all, the model and the software implementation in AMPL are what really matters. Here’s what I get:

[solution deleted by ORbyTheBeach]

Thanks for offering the nice practice problem, professor.

Regards,

Geoffrey

Geoffrey,

Thank you for your comment. I’m happy to see this problem provided you with many hours of fun. I deleted the solution you posted because I don’t want my students (or anyone using Ragsdale’s textbook) to have it. This has nothing to do with me getting paid to share my knowledge; I share my knowledge all the time without expecting any payment in return. Just like I’m sure you learned a lot by trying to solve the problem and not knowing the solution in advance, I want my students to have the same experience. I want them to hit the brick wall and figure out how to jump over it.