Facets of an Assignment Problem with 0–1 Side Constraint

Abstract

We show that the problem of finding a perfect matching satisfying a single equality constraint with a 0–1 coefficients in an n × n incomplete bipartite graph, polynomially reduces to a special case of the same peoblem called the partitioned case. Finding a solution matching for the partitioned case in the incomlpete bipartite graph, is equivalent to minimizing a partial sum of the variables over = the convex hull of incidence vectors of solution matchings for the partitioned case in the complete bipartite graph. An important strategy to solve this minimization problem is to develop a polyhedral characterization of . Towards this effort, we present two large classes of valid inequalities for , which are proved to be facet inducing using a facet lifting scheme.