# Category Archives: Motivation

## How to Build the Best Fantasy Football Team, Part 2

UPDATE on 10/5/2015: Explained how to model a requirement of baseball leagues (Requirement 4).

UPDATE on 10/8/2015: Explained how to model a different objective function (Requirement 5).

Yesterday, I wrote a post describing an optimization model for picking a set of players for a fantasy football team that maximizes the teams’ point projection, while respecting a given budget and team composition constraints. In this post I’ll assume you’re familiar with that model. (If you are not, please spend a few minutes reading this first.)

Fellow O.R. blogger and Analytics expert Matthew Galati pointed out that my model did not include all of the team-building constraints that appear on popular fantasy football web sites. Therefore, I’m writing this follow-up post to address this issue. (Thanks, Matthew!) My MBA student Kevin Bustillo was kind enough to compile a list of rules from three sites for me. (Thanks, Kevin!) After looking at them, it seems my previous model fails to deal with three kinds of requirements:

1. Rosters must include players from at least $N_1$ different NFL teams ($N_1=2$ for Draft Kings and $N_1=3$ for both Fan Duel and Yahoo!).
2. Rosters cannot have more than $N_2$ players from the same team ($N_2=4$ for Fan Duel and $N_2=6$ for Yahoo! Draft Kings does not seem to have this requirement).
3. Players in the roster must represent at least $N_3$ different football games (Only Draft Kings seems to have this requirement, with $N_3=2$).

Let’s see what the math would look like for each of the three requirements above. (Converting this math into Excel formulas shouldn’t be a problem if you follow the methodology I used in my previous post.) I’ll be using the same variables I had before (recall that binary variable $x_i$ indicates whether or not player $i$ is on the team).

Requirement 1

Last time I checked, the NFL had 32 teams, so let’s index them with the letter $j=1,2,\ldots,32$ and create 32 new binary variables called $y_j$, each of which is equal to 1 when at least one player from team $j$ is on our team, and equal to zero otherwise. The requirement that our team must include players from at least $N_1$ teams can be written as this constraint:

$\displaystyle \sum_{j=1}^{32} y_j \geq N_1$

The above constraint alone, however, won’t do anything unless the $y_j$ variables are connected with the $x_i$ variables via additional constraints. The behavior that we want to enforce is that a given $y_j$ can only be allowed to equal 1, if at least one of the players from team $j$ has its corresponding $x$ variable equal to 1. To make this happen, we add the constraint below for each team $j$:

$\displaystyle y_j \leq \sum_{\text{all players } i \text{ that belong to team } j} x_i$

For example, if the Miami Dolphins are team number 1 and their players are numbered from 1 to 20, this constraint would look like this: $y_1 \leq x_1 + x_2 + \cdots + x_{20}$

Requirement 2

Repeat the following constraint for every team $j$:

$\displaystyle \sum_{\text{all players } i \text{ that belong to team } j} x_i \leq N_2$

Assuming again that the first 2o players represent all the players from the Miami Dolphins, this constraint on Fan Duel would look like this: $x_1 + x_2 + \cdots + x_{20} \leq 4$

Requirement 3

My understanding of this requirement is that it applies to short-term leagues that get decided after a given collection of games takes place (it could even be a single-day league). This could be implemented in a way that’s very similar to what I did for requirement 1. Create one binary $z_g$ variable for each game $g$. It will be equal to 1 if your team includes at least one player who’s participating in game $g$, and equal to zero otherwise. Then, you need this constraint

$\displaystyle \sum_{\text{all games } g} z_g \geq N_3$

as well as the constraint below repeated for each game $g$:

$\displaystyle z_g \leq \sum_{\text{all players } i \text{ that participate in game } g} x_i$

Additional Requirements Submitted by Readers

I earlier claimed that this model can be adapted to fit fantasy leagues other than football. So here’s a question I received from one of my readers:

For fantasy baseball, some players can play multiple positions. E.g. Miguel Cabrera can play 1B or 3B. I currently use OpenSolver for DFS and haven’t found a good way to incorporate this into my model. Any ideas?

Let’s call this…

Requirement 4: What if some players can be added to the team at one of several positions?

