Resources

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;