The Network Solver (Experimental)

Example 8.3 Linear Assignment Problem for Minimizing Swim Times

A swimming coach needs to assign male and female swimmers to each stroke of a medley relay team. The swimmers’ best times for each stroke are stored in a SAS data set. The LINEAR_ASSIGNMENT option evaluates the times and matches strokes and swimmers to minimize the total relay swim time.

The data are stored in matrix format, where the row identifier is the swimmer’s name (variable name) and each swimming event is a column (variables: back, breast, fly, and free). In the following DATA step, the relay times are split into two categories, male and female:

data RelayTimes;
   input name $ sex $ back breast fly free;
   datalines;
Sue     F 35.1 36.7 28.3 36.1
Karen   F 34.6 32.6 26.9 26.2
Jan     F 31.3 33.9 27.1 31.2
Andrea  F 28.6 34.1 29.1 30.3
Carol   F 32.9 32.2 26.6 24.0
Ellen   F 27.8 32.5 27.8 27.0
Jim     M 26.3 27.6 23.5 22.4
Mike    M 29.0 24.0 27.9 25.4
Sam     M 27.2 33.8 25.2 24.1
Clayton M 27.0 29.2 23.0 21.9
;

The following statements solve the linear assignment problem for both male and female relay teams:

proc contents data=RelayTimes
   out=stroke_data(rename=(name=stroke) where=(type=1));
run;

proc optmodel;
   set <str> STROKES;
   read data stroke_data into STROKES=[stroke];
   set <str> SWIMMERS;
   str sex {SWIMMERS};
   num time {SWIMMERS, STROKES};
   read data RelayTimes into SWIMMERS=[name] sex
      {stroke in STROKES} <time[name,stroke]=col(stroke)>;
   set FEMALES = {i in SWIMMERS: sex[i] = 'F'};
   set FNODES = FEMALES union STROKES;
   set MALES = {i in SWIMMERS: sex[i] = 'M'};
   set MNODES = MALES union STROKES;
   set <str,str> PAIRS;

   solve with NETWORK /
      graph_direction = directed
      links           = (weight=time)
      subgraph        = (nodes=FNODES)
      lap
      out             = (assignments=PAIRS)
   ;
   put PAIRS;
   create data LinearAssignF from [name assign]=PAIRS sex[name] cost=time;

   solve with NETWORK /
      graph_direction = directed
      links           = (weight=time)
      subgraph        = (nodes=MNODES)
      lap
      out             = (assignments=PAIRS)
   ;
   put PAIRS;
   create data LinearAssignM from [name assign]=PAIRS sex[name] cost=time;
quit;

The progress of the two SOLVE WITH NETWORK calls is shown in Output 8.3.1.

Output 8.3.1: Network Solver Log: Linear Assignment for Swim Times

NOTE: The data set WORK.STROKE_DATA has 4 observations and 41 variables.

NOTE: There were 4 observations read from the data set WORK.STROKE_DATA.

NOTE: There were 10 observations read from the data set WORK.RELAYTIMES.

NOTE: The experimental Network solver is used.

NOTE: The SUBGRAPH= option filtered 16 elements from 'time.'

NOTE: The number of nodes in the input graph is 10.

NOTE: The number of links in the input graph is 24.

NOTE: Processing the linear assignment problem.

NOTE: The minimum cost linear assignment is 111.5.

NOTE: Processing the linear assignment problem used 0.00 (cpu: 0.00) seconds.

{<'Karen','breast'>,<'Jan','fly'>,<'Carol','free'>,<'Ellen','back'>}

NOTE: The data set WORK.LINEARASSIGNF has 4 observations and 4 variables.

NOTE: The experimental Network solver is used.

NOTE: The SUBGRAPH= option filtered 24 elements from 'time.'

NOTE: The number of nodes in the input graph is 8.

NOTE: The number of links in the input graph is 16.

NOTE: Processing the linear assignment problem.

NOTE: The minimum cost linear assignment is 96.6.

NOTE: Processing the linear assignment problem used 0.00 (cpu: 0.00) seconds.

{<'Jim','free'>,<'Mike','breast'>,<'Sam','back'>,<'Clayton','fly'>}

NOTE: The data set WORK.LINEARASSIGNM has 4 observations and 4 variables.

The data sets LinearAssignF and LinearAssignM contain the optimal assignments. Note that in the case of the female data, there are more people (set $S$ ) than there are strokes (set $T$ ). Therefore, the solver allows for some members of $S$ to remain unassigned.

Output 8.3.2: Optimal Assignments for Best Female Swim Times

name	assign	sex	cost
Karen	breast	F	32.6
Jan	fly	F	27.1
Carol	free	F	24.0
Ellen	back	F	27.8
			111.5

Output 8.3.3: Optimal Assignments for Best Male Swim Times

name	assign	sex	cost
Jim	free	M	22.4
Mike	breast	M	24.0
Sam	back	M	27.2
Clayton	fly	M	23.0
			96.6