Python raw material inventory optimizer

Question

I want to build a function that can look at the raw material on hand information I provide, then come up with combinations of inputs to achieve a desired number of finished products.

on_hand_inventory = {
    60: 370,
    66: 180,
    70: 752,
    74: 97,
    76: 5,
    77: 11,
    80: 40
}

The keys of the on_hand_inventory dictionary are the product's length in feet, and the values is the number of units on-hand.

I want to make finished products that are 1600 feet long, and I want to make 60 finished products. If this isn't possible, I want to know the combinations to use per finished product to get the most out of my inventory.

This is the code I have so far:

from itertools import combinations_with_replacement
from collections import Counter

on_hand_inventory = {
    60: 370,
    66: 180,
    70: 752,
    74: 97,
    76: 5,
    77: 11,
    80: 40
}

min_length = min([k for k,v in on_hand_inventory.items()])

target_length = 1600
num_finished_products_need = 60
product_lengths = sorted(on_hand_inventory.keys(), reverse=True)
max_pieces = 1600//min_length

# Step 1: Generate valid combinations
def find_combinations(product_lengths, target_length, max_pieces):
    valid_combos = []
    for num_pieces in range(max_pieces + 1):
        for combo in combinations_with_replacement(product_lengths, num_pieces):
            if sum(combo) == target_length:
                valid_combos.append(Counter(combo))
    return valid_combos

valid_combos = find_combinations(product_lengths, target_length, max_pieces)

# Step 3: Select 60 combinations without exceeding inventory
import random

def select_combinations(valid_combos, on_hand_inventory, num_finished_products_need, max_attempts=10000):
    best_selected = []
    best_used_inventory = Counter()

    for attempt in range(max_attempts):
        random.shuffle(valid_combos)
        selected_combos = []
        used_inventory = Counter()

        for combo in valid_combos:
            temp_inventory = used_inventory + combo
            if all(temp_inventory[length] <= on_hand_inventory[length] for length in on_hand_inventory):
                selected_combos.append(combo)
                used_inventory += combo
                if len(selected_combos) == num_finished_products_need:
                    return selected_combos, used_inventory  # full success

        # Save the best partial result
        if len(selected_combos) > len(best_selected):
            best_selected = selected_combos
            best_used_inventory = used_inventory

    return best_selected, best_used_inventory  # best attempt

selected_combos, inventory_used = select_combinations(valid_combos,on_hand_inventory,num_finished_products_need,max_attempts=1000)

# Step 4: Format the output
for i, combo in enumerate(selected_combos, 1):
    parts = [f"{count} pieces of {length}'" for length, count in sorted(combo.items())]
    print(f"String {i}: " + ", ".join(parts))

# Step 5: Print remaining quantities by length
if inventory_used:
    print("\nRemaining quantities by length:")
    for length in sorted(on_hand_inventory):
        remaining = on_hand_inventory[length] - inventory_used.get(length, 0)
        print(f"{length}': {remaining} pieces remaining")

if inventory_used:
    print("\nUsed quantities by length:")
    for length in sorted(inventory_used):
        print(f"{length}': {inventory_used[length]} pieces remaining")

This code works somewhat; however, it stops before using obvious combinations. For example, the code consistently returns a similar version of the following:

38 finished products made

Remaining quantities by length:
60': 65 pieces remaining
66': 13 pieces remaining
70': 467 pieces remaining
74': 0 pieces remaining
76': 0 pieces remaining
77': 1 pieces remaining
80': 0 pieces remaining

As you can see there is plenty of 60' and 70' product left to produce more finished products. Combining 1x 60' and 22x 70' would make 22 more finished products than the function returned.

Any advice is welcome!

Here is the full output of the Python code:

