Category Archives: Mathematical Programming

Buying Metrorail Tickets in Miami

(Credits: Thanks to my MBA student Mike Plytynski for the idea for this post.)

Instead of a subway system, Miami has surface trains like the one depicted below. This is known as our Metrorail system. The Metrorail connects to the Tri-Rail system (which takes you north as far as West Palm Beach) and also to the free-to-ride, fully-automated, electrically-powered Metromover.

If you are a (reasonably) frequent Metrorail rider, you may consider buying a rechargeable card at one of the ticket vending machines. There is a 1-day pass ($5.65), a 7-day pass ($29.25), and a monthly pass ($112.50) that offer unlimited rides, but let’s focus on the case when you don’t ride often enough to justify the cost of such passes.

The current cost of a one-way trip is $2.25, regardless of distance traveled. The vending machines at the entrance of each Metrorail station allow you to load the following pre-specified amounts onto your card: $1, $2.25, $3, $4.50, $5, $10, $20, and $40.

No one likes to waste time having to stop by the vending machine to reload the Metrorail card. Besides, by Murphy’s Law, the next train will arrive and depart exactly when you’re stuck in line at the machine trying to reload your card. Therefore, we’ll consider that our objective is to minimize the number of visits to the vending machine to load our card with enough money for n one-way trips. If we were free to load any amount on the card, we could simply load n times $2.25 and be done. The absence of this flexibility is what makes this situation both interesting and a reason for us to hate the Metrorail. So let’s write an optimization model to solve this problem.

Let variable x_1 be the number of times we go to the vending machine to load $1 on the card. Let x_2 be the number of times we load $2.25 on the card, and so on all the way to x_8 (how many times we load $40). To minimize the number of visits to the vending machine, we write the objective function

\min x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8

To make sure we load enough money on the card for n trips, we write the constraint

x_1 + 2.25x_2 + 3x_3 + 4.5x_4 + 5x_5 + 10x_6 + 20x_7 + 40x_8 \geq 2.25n

If we are not careful, we may end up with unnecessarily too much money left on the card. So it’s wise to limit that excess with the constraint

x_1 + 2.25x_2 + 3x_3 + 4.5x_4 + 5x_5 + 10x_6 + 20x_7 + 40x_8 - 2.25n \leq L

where L is a limit on what we’d be willing to have left on the card after the n trips are completed. Conceivably, this leftover amount could be applied toward your next batch of n trips. Hold that thought; we’ll return to it later.

I put together an Excel Solver spreadsheet model for this problem, which you can download from here (sheet named “standard” in the Excel file).

If you change the second constraint above to an equality and solve this problem for different values of n and L, you can create the following heat map. The numbers in the colored squares indicate the minimum number of required visits to the vending machine.

Interestingly, some values of n, such as 10, 18, and 20, are more friendly in the sense that they allow you to visit the machine at most twice while incurring a small leftover amount (no more than $0.50). On the other hand, to avoid visiting the machine more than twice when paying for 12, 14, or 16 trips, you must be willing to accept a much higher ending balance: $3, $8.50, and $4, respectively. In addition, some of the reload amounts that might at first seem useless, such as $5 and $10, actually do get used in the optimal solutions for some values of n and L.

Ending Balances As Multiples of $2.25

As we saw above, allowing for larger ending balances on the card can help reduce the number of visits to the vending machine. One way to make these balances useful is to apply them toward future trips. If the balance is a multiple of the cost of a one-way trip, even better. To do that, we can replace the second constraint above with

x_1 + 2.25x_2 + 3x_3 + 4.5x_4 + 5x_5 + 10x_6 + 20x_7 + 40x_8 - 2.25n = 2.25k

where k is a new, non-negative integer variable. The sheet called “leftover is multiple” in this Excel file implements this version of the optimization model. The conclusion is that you pretty much only need 2 visits to the vending machine for n \leq 20, and the value of k seems to decrease as n increases. (See Excel file for detailed results.)

Now, if only I could get someone from Miami-Dade Transit to read this post…

Advertisements

Leave a comment

Filed under Applications, Integer Programming, Knapsack, Mathematical Programming, Modeling, Motivation, Promoting OR, transportation

Choosing Summer Camps for Your Kids

