Facets of an assignment problem with a 0-1 side constraint.

Abstract

This dissertation focuses on the polyhedral characterization related to the problem of finding a perfect matching consisting of a specified number of edges of one of the colors, in a bicolored incomplete n x n bipartite graph. In particular, we investigate the polyhedral structure of the polytope $Q\sbsp{n\sb1,n\sb2}{n,r\sb1}$ defined as the convex hull of incidence vectors of perfect matchings in $K\sb{n,n},$ the complete bipartite graph, consisting of $r\sb1$ edges in $K\sbsp{n\sb1,n\sb2}{1},$ a complete bipartite subgraph of $K\sb{n,n}.$. In the nontrivial case, the dimension of the polytope $Q\sbsp{n\sb1,n\sb2}{n,r\sb1}$ is shown to be equal $n\sp2 -2n.$ Two large non-trivial classes of facets of $Q\sbsp{n\sb1,n\sb2}{n,r\sb1}$ are presented and a direct proof of these facets is given in the appendices. This proof is based on exhibiting $n\sp2 - 2n$ affinely independent assignments that belong to a facet F. We also present a facet lifting procedure, that is, given a facet F of $Q\sbsp{n\sb1,n\sb2}{n,r\sb1},$ we show how to derive a facet $F*$ of $Q\sbsp{n\sb1,n\sb2}{n+1,r\sb1},\ Q\sbsp{n\sb1+1,n\sb2}{n+1,r\sb1},\ Q\sbsp{n\sb1+1,n\sb2+1}{n+1,r\sb1+1},\ {\rm or}\ Q\sbsp{n\sb1,n\sb2+1}{n+1,r\sb1}.$ This procedure provides an alternative short proof of the two classes of facets based on mathematical induction. Adjacency relations on the polytope $Q\sb{c,r}$ defined as the convex hull of incidence vectors of assignments that lie in a given hyperplane defined by general integer coefficients $c\sb{ij}$ are also discussed. We show that the problem of checking nonadjacency of two given extreme points of $Q\sb{c,r}$ is solvable in ${\cal O}(n\sp5)$ if c = ($c\sb{ij})$ is a 0-1 matrix, and that it is NP-complete if c is a general integer matrix. Finally, we present a characterization of fractional extreme points of the polytope $P\sbsp{n\sb1,n\sb2}{n,r\sb1}$ which is the intersection of the assignment polytope with the hyperplane represented by the constraint that the assignment must contain $r\sb1$ allocations in the subgraph $K\sbsp{n\sb1,n\sb2}{1}\ (Q\sbsp{n\sb1,n\sb2}{n,r\sb1}$ is the convex hull of integer points in $P\sbsp{n\sb1,n\sb2}{n,r\sb1}).$ The simplest non-trivial case of $P\sbsp{n\sb1,n\sb2}{n,r\sb1}$ namely is also discussed. $P\sbsp{2,2}{n,1}$ is also discussed.