Here’s how to take care of this. Given a player $i$, let the index $t=1,2,\ldots,T_i$ represent the different positions he/she can play. Instead of having a binary variable $x_i$ representing whether or not $i$ is on the team, we have binary variables $x_{it}$ (as many as there are possible values for $t$) representing whether or not player $i$ is on the team at position $t$. Because a player can either not be picked or picked to play one position, we need the following constraint for each of these multi-position players:

$\displaystyle \sum_{t=1}^{T_i} x_{it} \leq 1$

Because we have replaced $x_i$ with a collection of $x_{it}$‘s, we need to replace all occurrences of $x_i$ in our model with $(x_{i1} + x_{i2} + \cdots + x_{iT_i})$.

In the Miguel Cabrera example above, let’s say Cabrera’s player ID (the index $i$) is 3, and that $t=1$ represents the first-base position, and $t=2$ represents the third-base position. The constraint above would become

$x_{31} + x_{32} \leq 1$

And we would replace all occurrences of $x_3$ in our model with $(x_{31} + x_{32})$.

That’s it!

Reader rs181602 asked me the following question:

I was wondering, is there a way to add an additional constraint that maximizes the minimum rating of the chosen players, if each player has some rating score. I tried to think that out, but can’t seem to get it to be linear.

Let’s call this…

Requirement 5: What if I want to maximize the point projection of the worst player on the team? (In other words, how do I make my worst player as good as possible?)

It’s possible to write a linear model to accomplish this. Technically speaking, we would be changing the objective function from maximizing the total point projection of all players on the team to maximizing the point projection of the worst player on the team. (There’s a way to do both together (sort of). I’ll say a few words about that later on.)

Here we go. Because we don’t know what the projection of the worst player is, let’s create a variable to represent it and call it $z$. The objective then becomes:

$\max z$

You might have imagined, however, that this isn’t enough. We defined in words what we want $z$ to be, but we still need formulas to make $z$ behave the way we want. Let $M$ be the largest point projection among all players that could potentially be on our team. It should be clear to you that the constraint $z\leq M$ is a valid ceiling on the value of $z$. In fact, the value of $z$ will be limited above by 9 values/ceilings: the 9 point projections of the players on the team. We want the lowest of these ceilings to be as high as possible.

When a player $i$ is not on the team ($x_i=0$), his point projection $p_i$ should not interfere with the value of $z$. When player $i$ is on the team ($x_i=1$), we would like $p_i$ to become a ceiling for $z$, by enforcing $z\leq p_i$. The way to make this happen is to write a constraint that changes its behavior depending on the value of $x_i$, as follows:

$z \leq p_ix_i + M(1-x_i)$

We need one of these for each player. To see why the constraint above works, consider the two possibilities for $x_i$. When $x_i=0$ (player not on the team), the constraint reduces to $z\leq M$ (the obvious ceiling), and when $x_i=1$ (player on the team), the constraint reduces to $z\leq p_i$ (the ceiling we want to push up).

BONUS: What if I want, among all possible teams that have the maximum total point projection, the one team whose worst player is as good as possible? To do this, you solve two optimization problems. First solve the original model maximizing the total point projection. Then switch to this $\max z$ model and include a constraint saying that the total point projection of your team (the objective formula of the first model) should equal the total maximum value you found earlier.

That’s it!

And that does it, folks!

Does your league have other requirements I have not addressed here? If so, let me know in the comments. I’m sure most (if not all) of them can be incorporated.

24 Comments

Filed under Analytics, Applications, Integer Programming, Modeling, Motivation, Sports

## How to Build the Best Fantasy Football Team

Note 1: This is Part 1 of a two-part post on building fantasy league teams. Read this first and then read Part 2 here.

Note 2: Although the title says “Fantasy Football”, the model I describe below can, in principle, be modified to fit any fantasy league for any sport.

I’ve been recently approached by several people (some students, some friends) regarding the creation of optimal teams for fantasy football leagues. With the recent surge of betting sites like Fan Duel and Draft Kings, this has become a multi-million (or should I say, billion?) dollar industry. So I figured I’d write down a simple recipe to help everybody out. We’re about to use Prescriptive Analytics to bet on sports. Are you ready? Let’s do this! I’ll start with the math model and then show you how to make it all work using a spreadsheet.

The Rules

