Broken records for the Movie Shoot Scheduling Problem

Nicolas Senior Optimization Scientist February 7, 2022

In this post, we describe and analyze the LocalSolver model of a simplified version of the Movie Shoot Scheduling Problem defined by Bomsdorf and Derigs in an OR Spectrum paper. This version is the subject of online competition on the Optimization Hub.

A movie consists of a set of scenes. Each scene must be shot in a given location and requires a determined set of actors. The order of shooting is not influenced by the order in the final version of the movie, but by economic reasons related to costs of actors and locations. Each actor has a daily cost and each location is associated with a fixed cost. There are also precedence constraints between scenes, stating that a scene must be shot before another. The movie shoot scheduling problem consists in finding the optimal sequence that satisfies the precedence constraints and minimizes the following costs:

Location cost: every time a location is visited to shoot a set of scenes, the cost of the location is added, independently of the number of scenes. Only the first visit is not considered in the cost, as every location must be visited at least once.
Actor cost: an actor must be present for their scenes and has to stay available on the set in between. Even when not playing, the actor is paid for these extra days of presence: this is the actor’s cost.

A solution to this problem can be represented by the following figure:

In the data set corresponding to the displayed solution, the movie is constituted of 10 scenes taking place in 2 different locations, each scene involving a subset of 5 actors. There are also two precedence constraints: scene 2 must be shot before 6, and scene 0 before 1. Assuming that each scene lasts one day, the total cost of the movie with this schedule is 2A₂ + 6A₅, where A₂ and A₅ are the daily cost of actors 2 and 5 respectively. As each location is visited only once, there is no location cost. If actor 5 has a very high daily cost, we can try to exchange scene 9 and 3 in the solution. The cost of this new solution is L₁ + 2L₂ + 2A₂ + A₃ + A₄ where L₁ and L₂ correspond to location costs.

This problem is highly combinatorial as only precedence constraints reduce the number of solutions compared to the number of permutations. Here is the LocalSolver model, written in Python language, which uses a single list decision to represent the scene schedule:

# Decision variable: A list, shoot_order[i] is the index of the ith scene to be shot
shoot_order = model.list(data.nb_scenes)

# All scenes must be scheduled
model.constraint(model.count(shoot_order) == data.nb_scenes)

# Constraint of precedence between scenes for i in range(data.nb_precedences):
model.constraint(model.index(shoot_order, data.precedences[i][0])
                         < model.index(shoot_order, data.precedences[i][1]))

To compute the objective function, which is nonlinear and difficult to compute with classic mathematical operators due to its high complexity, we use an external function:

# Minimize external function
cost_function = CostFunction(data)
func = model.create_int_external_function(cost_function.compute_cost)
func.external_context.lower_bound = 0
cost = func(shoot_order)
model.minimize(cost)

An external function is a function written in a programming language, here Python, which is called by the solver during the solving process to compute the value of an output expression from specified input expressions. In the case of the movie shoot scheduling problem, the external function is used to compute the value of the objective from the shoot schedule:

class CostFunction:

    def __init__(self, data):
        self.data = data

    def compute_cost(self, context):
        shoot_order = context[0]
        if len(shoot_order) < self.data.nb_scenes:
            # Infeasible solution if some shoots are missing
            return sys.maxsize

        location_extra_cost = self._compute_location_cost(shoot_order)
        actor_extra_cost = self._compute_actor_cost(shoot_order)
        return location_extra_cost + actor_extra_cost

In an external function, you can use any specific language feature or library of the programming language you may need to compute the desired value, which allows you to easily model problems that would be tough to model otherwise, despite the wide range of linear and nonlinear operators offered by LocalSolver

By using this straightforward modeling approach, LocalSolver has broken the best-known solutions on the hardest instances listed on the Optimization Hub. Now it’s your turn: try to beat us!

You can find the complete model of the movie scheduling problem in Python, Java, C#, C++, and LSP in our Example Tour.

We are at your disposal to accompany you in the discovery of LocalSolver. Don’t hesitate to contact us for any further information or support.

Broken records for the Movie Shoot Scheduling Problem

Recent posts

Categories