Finding the unique combination of values for each target using multiple knapsack algorithm

Question

we have 2 inputs one is targets and other is values. we have to find the unique combination of the values of each target and once used value cannot be used for the combination of another target which is working fine in the code.

from ortools.sat.python import cp_model

receivable_target = [97, 104, 276, 121] #  case 1
#receivable_target = [97, 104, 276, 121, 220000] #  case 2 - issue which needs to solved 
receivable_values = [97, 52, 52, 276, 121]

TDSReceivableVarianceUpperLimit = 10
TDSReceivableVarianceLowerLimit = 10

data = {}
data["weights"] = receivable_values
data["values"] = [1] * len(data["weights"])
assert len(data["weights"]) == len(data["values"])
data["num_items"] = len(data["weights"])
data["all_items"] = range(data["num_items"])

data["bin_capacities"] = receivable_target
data["num_bins"] = len(data["bin_capacities"])
data["all_bins"] = range(data["num_bins"])

solver = cp_model.CpSolver()
model = cp_model.CpModel()
x = {}
for i in data["all_items"]:
    for w in data["all_bins"]:
        x[i, w] = model.NewBoolVar(f'x_{i}_{w}')

# Constraints.
for i in data["all_items"]:
    model.Add(sum(x[i, w] for w in data["all_bins"]) <= 1)

# Add constraints to match bin capacities
for b in data["all_bins"]:
    model.Add(sum(x[i, b] * receivable_values[i] for i in data["all_items"]) == data["bin_capacities"][b]) # perfect match 
    # model.Add(sum(x[i, b] * receivable_values[i] for i in data["all_items"]) <= data["bin_capacities"][b] + TDSReceivableVarianceUpperLimit) # variance
    # model.Add(sum(x[i, b] * receivable_values[i] for i in data["all_items"]) >= data["bin_capacities"][b] - TDSReceivableVarianceLowerLimit) # variance

# Objective: Minimize the sum of indices of selected items
objective = sum(x[i, w] * i for i in data["all_items"] for w in data["all_bins"])
model.Minimize(objective)

selected_transactions = {b: [] for b in data["all_bins"]}

# Solve the model
status = solver.Solve(model)
if status == cp_model.OPTIMAL:
    for b in data["all_bins"]:
        for i in data["all_items"]:
            if solver.Value(x[i, b]) > 0:
                selected_transactions[b].append((i, receivable_values[i]))



# Print the results
if status == cp_model.OPTIMAL:
    for k, v in selected_transactions.items():
        indices, values = zip(*v) if v else ([], [])
        print(f'Bin {k} target: {receivable_target[k]}, selected indices: {indices}, selected items: {values}, total: {sum(values)}')
else:
    print("The problem does not have an optimal solution.")
# for i in data["all_items"]:
#     for b in data["all_bins"]:
#         value = solver.Value(x[i, b])
#         if value > 0:
#             item_value = receivable_values[i] 
#             print(f'x[{i},{b}] = {value > 0}, selected item value: {item_value}')

case 1 : already fetching output: Bin 0 target: 97, selected indices: (0,), selected items: (97,), total: 97 Bin 1 target: 104, selected indices: (1, 2), selected items: (52, 52), total: 104 Bin 2 target: 276, selected indices: (3,), selected items: (276,), total: 276 Bin 3 target: 121, selected indices: (4,), selected items: (121,), total: 121

case 2 : current output: The problem does not have an optimal solution. expected output: Bin 0 target: 97, selected indices: (0,), selected items: (97,), total: 97 Bin 1 target: 104, selected indices: (1, 2), selected items: (52, 52), total: 104 Bin 2 target: 276, selected indices: (3,), selected items: (276,), total: 276 Bin 3 target: 121, selected indices: (4,), selected items: (121,), total: 121 Bin 4 target: 220000, selected indices: (), selected items: (), total: 0

the code is behaving like. if there is a target which does not have any values to be matched. if is returning empty array and 0 for all the targets which i saw while debugging.

if this resolved, we have to check the matching along with variance condition.

# model.Add(sum(x[i, b] * receivable_values[i] for i in data["all_items"]) <= data["bin_capacities"][b] + TDSReceivableVarianceUpperLimit) # variance
# model.Add(sum(x[i, b] * receivable_values[i] for i in data["all_items"]) >= data["bin_capacities"][b] - TDSReceivableVarianceLowerLimit) # variance

this block of code is also giving Infeasible solution.

please help me to resolve the issue.

Thanks.

I have written code where it is giving correct results if and only if i have perfect match for all the targets in the values list but i have explained my issue in the question and I'm seeking help from the Google Ortools team or any expert who can help on ortools multiple knapsack problem.