Solve a Linear Assignment Problem With Proc Optnet in SAS

The Linear Assignment problem is a classic problem within optimization and operations research. Simply put, we have a set of workers S and a set of tasks T. Any worker can be assigned to any task, incurring some cost c. This problem forms a bipartite graph where all nodes in S connect to all nodes in T with some weight c. The optimization problem can then be written formally as.

$\begin{equation*} \begin{aligned} \min \quad & \sum_{(i, j) \in A}{c_{ij} x_{ij}} \\ \textrm{s.t.} \quad & \sum_{(i, j) \in A}{x_{ij} \leq 1}, \quad &i &\in S \\ & \sum_{(i, j) \in A}{x_{ij} = 1}, \quad &j &\in T \\ & x_{ij} \in \{0, 1\}, \quad &$i, j$ &\in A \end{aligned} \end{equation}$

Here, A denotes the set of all possible assignments between S and T.

A Simple Linear Assignment Problem in SAS

Let us see how simple it is to solve a linear assignment problem in SAS with Proc Optnet. I will use the small example data set below. Here, I have three workers s1, s2 and s3 and three tasks to be performed t1, t2 and t3. Each assigment has a weight. For example, assigning s1 to t1 has a weight of 30. The tassk here is to assign one worker to each task, minimizing the sum of weights.

/* Example data */
data have;
input from $ to $ weight;
datalines;
s1 t1 30 
s1 t2 20 
s1 t3 10 
s2 t1 15 
s2 t2 13 
s2 t3 60 
s3 t1 20 
s3 t2 8  
s3 t3 15 
;

Luckiliy this problem is easy to solve with Proc Optnet. We simply specify the input data and that the graph is directed. Meaning that we want to assign workers to tasks, not tasks to workers. Next, we use the Linear_Assignment Statement and specify that the results should be saved in the want data set.

/* Solve the linear assignment problem */
proc optnet data_links=have direction=directed;
   linear_assignment out=want;
run;

The result is below. We can see that s1 is assigned to t3, s2 to t1 and s3 to t2. This is the combination of assignments that minimize the sum of weights as desired.

Obs  from  to  weight
1    s1    t3  10
2    s2    t1  15
3    s3    t2  8

Furthermore, Proc Optnet outputs the status of the algorithm run and the final objective value. As you can see in the image below, the solution is optimal and the objective value is 33. This is the sum of 10, 15 and 8 in the result above.

Next, let us expand the problem a bit. The data above is quite small for demonstration purposes. Instead, let us consider the same problem. However, here we have 100 workers and 100 tasks. The code run is the same.

Proc Optnet Can Handle Large Problems

data have;
   do from = 1 to 100;
      do to = 101 to 200;
         weight = rand('integer', 1, 10000);
         output;
      end;
   end;
run;
 
proc optnet data_links=have direction=directed;
linear_assignment out=want;
run;

Again, the code ran swiftly and quite fast. Just as before, the result reveals that the solution is optimal and the final minimal objetive value.

Summary

In this post, we investigate how to solve a linear assignment problem in SAS. We do so with Proc Optnet. Proc Optnet lets us solve the problem efficiently with little coding. If you wan to learn more about Linear Assignment Problems or Proc Optnet in general, consult the Documentation.

You can download the entire code form this post here.