Finished Product #1: 1 pieces of 66', 12 pieces of 70', 5 pieces of 76', 2 pieces of 77', 2 pieces of 80'
Finished Product #2: 1 pieces of 60', 6 pieces of 66', 13 pieces of 70', 1 pieces of 74', 2 pieces of 80'
Finished Product #3: 2 pieces of 60', 9 pieces of 66', 2 pieces of 70', 9 pieces of 74', 1 pieces of 80'
Finished Product #4: 5 pieces of 70', 2 pieces of 74', 6 pieces of 77', 8 pieces of 80'
Finished Product #5: 2 pieces of 60', 6 pieces of 66', 3 pieces of 70', 2 pieces of 77', 9 pieces of 80'
Finished Product #6: 11 pieces of 60', 2 pieces of 66', 3 pieces of 70', 7 pieces of 74', 1 pieces of 80'
Finished Product #7: 15 pieces of 60', 1 pieces of 66', 8 pieces of 70', 1 pieces of 74'
Finished Product #8: 5 pieces of 60', 4 pieces of 66', 3 pieces of 70', 9 pieces of 74', 2 pieces of 80'
Finished Product #9: 2 pieces of 60', 1 pieces of 66', 4 pieces of 70', 11 pieces of 74', 4 pieces of 80'
Finished Product #10: 3 pieces of 60', 6 pieces of 66', 9 pieces of 70', 1 pieces of 74', 4 pieces of 80'
Finished Product #11: 5 pieces of 60', 14 pieces of 70', 4 pieces of 80'
Finished Product #12: 17 pieces of 60', 1 pieces of 66', 4 pieces of 70', 1 pieces of 74', 2 pieces of 80'
Finished Product #13: 2 pieces of 60', 3 pieces of 66', 14 pieces of 70', 3 pieces of 74', 1 pieces of 80'
Finished Product #14: 15 pieces of 60', 2 pieces of 66', 6 pieces of 70', 2 pieces of 74'
Finished Product #15: 6 pieces of 60', 8 pieces of 66', 7 pieces of 70', 3 pieces of 74'
Finished Product #16: 3 pieces of 60', 15 pieces of 70', 5 pieces of 74'
Finished Product #17: 22 pieces of 60', 2 pieces of 66', 2 pieces of 74'
Finished Product #18: 4 pieces of 60', 14 pieces of 66', 2 pieces of 70', 4 pieces of 74'
Finished Product #19: 8 pieces of 60', 2 pieces of 66', 12 pieces of 70', 2 pieces of 74'
Finished Product #20: 8 pieces of 60', 16 pieces of 70'
Finished Product #21: 11 pieces of 60', 10 pieces of 66', 4 pieces of 70'
Finished Product #22: 13 pieces of 60', 6 pieces of 66', 5 pieces of 70', 1 pieces of 74'
Finished Product #23: 22 pieces of 60', 1 pieces of 66', 2 pieces of 70', 1 pieces of 74'
Finished Product #24: 10 pieces of 60', 9 pieces of 70', 5 pieces of 74'
Finished Product #25: 8 pieces of 60', 1 pieces of 66', 14 pieces of 70', 1 pieces of 74'
Finished Product #26: 8 pieces of 60', 3 pieces of 66', 10 pieces of 70', 3 pieces of 74'
Finished Product #27: 5 pieces of 60', 3 pieces of 66', 2 pieces of 70', 13 pieces of 74'
Finished Product #28: 1 pieces of 60', 22 pieces of 70'
Finished Product #29: 5 pieces of 60', 8 pieces of 70', 10 pieces of 74'
Finished Product #30: 13 pieces of 60', 5 pieces of 66', 7 pieces of 70'
Finished Product #31: 20 pieces of 60', 5 pieces of 66', 1 pieces of 70'
Finished Product #32: 20 pieces of 66', 4 pieces of 70'
Finished Product #33: 6 pieces of 60', 5 pieces of 66', 13 pieces of 70'
Finished Product #34: 2 pieces of 60', 15 pieces of 66', 7 pieces of 70'
Finished Product #35: 15 pieces of 60', 10 pieces of 70'
Finished Product #36: 9 pieces of 60', 15 pieces of 66', 1 pieces of 70'
Finished Product #37: 4 pieces of 60', 10 pieces of 66', 10 pieces of 70'
Finished Product #38: 22 pieces of 60', 4 pieces of 70'

Remaining quantities by length:
60': 65 pieces remaining
66': 13 pieces remaining
70': 467 pieces remaining
74': 0 pieces remaining
76': 0 pieces remaining
77': 1 pieces remaining
80': 0 pieces remaining

It sounds like you're looking for algorithmic ideas for this problem. I thought it might be helpful to know the name of the problem. This is a multiple subset sum problem (the max-sum variant). This may help you look up published heuristics for this NP-hard problem. — josliber
– josliber, Commented May 21 at 17:05
Your solution uses random.shuffle and then greedily picks combinations until either 1.) It gets 60 combinations (success) or 2.) It can't fit more combos due to inventory constraints. Your algorithm can greedily grab parts that it should leave for later combos, and end up with 1600+ parts used before it has searched enough of the possible solutions, for instance with backtracking. You should look at the link @josliber suggested and rethink your algorithm. — Grismar
– Grismar, Commented May 22 at 1:27
I want to make 60 finished products. If this isn't possible, I want to know the combinations to use per finished product to get the most out of my inventory - So basically maximize the number of finished products, disregarding 60. ILP can do this; it's taking me a while to write a demonstration. — Reinderien
– Reinderien, Commented May 23 at 12:26

