Mixed-integer vertex covers on bipartite graphs

Let $A$ be the edge-node incidence matrix of a bipartite graph $G = (U, V ; E)$, $I$ be a subset of the nodes of $G$, and $b$ be a vector such that $2b$ is integral. We consider the following mixed-integer set: $X(G, b, I) = {x : Ax ≥ b, x ≥ 0, x_i$ integer for all $i ∈ I}$. We characterize conv$(X(G, b, I))$ in its original space. That is, we describe a matrix $(C, d)$ such that conv$(X(G, b, I)) = {x : Cx ≥ d}$. This is accomplished by computing the projection onto the space of the $x$-variables of an extended formulation, given in [1], for $conv(X(G, b, I))$. We then give a polynomial-time algorithm for the separation problem for conv$(X(G, b, I))$, thus showing that the problem of optimizing a linear function over the set $X(G, b, I)$ is solvable in polynomial time.