The fantasy football team rules state that a team must consist of:

• 1 quarterback (QB)
• 2 running backs (RB)
• 3 wide receivers (WR)
• 1 tight end (TE)
• 1 kicker
• 1 defense

Some leagues also have what’s called a “flex player”, which could be either a RB, WR, or TE. I’ll explain how to handle the flex player below. In addition, players have a cost and the person creating the team has a budget, call it $B$, to abide by (usually $B$ is $50,000 or$60,000).

The Data

For each player $i$, we are given the cost mentioned above, call it $c_i$, and a point projection $p_i$. The latter is an estimate of how many points we expect that player to score in a given week or game. When it comes to the defense, although it doesn’t always score, there’s also a way to calculate points for it (e.g. points prevented). How do these point projections get calculated, you may ask? This is where Predictive Analytics come into play. It’s essentially forecasting. You look at past/recent performance, you look at the upcoming opponent, you look at players’ health, etc. There are web sites that provide you with these projections, or you can calculate your own. The more accurate you are at these predictions, the more likely you are to cash in on the bets. Here, we’ll take these numbers as given.

The Optimization Model

The main decisions to be made are simple: which players should be on our team? This can be modeled as a yes/no decision variable for each player. So let’s create a binary variable called $x_i$ which can only take two values: it’s equal to the value 1 when player $i$ is on our team, and it’s equal to the value zero when player $i$ is not on our team. The value of $i$ (the player ID) ranges from 1 to the total number of players available to us.

Our objective is to create a team with the largest possible aggregate value of projected points. That is, we want to maximize the sum of point projections of all players we include on the team. This formula looks like this:

$\max \displaystyle \sum_{\text{all } i} p_i x_i$

The formula above works because when a player is on the team ($x_i=1$), its $p_i$ gets multiplied by one and is added to the sum, and when a player isn’t on the team ($x_i=0$) its $p_i$ gets multiplied by zero and doesn’t get added to the final sum. The mechanism I just described is the main idea behind what makes all formulas in this model work. For example, if the point predictions for the first 3 players are 12, 20, and 10, the maximization function start as: $\max 12x_1 + 20x_2 + 10x_3 + \cdots$

The budget constraint can be written by saying that the sum of the costs of all players on our team has to be less than or equal to our budget $B$, like this:

$\displaystyle \sum_{\text{all }i} c_i x_i \leq B$

For example, if the first 3 players cost 9000, 8500, and 11000, and our budget is 60,000, the above formula would look like this: $9000x_1 + 8500x_2 + 11000x_3 + \cdots \leq 60000$.

To enforce that the team has the right number of players in each position, we do it position by position. For example, to require that the team have one quarterback, we write:

$\displaystyle \sum_{\text{all } i \text{ that are quarterbacks}} x_i = 1$

To require that the team have two running backs and three wide receivers, we write:

$\displaystyle \sum_{\text{all } i \text{ that are running backs}} x_i = 2$

$\displaystyle \sum_{\text{all } i \text{ that are wide receivers}} x_i = 3$

The constraints for the remaining positions would be:

$\displaystyle \sum_{\text{all } i \text{ that are tight ends}} x_i = 1$

$\displaystyle \sum_{\text{all } i \text{ that are kickers}} x_i = 1$

$\displaystyle \sum_{\text{all } i \text{ that are defenses}} x_i = 1$

The Curious Case of the Flex Player

The flex player adds an interesting twist to this model. It’s a player that, if I understand correctly, takes the place of the kicker (meaning we would not have the kicker constraint above) and can be either a RB, WR, or TE. Therefore, right away, we have a new decision to make: what kind of player should the flex be? Let’s create three new yes/no variables to represent this decision: $f_{\text{RB}}$, $f_{\text{WR}}$, and $f_{\text{TE}}$. These variables mean, respectively: is the flex RB?, is the flex WR?, and is the flex TE? To indicate that only one of these things can be true, we write the constraint below:

$f_{\text{RB}} + f_{\text{WR}} + f_{\text{TE}} = 1$

In addition, having a flex player is equivalent to increasing the right-hand side of the constraints that count the number of RB, WR, and TE by one, but only for a single one of those constraints. We achieve this by changing these constraints from the format they had above to the following:

