Ranking optimization

Question

I am looking for a library that I can feed with a list of element rankings from users so that it computes an assignment from users to elements that makes everyone happy.

Each element has an individual maximum number of possible users it can handle. A single element ranking is an ordering of all elements so that the user who ranked the elements prefers the first one most and the last one least (like first choice, second choice, and so on). A user is happier, the better his ranking of the element assigned to him is.

What software/libraries are there to solve this common optimization problem?

Edit: A mathematical definition of what I want to compute:

Given a finite set U of users, a finite set S of elements and a function c from S to the natural numbers that specifies for each element how many users can be assigned to it.

Each user specifies a ranking R(U) that is a bijective map from S to {1..|S|}. For a given assignment A: User \to Element, a penalty is defined as the sum of R(u)(A(u))^2 over all users u. Now I want to find the assignment that minimizes the penalty (or one that is good enough) and considers c by not assigning more than c(e) users to the element e.

Answer 1

TL;DR - download a program that does exactly what you need from here.

This can be modeled as a cost flow problem. In a cost flow problem, items conceptually flow between nodes along directional arcs. Each arc has a cost that is incurred each time an item flows between its nodes. Arcs also have a capacity that limits how many items can flow across the arc. And finally, each node has a starting inventory of items. A node can only send an item along one of its attached arcs if it has an item in inventory. The item is transferred from the sending end of the arc to the receiving end of the arc. The receiving node can then send the item along one of its attached arcs to yet another node. The cost flow solver searches for the set of transfers that sends as many items as it can at the lowest cost.

So what does this have to do with assigning people to workshops? Well, you can think of each person as having one token that represents their ability to attend one workshop. They send their token to the workshop they will attend, and the cost (or penalty) of sending that token is a reflection of where that workshop is in the person's prioritized list of workshops. The workshop a person most wants to attend is very cheap, while the least preferred workshop is very expensive. Once a workshop gets tokens from attendees, it sends its tokens to a sink node. The arc between the workshop and the sink node has no cost, but it does have a capacity that indicates the maximum number of people that can attend that workshop. The optimization will try to get all of the tokens to the sink node, and at the lowest cost. The only way for every token to get to the sink is if every person goes to one workshop, and if the number of people going to each workshop doesn't exceed the workshop's capacity. The solver finds a way to do that at the lowest cost.

Here's a diagram showing the layout:

There's a node for each person, a node for each workshop, and a sink node. Numbers in square braces show a node's starting inventory. Numbers in parentheses show an arc's capacity. In this example, the maximum number of people that can attend each workshop is 3, 2, and 4, respectively. Nodes without a starting inventory displayed have a starting inventory of 0, and arcs without a capacity displayed have a capacity of 1.

This can be implemented using Google's open source cost flow solver. I've done just that, and wrapped it into a program that you can download from gitlab. It's written it in such a way that you only have to replace a little bit of C# code to solve your specific problem. Just replace the workshop and person information shown below with your own data.

    // Identifies all workshops, with the maximum number of people that can enroll in each.
    Dictionary<string, int> workshopCapacities = new Dictionary<string, int>()
    {
        {"A", 2 },
        {"B", 3 },
        {"C", 1 }
    };

    // Identifies each person by name, which maps to a list of workshops they want to attend in the order of preference
    Dictionary<string, string[]> peoplePreferences = new Dictionary<string, string[]>()
    {
        { "Betsy", new[]{ "A", "B", "C" } },
        { "Joe",   new[]{ "C", "B", "A" } },
        { "Maria", new[]{ "C", "A", "B" } },
        { "Kuang", new[]{ "C", "A", "B" } },
        { "Paula", new[]{ "B", "C", "A" } },
    };