# Tag Archives: modeling

## Improving a Homework Problem from Ragsdale’s Textbook

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):

1. 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.
2. 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:

1. It’s not as easy to eyeball an optimal solution as it was before.
2. 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.
3. 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.

Filed under Books, Integer Programming, Modeling, Teaching

## Big Bang Theory Party Planning

Penny is organizing a party at her apartment, but she is on a tight budget. Having a working knowledge of all of the important things in the universe, Sheldon knows everything about linear programming and offered to help her. He postulates that it’s ideal to have two kinds of mixed nuts: a plain party mix, and a luxury mix (for those with a distinct taste like himself). Based on the expected number of guests, Howard quickly calculates that they’ll need a total of at least 10 pounds of snacks, but no more than 6 pounds of each kind of mix. On his white board, Sheldon has already come up with the following table:

Raj wants to dip the hazelnuts into liquor, but that’s not in the budget, so he gives up. Leonard reminds everyone that, because of their allergies, it’s important to keep the average allergenicity level per pound in both mixes to no more than 3. Write an optimization model to help Penny prepare the two kinds of snacks at minimum cost. But be careful: Sheldon will check it later for correctness!

This post is part of my series “Having Fun with Exam Questions”. Previous questions dealt with Farmville, vampires, and (potentially) Valentine’s day.

1 Comment

Filed under Big Bang Theory, Exam Fun, Linear Programming, Modeling, Teaching

## Find Out What Happens to Mr. Lovr

I’ve had a number of people tell me that they like my Valentine’s Day post, but many of them did not solve the Excel Spreadsheet. That’s the most important part of the post! You have to see what happens to Mr. Lovr! There’s no set-up necessary; just open Excel Solver (it’s an add-in you have to enable in Windows and a separate program in the Mac), and click on the “Solve” button. You’ll be glad you did.

Filed under INFORMS Monthly Blog Challenge, Love, Valentine's Day

## Transporting Flowers with Love

Mr. Lovr, a lonely gentleman, does not want to spend Valentine’s day alone in 2011. As one of his New Year’s resolutions, he intends to send roses to nine of his lady friends. Being an avid procrastinator, however, he waits until the last minute and finds out that only eight flower shops in his city still have roses available. For lack of better names, let’s call those flower shops F1, F2, F3, …, F8. The number of bouquets of roses available at each shop are, respectively, 4, 4, 3, 2, 2, 2, 2, and 1. Based on how well he knows each of his potential valentines, whom we’re going to call V1, V2, V3, …, V9, he calculates how many bouquets he needs to send to each of them to increase his chances of going on at least one date. The numbers are, respectively, 3, 2, 2, 2, 2, 2, 2, 2, and 3. At this point, a light bulb goes off in Mr. Lovr’s head, and he remembers from his Operations Research class that this is a transportation problem. But there’s something missing…Ah! The costs! He calls each of the eight flower shops and asks how much it would cost to ship one bouquet of roses to the addresses of each of his nine lady friends. He then compiles the following table of costs (in dollars):

He also remembers that because the total supply is equal to the total demand, he can write all of the constraints in this problem as equalities. Essentially, he has to say that, for each flower shop, the number of bouquets that it ships has to be equal to the number of bouquets that it has. Similarly, he needs one constraint for each valentine saying that the number of bouquets that they receive has to be equal to the number that they want (according to his estimates above). To avoid suspicion, he also decides that it’s better for each flower shop to send no more than one bouquet to the same person. So far, so good, but he needs a specific shipment plan because he’s running out of time.

He opens up an Excel spreadsheet and creates the following layout of cells (he chose pink to make it more romantic):

