# Separation Oracle for Inverse Bipartite Matching Polytope

The $N$x$N$ bipartite matching problem can be written as finding a configuration of variables ${\mathbf y}^* = \{y^*_1, \ldots, y^*_N\}$, $y_i \in \{1, \ldots, N\}$ such that

$${\mathbf y}^* = \arg\min_{{\mathbf y}} \;\; E({\mathbf y}; {\mathbf w}),$$

where $y^*_i$ is the index of the point in partite set $B$ that the $i$th point in partite set $A$ is matched to in the optimal matching$^1$, and ${\mathbf w}$ is a $N$x$N$ matrix of matching costs, giving the cost of matching $A_i$ to $B_j$. The 1-to-1 constraints are implicit in $E$. For purposes here, further restrict ${\mathbf w}$ to lie inside a unit hypercube ${\mathbf w} \in [0,1]^{N\cdot N}$.

I'm interested in what I'm calling the inverse bipartite matching polytope, $R({\mathbf y})$, which contains all ${\mathbf w}$ that lead to ${\mathbf y}$ as a minimum cost matching, ie., $$R({\mathbf y}) = \{{\mathbf w} \mid \arg\min_{{\mathbf y'}} \;\; E({\mathbf y'}; {\mathbf w}) = {\mathbf y} \}.$$

It is straightforward to show that this is a convex polytope, but I don't know of any way to define it without using an exponential number of linear inequalities. So I'm interested in a separation oracle for $R({\mathbf y})$: given a $\hat {\mathbf w}$ that lies outside $R({\mathbf y})$, I'd like a linear constraint that separates $\hat {\mathbf w}$ from $R({\mathbf y})$, ideally cutting away as much space outside of $R({\mathbf y})$ as possible. (So while one simple solution is to find the optimal matching under $\hat {\mathbf w}$, $\hat {\mathbf y} = \arg\min_{{\mathbf y}} \;\; E({\mathbf y}; \hat {\mathbf w})$, then to enforce that the cost of ${\mathbf y}$ is less than the cost of $\hat {\mathbf y}$, this is unappealing because it seems to be a pretty shallow cut).

Is this a problem that has been studied, or is it closely related to a problem that has been studied? I'd appreciate any references or terms to narrow down my search.

[1] I'm assuming throughout that the minimum cost matching is unique.

• So $E$ is some magic cost function that wraps into it the constraints on the assignment ? – Suresh Venkat Oct 3 '11 at 17:41
• I don't understand what you mean by "cutting away as much space otuside of $R(\mathbf{y})$ as possible". The space outside $R(\mathbf{y})$ is unbounded, how much of it should be cut? Also, I thought that the oracle you describe suffices for the ellipsoid algorithm? – Sasho Nikolov Oct 3 '11 at 18:38
• @SureshVenkat yes. You can think of it as the sum of matching costs plus some penalty terms that assign infinite cost to any illegal matching. I'm not sure this specific formulation is necessary, it's just the way I've been thinking about it. – dan_x Oct 3 '11 at 18:51
• @SashoNikolov Intuitively, it seems like we should often be able to prove that some w will not lead to the target matching without looking at the full matrix. If we can do this, then this should give rise to a deeper cut, since it is lower dimensional. To define deepness of cut, how about saying something like the number of matchings y' that are cut away? (I.e., # of matchings y' for which R(y') is completely cut away.) – dan_x Oct 3 '11 at 18:57
• So you're not really looking for a separation oracle to run the ellipsoid algorithm. Your convex polytope can be written with one constraint for each legal matching $y'$, with the constraint enforcing that the cost of $y$ under weights $w$ is at most the cost of $y'$. You want a concise description of the polytope, and you're asking if there is some constraint that dominates (i.e. implies) at least a constant fraction of the other constraints? – Sasho Nikolov Oct 3 '11 at 20:53