Today I’m going to write about a decision that’s made by many American families each year: how to pick summer camps for our kids. There are several issues to take into account, such as cost, benefit, hours, and kids’ preferences. I’ll introduce an optimization model for summer camp selection through a numerical example. The example portrays a large family, but the same ideas apply if a few smaller families want to get together and solve this problem. This way they can take advantage of the discounts and take turns driving the kids around.

The Joneses have six kids: Amy, Beth, Cathy, David, Earl and Fred (yes, their first names are alphabetically sorted, matching their increasing order of age; Mr. and Mrs. Jones always knew they’d have six kids and hence named their firstborn with an ‘F’ name). This year, they’ve narrowed down their list of potential summer camps to the following ten: Math, Chess, Nature, Crafts, Cooking, Gymnastics, Soccer, Tennis, Diving, and Fishing. The Nature camp takes kids on a hike through the woods with the guidance of a biologist; they make frequent stops upon encountering specific plants and animals, during which a mini science lecture is delivered (pretty cool!). The Cooking camp involves cooking chemistry instruction, à la Alton Brown (also pretty cool).

The following table contains some data related to each camp:

The Cost column indicates the cost per child. The Discount column indicates the percentage discount that each child enrolled after the first would receive on the cost of each camp. For instance, if three children are enrolled in Math camp, the first would cost $1100, and the second and third would cost $770 each (30% less). The Hours column is self-explanatory and the last two columns indicate whether or not that particular camp develops mental and physical abilities, respectively (a value of one = yes, zero=no).

The next table shows some of the child-specific requirements:

For example, the Joneses want Fred to attend at least 3 camps that develop mental abilities, and at least 1 camp that develops physical abilities. The last two columns in the above table indicate the minimum and maximum number of camp hours for each child over the 9-week summer break.

The next thing parents need to take into account are their children’s preferences. So here they are:

The smaller the number in the above table, the more desirable a particular camp is. For example, Amy is a bit of a math nerd, and if we were to flip David’s preference scores for Math and Tennis, he could be classified as a bit of a jock. Some conflicts exist, in the sense that not all camps are compatible with each other in terms of time schedules. In this particular case, let’s assume that no child can attend both the Soccer and Tennis camps, or both the Nature and Soccer camps. Here’s how we are going to use this preference table to create a sense of fairness among the children: whenever a child that prefers camp X to camp Y goes to camp Y and doesn’t go to camp X, nobody else gets to go to camp X either. For example, if Amy goes to Nature camp and isn’t sent to either Math or Chess camp, none of her siblings are allowed to go to Math or Chess either. Conversely, if the Joneses decide to send Earl to Chess camp and Fred to Tennis camp, they must also send Earl to Tennis camp (because Earl prefers Tennis to Chess, and “Fred is going! Why can’t I go too!”). Clearly, there are other ways to use/interpret this table, such as trying to send everyone to at least one of their top N choices, but we won’t consider those alternatives here.

After taking all of the above issues and conditions into account, here’s a solution that satisfies all the requirements while resulting in the minimum cost of $22,180.00 (You guessed it…the Joneses are probably *not* among the 99%):

Amy goes to Math, Crafts, Cooking, and Tennis; Beth goes to Math, Cooking, Tennis, and Fishing; Cathy goes to Math, Crafts, Tennis, and Fishing; David goes to Math, Cooking, and Fishing; Earl goes to Math, Tennis, and Fishing; and Fred goes to Math, Crafts, Cooking, and Tennis. Mmm…interestingly, everyone goes to Math camp. I think the Joneses are on to something…

Depending on your own requirements, preferences, and costs your solution may differ, of course. But this should give you an idea of how this simple problem can easily become very complicated to solve. No need to fear, though! Operations Research is here!

Food for Thought: Here’s an interesting question that helps illustrate how high-quality solutions can be counterintuitive: by looking at the preferences table, we see that everyone prefers Soccer to Tennis. In addition, Soccer camp is less expensive than Tennis camp. So how come we send almost everyone to Tennis camp? Isn’t that strange? Let me know what you think in the comments below! That’s one of the advantages of using an analytical approach to decision making: it helps us find solutions we wouldn’t even consider otherwise because they don’t seem to make sense (at least not at first).

If you’re curious about how I managed to find the optimal solution, read on!

Details of the Analysis:

