# Category Archives: Applications

## Enforcing a Restricted Smoking Policy on the UM Campus: a TSP Variant

The Coral Gables campus of the University of Miami is slowly transitioning into a smoke-free campus. (I can’t wait for that to happen.) Presently, there are a number of designated smoking areas (DSAs) around campus and nobody is supposed to smoke anywhere else. Here’s a map of campus with red dots representing DSAs (right-click on it and open it in a new tab to see a larger version):

Unfortunately, enforcement of this smoking policy is nowhere to be seen. The result? Lots of students smoking wherever they want and, even worse, smoking while walking around campus, which is a great way to maximize their air pollution effect. Don’t you love people who live in the universe of me, myself, and I? But let me stop ranting and return to operations research…

As someone who does not enjoy (and is allergic to) cigarette smoke, I started thinking about how to use OR to help with the enforcement effort. Let’s say there will be an enforcer (uniformed official) whose job is to walk around campus in search of violators. Based on violation reports submitted by students, faculty and staff, the University can draw a second set of colored dots, say black, on the above map. These black dots represent the non-smoking areas in which violations have been reported most often. For simplicity, let’s call them violation areas, or VAs.

In possession of the VA map, what is the enforcer supposed to do? You probably answered “walk around campus visiting each VA”. If you’re now thinking about the Traveling Salesman Problem (TSP), you’re on the right track. The enforcer has to visit each VA and return to his/her starting point. However, this is not quite like a pure TSP. Let me explain why. First of all, unlike the pure TSP, the enforcer has to make multiple passes through the VAs on a single day. Secondly, it’s also likely that some VAs are more popular than others. Therefore, we’d like the enforcer to visit them more often. Finally, we want the multiple visits to each VA to be spread throughout the day. With these considerations in mind, let me define the Smoking Policy Enforcement Problem (SPEP): We are given a set of $n$ locations on a map. For each location $i$, let $v_i$ be the minimum number of times the enforcer has to visit $i$ during the day, and let $s_i$ be the minimum separation between consecutive visits to location $i$. In other words, each time the enforcer visits $i$, he/she has to visit at least $s_i$ other locations before returning to $i$. The goal is to find a route for the enforcer that satisfies the visitation requirements ($v_i$ and $s_i$) while minimizing the total distance traveled.

After a few Google searches, I discovered that the SPEP is not a new problem. This shouldn’t have come as a surprise, given the TSP is one of the most studied problems in the history of OR. The article I found, written by R. Cheng, M. Gen, and M. Sasaki, is entitled “Film-copy Deliverer Problem Using Genetic Algorithms” and appeared in Computers and Industrial Engineering 29(1), pp. 549-553, 1995. Here’s how they define the problem:

There are a few minor differences with respect to the SPEP. In the above definition, $s_i=1$ for every location $i$. What they call $d_i$ is what I call $v_i$, and they require exactly $d_i$ visits, whereas I require at least $v_i$ visits.

I wasn’t aware of this TSP variant and I think it’s a very interesting problem. I’m happy to have found yet another application for it. Can you think of other contexts in which this problem appears? Let me know in the comments.

2 Comments

Filed under Applications, Motivation, Traveling Salesman Problem

## Installing iPhone Apps: Apple Doesn’t Care About Average Completion Time

Having recently spent some time outside the US, I found, upon my return, that many of the Apps on my iPhone needed to be updated. No big deal: I clicked “Update all”, typed in my password, and let the operating system finish the job. After watching the update process for a minute or so, I noticed one interesting fact: Apps were updated (i.e. downloaded+installed) in the order the updates became available (chronologically increasing), rather than by increasing order of the size of the update (in bytes). If you’re asking “why does it matter?”, read on.

During my grad school years at Carnegie Mellon, I had the pleasure of taking the Sequencing and Scheduling class with Egon Balas (I later sat in the class again as his TA, and finally taught it to the MBA students in 2004). So let’s start with some terminology: given a machine (the iPhone) and a set of tasks (Apps) to be executed (updated) on the machine, the completion time of a task is the time at which it is finished. For example, let’s assume the Concorde TSP App needs an update. If time zero is the moment I enter my iTunes password, the completion time of task “Concorde TSP” is the earliest time at which this App’s latest version is ready to run on my iPhone. The total completion time of a set of tasks is simply the sum of the completion times of all tasks, and the makespan is the completion time of the task that gets updated last.

The App update process has no release dates (all outdated Apps are ready to be updated at time zero), is non-preemptive (once started, the update of an App continues until it’s finished; ignoring crashes and other issues), and doesn’t involve sequence-dependent setup times (as soon as an App finishes updating, the next App in line can start its update right away). Under these circumstances, the makespan of a group of outdated Apps is always the same, regardless of the order in which they get updated. For example, if App A takes 15 seconds to download and install, and App B takes 10 seconds to download and install, it will take me 25 seconds to update both of them, regardless of which one is updated first. So far, so good. But let’s see what happens with the total (or average) completion time.

Continuing with the two-App example above, if I update the Apps in the order A, B, the completion time of A is 15, and the completion time of B is 25. The total completion time is 15+25=40, and the average completion time is 40/2=20 seconds. If the Apps are updated in the reverse order B, A, the completion time of B is 10, and the completion time of A is 25. The total completion time now is 10+25=35, and the average completion time decreases to 35/2=17.5 seconds. If there were other Apps being updated before or after the pair A, B, swapping them to make sure that B goes before A (because B takes less time) would have the same effect (the A, B swap doesn’t change the completion time of other Apps). What I just explained is called an exchange argument. It proves that whenever two Apps are out of order (in the sense that a smaller one is placed after a larger one), swapping them reduces the total/average completion time. Therefore, the minimum total/average completion time is obtained when the Apps are sorted by increasing order of duration. In the scheduling literature, this is called the SPT rule (Shortest Processing Time first).

