<p>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</p>

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

<p>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}$. </p>

<p>I'm interested in what I'm calling the <i>inverse bipartite matching polytope</i>, $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&#39;}} \;\; E({\mathbf y&#39;}; {\mathbf w}) = {\mathbf y} \}.$$</p>

<p>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).</p>

<p>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.</p>

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

CC BY-SA 3.0
2011-10-03T17:41:08.333Z
So $E$ is some magic cost function that wraps into it the constraints on the assignment ?
Suresh Venkat
CC BY-SA 3.0
2011-10-03T18:38:25.723Z
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
CC BY-SA 3.0
2011-10-03T18:51:46.930Z
@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
CC BY-SA 3.0
2011-10-03T18:57:29.993Z
@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
CC BY-SA 3.0
2011-10-03T20:53:09.930Z
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
CC BY-SA 3.0
2011-10-03T21:11:26.560Z
@SashoNikolov I suppose your description is correct.  I would only add that I'm interested in constraints relative to a particular \hat w, and I'd like a constraint that dominates as many other of these simple constraints as possible (and is computationally feasible to find), given that we're restricted to linear constraints.
dan_x
CC BY-SA 3.0
2011-10-04T00:05:16.383Z
well if this describes your question accurately you're probably better off clarifying these things in your question. unless you think most users except me won't be confused by the phrase "shallow cut"
Sasho Nikolov
CC BY-SA 3.0
2011-10-04T05:54:30.970Z
I think the question made sufficient sense to me: however, I don't have an answer :)
Suresh Venkat
<ds.algorithms><graph-theory><graph-algorithms>
Separation Oracle for Inverse Bipartite Matching Polytope
dan_x
# Separation Oracle for Inverse Bipartite Matching Polytope

(Asked by: username_0 on 2011-10-03)

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.

**Tags:** ds.algorithms, graph-theory, graph-algorithms

> **Comments:**
> **username_1**: So $E$ is some magic cost function that wraps into it the constraints on the assignment ?  
> **username_2**: 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?  
> **username_0**: @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.  
> **username_0**: @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.)  
> **username_2**: 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?  
> **username_0**: @SashoNikolov I suppose your description is correct.  I would only add that I'm interested in constraints relative to a particular \hat w, and I'd like a constraint that dominates as many other of these simple constraints as possible (and is computationally feasible to find), given that we're restricted to linear constraints.  
> **username_2**: well if this describes your question accurately you're probably better off clarifying these things in your question. unless you think most users except me won't be confused by the phrase "shallow cut"  
> **username_1**: I think the question made sufficient sense to me: however, I don't have an answer :)  

---

## 0 answers

