排名优化

Question

我正在寻找一个库，我可以在其中提供用户的元素排名列表，以便它计算用户对元素的分配，让每个人都开心。

每个元素都有它可以处理的最大可能用户数。单个元素排名是对所有元素进行排序，以便对元素进行排名的用户最喜欢第一个元素而最不喜欢最后一个元素（如第一选择、第二选择等）。用户越开心，他对分配给他的元素的排名就越好。

有什么software/libraries可以解决这个常见的优化问题？

编辑：我要计算的数学定义：

给定用户的有限集 U、元素的有限集 S 和从 S 到自然数的函数 c，该函数为每个元素指定可以为其分配多少用户。

每个用户指定一个排名 R(U)，它是从 S 到 {1..|S|} 的双射映射。对于给定的分配 A: User \to Element，惩罚定义为所有用户 u 的 R(u)(A(u))^2 之和。现在我想找到最小化惩罚的分配（或足够好的分配）并通过不将超过 c(e) 个用户分配给元素 e 来考虑 c。

Answer 1

TL;DR - 从 here.

下载完全满足您需求的程序

这可以建模为成本流问题。在成本流问题中，项目在概念上沿着有向弧在节点之间流动。每条弧都有一个成本，每次项目在其节点之间流动时都会产生成本。 Arcs 也有一个容量限制有多少项目可以流过 arc。最后，每个节点都有一个初始物品清单。如果节点在库存中有物品，则它只能沿着其附加的弧线之一发送物品。项目从弧的发送端转移到弧的接收端。然后，接收节点可以将项目沿着其附加的弧之一发送到另一个节点。成本流求解器搜索以最低成本发送尽可能多的项目的一组传输。

那么这和派人去车间有什么关系呢？好吧，你可以认为每个人都有一个令牌，代表他们参加一个研讨会的能力。他们将他们的令牌发送到他们将参加的研讨会，发送该令牌的成本（或惩罚）反映了该研讨会在该人的优先研讨会列表中的位置。一个人最想参加的研讨会非常便宜，而最不喜欢的研讨会非常昂贵。一旦研讨会从与会者那里获得令牌，它就会将其令牌发送到汇节点。研讨会和汇聚节点之间的弧线没有成本，但它确实有一个容量，表示可以参加该研讨会的最大人数。优化将尝试以最低的成本将所有令牌发送到汇聚节点。每个代币到达水槽的唯一方法是每个人都去一个车间，并且每个车间去的人数不超过车间的容量。求解器找到了一种以最低成本做到这一点的方法。

这是显示布局的图表：

每个人一个节点，每个车间一个节点，一个sink节点。方括号中的数字显示节点的起始库存。括号中的数字表示电弧的容量。在此示例中，每个研讨会可参加的最大人数分别为 3、2 和 4。没有显示起始库存的节点的起始库存为 0，没有显示容量的弧的容量为 1。

这可以使用 Google 的开源 cost flow solver. I've done just that, and wrapped it into a program that you can download from gitlab 来实现。它的编写方式使您只需替换一点 C# 代码即可解决您的特定问题。只需将下面显示的车间和人员信息替换为您自己的数据即可。

    // 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" } },
    };

排名优化

Ranking optimization

algorithm

optimization

ranking