Discrete optimization algorithm

Question

I'm trying to decide on the best approach for my problem, which is as follows:

I have a set of objects (about 3k-5k) which I want to uniquely assign to about 10 groups (1 group per object). Each object has a set of grades corresponding with how well it fits within each group. Each group has a capacity of objects it can manage (the constraints). My goal is to maximize the sum of grades my assignments receive.

For example, let's say I have 3 objects (o1, o2, o3) and 2 groups (g1,g2) with a cap. of 1 object each. Now assume the grades are:

o1: g1=11, g2=8

o2: g1=10, g2=5

o3: g1=5, g2=6

In that case, for the optimal result g1 should receive o2, and g2 should receive o1, yielding a total of 10+8=18 points.

Note that the number of objects can either exceed the sum of quotas (e.g. leaving o3 as a "leftover") or fall short from filling the quotas.

How should I address this problem (Traveling Salesman, sort of a weighted Knap-Sack etc.)? How long should brute-forcing it take on a regular computer? Are there any standard tools such as the linprog function in Matlab that support this sort of problem?

Answer 1

It can be solved with min cost flow algorithm. The graph can look the following way:

It should be bipartite. The left part represents objects(one vertex for each object). The right part represents groups(one vertex for each group). There is an edge from each vertex from the left part to each vertex from the right part with capacity = 1 and cost = -grade for this pair. There is also an edge from the source vertex to each vertex from the left part with capacity = 1 and cost = 0 and there is an edge from each vertex from the right part to the sink vertex(sink and source are two additional vertices) with capacity = constraints for this group and cost = 0.

The answer is -the cheapest flow cost from the source to the sink.

It is possible to implement it with O(N^2 * M * log(N + M)) time complexity(using Dijkstra algorithm with potentials)(N is the number of objects, M is the number of groups).