Somewhere else in his spreadsheet he also typed the table of costs shown above. To his surprise, he even remembered to use the SUMPRODUCT function to calculate the total cost expression. He clicks “Solve” and finds out that the cheapest way to send all 20 bouquets will cost him $38. Not bad…but wait a second…something amazing happened! He cannot believe his eyes! The optimal solution exhibits a very curious pattern! Could it be a Valentine’s Day miracle? Could it be the power of love? If you want to see for yourself, download Mr. Lovr’s spreadsheet, open Excel Solver, and solve the model (no setup necessary, just click the “Solve” button). (NOTE: this spreadsheet has been tested with Excel 2007 under Windows XP, and with Excel 2008 under Mac OS X Snow Leopard. I’m not sure the “trick” will work in earlier Excel versions. For a free download of Excel Solver for Mac OS X, go here.) Thanks to my love for giving me the idea for this blog post. 12 Comments ## Twilight Network Flow CAUTION: Spoiler Alert! Part of a professor’s job is to come up with new exam questions each year. That may be a time-consuming (and sometimes tedious) task. You want the question to be just right: not too easy, not too difficult, and capable of testing whether or not the students understood a given concept. This year, I figured I might as well have some fun while doing it. Inspired by Laura McLay’s insightful (and very popular) post on vampire populations, I decided to create a Twilight-themed network flow question: Alice is in charge of planning Edward and Bella’s wedding and she ordered 2000 roses to be delivered to three locations as shown in the network below. The Cullen’s house (node 2) needs 1000 roses, Charlie’s house (node 4) needs 800 roses, and Billy’s house (node 7) is supposed to get 200 roses (just to tease Jacob). The numbers next to the arcs of the network represent shipping costs per rose (in cents); they’re proportional to the distance between each node. The roses are coming from two local growers in Forks (nodes 1 and 3). Each of them can supply 1000 roses. Arrows with two heads indicate that shipments can be made in both directions. Write down the supply and/or demand values next to each node and write a linear programming model to determine the shipment plan that minimizes the total cost of delivering all the roses (include all the necessary constraints). (Note: Alice already knows whether you’re going to get the right answer.) The second half of the fun is to see if any students react to it. In fact, I got a couple of interesting written comments: “How dare you incorporate Twilight into Management Science?”, and a Harry Potter enthusiast wrote “Team Harry!”, while at the same time substituting the names of Hermione, Harry, Ginny and Malfoy for Alice, Edward, Bella, and Jacob. 4 Comments Filed under Exam Fun, Linear Programming, Modeling, Network Flows, Teaching ## Using Airline Miles to Buy Magazines: a Hidden Deeper Lesson Last month, I received a letter from American Airlines’ Rewards Processing Center saying that I have 4735 miles that are about to expire and asking whether I’d be interested in redeeming them for some magazine subscriptions. These were the choices:  Magazine Issues Miles Needed Afar 6 600 Architectural Digest 12 800 Barron’s 26 1700 Business Week 50 1600 Cat Fancy 12 500 Cigar Aficionado 6 400 Daily Variety 252 5500 Diabetes Forecast 12 500 ESPN the Magazine 26 500 Ebony and Jet 38 800 Elle 12 400 Entertainment Weekly 55 1300 Essence 12 500 Essence 2yrs 24 800 Fortune 25 1400 Golf Digest 12 700 Golf Magazine 12 700 Golfweek 45 1300 Martha Stewart Living 24 1400 Money 12 800 New York Magazine 46 700 Sports Illustrated 56 1400 SI and Golf Mag 68 1500 Sports Illustrated KIDS 12 1000 The Economist 51 3200 The Wall Street Journal 190 2800 US News & World Report 12 700 Variety 50 5500 Wine Spectator 15 900 Wired 12 400 Wow! 30 different magazines! How could I possibly decide…oh, wait! Maybe I can use some analytical techniques to help me make a better decision…what’s that thing called again…O.R.!!! First, what do I want to accomplish? a) Get as many issues of whatever magazine as possible: this is what a dentist’s office or any place with a waiting room might want to do. Note that the WSJ subscription provides 190 issues, but let’s say I only want to consider actual magazines. One possible answer is to subscribe to ESPN the Magazine, Ebony and Jet, Entertainment Weekly, New York Magazine, and Sports Illustrated. That will buy me 221 issues and use 4700 of my 4735 miles. Just out of curiosity, I could have gotten 286 issues if I hadn’t excluded the WSJ. b) Get as many different subscriptions as possible: This one is easy. Just pick the magazines that require the least number of miles. One solution is Afar, Cat Fancy, Cigar Aficionado, Diabetes Forecast, ESPN the Magazine, Elle, Essence, US News & World Report, and Wired. That’s a total of 9 subscriptions, using 4500 of my 4735 miles (a waste of 235 miles). c) Get the “best” 9 magazines you can afford: Since I know I can get 9 subscriptions, what are the 9 that make me use the most out of my 4735 miles? Maybe they’ll constitute a better set of 9 than those I found in item (b) above (positive correlation between quality and miles needed?). In this case the answer is to substitute New York Magazine for Essence in the set of 9 found in item (b). This alternative totals 144 issues and wastes only 35 miles. d) Get the 9 magazines that provide the largest total number of issues: In that case I’d want to go with Cat Fancy, Cigar Aficionado, Diabetes Forecast, ESPN the Magazine, Ebony and Jet, Elle, Essence, New York Magazine and Wired. That’s a total of 176 issues and a waste of 35 miles as well. For those of you who are thinking “who cares?”, don’t let appearances fool you. Say that I am United Way and 4735 is my budget (in thousands of US$). There are 30 charities (“magazines”) asking me for money (the “miles needed”) and telling me that they will help a certain number of people (the “issues”, in thousands). If I fund the charities in rows 9, 10, 12, 21 and 22 of the above table, I’ll spend US$4,700,000 and help 221 thousand people. That’s the best I can do! (if I am not allowed to fund the charity in row 26). Lots of other problems can be cast into this framework. Another example: NASA is sending a spaceship to Mars. My available miles are the spaceship’s cargo capacity, the magazines are scientific experiments to be conducted in space (each requiring equipment to be loaded into the spaceship (the “miles needed”) and promising a certain (quantifiable) scientific benefit (the “issues”). This a generic resource allocation problem and the mathematical model we have used here is called The 0-1 Knapsack Problem. Technical Details: Want to solve your own budget allocation problem? Here’s how you can do it. We have $n$ projects that require funding and a budget $B$. For each project $i = 1,\ldots,n$, let $m_i$ be how much money it needs and let $p_i$ be its payoff (e.g. lives saved). Let the binary variable $x_i$ be equal to 1 if we decide to allocate money to project $i$, and equal to zero otherwise. The objective is to maximize the payoff $\sum_{i=1}^n p_i x_i$. The constraint is to respect the budget: $\sum_{i=1}^n m_i x_i \leq B$. This model also allows you to include some useful side constraints. For example: “if I fund project $i$, then I must also fund project $j$” would be written as $x_i \leq x_j$. And “if I fund project $i$, then I cannot fund project $j$“, would become $x_i + x_j \leq 1$. I’ve talked about these kinds of logical conditions in another post. Here’s the AMPL file I used to solve the magazine problem and its variations. Enjoy! P.S.: Being an Economics major and an amazing cook, my wife requested The Economist and Martha Stewart Living; that’s what her objective function told her to do, I guess. 4 Comments Filed under Applications, Integer Programming, Knapsack, Modeling ## Using a Mathematical Model to Predict the Likelihood of Insurgent Attacks University of Miami physicist Neil Johnson and his co-authors have found that there is a “generic way in which humans carry out insurgency and terrorism when faced by a large powerful state force, and this is irrespective of background history, motivation, ideology, politics, and location”. Their study is featured as the cover of the December 17, 2009 issue of Nature: We have found a unified model of modern insurgent wars that shows a fundamental pattern in the apparent chaos of wars,” says Johnson. “In practical terms, our analysis can be used to create and explore scenarios, make predictions, and assess risks for present and future wars. Here’s a link to the full story that appeared in UM’s E-Veritas publication. This paper will make for some nice holiday reading. Leave a Comment Filed under Applications, Modeling, War ## Let’s Join O.R. Forces to Crack the 17×17 Challenge I recently came across this post by bit-player, which refers to this post by William Gasarch, on a very interesting feasibility problem: given an $m \times n$ grid, assign one of $c$ colors to each position on the grid so that no rectangle ends up with the same color in all of its vertices (see the original post for applications of this problem). Many results are known for different values of $m$, $n$, and $c$, but the challenge (which comes with a reward of US$289) is to decide whether a feasible solution exists when $m=n=17$ and $c = 4$.

