Tag Archives: knapsack

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…

Leave a comment

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

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.


Filed under Applications, Integer Programming, Knapsack, Modeling