Efficiently solving assignment problem with constraints

Question

I have a variation of https://en.wikipedia.org/wiki/Assignment_problem#Unbalanced_assignment:

A bipartite graph with vertex sets A and T,
Non-negative costs on the edges,
All vertexes in A and T must occur at most once in a matching.

But with following modifications:

The edges in a matching must not intersect, i.e. with vertexes a_i in A and t_j in T sorted by some index value on both sides of the graph, a_(i_1) and t_(j_2) must not be connected in the matching when a_(i_2) and t_(j_1) are with i_1 < i_2 and j_1 < j_2.
Also for the smaller vertex set of the bipartite graph, not all vertexes need to be assigned, i.e. the optimal matching might only contain 1 edge when it has extreme costs.
We don't provide a constant s for the size of the matching to find.
Want to MAXIMIZE the sum of edge costs of the assignment.

How can that be solved most efficiently?

Linear program seems to be inefficient.

The problem can also be formulated as shortest-path problem with vertexes v_(i,j) when a_i and t_j are connected in the original bipartite graph, additional source and sink, and edges where above modifications 1 & 2 are satisfied. This still has |A|!*|T|! edges roughly which would also result in high runtime. Costs of edge from v(i_1,j_1) to v(i_2,j_2) should be set to minus the cost of the edge from a_(i_2) to t(j_2) in the original bipartite graph, so we're replicating cost values many times.

Is there some more efficient shortest-path variant with costs on vertexes instead of edges?

Or can the https://en.wikipedia.org/wiki/Hungarian_algorithm be modified to respect above modification 1? For modification 2 and 3 I see a trivial approach by adding rows and columns with values of 0 in order to get a balanced assignment problem, and modification 4 should be just negating the cost function.

For modification (1), are the orderings given or do you have to find the best result among all possible orderings? — Matt Timmermans
– Matt Timmermans, Commented Jun 20, 2022 at 17:01
The orderings are given. The vertexes at each side of the bipartite graph have been sorted before. — Luma
– Luma, Commented Jun 20, 2022 at 19:06
Just found that the Dijkstra algorithm seems to solve it within O((|A|*|T|)^2), despite of the high number of edges... Will give an update when I have final results... — Luma
– Luma, Commented Jun 20, 2022 at 19:10
If the orderings are given, then there's an O(|A|*|T|) dynamic programming solution similar to longest-common-subsequence — Matt Timmermans
– Matt Timmermans, Commented Jun 20, 2022 at 19:49
Wow thanks for that hint, I can see it. Will post it as the solution together with the concrete algorithm as soon as I'm ready. — Luma
– Luma, Commented Jun 20, 2022 at 21:25

Luma · Accepted Answer · 2022-06-22 12:33:24Z

According to above hint from @MattTimmermans, I ended up in the following dynamic programming approach (which is a modification of bipartite graph and dynamic programming):

Let w(a, t) be edge weight between nodes a in A and t in T, and let M(i, j) be solution (maximum cost matching graph without intersecting edges) for vertexes {a_0, a_1, ..., a_(i-1)} subset A and {t_0, t_1, ..., t_(j-1)} subset T, where 0 <= i < |A| and 0 <= j < |T|. For i = 0 and j = 0 the vertexes subsets are empty, i.e. prepending the matrix M by 1 row and 1 column.

for i in 0...|A|
    for j in 0...|T|
        if (i == 0 and j == 0)
            M(i,j) = {cost: 0, step_type: null}
        else
            candidates = []

            if (i >= 1 and j >= 1)
                // subtract indexes in w(...) because of prepended artificial row and column in M
                candidates.add({cost: M(i-1, j-1)[:cost] + w(i-1,j-1), step_type: 'right-down'})
            end
            if (i >= 1)
                candidates.add({cost: M(i-1, j)[:cost], step_type: 'down'})
            end
            if j >= 1
                candidates.add({cost: M(i, j-1)[:cost], step_type: 'right'})
            end

            M(i,j) = candidates.argmax(|map| map[:cost])
        end
    end
end

And then go backwards from M(|A|,|T|) according to step_type in every step, till we reach M(0,0). This gives a list of the edges in the best matching (in reverse order).

Collectives™ on Stack Overflow

Efficiently solving assignment problem with constraints

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related