Apparently, some attempts have been made to use Integer Programming (IP) to solve this problem:

SAT-solvers and IP-programs have been used but have not worked— however, I don’t think they were tried that seriously.

By writing this post, I hope to get enough O.R. people excited to brainstorm together in search of a solution. Given this is a feasibility problem, another method of choice here would be Constraint Programming (more on that later).

I decided to begin with the first IP formulation that came to mind. I didn’t expect it to close the deal, but I wanted to see how far it would take me. Here it is: let the binary variable $x_{ijt}$ equal 1 if the cell in row $i$ and column $j$ receives color $t$. There are two groups of constraints.

Every cell must have a color:

$\sum_{t=1}^c x_{ijt} = 1, \enspace \forall \; i,j$

Every rectangle can have at most 3 vertices with the same color:

$x_{ijt} + x_{i+a,jt} + x_{i,j+b,t} + x_{i+a,j+b,t} \leq 3, \enspace \forall \; i,j,a,b,t$

where

$1 \leq i \leq m-1$, $1 \leq j \leq n-1$, $1 \leq a \leq m-i$, and $1 \leq b \leq n-j$.

The objective function does not matter (in theory), but my limited experiments indicate that it’s better to minimize the sum of all $x_{ijt}$ than it is to maximize it. Gasarch also provides this diagram with a rectangle-free subset of size 74 for a 17 x 17 grid. I then added constraints of the form $x_{ij1}=1$ for every cell $(i,j)$ with an “R” in the diagram. This may be too restrictive, since it’s not clear to me whether a feasible solution to the 17 x 17 grid must contain that diagram as a subset. If that’s true, the latter constraints help with symmetry breaking and also substantially reduce the problem size. To reduce some of the color symmetry in the problem, I also arbitrarily chose cell (1,1) to contain color 2, i.e. $x_{112}=1$. Note that this still allows colors 3 and 4 to be swapped. I could have set $x_{123}=1$, but that would mean taking a risk.

