The Linear Assignment Problem (LSAP) is one of the most famous problems in linear programming and in combinatorial optimization. Informally speaking, we are given an $n \times n$ cost matrix $C = (cij)$ , and we want to select $n$ elements of $C$ , so that there is exactly one element in each row and one in each column, and the sum of the corresponding costs is a minimum.

Mathematical model: By introducing a binary matrix $X = (x_{ij})$ such that:

$\displaystyle x_{ij} = \left\{ \begin{array}{ll} 1 & \mbox{if row $i$ is assigned to column $j$,}\\[0.2cm] 0 & \mbox{otherwise,} \end{array} \right.$

LSAP can be modeled as

	$\displaystyle \min \quad$	$\displaystyle$	$\displaystyle \sum _{i=1}^ n \sum _{j=1}^ n c_{ij} x_{ij}$
	$\displaystyle ~ \text {s.t.}$	$\displaystyle$	$\displaystyle \sum _{j=1}^ n x_{ij} = 1\qquad (i = 1,2, \dots ,n),$
	$\displaystyle$	$\displaystyle$	$\displaystyle \sum _{i=1}^ n x_{ij} = 1\qquad (j = 1,2, \dots ,n),$
	$\displaystyle$	$\displaystyle$	$\displaystyle x_{ij} \in \{ 0,1\} \qquad (i, j = 1,2, \dots ,n).$

To get more, read the Introduction