Puzzle: Action Movie Scene Sequencing

DS City is a prime movie location. The filmmakers have some more action scenes to shoot. Which will destroy the set. The question is, in what order should they shoot the scenes?

The scenes in question are

A. Ballroom Dance (Requires a pristine floor)

B. Table-Flip Fight (Scatters furniture/glass)

C. Chandelier Drop (Destroys the ceiling)

D. Window Crash (Shards everywhere)

E. Pipe Burst (Floods the set)

F. Motorcycle Burnout (Leaves heavy tire marks)

G. Wall Explosion (Major structural debris/smoke)

Now, there are some constraints on when we can shoot what scene:

• Actor’s Schedule (B - Fight): One actor for the Table-Flip Scene is only available for the morning. B must be in position 1, 2, or 3.
• Rider's Arrival (F - Bike): The motorcycle pro is traveling from another set. The Motorcycle Burnout cannot be in positions 1, 2, 3, or 4.
• Safety Buffer (G - Explosion & E - Pipe): To protect equipment from moisture/smoke interference, the Explosion (G) and Flood (E) crews cannot work back-to-back. There must be at least one scene scheduled between G and E.
• The other constraints follow from parts of the set that are needed intact in some scenes but destroyed in others. A must precede B, E, and G. B must precede G. C must precede G. D must precede E. F must precede E.

Any sequence that obeys the above rules would be okay, but there is also the time needed to set up a scene, which depends on the scene right before. Here is the transition matrix, with time in minutes:

Can you optimize the sequence so that these last seven scenes can be shot in the least amount of time?

We need to enforce these precedences:

precedences = [[1,4,6],
               [6],
               [6],
               [4],
               [],
               [4],
               []]

If you had a modeling API that allows both, what would you prefer:

sequence_perm = env.permutation(7, precedences)
seq = sequence_perm.get_permutation()
scene_pos = sequence_perm.get_permutation_inverse()

or

x = [[env.ordinal(0,1) for _ in range(7)] for _ in range(7)]
for i in range(7):
    env.enforce_eq(env.sum(x[i]), 1)
    env.enforce_eq(env.sum([x[j][i] for j in range(7)]), 1)
seq = [env.sum([j*x[i][j] for j in range(7)]) for i in range(7)]
scene_pos = [env.sum([i*x[i][j] for i in range(7)]) for j in range(7)]
for pi, p in enumerate(precedences):
    for j in p:
        env.enforce_lt(seq[pi], j)

Yeah, we thought so, too. That is why Seeker 2.2 offers permutations that adhere to precedence constraints.

All optimal sequences have total setup time of 38. One possible solution is:

1. Ballroom Dance
2. Table-Flip Fight
3. Window Crash
4. Chandelier Drop
5. Wall Explosion
6. Motorcycle Burnout
7. Pipe Burst

An alternative sequence is:

1. Chandelier Drop
2. Ballroom Dance
3. Table-Flip Fight
4. Wall Explosion
5. Window Crash
6. Motorcycle Burnout
7. Pipe Burst