ASSIGNMENT POLYTOPE

Assignment polytope - (X in R^(n*n): X >= 0, Sum_i(X(i, j)) = 1 for all j, Sum_j(X(i, j)) = 1 for all i). The name stems from a meaning of its extreme points in the assignment problem : If X(i, j) = 1, assign person i to task j. Each extreme point has the property that each element of X is 0 or 1. The sums in the polytope then require that each row (i) and each column (j) has exactly one 1 in it. This means every person is assigned to some task, and every task is assigned to be done by one person. The polytope is also the set of doubly stochastic matrices, whose extreme points are the permutation matrices.