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:

1. 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.
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.
3. We don't provide a constant s for the size of the matching to find.
4. 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.

Answer 1

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