Facets of an Assignment Problem with 0–1 Side Constraint

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 $$Q_{n_{1,} n_2 }^{n,r_1 } $$ = 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 $$Q_{n_{1,} n_2 }^{n,r_1 } $$ . Towards this effort, we present two large classes of valid inequalities for $$Q_{n_{1,} n_2 }^{n,r_1 } $$ , which are proved to be facet inducing using a facet lifting scheme.