FICO
FICO Xpress Optimization Examples Repository
FICO Optimization Community FICO Xpress Optimization Home
Back to examples browserPrevious exampleNext example

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

scenesalloc.zip[download all files]

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

Back to examples browserPrevious exampleNext example