The Optimal Craft of Movie Shooting Schedule using ORTools

Author(s): Optimization team

Originally published on Towards AI.

In a movie, there are often numerous scenes, each resembling puzzle pieces, meticulously arranged by the director. These scenes unfold, not always in sequential order, forming the cohesive narrative of the film. For instance, let’s consider a scenario with 19 scenes and 11 actors/actresses. Each individual is assigned specific scenes and corresponding compensation based on their involvement.

The question is how to arrange shooting these scenes as fast as possible at min cost.

Data (source )

1 Patt 26481 2 5 7 10 11 13 15 17 .
2 Casta 25043 4 7 9 10 13 16 19 . .
3 Scolaro 30310 3 6 9 10 14 16 17 18 .
4 Murphy 4085 2 8 12 13 15 . . . .
5 Brown 7562 2 3 12 17 . . . . .
6 Hacket 9381 1 2 12 13 18 . . . .
7 Anderson 8770 5 6 14 . . . . . .
8 McDougal 5788 3 5 6 9 10 12 15 16 18
9 Mercer 7423 3 4 5 8 9 16 . . .
10 Spring 3303 5 6 . . . . . . .
11 Thompson 9593 6 9 12 15 18 . . . .

The data is read as follows:

Patt's salary is $26481/day and he is about to take part in scenes [2 5 7 10 11 13 15 17]

Assumptions

An artist will receive the daily rate no matter how many scense he/she is involved in

Max number of scenes per day is 5

First, I’ll outline the mathematical formulation of the problem, followed by implementing the solution using the ORTools optimization package.

Problem formulation

Case 1) Cost minimization, no additional constraint

1. Objective function is defined as the total payments to the artists.
2. Each scene should be assigned to one day
3. The toal scenes assigned to each day should not exceed 5
4. If an artist is not assigned to day d then all scens with this person involved will be cancelled
5. U_sd, AC_ad show if scene s/actor a is scheduled on day d (binary variables)

Python Code

model = cp_model.CpModel()
solver = cp_model.CpSolver()
U = {(s,d):model.NewBoolVar(f"scen_day_{s}_{d}") for s in scenes for d in days}
AC = {(a,d):model.NewBoolVar(f"actor_day_{a}_{d}") for a in actors for d in days}
for s in scenes:
 expressions = [U[s,d] for d in days ]
 model.AddExactlyOne(expressions)
for d in days:
 expressions = [U[s,d] for s in scenes ]
 model.Add(sum(expressions) <= 5)
for (s,d),v in U.items():
 for actor in scene_dic[s]:
 model.Add(v<=AC[actor,d] ) 
expressions = [v*df_cost[actor] for (actor,d),v in AC.items()]
model.Minimize(sum(expressions))
solver.parameters.max_time_in_seconds = 60
status = solver.Solve(model)

if status == cp_model.OPTIMAL:
 print("OPTIMAL")
elif status == cp_model.FEASIBLE:
 print("FEASIBLE")
elif status == cp_model.INFEASIBLE:
 print("INFEASIBLE")
 print("FEASIBLE")
elif status == cp_model.UNKNOWN:
 print("UNKNOWN")

Result:

The total costs would be OF = 334144.0,

On the day 1: Thompson, Spring, McDougal, Anderson, Hacket and Scolaro are supposed be present to take the scenes [1, 6,14 and 18].

Case 2) Cost minimization, Symmetry Breaking

Case 1 exhibits symmetry, indicating that exchanging any pair of days would yield the same objective function. This symmetry arises due to the absence of precedence constraints within the problem.

We can easily break this symmetry by adding the following constraint:

Constraint 5 imposes a requirement for the solver to organize the assignment of scenes to each day in ascending order.

model = cp_model.CpModel()
solver = cp_model.CpSolver()
U = {(s,d):model.NewBoolVar(f"scen_day_{s}_{d}") for s in scenes for d in days}
AC = {(a,d):model.NewBoolVar(f"actor_day_{a}_{d}") for a in actors for d in days}
for s in scenes:
 expressions = [U[s,d] for d in days ]
 model.AddExactlyOne(expressions)
for d in days:
 expressions = [U[s,d] for s in scenes ]
 model.Add(sum(expressions) <= 5)
 if d+1 in days:
 expressions_scen = [s*U[s,d] for s in scenes ]
 expressions_scen2 = [s*U[s,d+1] for s in scenes ]
 model.Add( sum(expressions_scen) <= sum(expressions_scen2))
 
for (s,d),v in U.items():
 for actor in scene_dic[s]:
 model.Add(v<=AC[actor,d] ) 

expressions = [v*df_cost[actor] for (actor,d),v in AC.items()]
model.Minimize(sum(expressions))
solver.parameters.max_time_in_seconds = 60
status = solver.Solve(model)
if status == cp_model.OPTIMAL:
 print("OPTIMAL")
elif status == cp_model.FEASIBLE:
 print("FEASIBLE")
elif status == cp_model.INFEASIBLE:
 print("INFEASIBLE")
 print("FEASIBLE")
elif status == cp_model.UNKNOWN:
 print("UNKNOWN")

OF = 334144.0 (no suprise this is the same as case 1, but solver does not have to check all possible solutions to return the optimal solution)

The total sum of scenes'numbers is ascending. [39, 42, 54, 55]. This is going to be helpful in larger instances.

Case 3) Cost minimization, Actors Who Refuse To Work With Each Other , Hacket and Spring