To find the minimum-cost solution, we can create a mathematical representation of the problem, a.k.a. a model, and then solve this model with the help of a computer. Let’s see how.

The first obvious decision to make is who goes where. So let the binary variable x_{ij} equal 1 when child i goes to camp j, and equal to 0 otherwise. We’ll also need another binary variable y_j that is equal to 1 when at least one child goes to camp j and equal to 0 when none of the children go to camp j. We are now ready to write our objective function and constraints. I’ll refer to the problem data using the column headings of the tables above. The subscript i will always refer to a child, and the subscript j will always refer to a camp.

To minimize the total cost, we write the following objective function:

\displaystyle \min \sum_i \sum_j (1-\mathrm{Discount}_j)\mathrm{Cost}_j x_{ij} + \sum_j \mathrm{Discount}_j \mathrm{Cost}_j y_j

Note how we are using the y_j variable to handle the discount for sending more than one child to camp j: we charge every child the discounted price in the double summation and add the discount back in only once if y_j=1.

Now we have to deal with the four requirements: minimum and maximum hours, mental activity, and physical activity. For every child i, we have to write the following four constraints:

\displaystyle \sum_j \mathrm{Hours}_j x_{ij} \geq \mathrm{MinTimeReq}_i

\displaystyle \sum_j \mathrm{Hours}_j x_{ij} \leq \mathrm{MaxTimeReq}_i

\displaystyle \sum_j \mathrm{IsMental}_j x_{ij} \geq \mathrm{MentalReq}_i

\displaystyle \sum_j \mathrm{IsPhysical}_j x_{ij} \geq \mathrm{PhysicalReq}_i

Next, we enforce the preference rules. Let’s recall the example involving Earl and Fred: if Earl goes to Chess camp and someone else (it doesn’t matter who) goes to Tennis camp, then Earl has to go to Tennis camp as well. Here’s what this constraint would look like:

x_{\mathrm{Earl},\mathrm{Chess}} + y_{\mathrm{Tennis}} - x_{\mathrm{Earl},\mathrm{Tennis}} \leq 1

Of course, we have to repeat this constraint for every child i and every pair of camps j_1 and j_2 such that child i prefers j_1 to j_2 in the following way:

x_{ij_2} + y_{j_1} - x_{ij_1} \leq 1

The camp compatibility constraints say that no child i can attend both Soccer and Tennis, or both Nature and Soccer, therefore:

x_{i,\mathrm{Soccer}} + x_{i,\mathrm{Tennis}} \leq 1

x_{i,\mathrm{Nature}} + x_{i,\mathrm{Soccer}} \leq 1

Finally, we need to relate the x_{ij} and y_j variables by stating that unless y_j=1 , no x_{ij} can be equal to 1 . So we write the following constraint for all values of i and j :

x_{ij} \leq y_j

And that’s the end of our model. Here’s a representation of this mathematical model in AMPL in case you want to play with it yourself. This is the model I used to obtain the numerical results reported above. Enjoy!

5 Comments

Filed under Applications, INFORMS Monthly Blog Challenge, Integer Programming, Mathematical Programming, Modeling, Motivation, Promoting OR, Summer camp

Optima Newsletter

optimaThe main focus of my research so far has been on the integration of optimization techniques. Although I have used Integer Programming theory, I hadn’t (until recently) done research on creating new IP theory. Perhaps as a result of that, I spent many years unaware of Optima, the newsletter of the Mathematical Programming Society. Thanks to my recent trip to the ISMP, however, I was able to get a hold of issues 76 through 79 of Optima (they’re also available online). A quick browse through the pages left me with a very good impression. Every single issue had a discussion or short paper on a topic that interested me, and I can’t wait to sit down to read them more carefully (see for instance Javier Peña‘s article on Nash Equilibria Computation via Smoothing Techniques (Nov 2008 issue); Texas Hold’em poker anyone?). I particularly like the fact that the short papers are written at a more accessible level (at least to me), when compared to papers published in Mathematical Programming; it’s a great way to get introduced to a new topic. Another great feature are the Discussion Columns, which give expert opinions and historical perspectives about  a variety of topics.

I’m glad I came across Optima and did not shy away from grabbing some of the free issues available at ISMP. I strongly recommend it to anyone interested in the field of mathematical programming.

Leave a comment

Filed under Mathematical Programming