Progressive Party Problem (oclpe09)
/***************************************************************/
/* */
/* S A S S A M P L E L I B R A R Y */
/* */
/* NAME: oclpe09 */
/* TITLE: Progressive Party Problem (oclpe09) */
/* PRODUCT: OR */
/* SYSTEM: ALL */
/* KEYS: OR */
/* PROCS: OPTMODEL */
/* DATA: */
/* */
/* SUPPORT: UPDATE: */
/* REF: */
/* MISC: Example 9 from the CLP solver chapter of the */
/* Mathematical Programming book. */
/* */
/***************************************************************/
data capacities;
input boatnum capacity crewsize;
datalines;
1 6 2
2 8 2
3 12 2
4 12 2
5 12 4
6 12 4
7 12 4
8 10 1
9 10 2
10 10 2
11 10 2
12 10 3
13 8 4
14 8 2
15 8 3
16 12 6
17 8 2
18 8 2
19 8 4
20 8 2
21 8 4
22 8 5
23 7 4
24 7 4
25 7 2
26 7 2
27 7 4
28 7 5
29 6 2
30 6 4
31 6 2
32 6 2
33 6 2
34 6 2
35 6 2
36 6 2
37 6 4
38 6 5
39 9 7
40 0 2
41 0 3
42 0 4
;
data hostability;
set capacities;
spareCapacity = capacity - crewsize;
run;
data hosts guests;
set hostability;
if (boatnum <= 12 or boatnum eq 14) then do;
output hosts;
end;
else do;
output guests;
end;
run;
/* sort so guest boats with larger crews appear first */
proc sort data=guests;
by descending crewsize;
run;
data capacities;
format boatnum capacity 2.;
set hosts guests;
seqno = _n_;
run;
%let rounds=2;
%let numhosts=13;
proc optmodel;
num numrounds = &rounds;
set ROUNDS = 1..numrounds;
num numhosts = &numhosts;
set HOSTS = 1..numhosts;
set BOATS;
num numboats = card(BOATS);
num capacity {BOATS};
num crewsize {BOATS};
num spareCapacity{hi in HOSTS} = capacity[hi] - crewsize[hi];
/* Use the descending crew order for guests (seqno)
rather than the actual boat id (boatnum)
to help the performance of the PACK predicate. */
read data capacities into BOATS=[seqno] capacity crewsize;
/* Assume that the first numhosts boats are hosts,
and process each round in turn.
X is the host assigned to non-host i for round t. */
var X {numhosts+1..numboats, ROUNDS} integer >= 1 <= numhosts;
/* The load of the host boat. */
var L {hi in HOSTS, ROUNDS} integer >= 0 <= spareCapacity[hi];
/* Assign different hosts each round. */
con AlldiffCon {i in numhosts+1..numboats}:
alldiff({t in ROUNDS} X[i,t]);
/* Two crews cannot meet more than once. */
var M {i in numhosts+1..numboats-1, j in i+1..numboats, t in ROUNDS} binary;
con ReifyCon {i in numhosts+1..numboats-1, j in i+1..numboats, t in ROUNDS}:
reify(M[i,j,t], X[i,t] = X[j,t]);
con Assign {i in numhosts+1..numboats-1, j in i+1..numboats}:
sum {t in ROUNDS} M[i,j,t] <= 1;
/* Honor capacities. */
con PackCon {t in ROUNDS}:
pack(
{i in numhosts+1..numboats} X[i,t],
{i in numhosts+1..numboats} crewsize[i],
{h in HOSTS} L[h,t]
);
/* Break symmetries. */
con SymmetryCon {t in 1..numrounds-1}:
X[numboats,t] < X[numboats,t+1];
solve with CLP / varselect=FIFO;
create data out from
{i in numhosts+1..numboats, t in ROUNDS} <col('X_'||i||'_'||t)=X[i,t]>
{h in HOSTS, t in ROUNDS} <col('L_'||h||'_'||t)=L[h,t]>
{i in numhosts+1..numboats-1, j in i+1..numboats, t in ROUNDS}
<col('M_'||i||'_'||j||'_'||t)=M[i,j,t]>;
quit;