AirSquid · Accepted Answer · 2025-05-23 15:16:31Z

As mentioned in the comments, this is approachable via a ILP (Integer Linear Program). The below produces 61 products, the optimal solution with little waste. Likely because this is a contrived set of data.

This implementation uses the highs solver and the pyomo linear programming framework

This isn't necessarily a good "generalizable" approach to these problems which can be a bit more complex and use other ILP techniques similar to cutting stock problems, but it works in this case and solves rather quickly.

Code:

import pyomo.environ as pyo

### DATA ###

on_hand_inventory = {60: 370, 66: 180, 70: 752, 74: 97, 76: 5, 77: 11, 80: 40}

inventory = {}
lengths = {}
for k, v in on_hand_inventory.items():
    name = f"stock-{k}"
    inventory[name] = v
    lengths[name] = k

### MODEL ###
m = pyo.ConcreteModel()

reasonable_upper_production_limit = 100

### SETS ###
m.I = pyo.Set(initialize=list(inventory.keys()), doc="Inventory")
m.P = pyo.Set(initialize=list(range(reasonable_upper_production_limit)), doc="Pieces")

### VARS ###
m.make = pyo.Var(
    m.I, m.P, domain=pyo.NonNegativeIntegers
)  # use this count of inventory item i to build piece p
m.built = pyo.Var(m.P, domain=pyo.Binary)  # indicator if piece p is "made"

### PARAMs ###
m.length = pyo.Param(m.I, initialize=lengths, doc="length of piece")
m.inventory = pyo.Param(m.I, initialize=inventory, doc="inventory on hand")


### OBJ ###
m.obj = pyo.Objective(expr=-sum(m.built[p] for p in m.P))


### CONSTRAINTS ###
@m.Constraint(m.P)
def correct_length(m, p):
    return sum(m.make[i, p] * m.length[i] for i in m.I) == m.built[p] * 1600


@m.Constraint(m.I)
def inventory_cap(m, i):
    return sum(m.make[i, p] for p in m.P) <= m.inventory[i]

### CHECK IT ##
m.pprint()

### SOLVE ###
opt = pyo.SolverFactory("highs")
res = opt.solve(m, tee=True)

### OUTPUT ###
if pyo.check_optimal_termination(res):
    # sum up the made variable...
    print(f"made: {sum((1 for p in m.P if pyo.value(m.built[p]) > 0.1))}")
    for i in m.I:
        consumed = sum(pyo.value(m.make[i, p]) for p in m.P)
        print(f"consumed {consumed} of {m.inventory[i]} for stock item {i}")


else:
    print("non-optimal solution reached:  see log output...")

Output (truncated):

Solving report
  Status            Optimal
  Primal bound      -61
  Dual bound        -61
  Gap               0% (tolerance: 0.01%)
  P-D integral      0.0632989867899
  Solution status   feasible
                    -61 (objective)
                    0 (bound viol.)
                    0 (int. viol.)
                    0 (row viol.)
  Timing            1.43 (total)
                    0.00 (presolve)
                    0.00 (solve)
                    0.00 (postsolve)
  Max sub-MIP depth 5
  Nodes             4563
  Repair LPs        0 (0 feasible; 0 iterations)
  LP iterations     13027 (total)
                    609 (strong br.)
                    1109 (separation)
                    3996 (heuristics)
made: 61
consumed 368.0 of 370 for stock item stock-60
consumed 172.0 of 180 for stock item stock-66
consumed 752.0 of 752 for stock item stock-70
consumed 97.0 of 97 for stock item stock-74
consumed 5.0 of 5 for stock item stock-76
consumed 10.0 of 11 for stock item stock-77
consumed 40.0 of 40 for stock item stock-80

I get the following error when running the code: "pyomo.common.errors.ApplicationError: Solver "highs" is not available. The returned status is: NotFound." I didn't change anything about the code in your solution, what do you think could be going on?
Yes. You need to install the highspy package, which is the solver that is being called. pip install highspy. Alternatively, there are other solvers to use, but highs works well on this instance. pypi.org/project/highspy

Collectives™ on Stack Overflow

Python raw material inventory optimizer

1 Answer 1

Code:

Output (truncated):

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Code:

Output (truncated):

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related