Symmetry breaking: scenes allocation problem
A movie producer has to decide when to shoot the scenes for a movie. Every scene involves a specific set of actors. A least 2 scenes and at most 5 scenes can be filmed per day. All actors of a scene must, of course, be present on the day the scene is shot. The actors have fees representing the amount they are paid per day they spend in the studio. The movie producer wishes to minimize the production costs incurred through the actors' fees.
Model formulation
Let SCENES denote the set of scenes, ACTORS all the actors taking part in the movie, and DAYS the set of eligible days. The decision variables shoots indicating which day a scene is shot take their values in the set DAYS. A second set of variables are the binary indicators workad that take the value 1 if actor a works on the day d.
Every day, the number of scenes shot needs to lie within the interval of minimum and maximum permissible numbers (MINSCENESHOTd,...,MAXSCENESHOTd). We also need to formulate the implication 'if an actor works on a day, then this day is due', or stated otherwise 'if a scene that the actor appears in is scheduled on day d, then the actor is working on this day':
∀ a ∈ ACTORS, d ∈ DAYS: workad ∈ {0,1}
∀ d ∈DAYS: |shoots = d|s ∈ SCENES ∈ {MINSCENESHOTd,...,MAXSCENESHOTd}
∀ a ∈ ACTORS, s ∈ APPEARa, d ∈ DAYS: shoots=d ⇒ workad=1
The objective function is to minimize the total cost incurred through actors' fees:
Symmetry breaking constraints: it is easy to see that days are entirely interchangeable (e.g. all scenes from day 1 could be exchanged with those assigned to day 2 without any impact on the total cost). Indeed, any permuation of days with the same scene allocations will result in the same total cost. So it might be worthwhile to investigate how we can reduce the number of permutations in order to shorten solving times.
Consider a scene s1: it needs to be assigned some specific day, say day 1 (all days are interchangeable at this point). Now consider a second scene s2: it can either be assigned the same day as the first or some other (additional) day—all other days being interchangeable at this point we can assume this will be day 2. Generalizing this observation, for any scene s we can limit its value set to the days already used by scenes 1,...,s-1 plus one additional day, that is:
∀ s ∈SCENES, s>1: shoots ≤ maximum(shoot1,...,shoots-1) + 1
Implementation
For the implementation of the lower and upper bounds on the number of scenes to be shot per day we use a global cardinality ('distribute') constraint that distributes the scenes to be shot over the available days.
For the formulation of the symmetry breaking constraints some auxiliary objects are introduced, namely the list shootListSb of the predecessors of scene s (that is, shoot1,...,shoots-1) in enumeration order of the set of scenes, and an additional decision variable maxShootSbs defined as the maximum value among the variables in this list.
model "Scenes Allocation (CP)"
uses "kalis" ! Gain access to the Xpress Kalis solver
! **** Data ****
declarations
SCENES: range ! Set of scene numbers
DAYS = 1..5 ! Day numbers when the scenes can be shot
ACTORS: set of string ! Set of actors
DAILYFEE: array(ACTORS) of integer ! Daily fees of actors
CAST: array(SCENES) of set of string ! Cast of actors per scene
APPEAR: array(ACTORS) of set of integer ! Scenes where an actor appears
MINSCENESHOT: array(DAYS) of integer ! Minimum number of scenes per day
MAXSCENESHOT: array(DAYS) of integer ! Maximum number of scenes per day
end-declarations
! Initialize actors DAILYFEE
DAILYFEE::(["Georges Clooney","Penelope Cruz","Leonardo DiCaprio",
"Nathalie Portman","Ryan Gosling","Monica Bellucci","Javier Bardem",
"Keira Knightley","Vincent Cassel","Marion Cotillard","Emma Watson"])[264, 250, 303,
40, 75, 93, 87, 57, 74, 33, 95]
! Initialize minimum and maximum numbers of scenes that have to be shot per day
MINSCENESHOT::([1,2,3,4,5])[2,2,2,2,2]
MAXSCENESHOT::([1,2,3,4,5])[5,5,5,5,5]
! Initialize sets of actors per scene
CAST(1):= {"Monica Bellucci"}
CAST(2):= {"Georges Clooney","Monica Bellucci","Ryan Gosling","Nathalie Portman"}
CAST(3):= {"Keira Knightley","Leonardo DiCaprio","Vincent Cassel","Ryan Gosling"}
CAST(4):= {"Penelope Cruz","Vincent Cassel"}
CAST(5):= {"Vincent Cassel","Javier Bardem","Georges Clooney","Keira Knightley","Marion Cotillard"}
CAST(6):= {"Emma Watson","Keira Knightley","Javier Bardem","Leonardo DiCaprio","Marion Cotillard"}
CAST(7):= {"Penelope Cruz","Georges Clooney"}
CAST(8):= {"Vincent Cassel","Nathalie Portman"}
CAST(9):= {"Penelope Cruz","Keira Knightley","Vincent Cassel","Leonardo DiCaprio","Emma Watson"}
CAST(10):= {"Penelope Cruz","Keira Knightley","Leonardo DiCaprio","Georges Clooney"}
CAST(11):= {"Georges Clooney"}
CAST(12):= {"Monica Bellucci","Emma Watson","Keira Knightley","Nathalie Portman","Ryan Gosling"}
CAST(13):= {"Monica Bellucci","Nathalie Portman","Penelope Cruz","Georges Clooney"}
CAST(14):= {"Javier Bardem","Leonardo DiCaprio"}
CAST(15):= {"Emma Watson","Nathalie Portman","Keira Knightley","Georges Clooney"}
CAST(16):= {"Leonardo DiCaprio","Keira Knightley","Penelope Cruz","Vincent Cassel"}
CAST(17):= {"Leonardo DiCaprio","Georges Clooney","Ryan Gosling"}
CAST(18):= {"Leonardo DiCaprio","Keira Knightley","Monica Bellucci","Emma Watson"}
CAST(19):= {"Penelope Cruz"}
! Calculate appearance in scenes for each actor
forall(a in ACTORS) APPEAR(a):= union(s in SCENES | a in CAST(s)) {s}
! **** Problem statement ****
declarations
shoot: array(SCENES) of cpvar ! Decision var.s: day when a scene will be shot
work: array(ACTORS,DAYS) of cpvar
! Decision var.s: presence of actor i on day k
totalCost: cpvar ! Objective
shootListSb: cpvarlist ! List of shoot variables for symmetry breaking
maxShootSb: array(SCENES) of cpvar ! Max. value of shoot variables list
! per scene (formulation of symmetry breaking)
end-declarations
setparam("kalis_default_ub", 200000000) ! Kalis default upper bound
! **** Domain definition ****
! Each shoot variable takes a value from the set DAYS
forall(s in SCENES) do
setname(shoot(s),"shoot["+s+"]")
setdomain(shoot(s), DAYS)
end-do
! The total cost has a lower bound of $0 and an upper bound of $200000000
setname(totalCost, "totalCost")
setdomain(totalCost, 0, 200000000)
! work : binary variables that indicate if actor i is present on day k
forall(a in ACTORS, d in DAYS) do
setname(work(a,d), "work["+a+","+d+"]")
setdomain(work(a,d), 0, 1)
end-do
! **** Constraints ****
! Global Cardinality Constraint to express lower and upper bounds on the
! number of scenes that have to be shot each day
distribute(shoot,DAYS,MINSCENESHOT,MAXSCENESHOT)
! When an actor works on a day, this day is due
forall(a in ACTORS, s in APPEAR(a), d in DAYS)
implies(shoot(s)=d, work(a,d)=1)
! Symmetry breaking
shoot(1) = 1 ! All days are interchangeable at this stage
forall(s in SCENES | s > 1) do
shootListSb += shoot(s-1) ! For a scene s, we need to consider
maxShootSb(s) = maximum(shootListSb) ! just the previously used days + 1:
shoot(s) <= maxShootSb(s)+1 ! D(s)={1,...,max(shoot(1),...,shoot(s-1))+1}
end-do
! Objective function
totalCost = sum(a in ACTORS, d in DAYS) DAILYFEE(a)*work(a,d)
! Branching strategy
cp_set_branching(assign_and_forbid(KALIS_INPUT_ORDER, KALIS_MIN_TO_MAX, shoot))
! **** Problem solving and solution reporting ****
if cp_minimize(totalCost) then
! Display total cost
writeln("Total cost: ", getsol(totalCost))
! Display scenes scheduled on each day
forall(d in DAYS) do
write("\nDay ", d, ": scenes ")
forall(s in SCENES | getsol(shoot(s))=d) write(s, " ")
end-do
! Display days worked by each actor
forall(a in ACTORS) do
write("\n", strfmt(a,-16), " :")
forall(d in DAYS | getsol(work(a,d)) = 1) write(" Day ",d)
end-do
writeln
else
writeln("No solution found.")
end-if
end-model
Results
The model shown above generates the following output:
Total cost: 3497 Day 1: scenes 1 8 Day 2: scenes 2 5 11 12 15 Day 3: scenes 3 7 10 13 17 Day 4: scenes 4 19 Day 5: scenes 6 9 14 16 18 Georges Clooney : Day 2 Day 3 Penelope Cruz : Day 3 Day 4 Day 5 Leonardo DiCaprio: Day 3 Day 5 Nathalie Portman : Day 1 Day 2 Day 3 Ryan Gosling : Day 2 Day 3 Monica Bellucci : Day 1 Day 2 Day 3 Day 5 Javier Bardem : Day 2 Day 5 Keira Knightley : Day 2 Day 3 Day 5 Vincent Cassel : Day 1 Day 2 Day 3 Day 4 Day 5 Marion Cotillard : Day 2 Day 5 Emma Watson : Day 2 Day 5
Without the symmetry breaking constraints, the solving time is more than one order of magnitude longer (both for finding the optimal solution and proving its optimality) than when these constraints are included in the model.