$\displaystyle \sum_{\text{all } i \text{ that are running backs}} x_i = 2 + f_{\text{RB}}$

$\displaystyle \sum_{\text{all } i \text{ that are wide receivers}} x_i = 3 + f_{\text{WR}}$

$\displaystyle \sum_{\text{all } i \text{ that are tight ends}} x_i = 1 + f_{\text{TE}}$

Note that because only one of the $f$ variables can be equal to 1, only one of the three constraints above will have its right-hand side increased from its original value of 2, 3, or 1.

Other Potential Requirements

Due to personal preference, inside information, or other esoteric considerations, one might want to include other requirements in this model. For example, if I want the best team that includes player number 8 and excludes player number 22, I simply have to force the x variable of player 8 to be 1, and the x variable of player 22 to be zero. Another constraint that may come in handy is to say that if player 9 is on the team, then player 10 also has to be on the team. This is achieved by:

$x_9 \leq x_{10}$

If you wanted the opposite, that is if player 9 is on the team then player 10 is NOT on the team, you’d write:

$x_9 + x_{10} \leq 1$

Other conditions along these lines are also possible.

Putting It All Together

If you were patient enough to stick with me all the way through here, you’re eager to put this math to work. Let’s do it using Microsoft Excel. Start by downloading this spreadsheet and opening it on your computer. Here’s what it contains:

• Column A: list of player names.
• Column B: yes/no decisions for whether a player is on the team (these are the x variables that Excel Solver will compute for us).
• Columns C through H: flags indicating whether or not a player is of a given type (0 = no, 1 = yes).
• Columns I and J: the cost and point projections for each player.

Now scroll down so that you can see rows 144 through 150. The cells in column B are currently empty because we haven’t chosen which players to add to the team yet. But if those choices had been made (that is, if we had filled column B with 0’s and 1’s), multiplying column B with column C in a cell-wise fashion and adding it all up would tell you how many quarterbacks you have. I have included this multiplication in cell C144 using the SUMPRODUCT formula. In a similar fashion, cells D144:H144 calculate how many players of each kind we’d have once the cells in column B receive values. The calculations of total team cost and total projected points for the team are analogous to the previous calculations and also use the SUMPRODUCT formula (see cells I144 and J144). You can try picking some players by hand (putting 1’s in some cells of column B) to see how the values of the cells in row 144 will change.

If you now open the Excel Solver window (under the Data tab, if your Solver add-in is active), you’ll see that I already have the entire model set up for you. If you’ve never used Excel Solver before, the following two-part video will get you started with it: part 1 and part 2.

The objective cell is J144, and that’s what we want to maximize. The variables (a.k.a. changing cells) are the player selections in column B, plus the flex-player type decisions (cells D147:F147). The constraints say that: (1) the actual number of players of each type (C144:H144) are equal to the desired number of each type (C146:H146), (2) the total cost of the team (I144) doesn’t exceed the budget (I146), (3) the three flex-player binary variables add up to 1 (D150 = F150), and, (4) all variables in the problem are binary. (I set the required number of kickers in cell G146 to zero because we are using the flex-player option. If you can have both a flex player and a kicker, just type a 1 in cell G146.) If you click on the “Solve” button, you’ll see that the best answer is a team that costs exactly $50,000 and has a total projected point value of 78.3. Its flex player ended up being an RB. This model is small enough that I can solve it with the free student version of Excel Solver (which comes by default with any Office installation). If you happen to have more players and your total variable count exceeds 200, the free solver won’t work. But don’t despair! There exists a great Solver add-in for Excel that is also free and has no size limit. It’s called OpenSolver, and it will work with the exact same setup I have here. That’s it! If you have any questions or remarks, feel free to leave me a note in the comments below. UPDATE: In a follow-up post, I explain how to model a few additional fantasy-league requirements that are not included in the model above. 18 Comments Filed under Analytics, Applications, Integer Programming, Modeling, Motivation, Sports ## Optimally Resting NBA Players To celebrate the start of the 2013-2014 NBA season this past Tuesday, I decided to write a post on basketball. More specifically, on the important issue of how to give players some much needed rest in an “optimal” way. My inspiration came from an article by Michael Wallace published on ESPN.com on October 19. Here are some relevant excerpts: After playing in the Miami Heat’s first five preseason games, LeBron James sat out Saturday night’s 121-96 victory over the San Antonio Spurs to rest…James said the decision to sit was part of the team’s “maintenance” process. Heat teammate Dwyane Wade played Saturday and scored 25 points in 26 minutes, but previously skipped three preseason games…”No, no injuries — just not suiting up,” James said. “It’s OK for LeBron to take one off.” The key term here is maintenance process. You may also recall that, back in November 2012, the Spurs were fined$250,000 by the league after coach Popovich sent Duncan, Parker, Ginobili, and Green home right before a game against the Miami Heat.

