Model is infeasible even though constraints are correct

Question

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:

• x_ij be a binary decision variable where x_ij = 1 if item i is assigned to category j, and x_ij = 0 otherwise.
• p_i be the price of item i.
• c_j be the price limit of category j.

The constraints are as follows:

1. Each item must be assigned to exactly one category.

2. 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.

Answer 1

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