I still haven’t answered the question of whether all of this matters because the makespan doesn’t depend on the order of Apps (updating A and B always takes 25 seconds). The answer is I don’t know! It’s a psychological effect. Shorter completion times may give the user the impression that the update process is going fast because a bunch of small Apps get updated quickly. By updating larger Apps first, the user may have the impression that the process is taking longer because, after a while, there are still many Apps to go. Should Apple worry about this? I’ll leave that question to my colleagues in the Marketing department who specialize in Consumer Behavior. If the answer turns out to be “yes”, then you now know what to do.

P.S. I’d like to know what other mobile operating systems do. Do they use SPT? Please let me know in the comments.

5 Comments

Filed under Applications, iPhone

## How Should Santa Pair Up His Reindeer?

It’s almost Christmas time and Santa is probably very busy with some last-minute preparations before his longer-than-7.5-million-kilometer trip around the world. One of the many things he has to worry about is how to pair up his reindeer in front of the sleigh. We all know that Rudolf goes right in front of everyone else because of his shiny nose, but what about his other eight four-legged friends? The traditional Christmas carols tell us that the reindeer are typically arranged in four pairs, front to back, as follows:

Dasher, Dancer

Prancer, Vixen

Comet, Cupid

Donner, Blitzen

Therefore, we are going to assume that this is an arrangement that works pretty well (after all it’s been working since 1823). As someone with a degree in a STEM field (he wouldn’t reveal which, though), Santa can’t stop thinking about this interesting question: “Are there other good ways to pair up my reindeer?” Before we can answer that question, we need to define what a “good” pairing of reindeer is. After working tirelessly on Christmas eve, Santa’s reindeer have all the other 364 days of the year to hang out and get to know each other. As in every group of friends who spend a lot of time together, some friendships become closer than others. So it’s reasonable to expect that Rudolf’s eight friends will have a favorite companion for side-by-side galloping, a second favorite, a third favorite, etc. In addition, there’s one more important detail when it comes to reindeer pairings, according to Mrs. Claus: some of them like to be on the left side (Dasher, Prancer, Comet, and Donner), while others prefer to ride on the right side in front of Santa’s sleigh (Dancer, Vixen, Cupid, and Blitzen). Before you mention that I should also consider that male reindeer would rather be side-by-side with female reindeer, there’s scientific evidence that all of Santa’s reindeer are female, so we don’t have to worry about that.

After a nice conversation in front of his cozy fireplace, Santa was kind enough to provide me with the following lists of pairing preferences for each of his reindeer; though he vehemently asked me not to show any of this to his furry friends. I’m counting on you, my readers, to keep these lists to yourselves! The names in each list are sorted in decreasing order of pairing preference. The lefties appear in blue, while the righties appear in red (any resemblance to US political parties is a mere coincidence):

Dasher: Dancer, Cupid, Vixen, Blitzen

Prancer: Vixen, Blitzen, Dancer, Cupid

Comet: Cupid, Dancer, Blitzen, Vixen

Donner: Blitzen, Vixen, Dancer, Cupid

Dancer: Prancer, Comet, Dasher, Donner

Vixen: Dasher, Donner, Prancer, Comet

Cupid: Prancer, Dasher, Comet, Donner

Blitzen: Comet, Prancer, Donner, Dasher

Note that if we were to adhere to the lefties’ first picks, we’d end up with the traditional line-up. We are now ready to define what a good pairing is: a pairing is good (a.k.a. stable) if no one has an incentive to change pairs. In other words, if A is paired up with B, and A prefers C to B, it so happens that C, who is paired up with D, prefers D to A. (Note: this problem is known in the literature as the stable marriage problem and it arises in real life, for example, in the context of the National Resident Matching Program, which pairs up medical residents with hospitals every year in the United States.) Obviously, the traditional pairing shown above satisfies these goodness/stability conditions, given the reindeer’s preferences.

What Santa would like to know is whether or not there are other good pairings in addition to the traditional one. If so, he can add some variety to his line-up and the reindeer won’t get so bored by galloping side-by-side with the same companion every year. How can we help Santa answer this question? Using Operations Research, of course! More precisely, Constraint Programming (CP).

Constraint Programming is a modeling and solution paradigm for feasibility and optimization problems that allows one to represent complicated requirements (such as the stability condition above) in ways that are often easier and simpler than using traditional O.R. techniques such as Integer Programming. For example, indexing variables with variables and expressing logical constraints such as implications are a piece of cake in CP. Here’s a CP model written in the Comet language (not to be confused with Comet the reindeer) that answers Santa’s question. It essentially enforces the stability condition for every choice of A, B, C, and D.

The good news is that, in 3 milliseconds, that CP model finds all of the five different stable pairings. Here they are:

Update (1/1/2012): Here’s an AIMMS version of the CP model, kindly created and provided by Chris Kuip. Look for this reindeer example, including an accompanying graphical user interface, in an upcoming update to the set of examples in AIMMS.

I hope Santa reads this blog post before Christmas eve, but in case he doesn’t, please tell him to check this out if you run into him this holiday season. I’m sure his reindeer would appreciate a little change after 189 years.

9 Comments