## Scene Allocation Problem (clp6)

```/***************************************************************/
/*                                                             */
/*          S A S   S A M P L E   L I B R A R Y                */
/*                                                             */
/*    NAME: clp6                                               */
/*   TITLE: Scene Allocation Problem (clp6)                    */
/* PRODUCT: OR                                                 */
/*  SYSTEM: ALL                                                */
/*    KEYS: OR                                                 */
/*   PROCS: CLP, GANTT                                         */
/*    DATA:                                                    */
/*                                                             */
/* SUPPORT:                             UPDATE:                */
/*     REF: Constraint and Integer Programming in OPL          */
/*          INFORMS J of Computing 14(4) 345-372, 2002         */
/*    MISC: Example 6 from the CLP Procedure chapter of the    */
/*          Constraint Programming book.                       */
/*                                                             */
/***************************************************************/

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

proc print data=scene;
run;

%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 scene_cost;
set scene;
keep DailyFee A;
retain DailyFee A;
do day=1 to 4;
A='A'||left(strip(_N_))||'_'||left(strip(day));
output;
end;
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;
/* Create constraint data set which defines the objective function */
proc transpose data=scene_cost out=cost(drop=_name_);
var DailyFee;
id A;
run;
data cost;
set cost;
_TYPE_='MIN';
_RHS_=.;
run;

/* Find the minimum objective value.                   */
proc clp condata=cost out=out varselect=maxc;
/* Set lower and upper bounds for the objective value   */
/* Lower bound: every actor appears on one day.         */
/* Upper bound: every actor appears on all four days.   */
obj lb=137739 ub=550956;

/* 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;

run;
%put &_ORCLP_;
/* Generate the Gantt charts */
%gantt_gen;

%mend scene;

%macro scenesbyday;
proc transpose data=out out=dayout; run;
%do i=1 %to 4;
%global day&i.;
proc sql;
create table day&i. as
select substr( '     ',length(_name_)-2)||
substr(_name_,2,index(_name_,'_')-2)
from dayout where _name_ like 'S%_'||"&i." and col1=1;
quit;
data _null_;
set day&i. end=lastobs;
format string \$32.;
retain string '';
string = strip(string) || substr('     ',length(strip(_TEMA001)))
|| (strip(_TEMA001));
if lastobs then do;
var = 'day' || strip(put(&i.,best.));
call symput(var, string);
end;
run;
%end;
proc sql;
insert into day1 values(' ');
quit;
data scenes;
rename _TEMA001 = label;
set day1 day2 day3 day4;
fmtname='scenes';
start = _n_;
end = _n_;
run;
proc sql;
insert into scenes values(' ', 'scenes', 21, 21);
quit;
proc format cntlin=scenes; run;
proc format;
value days
1 = '               Day 1       '
6 = '               Day 2'
11 = '               Day 3'
16 = '               Day 4'
;

value scenedays
1 = '             Scenes         '
6 = '             Scenes'
11 = '             Scenes'
16 = '             Scenes'
;
run;
%mend;

%macro gantt_gen;
%scenesbyday;
data gantt_actor;
format actor \$15.;
format s_start s_finish scenes.;
set out;
label actor='Actor';
keep _label _labele segmt_no actor s_start s_finish;
%do i = 1 %to 11;/* 11 actors */
segmt_no = 1;
%do k = 1 %to 4; /* 4 days */
actor="&&Name&i";
if (A&i._&k ne 0) then do;
%let j = 1;
%let m = 1;
%let scene = %scan(&&day&k.,&j.);
%do %while (&scene. ne );
_label = '';
_labele = 'W';
%if (&&A&i._S&scene.>0) %then %do;
if (S&scene._&k=1) then do;
_label = 'W';
_labele = '';
end;
%end;
s_start=(&k.-1)*5 + &m.;
s_finish=s_start + 0.9;
output;
segmt_no = segmt_no + 1;
%let m = %eval(&m.+1);
%let j = %eval(&j.+1);
%let scene = %scan(&&day&k.,&j.);
%end;
_label = "";
end;
%end;
%end;
run;

data labels;
format _flabel _lvar \$10.;
_y=-1;
_lvar="_label";
_xvar="s_start";
_hlabel=3;
_yoffset = 2.0;
_xoffset = 0.3;
_flabel='marker';
output;
_y=-1;
_lvar="_labele";
_flabel='markere';
output;
run;

data gantt_scene;
format _label \$80. scene \$2.;
format s_start s_finish scenes.;
set out;
label scene='Scene';
keep _label segmt_no scene s_start s_finish duration;
retain duration 0.95;
%do j = 1 %to 19;/* 19 scenes */
%do k = 1 %to 4; /* 4 days */
if ( S&j._&k = 0) then do;
s_start=.;
s_finish=.;
segmt_no = &k;
_label = "";
scene="&j";
output;
end;
else do;
%do i = 1 %to 11;/* 11 actors */
%if (&&A&i._S&j>0) %then %do;
if (_label ne '') then
_label = strip(_label)||", &&Name&i";
else _label = "&&Name&i";
%end;
%end;
s_start=%eval(&k-1)+0.5;
s_finish=&k+0.45;
segmt_no = &k;
scene="&j";
output;
_label = "";
end;
%end;
%end;
run;
%mend gantt_gen;

%scene;

title1 h=4pct "Scene Allocation Problem";
title2 h=3pct "Optimal Schedule by Actor";
goption reset=pattern;
pattern1 v=e c=white r=10;
proc gantt data=gantt_actor labdata=labels;
chart /
skip=3
nojobnum
nolegend
pcompress
act=actor
increment=1
useformat
ref=6 11 16
height=3
chartwidth=89
timeaxisformat=(days., scenedays., scenes.);
;
id actor;
run;

title1 h=4pct "Scene Allocation Problem";
title2 h=3pct "Optimal Schedule by Scene";

proc format;
value scenes
0.5 = '                            1'
1.5 = '                            2'
2.5 = '                            3'
3.5 = '                            4'
4.5 = ' '
;
run;

data labels;
_y=-1;
_lvar="_label";
_xvar="s_start";
_hlabel=4;
_yoffset = -0.4;
_xoffset = 0;
run;

goption reset=pattern;
pattern1 r=10 c=ltgray v=s;
proc gantt data=gantt_scene labdata=labels;
chart /
skip=3
nolegend
nojobnum
compress
act=scene
duration=duration
increment=1
mindate=0.5
labsplit='/'
useformat
height=4
chartwidth=95
barht=1.1
;
id scene;
run;

```