In light of recent rumors, it appears that Hacket and Spring refuse to collaborate. Therefore, the director must design the schedule in such a manner that ensures these two individuals are not scheduled to work on the same day.

We can easily avoid the conflict between these two stars by adding the following constraint:

model = cp_model.CpModel()
solver = cp_model.CpSolver()
U = {(s,d):model.NewBoolVar(f"scen_day_{s}_{d}") for s in scenes for d in days}
AC = {(a,d):model.NewBoolVar(f"actor_day_{a}_{d}") for a in actors for d in days}
for s in scenes:
 expressions = [U[s,d] for d in days ]
 model.AddExactlyOne(expressions)
for d in days:
 expressions = [U[s,d] for s in scenes ]
 model.Add(sum(expressions) <= 5)
 model.Add(AC['Hacket',d]+AC['Spring',d] <= 1)

for (s,d),v in U.items():
 for actor in scene_dic[s]:
 model.Add(v<=AC[actor,d] ) 

expressions = [v*df_cost[actor] for (actor,d),v in AC.items()]
model.Minimize(sum(expressions))
solver.parameters.max_time_in_seconds = 60
status = solver.Solve(model)

OF = 343256.0, it is more than case 1 (just because two people don't want to visit eachother!). By looking at the visualized schedule we observe that Hacket and Spring are never present on the same day.

Case 4) Cost minimization, Scene 3 should be taken before 9

model = cp_model.CpModel()
solver = cp_model.CpSolver()
U = {(s,d):model.NewBoolVar(f"scen_day_{s}_{d}") for s in scenes for d in days}
AC = {(a,d):model.NewBoolVar(f"actor_day_{a}_{d}") for a in actors for d in days}
for s in scenes:
 expressions = [U[s,d] for d in days ]
 model.AddExactlyOne(expressions)
for d in days:
 expressions = [U[s,d] for s in scenes ]
 model.Add(sum(expressions) <= 5)

model.Add( sum(d*U[3,d] for d in days) <= sum(d*U[9,d] for d in days) )
for (s,d),v in U.items():
 for actor in scene_dic[s]:
 model.Add(v<=AC[actor,d] ) 
expressions = [v*df_cost[actor] for (actor,d),v in AC.items()]
model.Minimize(sum(expressions))

OF = 336410.0 , the costs are more than case 1. Scene 3 is taken in day 2 while scene 9 is scheduled for day 3.

Case 5) Cost minimization, Max Scenes for each actor is 3

By looking at the case 1, it is observed that the number of scenes assigned to each actor per day varies from 0 (Murphy day 1) to 5 (Scolaro day 2). This is something that might create conflict between the actors ! Let's balance it by putting a cap on the max number of scenes for each actor/day.

The formulation is updated as follows:

model = cp_model.CpModel()
solver = cp_model.CpSolver()
U = {(s,d):model.NewBoolVar(f"scen_day_{s}_{d}") for s in scenes for d in days}
AC = {(a,d):model.NewBoolVar(f"actor_day_{a}_{d}") for a in actors for d in days}
for s in scenes:
 expressions = [U[s,d] for d in days ]
 model.AddExactlyOne(expressions)
for d in days:
 expressions = [U[s,d] for s in scenes ]
 model.Add(sum(expressions) <= 5)

 for a in actors:
 scens_assigned_to_actor = [U[s,d] for s in scenes if a in scene_dic[s]]
 model.Add(sum(scens_assigned_to_actor) <= 3) # max scen per actor/actress is 3 

for (s,d),v in U.items():
 for actor in scene_dic[s]:
 model.Add(v<=AC[actor,d] ) 

expressions = [v*df_cost[actor] for (actor,d),v in AC.items()]
model.Minimize(sum(expressions))
solver.parameters.max_time_in_seconds = 60
status = solver.Solve(model)

OF = 367185.0 , the costs are more than case 1. However, each actor is not assigned more than 3 scenes per day.

Case 6) Cost minimization, Max actors per day is 7

The producer has informed the director of a constraint: the shooting location facilities can accommodate only a limited number of movie cast members each day. Consequently, the director must ensure that the number of actors per day does not exceed 7 individuals (look at case 5, day 4, there are 8 actors).

The model is edited as follows:

model = cp_model.CpModel()
solver = cp_model.CpSolver()
U = {(s,d):model.NewBoolVar(f"scen_day_{s}_{d}") for s in scenes for d in days}
AC = {(a,d):model.NewBoolVar(f"actor_day_{a}_{d}") for a in actors for d in days}
for s in scenes:
 expressions = [U[s,d] for d in days ]
 model.AddExactlyOne(expressions)
for d in days:
 expressions = [U[s,d] for s in scenes ]
 model.Add(sum(expressions) <= 5)

 expressions_actors = [AC[a,d] for a in actors ]
 model.Add(sum(expressions_actors) <= 7)


for (s,d),v in U.items():
 for actor in scene_dic[s]:
 model.Add(v<=AC[actor,d] ) 

expressions = [v*df_cost[actor] for (actor,d),v in AC.items()]
model.Minimize(sum(expressions))
solver.parameters.max_time_in_seconds = 60
status = solver.Solve(model)

OF = 348171.0

Some resources for learning the ORTools:

• Official ORTools website: https://developers.google.com/optimization
• Solved examples on my github : https://github.com/OptimizationExpert/Pyomo

Join thousands of data leaders on the AI newsletter. Join over 80,000 subscribers and keep up to date with the latest developments in AI. From research to projects and ideas. If you are building an AI startup, an AI-related product, or a service, we invite you to consider becoming a sponsor.

Published via Towards AI