在保持比例的同时对网格进行约束优化
Constrained optimization over a grid while maintaining proportions
假设我有一个这样的 user/item 网格：
item_1 item_2
user_1 v_11 v_12
user_2 v_21 v_22
user_3 v_31 v_32
其中每个 user/item 对都有一个值，如在网格中捕获的那样。目标是为每个用户分配恰好一个项，以最大化值的总和。
而且，"prior" 比例必须保持。例如，如果过去 item_1 被分配给 3 个用户中的 2 个，而 item_2 只被分配给 1 个用户，那么今后我们 或者 必须有:
item_1 被分配给 3 个用户中的 2 个（可能是与过去不同的用户！），item_2 被分配给其余用户，或者
item_2 被分配给 3 个用户中的 2 个，item_1 被分配给其余用户
这两个项目都不能分配给每个 用户。这就是"maintaining"比例的意思。我应该如何分析地处理这样的问题？在 Python 中以编程方式怎么样？如果我可以进一步澄清，请告诉我。假设我们知道所有的值（v）。谢谢。
让我试试这个。
我假设我们有以下包含 10 个项目和 20 个用户的数据集：
---- 23 SET i items
item1 , item2 , item3 , item4 , item5 , item6 , item7 , item8 , item9 , item10
---- 23 SET j users
user1 , user2 , user3 , user4 , user5 , user6 , user7 , user8 , user9 , user10, user11
user12, user13, user14, user15, user16, user17, user18, user19, user20
---- 23 PARAMETER x0 initial allocations
user1 user2 user3 user4 user5 user6 user7 user8 user9
item1 1
item2 1
item3 1 1
item4 1 1
item6 1
item9 1 1
+ user10 user11 user12 user13 user14 user15 user16 user17 user18
item2 1 1
item3 1
item6 1 1
item7 1
item8 1
item10 1 1
+ user19 user20
item5 1
item7 1
---- 23 PARAMETER n sum initial allocations
item1 1, item2 3, item3 3, item4 2, item5 1, item6 3, item7 2, item8 1, item9 2
item10 2
---- 23 PARAMETER v values
user1 user2 user3 user4 user5 user6 user7 user8 user9
item1 4.237 4.163 2.183 2.351 6.302 8.478 3.077 6.992 7.983
item2 4.720 2.059 3.828 1.419 4.047 2.639 6.812 6.047 7.930
item3 1.655 2.581 5.731 7.752 2.603 1.307 6.266 6.591 4.504
item4 2.818 1.046 3.427 5.499 2.362 2.568 3.976 3.852 3.899
item5 1.463 1.054 4.611 5.679 6.660 3.032 4.565 3.484 2.371
item6 1.915 4.455 3.917 2.729 2.011 6.369 5.603 1.406 8.048
item7 9.880 3.053 7.081 7.991 9.392 2.811 3.674 2.775 3.217
item8 8.612 6.514 9.784 1.242 2.687 1.784 5.864 2.142 7.606
item9 1.222 2.600 1.552 1.150 8.521 6.415 1.243 2.765 9.556
item10 9.395 4.139 1.075 9.540 6.147 4.003 9.854 7.898 1.991
+ user10 user11 user12 user13 user14 user15 user16 user17 user18
item1 3.733 1.994 5.521 2.442 8.852 3.386 3.572 6.346 7.504
item2 3.680 6.950 7.802 6.647 3.555 1.778 1.923 6.771 5.908
item3 4.228 3.187 3.218 2.175 9.401 4.419 8.051 3.700 2.129
item4 9.676 9.942 4.329 4.356 7.948 4.570 9.218 2.076 7.619
item5 9.427 4.804 2.212 4.475 4.372 3.416 9.535 2.700 3.678
item6 9.512 6.368 6.466 4.263 6.347 7.119 5.559 2.433 6.912
item7 6.818 7.615 1.769 2.353 4.908 2.682 7.234 7.867 2.393
item8 2.019 5.395 8.160 5.428 5.802 1.096 5.895 5.060 9.778
item9 4.020 6.348 3.333 6.766 2.397 5.140 4.540 8.249 5.869
item10 9.953 6.223 2.498 6.790 4.099 9.211 9.101 1.146 4.318
+ user19 user20
item1 6.654 5.174
item2 1.284 8.131
item3 7.740 1.623
item4 1.499 6.187
item5 1.671 4.612
item6 5.715 2.120
item7 4.504 7.259
item8 2.655 2.472
item9 4.516 6.020
item10 6.979 6.340
---- 23 PARAMETER z0 = 97.192 initial total value
问题是为用户 x(i,j) 找到新的项目分配：
- 每个用户只收到一件物品。
- 每个项目的总数是每个项目的原始数量的排列。因此，如果我们有 3 个项目并且总数为 1、2、3，那么我们现在可以有 3、2、1（或 1、2、3 的任何其他排列）。
为此我们定义了两个二进制变量：
x(i,j) = 1 if user j receives item i
0 otherwise
p(i,k) : a permuted identity matrix
我们可以开发以下混合整数规划 (MIP) 模型：
这是一个简单的 MIP 模型，可以使用任何 MIP 求解器求解。最佳解决方案如下：
---- 49 VARIABLE x.L
user1 user2 user3 user4 user5 user6 user7 user8 user9
item1 1 1
item7 1 1
item8 1 1
item9 1
item10 1 1
+ user10 user11 user12 user13 user14 user15 user16 user17 user18
item2 1
item3 1
item4 1
item5 1
item6 1
item8 1
item9 1 1
item10 1
+ user19 user20
item2 1
item3 1
---- 49 VARIABLE z.L = 176.058
---- 54 PARAMETER sumitems sum new allocations
item1 2, item2 2, item3 2, item4 1, item5 1, item6 1, item7 2, item8 3, item9 3
item10 3
最后一个向量 sumitems 是我们数据集的向量 n 的排列。
我们看到这个最优解的 objective 值为 176.058，比我们初始（随机）数据集的值 (97.192) 好很多。
假设我有一个这样的 user/item 网格：
item_1 item_2
user_1 v_11 v_12
user_2 v_21 v_22
user_3 v_31 v_32
其中每个 user/item 对都有一个值，如在网格中捕获的那样。目标是为每个用户分配恰好一个项，以最大化值的总和。
而且，"prior" 比例必须保持。例如，如果过去 item_1 被分配给 3 个用户中的 2 个，而 item_2 只被分配给 1 个用户，那么今后我们 或者 必须有:
item_1 被分配给 3 个用户中的 2 个（可能是与过去不同的用户！），item_2 被分配给其余用户，或者
item_2 被分配给 3 个用户中的 2 个，item_1 被分配给其余用户
这两个项目都不能分配给每个 用户。这就是"maintaining"比例的意思。我应该如何分析地处理这样的问题？在 Python 中以编程方式怎么样？如果我可以进一步澄清，请告诉我。假设我们知道所有的值（v）。谢谢。
让我试试这个。
我假设我们有以下包含 10 个项目和 20 个用户的数据集：
---- 23 SET i items
item1 , item2 , item3 , item4 , item5 , item6 , item7 , item8 , item9 , item10
---- 23 SET j users
user1 , user2 , user3 , user4 , user5 , user6 , user7 , user8 , user9 , user10, user11
user12, user13, user14, user15, user16, user17, user18, user19, user20
---- 23 PARAMETER x0 initial allocations
user1 user2 user3 user4 user5 user6 user7 user8 user9
item1 1
item2 1
item3 1 1
item4 1 1
item6 1
item9 1 1
+ user10 user11 user12 user13 user14 user15 user16 user17 user18
item2 1 1
item3 1
item6 1 1
item7 1
item8 1
item10 1 1
+ user19 user20
item5 1
item7 1
---- 23 PARAMETER n sum initial allocations
item1 1, item2 3, item3 3, item4 2, item5 1, item6 3, item7 2, item8 1, item9 2
item10 2
---- 23 PARAMETER v values
user1 user2 user3 user4 user5 user6 user7 user8 user9
item1 4.237 4.163 2.183 2.351 6.302 8.478 3.077 6.992 7.983
item2 4.720 2.059 3.828 1.419 4.047 2.639 6.812 6.047 7.930
item3 1.655 2.581 5.731 7.752 2.603 1.307 6.266 6.591 4.504
item4 2.818 1.046 3.427 5.499 2.362 2.568 3.976 3.852 3.899
item5 1.463 1.054 4.611 5.679 6.660 3.032 4.565 3.484 2.371
item6 1.915 4.455 3.917 2.729 2.011 6.369 5.603 1.406 8.048
item7 9.880 3.053 7.081 7.991 9.392 2.811 3.674 2.775 3.217
item8 8.612 6.514 9.784 1.242 2.687 1.784 5.864 2.142 7.606
item9 1.222 2.600 1.552 1.150 8.521 6.415 1.243 2.765 9.556
item10 9.395 4.139 1.075 9.540 6.147 4.003 9.854 7.898 1.991
+ user10 user11 user12 user13 user14 user15 user16 user17 user18
item1 3.733 1.994 5.521 2.442 8.852 3.386 3.572 6.346 7.504
item2 3.680 6.950 7.802 6.647 3.555 1.778 1.923 6.771 5.908
item3 4.228 3.187 3.218 2.175 9.401 4.419 8.051 3.700 2.129
item4 9.676 9.942 4.329 4.356 7.948 4.570 9.218 2.076 7.619
item5 9.427 4.804 2.212 4.475 4.372 3.416 9.535 2.700 3.678
item6 9.512 6.368 6.466 4.263 6.347 7.119 5.559 2.433 6.912
item7 6.818 7.615 1.769 2.353 4.908 2.682 7.234 7.867 2.393
item8 2.019 5.395 8.160 5.428 5.802 1.096 5.895 5.060 9.778
item9 4.020 6.348 3.333 6.766 2.397 5.140 4.540 8.249 5.869
item10 9.953 6.223 2.498 6.790 4.099 9.211 9.101 1.146 4.318
+ user19 user20
item1 6.654 5.174
item2 1.284 8.131
item3 7.740 1.623
item4 1.499 6.187
item5 1.671 4.612
item6 5.715 2.120
item7 4.504 7.259
item8 2.655 2.472
item9 4.516 6.020
item10 6.979 6.340
---- 23 PARAMETER z0 = 97.192 initial total value
问题是为用户 x(i,j) 找到新的项目分配：
- 每个用户只收到一件物品。
- 每个项目的总数是每个项目的原始数量的排列。因此，如果我们有 3 个项目并且总数为 1、2、3，那么我们现在可以有 3、2、1（或 1、2、3 的任何其他排列）。
为此我们定义了两个二进制变量：
x(i,j) = 1 if user j receives item i
0 otherwise
p(i,k) : a permuted identity matrix
我们可以开发以下混合整数规划 (MIP) 模型：
这是一个简单的 MIP 模型，可以使用任何 MIP 求解器求解。最佳解决方案如下：
---- 49 VARIABLE x.L
user1 user2 user3 user4 user5 user6 user7 user8 user9
item1 1 1
item7 1 1
item8 1 1
item9 1
item10 1 1
+ user10 user11 user12 user13 user14 user15 user16 user17 user18
item2 1
item3 1
item4 1
item5 1
item6 1
item8 1
item9 1 1
item10 1
+ user19 user20
item2 1
item3 1
---- 49 VARIABLE z.L = 176.058
---- 54 PARAMETER sumitems sum new allocations
item1 2, item2 2, item3 2, item4 1, item5 1, item6 1, item7 2, item8 3, item9 3
item10 3
最后一个向量 sumitems 是我们数据集的向量 n 的排列。
我们看到这个最优解的 objective 值为 176.058，比我们初始（随机）数据集的值 (97.192) 好很多。