| |||||||||

Scenes allocation problem: symmetry breaking Description Assigning time slots for shooting movie scenes: 'implies', 'distribute', 'maximum' constraints; the model demonstrates the impact of additional symmetry breaking constraints on the enumeration. Further explanation of this example:
'Xpress Kalis User Guide', Section 3.12 Symmetry breaking: scenes allocation problem
Source Files scenesalloc.mos (!**************************************************************** CP example problems =================== file scenesalloc.mos ```````````````````` Scenes allocation problem. A movie producer has to decide when to shoot scenes for a movie. Every scene involves a number of actors. A least 2 scenes and at most 5 scenes a day can be filmed. All actors of a scene must, of course, be present on the day the scene is shot. The actors have fees representing the amount to be paid per day they spend in the studio. The goal of the application is to minimize the production costs. (c) 2017 Artelys S.A. and Fair Isaac Corporation *****************************************************************!) 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 | |||||||||

Copyright 2017 Fair Isaac Corporation. |