I have the following problem I want to solve:
We have N items with a price and ID, and M categories, where each category has a total balance / limit on the sum of prices of items with that category. In the end, we want each item to be assigned to ONLY ONE category, and each category doesn't exceed its total balance / limit.
Let:
The constraints are as follows:
Each item must be assigned to exactly one category.
The total price sum of items assigned to each category must not exceed the category limit.
I have created the linear programming code using PuLP python module:
def assign_items_to_categories(items, categories, category_limits):
n = len(items)
m = len(categories)
model = pulp.LpProblem("Assign_Items_to_Categories")
# Define decision variables
x = pulp.LpVariable.dicts("x", ((i, j) for i in range(n) for j in range(m)), cat='Binary')
# Constraints
# 1st constraint
for i in range(n):
model += pulp.lpSum(x[(i, j)] for j in range(m)) == 1
# 2nd constraint
for j in range(m):
model += pulp.lpSum(items[i]["price"] * x[(i, j)] for i in range(n)) <= category_limits[categories[j]]
# Solve the problem
model.solve()
model.writeLP('model.lp')
# Extract the solution
assignment_result = {category: [] for category in categories}
for i in range(n):
for j in range(m):
if pulp.value(x[(i, j)]) == 1:
valid = True
assignment_result[categories[j]].append(items[i])
return assignment_result
items = [{
"id": "0892ADA75MH1-00",
"price": 0.0
},
{
"id": "3WR21137BHJ81",
"price": 2616023.02
},
{
"id": "3137344ABHEX1",
"price": 367419.34
},
{
"id": "2312312AAWW31-1",
"price": 676545.32
},
{
"id": "313243A8WTQV1",
"price": 228518.29
}]
categories = ['APPLE', 'META', 'TESLA', 'NETFLIX', 'GOOGLE']
cateogory_limit =
{
"APPLE": 2754707.42,
"META": 43002.21,
"TESLA": 240301.31,
"NETFLIX": 500432.54,
"GOOGLE": 3100233.41,
},
However, the result always indicated that the problem is infeasible. I believe that the constraint I coded reflected to the constraint that was mentioned in the instructions. Any suggestions to improve this code will be very helpful!
Edit: I have added some sample data for better reference.
One crude but fast objective minimizing difference between category allocations is to minimize the maximum category subtotal. For very few items it doesn't work very well; for many items it works fine:
import pandas as pd
import pulp
def assign_items_to_categories(
item_prices: pd.Series,
cat_limits: pd.Series,
):
model = pulp.LpProblem(name="Assign_Items_to_Categories", sense=pulp.LpMinimize)
assign = pd.DataFrame(
data=pulp.LpVariable.matrix(
name='assign', cat=pulp.LpBinary,
indices=(cat_limits.index, item_prices.index),
),
index=cat_limits.index,
columns=item_prices.index,
)
tmax = pulp.LpVariable(name='tmax', cat=pulp.LpContinuous)
# Each item must be assigned to exactly one category.
for item, row in assign.items():
model.addConstraint(
name=f'excl_{item}',
constraint=pulp.lpSum(row) == 1,
)
subtotals = assign @ item_prices
for cat, subtotal in subtotals.items():
# The total price sum of items assigned to each category must not exceed the category limit.
model.addConstraint(
name=f'limit_{cat}', constraint=subtotal <= cat_limits[cat])
model.addConstraint(
name=f'tmax_{cat}', constraint=subtotal <= tmax)
model.setObjective(tmax)
model.solve()
if model.status != pulp.LpStatusOptimal:
raise ValueError(model.status)
assign = assign.map(pulp.value)
subtotals = subtotals.apply(pulp.value)
return assign, subtotals
def main() -> None:
prices = pd.Series(
index=pd.Index(
name='item',
data=('0892ADA75MH1-00', '3WR21137BHJ81', '3137344ABHEX1',
'2312312AAWW31-1', '313243A8WTQV1'),
),
name='price',
data=(0.0, 2_616_023.02, 367_419.34, 676_545.32, 228_518.29),
)
cat_limits = pd.Series(
index=pd.Index(
name='category',
data=('APPLE', 'META', 'TESLA', 'NETFLIX', 'GOOGLE'),
),
data=(2_754_707.42, 43_002.21, 240_301.31, 500_432.54, 3_100_233.41),
)
assign, subtotals = assign_items_to_categories(item_prices=prices, cat_limits=cat_limits)
print(subtotals)
print(assign.T)
if __name__ == '__main__':
main()
Result - Optimal solution found
Objective value: 2616023.02000000
Enumerated nodes: 0
Total iterations: 0
Time (CPU seconds): 0.02
Time (Wallclock seconds): 0.02
Option for printingOptions changed from normal to all
Total time (CPU seconds): 0.02 (Wallclock seconds): 0.02
category
APPLE 676545.32
META 0.00
TESLA 228518.29
NETFLIX 367419.34
GOOGLE 2616023.02
dtype: float64
category APPLE META TESLA NETFLIX GOOGLE
item
0892ADA75MH1-00 0.0 0.0 1.0 0.0 0.0
3WR21137BHJ81 0.0 0.0 0.0 0.0 1.0
3137344ABHEX1 0.0 0.0 0.0 1.0 0.0
2312312AAWW31-1 1.0 0.0 0.0 0.0 0.0
313243A8WTQV1 0.0 0.0 1.0 0.0 0.0