Scheduling (optmie04)
/***************************************************************/
/* */
/* S A S S A M P L E L I B R A R Y */
/* */
/* NAME: optmie04 */
/* TITLE: Scheduling (optmie04) */
/* PRODUCT: OR */
/* SYSTEM: ALL */
/* KEYS: OR */
/* PROCS: OPTMILP, SQL, SORT, FORMAT, TEMPLATE */
/* DATA: */
/* */
/* SUPPORT: UPDATE: */
/* REF: */
/* MISC: Example 4 from the OPTMILP chapter of Mathematical */
/* Programming. */
/* */
/***************************************************************/
data raw;
input name $ hour slot mon tue wed thu fri;
datalines;
marc 20 1 10 10 10 10 10
marc 20 2 9 9 9 9 9
marc 20 3 8 8 8 8 8
marc 20 4 1 1 1 1 1
marc 20 5 1 1 1 1 1
marc 20 6 1 1 1 1 1
marc 20 7 1 1 1 1 1
marc 20 8 1 1 1 1 1
mike 20 1 10 9 8 7 6
mike 20 2 10 9 8 7 6
mike 20 3 10 9 8 7 6
mike 20 4 10 3 3 3 3
mike 20 5 1 1 1 1 1
mike 20 6 1 2 3 4 5
mike 20 7 1 2 3 4 5
mike 20 8 1 2 3 4 5
bill 20 1 10 10 10 10 10
bill 20 2 9 9 9 9 9
bill 20 3 8 8 8 8 8
bill 20 4 0 0 0 0 0
bill 20 5 1 1 1 1 1
bill 20 6 1 1 1 1 1
bill 20 7 1 1 1 1 1
bill 20 8 1 1 1 1 1
bob 20 1 10 9 8 7 6
bob 20 2 10 9 8 7 6
bob 20 3 10 9 8 7 6
bob 20 4 10 3 3 3 3
bob 20 5 1 1 1 1 1
bob 20 6 1 2 3 4 5
bob 20 7 1 2 3 4 5
bob 20 8 1 2 3 4 5
;
data model;
array workweek{5} mon tue wed thu fri;
array hours{4} hours1 hours2 hours3 hours4;
retain hours1-hours4;
set raw end=eof;
length _row_ $ 8 _col_ $ 8 _type_ $ 8;
keep _type_ _col_ _row_ _coef_;
if name='marc' then i=1;
else if name='mike' then i=2;
else if name='bill' then i=3;
else if name='bob' then i=4;
hours{i}=hour;
/* build the objective function */
do k=1 to 5;
_col_='x'||put(i,1.)||put(slot,1.)||put(k,1.);
_row_='object';
_coef_=workweek{k} * 1000;
output;
end;
/* build the rest of the model */
/* cannot work during unavailable slots */
do k=1 to 5;
if workweek{k}=0 then do;
_row_='off'||put(i,1.)||put(slot,1.)||put(k,1.);
_type_='eq';
_col_='_RHS_';
_coef_=0;
output;
_col_='x'||put(i,1.)||put(slot,1.)||put(k,1.);
_coef_=1;
_type_=' ';
output;
end;
end;
if eof then do;
_coef_=.;
_col_=' ';
/* every hour 1 person working */
do j=1 to 8;
do k=1 to 5;
_row_='work'||put(j,1.)||put(k,1.);
_type_='eq';
_col_='_RHS_';
_coef_=1;
output;
_coef_=1;
_type_=' ';
do i=1 to 4;
_col_='x'||put(i,1.)||put(j,1.)||put(k,1.);
output;
end;
end;
end;
/* each person has a lunch */
do i=1 to 4;
do k=1 to 5;
_row_='lunch'||put(i,1.)||put(k,1.);
_type_='le';
_col_='_RHS_';
_coef_=1;
output;
_coef_=1;
_type_=' ';
_col_='x'||put(i,1.)||'4'||put(k,1.);
output;
_col_='x'||put(i,1.)||'5'||put(k,1.);
output;
end;
end;
/* work at most 2 slots in a row */
do i=1 to 4;
do k=1 to 5;
do l=1 to 6;
_row_='seq'||put(i,1.)||put(k,1.)||put(l,1.);
_type_='le';
_col_='_RHS_';
_coef_=2;
output;
_coef_=1;
_type_=' ';
do j=0 to 2;
_col_='x'||put(i,1.)||put(l+j,1.)||put(k,1.);
output;
end;
end;
end;
end;
/* work at most n hours in a week */
do i=1 to 4;
_row_='capacit'||put(i,1.);
_type_='le';
_col_='_RHS_';
_coef_=hours{i};
output;
_coef_=1;
_type_=' ';
do j=1 to 8;
do k=1 to 5;
_col_='x'||put(i,1.)||put(j,1.)||put(k,1.);
output;
end;
end;
end;
end;
run;
/* the following code transforms the above sparse data set */
/* into an MPS-format data set */
/* generate the header of the MPS-format data set */
data mps0;
format field1 field2 field3 $10.;
format field4 10.;
format field5 $10.;
format field6 10.;
field1 = 'NAME';
field2 = ' ';
field3 = 'PROBLEM';
field4 = .;
field5 = ' ';
field6 = .;
output;
field1 = 'ROWS';
field3 = '';
output;
field1 = 'MAX';
field2 = 'object';
field3 = '';
output;
run;
/* generate rows */
proc sql;
create table mps1 as
select _type_ as field1, _row_ as field2 from model
where _row_ eq 'object' and _type_ ne '' union
select 'E' as field1, _row_ as field2 from model
where _type_ eq 'eq' union
select 'L' as field1, _row_ as field2 from model
where _type_ eq 'le' union
select 'G' as field1, _row_ as field2 from model
where _type_ eq 'ge';
quit;
/* indicate start of columns section and declare type of all */
/* variables as integer */
data mps2;
format field1 field2 field3 $10.;
format field4 10.;
format field5 $10.;
format field6 10.;
field1 = 'COLUMNS';
field2 = ' ';
field3 = ' ';
field4 = .;
field5 = ' ';
field6 = .;
output;
field1 = ' ';
field2 = '.MARK0';
field3 = "'MARKER'";
field4 = .;
field5 = "'INTORG'";
field6 = .;
output;
run;
/* generate columns */
data mps3;
set model;
format field1 field2 field3 $10.;
format field4 10.;
format field5 $10.;
format field6 10.;
keep field1-field6;
field1 = ' ';
field2 = _col_;
field3 = _row_;
field4 = _coef_;
field5 = ' ';
field6 = .;
if field2 ne '_RHS_' then do;
output;
end;
run;
/* sort columns by variable names */
proc sort data=mps3;
by field2;
run;
/* indicate the end of the columns section */
data mps4;
format field1 field2 field3 $10.;
format field4 10.;
format field5 $10.;
format field6 10.;
field1 = ' ';
field2 = '.MARK1';
field3 = "'MARKER'";
field4 = .;
field5 = "'INTEND'";
field6 = .;
output;
run;
/* indicate the start of the RHS section */
data mps5;
format field1 field2 field3 $10.;
format field4 10.;
format field5 $10.;
format field6 10.;
field1 = 'RHS';
run;
/* generate RHS entries */
data mps6;
set model;
format field1 field2 field3 $10.;
format field4 10.;
format field5 $10.;
format field6 10.;
keep field1-field6;
field1 = ' ';
field2 = _col_;
field3 = _row_;
field4 = _coef_;
field5 = ' ';
field6 = .;
if field2 eq '_RHS_' then do;
output;
end;
run;
/* denote the end of the MPS-format data set */
data mps7;
format field1 field2 field3 $10.;
format field4 10.;
format field5 $10.;
format field6 10.;
field1 = 'ENDATA';
run;
/* merge all sections of the MPS-format data set */
data mps;
format field1 field2 field3 $10.;
format field4 10.;
format field5 $10.;
format field6 10.;
set mps0 mps1 mps2 mps3 mps4 mps5 mps6 mps7;
run;
/* solve the binary program */
proc optmilp data=mps
printlevel=0 loglevel=0
primalout=solution maxtime=1000;
run;
/* report the solution */
title 'Reported Solution';
data assignments;
set solution;
keep slot mon tue wed thu fri;
if substr(_var_,1,1)='x' then do;
if _value_>0 then do;
n=input(substr(_var_,2,1), 8.);
slot=input(substr(_var_,3,1), 8.);
d=substr(_var_,4,1);
if d='1' then mon=n;
else if d='2' then tue=n;
else if d='3' then wed=n;
else if d='4' then thu=n;
else fri=n;
output;
end;
end;
run;
proc format;
value namefmt 1='Marc' 2='Mike' 3='Bill' 4='Bob' .=' ';
run;
proc sort data=assignments;
by slot;
run;
data report;
do until (last.slot);
set assignments;
by slot;
if mon ne . then Monday = mon;
if tue ne . then Tuesday = tue;
if wed ne . then Wednesday = wed;
if thu ne . then Thursday = thu;
if fri ne . then Friday = fri;
end;
drop mon tue wed thu fri;
format Monday Tuesday Wednesday Thursday Friday namefmt.;
run;
proc print data=report;
id slot;
run;
%put &_OROPTMILP_;
