0
$\begingroup$

Statement of problem

We have two sets of vertices, $V$ and $U$, each of which has a vector of attributes $A$.

The set of edges $E$ is defined such that there is an edge $vu\in{E}$ between vertices $v$ with attributes $[a_1,a_2,...]$ and $u$ with attributes $[a'_1,a'_2,...]$ IFF a function $f([a_1,a_2,...],[a'_1,a'_2,...])=true$.

It is allowed to match each vertex in $V$ up to $m$ times, and each vertex in $U$ up to $n$ times.

We need a maximum matching betteen $V$ and $U$.

This was the original problem, and we have a working solution for this.

We now have an additional requirement.

Vertices in $U$ have an additional attribute $s\in{S}$. $S$ is a finite set. We have a vector $R$ of ratios for $S$ (that is, if $S = \{s_1,s_2,...,s_{|S|}\}$, a vector $[r_1,r2,...,r_{|S|}]$ such that for each $i$, $0\le{r_i}\le1$, and $\sum_1^{|S|}{r_i}=1$ ).

We need the set $U'$ of matched vertices from $U$, from the maximum matching, to fit this vector of ratios as best it can. To put it more formally, we also have a function $g(U')$ which takes a subset $U'\subseteq{U}$, calculates $[\frac{freqency(s_1)}{|U'|},\frac{freqency(s_2)}{|U'|},...]$, and calculates a distance between that and our vector $R$. We need to produce a maximum matching with minimum $g(U')$.

Due to the nature of our data, there may be many maximum matchings. So the aim is to select the maximum matching that minimizes $g(U')$. That is, getting maximum coverage is first priority, the ratios are second priority.

The existing solution

If possible, we would like to do this as an extension to our existing implementation rather than start from scratch. So here is how we solved the first part of the problem.

  • We noticed that many vertices in $V$ and $U$ had the same vector of attributes $A$. So we decided to define new artificial sets of vertices $V_{agg}$ and $U_{agg}$, which had one vertex for each of the existing vectors. Each $v_{agg}$ also carries the number of vertices in $V$ that it stands for, $w$, and $u_{agg}$ the number of vertices in $U$ it stands for, $w'$. We kept a record of the exact vertices represented by each $v_{agg}$ and $u_{agg}$.

  • We break the graph into connected components and solve each independently.

  • We use a flow network to represent the graph.

    • From the source to each $v_{agg}$, we have an edge with weight $m\times{w}$.
    • from each $v_{agg}$ to each $u_{agg}$ for which $f(A,A')=true$, we have an edge whose weight is infinite.
    • from each $u_{agg}$ to the sink, we have an edge with weight $n\times{w'}$.
  • We solve for maximum flow using Push-Relabel

  • Once we have final weights on the edges (the ones who had infinite capacity), we use those to create individual matches between the original vertices.

The question

  • How can we adjust the maximum flow algorithm so it also minimizes the ratio distance function?
    • I realize that we might not be able to break the data into connected components because the ratios are over the entire output set.
    • We may also need to aggregate the vertices in $U_{agg}$ more finely - group together vertices that share both the same $A'$ and the same value of $s$.
  • If not possible, is there another algorithm that will do this?
  • If not possible, is there a sub-optimal solution? The coverage needs to be maximum, but we can be somewhat lenient about the distance function $g(U')$, i.e., it's good enough if $g(U')\lt{k}$ for a given $k$.
$\endgroup$
3
  • $\begingroup$ Your problem is not yet well-defined, because you have listed two objectives (maximum matching, minimum distance), and it's not clear to me how you want those two to be traded off. Likely the solution that is optimal for one metric may not be optimal for the other. Do you want a maximum matching, and out of all matchings with the same number of edges with as the maximum, minimize the distance (so the primary metric is the number of edges in the matching and distance is a tie-breaker)? Do you want some other tradeoff? $\endgroup$
    – D.W.
    Aug 17, 2023 at 3:34
  • $\begingroup$ @D.W. Yes, basically. Assuming there is more than one maximum matching (which for the individual, not aggregated, level, is very likely), we want to select the one that minimizes the distance. $\endgroup$ Aug 17, 2023 at 12:45
  • $\begingroup$ Please edit the post so that this information can be found in the post, and people don't have to read the comments to understand what is being asked. Thank you! $\endgroup$
    – D.W.
    Aug 17, 2023 at 16:14

1 Answer 1

1
$\begingroup$

Try using (integer) linear programming.

The matching problem can be expressed as a linear programming instance. In particular, you have a variable $x_{u,v}$ for each pair of variables joined by an edge, with the intended meaning that $x_{u,v}=1$ means $(u,v)$ is included in the matching and $x_{u,v}=0$ means it is not; then you can write down linear inequalities to capture a maximum matching (e.g., $0 \le x_{u,v} \le 1$, $\sum_u x_{u,v} \le 1$, $\sum_v x_{u,v} \le 1$, maximize $\sum_{u,v} x_{u,v}$).

In your case, let's assume you have pre-computed a maximal matching (without additional constraints), so you know the size of the maximal matching is $s$. Now you can add the inequality $\sum_{u,v} x_{u,v} \ge s$.

Now add in linear inequalities to compute your distance. If you use the L2 distance, that's not expressible with linear inequalities, so I suggest you use the L1 or L$\infty$ distance. For L$\infty$ distance, add a new variable $d$, and add the inequality

$$2r_i s - 2ds \le \sum_{u \in S_i,v \in V} x_{u,v} + \sum_{u \in V,v \in S_i} x_{u,v} \le 2r_i s + 2ds$$

where here $S_i$ is the set of vertices whose attribute is $s_i$. Then find a solution to the linear program that minimizes $d$. For L1 distance, we're going to do almost the same: add variables $d_1,d_2,\dots$, and for each $i$, add the inequality

$$2r_i s - 2d_i s \le \sum_{u \in S_i,v \in V} x_{u,v} + \sum_{u \in V,v \in S_i} x_{u,v} \le 2r_i s + 2d_i s$$

and then minimize the objective function $d_1+d_2+\dots$.

Now solve this with an off-the-shelf ILP solver and require that all of the $x$'s be integers. I am hopeful that the resulting ILP might be feasible, given that without the additional distance constraint it can be solved in polynomial time, but I imagine there are no guarantees.

See also https://en.wikipedia.org/wiki/Assignment_problem#Solution_by_linear_programming.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.