\sum_{i\in A}x_{ij}=1\text{ for }j\in T 0\le x_{ij}\le 1\text{ for }i,j\in A,T, \, x_{ij}\in \mathbb{Z}\text{ for }i,j\in A,T. 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 totally unimodular – it satisfies the four conditions of Hoffman and Gale.