So we want to rest our players to keep them healthy, but this cannot come at the expense of losing games. There are many factors to be taken into account here, such as players’ current physical condition, strength and tightness of schedule, and match-ups (how well a team stacks up against another team), to name a few. This is definitely not an easy problem. However, some insight is better than no insight at all. Therefore, let’s see what we can do with a simple O.R. model, and then we can talk about the strengths and weaknesses of our initial approach. (Here’s where you, dear reader, are supposed to chime in!)

Let’s begin with two simple assumptions: (i) when it comes to resting, we have to take players’ individual needs into account, i.e., we’ll use player-specific data; and (ii) when it comes to the likelihood of beating an opposing team, it’s better to think in terms of full lineups, rather than in terms of individual players, i.e., we’ll use lineup-specific data. The data in assumption (i) comes from doctors, players’ medical records, and coaches’ strategies. In essence, it boils down to one number: how many minutes, at most, should each player play in each game, under ideal circumstances. A useful measure of the strength of a lineup is its adjusted plus-minus score (see, for example, the work of Wayne Winston and his book Mathletics). In summary, it’s a number that tells you how many points a given lineup plays above (or below) an average lineup in the league over 48 minutes (or over 100 possessions, or another metric of reference).

For the sake of explanation, I’ll pretend to be in charge of resting Miami Heat players (surprise!). I’ll refer to a generic lineup by the letter $i$ ($i=1,\ldots,8$), to a generic player by the letter $j$ ($j=$ LeBron, D-Wade, …, Andersen (Bird Man)), and to a generic game by the letter $k$.

We’re now ready to begin. Fasten your seat belts!

What are the decisions to be made? Let’s consider a planning horizon that consists of the next 7 games (or pick your favorite number). So $k=1,\ldots,7$. For the Heat, the first 7 games of the 2013-2014 season are against the following teams: Bulls, 76ers, Nets, Wizards, Raptors, Clippers, and Celtics. For each one of my potential lineups $i$ and each game $k$, I want to figure out the number of minutes I should use lineup $i$ during game $k$. Because this is an unknown number right now, it’s a variable in the model. Let’s call it $x_{ik}$. Note it’s also OK to think of $x_{ik}$ as a percentage, rather than minutes. I’ll adopt the latter interpretation.

What are the constraints in this problem? There are three main constraints to worry about: (a) make sure to pick enough lineups to play each game in its entirety; (b) make sure your lineups are good enough to hopefully beat your opponents in each game; (c) keep track of players’ minutes, and don’t let them get out of hand. The next step is to represent each constraint mathematically.

Constraint (a): Pick enough lineups to completely cover each game. For every game $k$, we want to impose the following constraint:

$\displaystyle \sum_{i=1}^{10} x_{ik}=1$

This means that if we sum the percentage of time each lineup is used during game $k$, we reach 100%.

Constraint (b): Choose your lineups so that you expect to score enough points in every game to beat your opponents. In this example, I’ll focus on plus-minus scores, but as a coach you could focus on any metric that matters to you. Given a lineup $i$, let $p_i$ be its adjusted plus-minus score. For example, the lineup of LeBron, Wade, Bosh, Chalmers, and Allen in the 2012-2013 season had the amazing $p_i$ score of +36.9 (you can obtain these numbers, and many other neat statistics, from the web site stats.nba.com). Now let’s say you have the plus-minus score of your opponent in game $k$, which we’ll call $P_k$. One way to increase your chances of victory is by requiring that the expected plus-minus score of your lineup combination in game $k$ exceed $P_k$ by a certain amount. Therefore, for every game $k$, we write the following constraint:

