Editing Assignment problem (section)

=== Solution by linear programming ===
The assignment problem can be solved by presenting it as a [[linear program]]. For convenience we will present the maximization problem. Each edge {{math|(''i'',''j'')}}, where ''i'' is in A and ''j'' is in T, has a weight <math display="inline">w_{ij}</math>. For each edge {{tmath|(i,j)}} we have a variable <math display="inline">x_{ij}</math><sub>.</sub> The variable is 1 if the edge is contained in the matching and 0 otherwise, so we set the domain constraints:  
<math display="block">0\le x_{ij}\le 1\text{ for }i,j\in A,T, \, </math> <math display="block">x_{ij}\in \mathbb{Z}\text{ for }i,j\in A,T. </math>

The total weight of the matching is: <math>\sum_{(i,j)\in A\times T} w_{ij}x_{ij}</math>. The goal is to find a maximum-weight perfect matching.

To guarantee that the variables indeed represent a perfect matching, we add constraints saying that each vertex is adjacent to exactly one edge in the matching, i.e.,  
<math display="block">\sum_{j\in T}x_{ij}=1\text{ for }i\in A, \,
~~~
\sum_{i\in A}x_{ij}=1\text{ for }j\in T, \, </math>.

All in all we have the following LP:

<math display="block">\text{maximize}~~\sum_{(i,j)\in A\times T} w_{ij}x_{ij}
</math><math display="block">\text{subject to}~~\sum_{j\in T}x_{ij}=1\text{ for }i\in A, \,
~~~
\sum_{i\in A}x_{ij}=1\text{ for }j\in T </math><math display="block">0\le x_{ij}\le 1\text{ for }i,j\in A,T, \, </math><math display="block">x_{ij}\in \mathbb{Z}\text{ for }i,j\in A,T. </math>This is an integer linear program.  However, we can solve it without the integrality constraints (i.e., drop the last constraint), using standard methods for solving continuous linear programs. While this formulation allows also fractional variable values, in this special case, the LP always has an optimal solution where the variables take integer values.  This is because the constraint matrix of the fractional LP is [[Unimodular matrix#Total unimodularity|totally unimodular]]&nbsp;– it satisfies the four conditions of Hoffman and Gale.