Finally, for the 17 x 17 grid, it is suspected that each line and each row will have three colors used four times and one color used five times, hence, I also included the following constraints:

$4 \leq \sum_{j=1}^n x_{ijt} \leq 5, \enspace \forall \; i,t$

$4 \leq \sum_{i=1}^m x_{ijt} \leq 5, \enspace \forall \; j,t$

Once again, if my understanding is correct, there’s no formal proof that the above constraints are valid.

Here’s a ZIMPL model that can be used to  generate the .LP files and here’s the 17 x 17 LP. I set CPLEX’s MIP emphasis to 4 (look for hidden feasible solutions) and first ran a 14 x 14 as a warm-up. CPLEX 12.1 finds a feasible solution in under 5 seconds (I substituted 1 for 4 in the color usage constraints above). I stopped the 15 x 15 problem after 12 fruitless hours of search, so 14 x 14 is apparently the largest of the easy instances.

I started the 17 x 17 run last Thursday. The initial IP has 1156 variables and 74,620 constraints. Pre-processing reduces that to 642 variables and 15,775 constraints. After approximately 122 hours and 77,000 nodes on a dual-core machine (3.79 GHz), no solution was found.

Now it’s time for smarter ideas. Here are a few candidates:

1) Try a column-generation approach. It’s easy to find solutions for 8×8 and 9×9 grids, which will appear as sub-grids of a 17×17 solution. So it may be possible to write a set partitioning formulation (with side constraints) that has the 8×8 and 9×9 solutions as variables.

2) Try a meta-heuristic approach (e.g. simulated annealing). This problem is probably one of those for which an almost-feasible solution (like this one) can be very far from a feasible solution.

3) Try constraint programming. I think the main difficulty here will be finding a good variable and value selection heuristic. I started building a Comet model for the problem using the global constraint cardinality; here it is. It still does not include the constraints that fix the color of the rectangle free subset provided by Gasarch, but those are very easy to add (see the code that is commented out).

Let me know what your thoughts and hunches are!