$\displaystyle \sum_{i=1}^{10} p_i x_{ik} \geq P_k + 0.5$

I want to emphasize two things. First, $p_i$ can be any measure of goodness of your lineup, and it can take into account the specific opponent in game $k$. Likewise, $P_k$ can be any measure of goodness of team $k$, as long as it’s consistent with $p_i$. Second, you’re not restricted to having only one of these constraints. If many measures of goodness matter to you, add them all in. For example, if you’re playing a team that’s particularly good at rebounding and you believe that rebounding is the key to beating them (e.g. Heat vs. Pacers), then either replace the constraint above with the analogous rebounding version, or include the rebounding version in addition to the constraint above. Finally, note that I picked 0.5 as a fixed amount by which to exceed $P_k$, but it could be any number you wish, of course. It can even be a number that varies depending on the opponent.

Constraint (c): Keep track of how many minutes your players are playing above and beyond what you’d like them to play. For any given player $j$ and any given game $k$, let $m_{jk}$ be $j$‘s ideal number of playing minutes in game $k$ (make it zero if you want the player to sit out). When it’s not possible to match $m_{jk}$ exactly, we need to know how many minutes player $j$ played under or over $m_{jk}$. Let’s call these two unknown numbers (variables) $u_{jk}$ and $o_{jk}$, respectively. So, for every player $j$ and game $k$, we write the following constraint:

$\displaystyle 48\left(\sum_{i \text{ that includes } j} x_{ik}\right) + u_{jk} - o_{jk}=m_{jk}$

The expression “$i$ that includes $j$” under the summation means that we’re summing variables $x_{ik}$ for all lineups of which $j$ is a member. We’re multiplying the summation by 48 minutes because $x_{ik}$ is in percentage points and $m_{jk}$ is in minutes.

What is our goal? (a.k.a. objective function) It’s simple: we don’t want players to play too many minutes above $m_{jk}$. Because this overage amount is captured by variable $o_{jk}$, we can write our goal as:

$\displaystyle \text{minimize } \sum_{j=1}^{9} \sum_{k=1}^{7} o_{jk}$

This minimizes the total overage in playing minutes. For a more balanced solution, it’s also possible to minimize the maximum overage over all players, or add weights in front of the $o_{jk}$ variables to give preference to some players.

Now what? Well, the next step would be to solve this model and see what happens. I created a Microsoft Excel spreadsheet that can be solved with Excel Solver or OpenSolver. You can download it from here. Feel free to adapt it to your own needs and play around with it (this is the fun part!). Because my model was limited in size (I can’t use OpenSolver on my Mac at home), the solution isn’t very good (too many overage minutes). However, by adding more players and more lineups, the quality will certainly improve (use OpenSolver to break free from limits on model size). Here are some notes to help you understand the spreadsheet:

• Variables $x_{ik}$ are in the range B18:H25.
• Variables $u_{jk}$ and $o_{jk}$ are in ranges B56:J62 and B65:J71, respectively.
• Constraints (a) are implemented in rows 27, 28, 29.
• Constraints (b) are implemented in rows 33, 34, 35.
• The left-hand side of constraints (c) are in the range B74:J80. This range is required to be equal to the range B47:J53 (where the $m_{jk}$ are) inside the Solver window.
• The objective function whose formula appears above is in cell J21.

What are the pros and cons of this model? Can you make it better? No model is perfect. There are always real-life details that get omitted. The art of modeling is creating a model that is detailed enough to provide useful answers, but not too detailed to the point of requiring an unreasonable amount of time to solve. The definitions of “detailed enough” and “unreasonable amount of time” are mostly client-specific. (What would please Erik Spoelstra and his coaching staff?) What do you think are the main strengths and weaknesses in the model I describe above? What would you change? Good data is a big issue in this particular case. If you don’t like my data, can you propose alternative sources that are practical? I believe there’s plenty to talk about in this context, and I’m looking forward to receiving your feedback. Maybe we can converge to a model that is good enough for me to go knocking on the Miami Heat’s door! (Don’t worry. In the unlikely event they open the door, I’ll share the consulting fees.)

3 Comments

Filed under Applications, Linear Programming, Modeling, Motivation, Sports

## 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