Constrained optimization over a grid while maintaining proportions
Suppose I have a user/item grid like this:
item_1 item_2
user_1 v_11 v_12
user_2 v_21 v_22
user_3 v_31 v_32
Where each user/item pair has a value, as captured in the grid. The goal is to assign exactly one item to each user, so as to maximize the sum of the values.
But also, "prior" proportions must be maintained. For example, if in the past item_1 was assigned to 2 out of 3 users and item_2 was assigned to only 1 user, going forward we either have to have:
item_1 gets assigned to 2 out of 3 users (could be different users than in the past!), and item_2 gets assigned to the remaining user, OR
item_2 gets assigned to 2 out of 3 users, and item_1 gets assigned to the remaining user
Neither item may be assigned to every user. This is what is meant by "maintaining" proportions. How should I approach a problem like this analytically? What about programmatically in Python? Please let me know if I can clarify further. Assume we know all the values (the v's). Thank you.
Let me give this a try.
I assume we have the following data set with 10 items and 20 users:
---- 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
The problem is to find a new assignment of items to users x(i,j) with:
- each user receives exactly one item.
- the total number of each item is a permutation of the original number of each item. So if we have 3 items and the totals were 1,2,3 then we can have now 3,2,1 (or any other permutation of 1,2,3).
For this we define two binary variables:
x(i,j) = 1 if user j receives item i
0 otherwise
p(i,k) : a permuted identity matrix
We this we can develop the following Mixed Integer Programming (MIP) model:
This is a simple MIP model that can be solved with any MIP solver. The optimal solution looks like:
---- 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
The last vector sumitems is a permutation of the vector n of our data set.
We see the objective value of this optimal solution is 176.058 which is much better than the value of our initial (random) data set (97.192).
- Webscraping Roblox
- Remove the mandatory field label 'This field is required.' and fix the bug with 'clean_email'
- How to plot a Probability Density Function in Python?
- How large is a fresh install of Python?
- Appending new elements into an empty list
- Simple way to measure cell execution time in ipython notebook
- PyAudio working, but spits out error messages each time
- Reportlab show page number and page count IF there is more than one page in a document
- How to read SharePoint Online (Office365) Excel files into Python specifically pandas with Work or School Account?
- How to set a column which suffix name is based on a value in another column
- Debugging Python C++ extension from Visual Studio Code on Linux
- How can I get all users on Google admin_sdk?
- csv.Error: iterator should return strings, not bytes
- How to check if an object has an attribute?
- How to use selenium with proxy auth in headless mode?
- Is there a way to exit a pytest test and continue to the next one?
- Returning the lowest index for the first non whitespace character in a string in Python
- Formatting exceptions as Python does
- Prime factorization using list comprehension in Python
- Why does the power spectrum E(k) of my velocity field follow 𝑘 ^(−(n−1)) instead of 𝑘^(−n)?
- How to merge dataframes over multiple columns and split rows?
- How to create a Sympy IndexedBase using a custom subclass of Symbol?
- Removing dynamically an element from a list
- Returning boolean if set is empty
- Can variables be decorated?
- Fast(est) exponentiation of numpy 3D matrix
- Removing an element from a list based on a condition
- Printing elements of dictionary line by line
- Matplotlib does not display the hatch of a patch in a legend
- Python win32com - Class not registered error