The OPTGRAPH Procedure

Linear Assignment (Matching)

The linear assignment problem (LAP) is a fundamental problem in combinatorial optimization that involves assigning workers to tasks at minimal costs. In graph theoretic terms, LAP is equivalent to finding a minimum-weight matching in a weighted bipartite directed graph. In a bipartite graph, the nodes can be divided into two disjoint sets S (workers) and T (tasks) such that every link connects a node in S to a node in T. That is, the node sets S and T are independent. The concept of assigning workers to tasks can be generalized to the assignment of any abstract object from one group to some abstract object from a second group.

The linear assignment problem can be formulated as an integer programming optimization problem. The form of the problem depends on the sizes of the two input sets, S and T. Let A represent the set of possible assignments between sets S and T. In the bipartite graph, these assignments are the links. If $|S| \geq |T|$, then the following optimization problem is solved:

\begin{alignat*}{3}& \text {minimize} & & \quad \sum _{(i,j) \in A} c_{ij} x_{ij} \\ & \text {subject to} & & \quad \sum _{(i,j) \in A} x_{ij} \le 1 & & \quad i \in S \\ & & & \quad \sum _{(i,j) \in A} x_{ij} = 1 & & \quad j \in T \\ & & & \quad x_{ij} \in \{ 0,1\} & & \quad (i,j) \in A \end{alignat*}

This model allows for some elements of set S (workers) to go unassigned (if $|S| > |T|$). However, if $|S| < |T|$, then the following optimization problem is solved:

\begin{alignat*}{3}& \text {minimize} & & \quad \sum _{(i,j) \in A} c_{ij} x_{ij} \\ & \text {subject to} & & \quad \sum _{(i,j) \in A} x_{ij} = 1 & & \quad i \in S \\ & & & \quad \sum _{(i,j) \in A} x_{ij} \le 1 & & \quad j \in T \\ & & & \quad x_{ij} \in \{ 0,1\} & & \quad (i,j) \in A \end{alignat*}

This model allows for some elements of set T (tasks) to go unassigned.

In PROC OPTGRAPH, you can invoke the linear assignment problem solver by using the LINEAR_ASSIGNMENT statement. The options for this statement are described in the section LINEAR_ASSIGNMENT Statement. The algorithm that the PROC OPTGRAPH uses for solving a LAP is based on augmentation of shortest paths (Jonker and Volgenant 1987). This algorithm can be applied to either matrix data input (see the section Matrix Input Data) or graph data input (see the section Graph Input Data) as long as the graph is bipartite.

The resulting assignment (or matching) is contained in the output data set that is specified in the OUT= option in the LINEAR_ASSIGNMENT statement.

The linear assignment problem solver reports status information in a macro variable called _OPTGRAPH_LAP_. See the section Macro Variable _OPTGRAPH_LAP_ for more information about this macro variable.

For a detailed example, see Linear Assignment Problem for Minimizing Swim Times.