Scene Allocation Problem (clpe06)
/***************************************************************/
/* */
/* S A S S A M P L E L I B R A R Y */
/* */
/* NAME: clpe06 */
/* TITLE: Scene Allocation Problem (clpe06) */
/* 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 . . . .
;
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";
goptions 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;
goptions 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;