Hungarian Extension: Additive Costs, Non-Additive Benefits

Question

I have a problem that's adjacent to the Hungarian algorithm, but not identical. Suppose I have $N$ workers and $N$ jobs, and I want to develop a matching for all $N$ on both sides. There are $N!$ ways of doing this, and lets index them as $i\in\{1,2,...,N!\}$.

As in the typical Hungarian setup, the costs of each pairwise assignment are additively separable. Each pairwise assignment $w\leftrightarrow j$ has a cost, $c_{wj}$. The total costs of an matching $i$ is the sum of all the $c_{wj}$s.

There are also benefits for each matching. Unlike the costs, the benefits are NOT additively separable. Instead, there is one lump-sum benefit ``$\beta(i)$'' for each possible matching $i$. This lump-sum may express non-linear synergies or complementarities across the assignments in $i$ on the benefits/revenue side.

So the goal would be to choose an $i$ to maximize the non-additive benefit $\beta(i)$ minus the (additive) costs. My notation for this would be: Choose an $i$ to maximize $B(i)-\sum_{wj\in i}c_{wj}$. Hopefully the point is clear.

Is this (hopefully) a known problem with some kind of polynomial time solution?

Answer 1

This makes no sense. Since there are no constraints on $\beta(i)$, it doesn’t matter whether you subtract some additively separable function from it. You might as well subtract another additively separable function, or none at all – as long as $\beta(i)$ is an arbitrary function with no known structure, all you can do is calculate the cost for each matching and find the lowest one.

Answer 2

The task of examining each benefit would require factorial time, so a polynomial time algorithm would not be able to consider every possible benefit. Put another way, inputting/calculating all the benefits would take factorial time. So unless the benefits have some sort of structure that can be exploited, there is no hope of a polynomial time algorithm.

If you are willing to settle for a heuristic solution (no guarantee of optimality), there are "random key" genetic algorithms that use permutations as the chromosome type. You would still have to calculate (and, preferably, cache) benefit values for each permutation encountered, but you might find a "good" solution in a "reasonable" amount of time (and memory).