PROC CLP: Scene Allocation Problem :: SAS/OR(R) 9.22 User's Guide: Constraint Programming

The CLP Procedure

Example 3.6 Scene Allocation Problem

The scene allocation problem consists of deciding when to shoot each scene of a movie in order to minimize the total production cost (Van Hentenryck; 2002). Each scene involves a number of actors, and at most five scenes a day can be shot. All actors who appear in a scene must be present on the day the scene is shot. Each actor has a daily rate for each day spent in the studio, regardless of the number of scenes in which he or she appears on that day. The goal is to minimize the production costs of the studio.

The actor names, daily fees, and the scenes they appear are given in the SCENE data set shown in Output 3.6.1. The variables S_Var1, ..., S_Var9 indicate the scenes in which the actor appears. For example, the first observation indicates that Patt’s daily fee is 26481 and that Patt appears in scenes 2, 5, 7, 10, 11, 13, 15, and 17.

Output 3.6.1 The Scene Data Set

Obs	Number	Actor	DailyFee	S_Var1	S_Var2	S_Var3	S_Var4	S_Var5	S_Var6	S_Var7	S_Var8	S_Var9
1	1	Patt	26481	2	5	7	10	11	13	15	17	.
2	2	Casta	25043	4	7	9	10	13	16	19	.	.
3	3	Scolaro	30310	3	6	9	10	14	16	17	18	.
4	4	Murphy	4085	2	8	12	13	15	.	.	.	.
5	5	Brown	7562	2	3	12	17	.	.	.	.	.
6	6	Hacket	9381	1	2	12	13	18	.	.	.	.
7	7	Anderson	8770	5	6	14	.	.	.	.	.	.
8	8	McDougal	5788	3	5	6	9	10	12	15	16	18
9	9	Mercer	7423	3	4	5	8	9	16	.	.	.
10	10	Spring	3303	5	6	.	.	.	.	.	.	.
11	11	Thompson	9593	6	9	12	15	18	.	.	.	.

There are nineteen scenes and at most five scenes can be filmed in one day, so at least four days are needed to schedule all the scenes ( $\text{[math]}$ ). Let $\text{[math]}$ be a binary variable that equals 1 if scene $\text{[math]}$ is shot on day $\text{[math]}$ . Let $\text{[math]}$ be another binary variable that equals 1 if actor $\text{[math]}$ is present on day $\text{[math]}$ .

The following %SCENECLP macro invokes the CLP procedure. It includes two sets of GCC constraints: one to make sure each scene is shot exactly once, and one to limit the number of scenes shot per day to be at least four and at most five. There are also three sets of LINCON constraints: one to indicate that an actor must be present if any of his or her scenes are shot that day, one for breaking symmetries to improve efficiency, and one to limit the total production cost to be less than or equal to the given objective.

%macro sceneclp(obj);
   %put The objective value is: &obj..;
   
   proc clp out=out varselect=maxc;
      /* Declare variables. */
      %do k=1 %to 4; /* 4 days */
         %do j=1 %to 19; /* 19 scenes */
            var S&j._&k=[0,1]; /* Indicates if scene j is shot on day k.   */
         %end;
         %do i=1 %to 11; /* 11 actors */
            var A&i._&k=[0,1]; /* Indicates if actor i is present on day k.*/
         %end;
      %end;
      
      /* Every scene is shot exactly once.*/
      %do j=1 %to 19; 
         gcc (
            %do k=1 %to 4; 
               S&j._&k
            %end;
            )=( (1, 1, 1) );
      %end;
      
      /* At least 4 and at most 5 scenes are shot per day. */
      %do k=1 %to 4; 
         gcc (
            %do j=1 %to 19; 
               S&j._&k
            %end;
            )=( (1, 4, 5) );
      %end;
      
      /* Actors for a scene must be present on day of shooting.*/
      %do k=1 %to 4;
         %do j=1 %to 19;            
            %do i=1 %to 11; 
               %if (&&A&i._S&j>0) %then %do;
                  lincon S&j._&k <= A&i._&k;
               %end;
            %end;
         %end;
      %end;
      
      /* Symmetry breaking constraints. Without loss of any generality, we */
      /* can assume Scene1 to be shot on day 1, Scene2 to be shot on day 1 */
      /* or day 2, and Scene3 to be shot on either day 1, day 2 or day 3.  */
      lincon S1_1 = 1, S1_2 = 0, S1_3 = 0, S1_4 = 0,
             S2_3 = 0, S2_4 = 0, S3_4 = 0;
             
      /* If Scene2 is shot on day 1,                */
      /* then Scene3 can be shot on day 1 or day 2. */
      lincon S2_1 + S3_3 <= 1;
             
      /* minimize total cost */
      lincon &obj >=
         %do i=1 %to 11; /* 11 actors */
            %do k=1 %to 4; /* 4 days */
               &&Cost&i*A&i._&k +
            %end;
         %end;
         0;
      run;
      
      /* when a solution is found,                      */
      /* &_ORCLP_ contains the string SOLUTIONS_FOUND   */
      %if %index(&_ORCLP_, SOLUTIONS_FOUND) %then %let clpreturn=SUCCESSFUL;
%mend sceneclp;

The %FINDMIN macro uses a bisection search method to compute the minimal cost. The %SCENE macro reads the SCENE data set and produces three sets of macro variables: $\text{[math]}$ is the name of the $\text{[math]}$ th actor; $\text{[math]}$ is the daily cost of the $\text{[math]}$ th actor; and $\text{[math]}$ if actor $\text{[math]}$ appears in scene $\text{[math]}$ , and 0 otherwise.

/* Bisection search method to determine the optimal objective value  */
%macro findmin(lb, ub);
   %do %while (&lb<&ub-1) ;
      %put Currently lb=&lb, ub=&ub..;
      %let newobj=%eval((&lb+&ub)/2);
      %let clpreturn=NOTFOUND;
      %sceneclp(obj=&newobj);
      %if &clpreturn=SUCCESSFUL %then %let ub=&newobj;
      %else %let lb=&newobj;
   %end;
   %sceneclp(obj=&ub);
   %put The minimum objective value within given range is &ub..; 
   %put Any value less than &ub makes the problem infeasible. ;
%mend findmin;

%macro scene;
   /* Ai_Sj=1 if actor i appears in scene j    */
   /* Ai_Sj=0 otherwise                        */
   /* Initialize to 0                          */
   %do i=1 %to 11; /* 11 actors */
      %do j=1 %to 19; /* 19 scenes */
         %let A&i._S&j=0; 
      %end;
   %end;
   
   data _null_;
      set scene;
      call symput("Name"||strip(_n_), Actor); /* read actor name */
      call symput("Cost"||strip(_n_), DailyFee); /* read actor cost */
      /* read whether an actor appears in a scene */
      %do i=1 %to 9; /* 9 scene variables in the data set */
         if S_Var&i > 0 then
            call symput("A"||strip(_n_)||"_S"||strip(S_Var&i), 1); 
      %end;
   run;

   /* Find the minimum objective value.                   */
   /* Lowerbound: every actor appears on one day.         */
   /* Upperbound: every actor appears on all four days.   */
   %findmin(137739, 550956);

   /* Generate the Gantt charts */
   %gantt_gen;

%mend scene;
%scene;

The optimal production cost is found to be 334,144. The corresponding actor schedules and scene schedules are displayed in Output 3.6.2 and Output 3.6.3, respectively.

Output 3.6.2 Scene Allocation Problem: Actor Schedules

Output 3.6.3 Scene Allocation Problem: Scene Schedules

Top of Page