The CLP Procedure

This example demonstrates the use of the PACK constraint to solve an instance of the progressive party problem (Smith et al. 1996). In the original progressive party problem, a number of yacht crews and their boats congregate at a yachting rally. In order for each crew to socialize with as many other crews as possible, some of the boats are selected to serve as "host boats" for six rounds of parties. The crews of the host boats stay with their boats for all six rounds. The crews of the remaining boats, called "guest crews," are assigned to visit a different host boat in each round.

Given the number of boats at the rally, the capacity of each boat, and the size of each crew, the objective of the original problem is to assign all the guest crews to host boats for each of the six rounds, using the minimum number of host boats. The partitioning of crews into guests and hosts is fixed throughout all rounds. No two crews should meet more than once. The assignments are constrained by the spare capacities (total capacity minus crew size) of the host boats and the crew sizes of the guest boats. Some boats cannot be hosts (zero spare capacity), and other boats must be hosts.

In this instance of the problem, the designation of the minimum requirement of thirteen hosts is assumed (boats one through twelve and fourteen). The formulation solves up to eight rounds, but only two rounds are scheduled for this example. The total capacities and crew sizes of the boats are shown in Output 3.14.1.

The following statements and DATA steps process the data and designate host boats:

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;

To model the progressive party problem for the CLP procedure, first define several sets of variables. Item variables give the host boat number for the assignment of guest boat i in round t. Load variables give the load of host boat h in round t. Variable are binary variables that take a value of 1 if and only if guest boats i and j are assigned the same host boat in round t.

Next, describe the set of constraints used in the model. ALLDIFFERENT constraints ensure that a guest boat is not assigned the same host boat in different rounds. The REIFY constraints regulate the values assigned to the aforementioned indicator variables . These indicator variables appear in LINCON constraints to enforce the meet-at-most-once requirement. One PACK constraint per round maintains the capacity limitations of the host boats. Finally, there is a symmetry-breaking LINCON constraint. This constraint orders the host boat assignments for the highest-numbered guest boat across rounds.

The following statements call the CLP procedure to define the variables, specify the constraints, and solve the problem.

%let rounds=2;
%let numhosts=13;

%macro ppp;
   proc sql noprint;
      select count(*) into :numboats from capacities;
      select max(capacity) into :maxcap from capacities;
      %do i = 0 %to &maxcap;
         select count(*) into :numclass_&i from capacities where capacity = &i;
      %end;
      select crewsize, spareCapacity into
         :crewsize_1-:crewsize_%scan(&numboats,1),
         :cap_1-:cap_%scan(&numboats,1) from capacities order by seqno;
   quit;

   proc clp out=out varselect=FIFO;
      /* assume first &numhosts boats are hosts */
      /* process each round in turn */
      %do t = 1 %to &rounds;
         %do i = &numhosts+1 %to &numboats;
            /* boat i assigned host value for round t */
            var x_&i._&t = [1,&numhosts];
         %end;
         %do h = 1 %to &numhosts;
            var L_&h._&t = [0,&&cap_&h]; /* load of host boat */
         %end;
      %end;

      %do i = &numhosts+1 %to &numboats;
         /* assign different host each round */
         alldiff (x_&i._1-x_&i._&rounds);
      %end;

      %do t = 1 %to &rounds;
         %do i = &numhosts+1 %to &numboats-1;
            /* boat i assigned host value for round t */
            %do j = &i+1 %to &numboats;
               var m_&i._&j._&t = [0,1];
               reify m_&i._&j._&t : (x_&i._&t = x_&j._&t);
            %end;
         %end;
      %end;

      %do i = &numhosts+1 %to &numboats-1;
         %do j = &i+1 %to &numboats;
            lincon 1 >= 0
            %do t = 1 %to &rounds;
               + m_&i._&j._&t
            %end;
            ;
         %end;
      %end;

      /* honor capacities */
      %do t = 1 %to &rounds;
         PACK((
         %do i = &numhosts+1 %to &numboats;
            x_&i._&t
         %end;
         ) (
         %do i = &numhosts+1 %to &numboats;
            &&crewsize_&i
         %end;
         ) (
         %do h = 1 %to &numhosts;
            L_&h._&t
         %end;
         ));
      %end;

      /* break symmetries */
      %do t = 1 %to &rounds-1;
         lincon x_%scan(&numboats,1)_&t < x_%scan(&numboats,1)_%eval(&t+1);
      %end;

   run;
%mend ppp;

%ppp;

The two charts in Output 3.14.2 show the boat assignments for the first two rounds. The horizontal axis shows the load for each host boat. Slack capacity is highlighted in red.

Output 3.14.2: Gantt Chart: Boat Schedule by Round

The charts in Output 3.14.3 break down the assignments by boat number for selected boats.

Output 3.14.3: Gantt Chart: Host Boat Schedule by Round