Exercise 8.8.1. Write constraints that prevents two movies from being on the

same screen at the same time. (It is on the book of Mathematics of Optimization: How to do Things Faster by Steven J Miller, Chapter8 Integral Programming)

8.1. The Movie Theater Problem

Let's imagine we run a movie theater. Our goal, not surprisingly, is to maximize profits. To figure out our optimal strategy, we need to study our revenues and expenditures; below is a partial list which provides a great starting point.

Sources of revenue:

selling tickets,

selling food,

selling advertisements, in-house arcades.

Expenditures:

labor wages,

rent/utilities,

cost of movies,

cost of food/arcades, taxes,

advertisement budget.

8.1. The Movie Theater Problem 123

It's important to remember that maximizing profits on the whole doesn't nec- essarily mean maximizing all of the revenue streams and minimizing all of the costs. Some theaters sell tickets for as low as $1 in order to attract customers who spend money on food and concessions, which is a much more profitable source of income than the ticket sales. It can sometimes be worthwhile to take a loss on product A in order to sell Product B; you can also see this in a lot of stores, which frequently have leading items which aren't profitable for the store, but serve to get customers inside; once they arrive, they'll buy other items.

Our problem is to schedule the movies at our theater; this means we'll need constraints, and we'll have to find what our variables should be. There are a lot of similarities with the oil problem. There, one of our variables was how much oil we shipped from refinery i to city j; here, the key variable is whether or not at time t movie m is shown on screen s.

Parameters.

• screens s {1,...,S},
• capacity cs (how many people can see a movie on screen s),
• demand dt,m (the number of people who wish to see movie m if it starts at time t),
• labor costs (different staff require different salaries),
• time t {1,...,T} (we break the day into a large number of discrete times),
• moviesm{1,...,M}(thecandidatemovies),
• run-time rm (how long movie m is),
• ticket prices (note these could be functions of the time of day and age of moviegoer).
• We have to be careful with our parameters above. This is just meant to be a first pass on the problem so we'll ignore some issues in our formulation, but it's worth mentioning them. Let's examine the demands, dt,m. The first difficulty is we need a way to estimate these values. Approximations can be done by comparing our movies to others that have been shown in the past. For example, we might have ticket sales from last week. Or we might have historical data on how action sequels do. Even if we know these values, however, there are other problems. Do movies compete with each other? If yes, does this mean the demands for movies at each moment must depend on what else has been shown during the day (and even potentially what might be in the queue for later)? For now we'll ignore issues such as these in order to introduce the main ideas.

124

8. Integer Programming

Variables:

decision variable xt,m,s =

1 if at time t movie m starts on screen s, 0 otherwise.

Variables such as these are called binary variables; they are either 0 or 1, and we'll see that they have a variety of nice properties.

While the above is an excellent choice for our decision variable, there are other options. We could have defined our decision variable as

yt,m,s =

1 if at time t movie m is running on screen s, 0 otherwise.

The advantage of our first formulation is that it highlights the action of starting a movie. Since we know how long the movie is, we can then figure out when the screen is next available. In particular, we would have the following constraint:

t+rm 1 S

If xt,m,s = 1, then x,m, = 0; =t+1 =1

in other words, if at time t we start movie m on screen s, then the earliest that movie can be started on any screen is time t + rm. We can encode constraints like this so concisely because our variables only take on the values 0 and 1. Thus, the only way the sum above can be zero is if each summand is zero.

Of course, the constraint above does not fit into our linear programming frame- work as written. We don't have a linear combination of our variables; instead, we have an if-then statement. We'll see below how to convert expressions such as this to our linear programming framework.

Objective function: For simplicity let's assume all ticket prices are P and that there is no concession revenue. Then we are trying to maximize

T M S

P min(cs,dt,m)xt,m,s

t=1 m=1 s=1

(we need the minimum above as we cannot have more people watching a movie

on screen s than can fit in that room). We could, and should, add terms related to food sales. The challenge is how to incorporate these. For example, which do you think generates more concession sales: a teen date movie, an action movie, a family movie, or a senior citizen favorite? Thus we might need to keep track of who is in the theater, not just the number of people. This suggests adding another parameter, say revt,m, which is the revenue generated by an average attendee who comes at time t to see movie m:

T M S

revt,m min(cs, dt,m)xt,m,s.

t=1 m=1 s=1