Optimizing product assembly / disassembly

Question

I have a store that contains items. Each item is either a component (which is atomal) or a product which consists of various components (but never of 2 or more of the same components).

Now, when I want to get a product out of the store, there are various scenarios:

• The store contains the necessary number of the product.
• The store contains components of which I can assemble the product.
• The store contains products that share components with the required product. I can disassemble those and assemble the required item.
• Any combination of the above.

Below you can see my code so far (getAssemblyPath). It does find a way to assemble the required item if it is possible, but it does not optimize the assembly path.

I want to optimize the path in two ways:

• First, choose the path which takes the least number of assembly/disassembly actions.
• Second, if there are various such paths, choose the path which leave the least amount of disassembled components in the store.

Now, here I am at a complete loss of how to get this optimization done (I am not even sure if this is a question for SO or for Maths).

How can I alter getAssemblyPath so that it meets my optimization requirements?

My code so far:

#! /usr/bin/python

class Component:
    def __init__ (self, name): self.__name = name

    def __repr__ (self): return 'Component {}'.format (self.__name)

class Product:
    def __init__ (self, name, components):
        self.__name = name
        self.__components = components

    @property
    def components (self): return self.__components

    def __repr__ (self): return 'Product {}'.format (self.__name)

class Store:
    def __init__ (self): self.__items = {}

    def __iadd__ (self, item):
        item, count = item
        if not item in self.__items: self.__items [item] = 0
        self.__items [item] += count
        return self

    @property
    def items (self): return (item for item in self.__items.items () )

    @property
    def products (self): return ( (item, count) for item, count in self.__items.items () if isinstance (item, Product) )

    @property
    def components (self): return ( (item, count) for item, count in self.__items.items () if isinstance (item, Component) )

    def getAssemblyPath (self, product, count):
        if product in self.__items:
            take = min (count, self.__items [product] )
            print ('Take {} of {}'.format (take, product) )
            count -= take
            if not count: return
        components = dict ( (comp, count) for comp in product.components)
        for comp, count in self.components:
            if comp not in components: continue
            take = min (count, components [comp] )
            print ('Take {} of {}'.format (take, comp) )
            components [comp] -= take
            if not components [comp]: del components [comp]
            if not components: return
        for prod, count in self.products:
            if prod == product: continue
            shared = set (prod.components) & set (components.keys () )
            dis = min (max (components [comp] for comp in shared), count)
            print ('Disassemble {} of {}.'.format (dis, prod) )
            for comp in shared:
                print ('Take {} of {}.'.format (dis, comp) )
                components [comp] -= take
                if not components [comp]: del components [comp]
                if not components: return
        print ('Missing components:')
        for comp, count in components.items ():
            print ('{} of {}.'.format (count, comp) )

c1 = Component ('alpha')
c2 = Component ('bravo')
c3 = Component ('charlie')
c4 = Component ('delta')

p1 = Product ('A', [c1, c2] )
p2 = Product ('B', [c1, c2, c3] )
p3 = Product ('C', [c1, c3, c4] )

store = Store ()
store += (c2, 100)
store += (c4, 100)
store += (p1, 100)
store += (p2, 100)
store += (p3, 10)
store.getAssemblyPath (p3, 20)

This outputs:

Take 10 of Product C
Take 10 of Component delta
Disassemble 10 of Product A.
Take 10 of Component alpha.
Disassemble 10 of Product B.
Take 10 of Component charlie.

Which works, but it does unnecessarily disassemble product A, as product B contains both of the required components alpha and charlie.

--

EDIT:

Answering the very sensible questions of Blckknght:

When you say you want "the least number of assembly/disassembly actions", do you mean the smallest number of items, or the smallest number of different products?

An "asm/disasm action" is the action of assembling or disassembling one product, no matter how many components are involved. I am looking for least number of touched items, no matter whether they be distinct or not.

That is, is is better to dissassemble 20 of Product A than to dissassemble 10 of Product A and an additional 5 of Product B?

The latter is closer to optimum.

Further, you say you want to avoid leaving many components behind, but in your current code all disassembled components that are not used by the requested Product are lost. Is that deliberate (that is, do you want to be throwing away the other components), or is it a bug?

The method getAssemblyPath only determines the path of how to get the items. It does not touch the actual store. At no moment it assigns to self.__items. Think of it as a function that issues an order to the store keep of what he must do in the (inmediate) future, in order to get the required amount of the required item out of his store.

--

EDIT 2:

The first obvious (or at least obvious to me) way to tackle this issue, is to search first those products, that share the maximum amount of components with the required product, as you get more required components out of each disassembly. But unfortunately this doesn't necessary yield the optimum path. Take for instance:

Product A consisting of components α, β, γ, δ, ε and ζ.

Product B consisting of components α, β, η, δ, ε and θ.

Product C consisting of components α, β, γ, ι, κ and λ.

Product D consisting of components μ, ν, ξ, δ, ε and ζ.

We have in store 0 of A, 100 of B, 100 of C and 100 of D. We require 10 of A. Now if we look first for the products that shares most components with A, we will find B. We disassemble 10 of B getting 10 each of α, β, δ and ε. But then we need to disassemble 10 of C (to get γ) and 10 of D (to get ζ). These would be 40 actions (30 disassembling and 10 assembling). But the optimum way would be to disassemble 10 of C and 10 of D (30 actions, 20 disassembling and 10 assembling).

--

EDIT 3:

You don't need to post python code to win the bounty. Just explain the algorithm to me and show that it does indeed yield the optimum path, or one of the optima if several exist.

Answer 1

Here is how I would solve this problem. I wanted to write code for this but I don't think I have time.

You can find an optimal solution recursively. Make a data structure that represents the state of the parts store and the current request. Now, for each part you need, make a series of recursive calls that try the various ways to fill the order. The key is that by trying a way to fill the order, you are getting part of the work done, so the recursive call is now a slightly simpler version of the same problem.

Here's a specific example, based on your example. We need to fill orders for product 3 (p3) which is made of components c1, c3, and c4. Our order is for 20 of p3, and we have 10 p3 in stock so we trivially fill the order for the first 10 of p3. Now our order is for 10 of p3, but we can look at it as an order for 10 of c1, 10 of c3, and 10 of c4. For the first recursive call we disassemble a p1, and fill an order for a single c1 and place an extra c2 in the store; so this recursive call is for 9 of c1, 10 of c3, and 10 of c4, with an updated availability in the store. For the second recursive call we disassemble a p2, and fill an order for a c1 and a c4, and put an extra c2 into the store; so this recursive call is for 9 of c1, 10 of c3, and 9 of c4, with an updated availability in the store.

Since each call reduces the problem, the recursive series of calls will terminate. The recursive calls should return a cost metric, which either signals that the call failed to find a solution or else signals how much the found solution cost; the function chooses the best solution by choosing the solution with the lowest cost.

I'm not sure, but you might be able to speed this up by memoizing the calls. Python has a really nifty builtin new in the 3.x series, functools.lru_cache(); since you tagged your question as "Python 3.2" this is available to you.

What is memoization and how can I use it in Python?

The memoization works by recognizing that the function has already been called with the same arguments, and just returning the same solution as before. So it is a cache mapping arguments to answers. If the arguments include non-essential data (like how many of component c2 are in the store) then the memoization is less likely to work. But if we imagine we have products p1 and p9, and p9 contains components c1 and c9, then for our purposes disassembling one of p1 or one of p9 should be equivalent: they have the same disassembly cost, and they both produce a component we need (c1) and one we don't need (c2 or c9). So if we get the recursive call arguments right, the memoization could just return an instant answer when we get around to trying p9, and it could save a lot of time.

Hmm, now that I think about it, we probably can't use functools.lru_cache() but we can just memoize on our own. We can make a cache of solutions: a dictionary mapping tuples to values, and build tuples that just have the arguments we want cached. Then in our function, the first thing we do is check the cache of solutions, and if this call is equivalent to a cached solution, just return it.

EDIT: Here's the code I have written so far. I haven't finished debugging it so it probably doesn't produce the correct answer yet (I'm not certain because it takes a long time and I haven't let it finish running). This version is passing in dictionaries, which won't work well with my ideas about memoizing, but I wanted to get a simple version working and then worry about speeding it up.

Also, this code takes apart products and adds them to the store as components, so the final solution will first say something like "Take apart 10 product A" and then it will say "Take 20 component alpha" or whatever. In other words, the component count could be considered high since it doesn't distinguish between components that were already in the store and components that were put there by disassembling products.

I'm out of time for now and won't work on it for a while, sorry.

#!/usr/bin/python3

class Component:
    def __init__ (self, name): self.__name = name

    #def __repr__ (self): return 'Component {}'.format (self.__name)
    def __repr__ (self): return 'C_{}'.format (self.__name)

class Product:
    def __init__ (self, name, components):
        self.__name = name
        self.__components = components

    @property
    def components (self): return self.__components

    #def __repr__ (self): return 'Product {}'.format (self.__name)
    def __repr__ (self): return 'P_{}'.format (self.__name)

class Store:
    def __init__ (self): self.__items = {}

    def __iadd__ (self, item):
        item, count = item
        if not item in self.__items: self.__items [item] = 0
        self.__items [item] += count
        return self

    @property
    def items (self): return (item for item in self.__items.items () )

    @property
    def products (self): return ( (item, count) for item, count in self.__items.items () if isinstance (item, Product) )

    @property
    def components (self): return ( (item, count) for item, count in self.__items.items () if isinstance (item, Component) )

    def get_assembly_path (self, product, count):
        store = self.__items.copy()
        if product in store:
            take = min (count, store [product] )
            s_trivial = ('Take {} of {}'.format (take, product) )
            count -= take
            if not count:
                print(s_trivial)
                return
            dict_decr(store, product, take)
            product not in store

        order = {item:count for item in product.components}
        cost, solution = solver(order, store)
        if cost is None:
            print("No solution.")
            return

        print("Solution:")
        print(s_trivial)
        for item, count in solution.items():
            if isinstance(item, Component):
                print ('Take {} of {}'.format (count, item) )
            else:
                assert isinstance(item, Product)
                print ('Disassemble {} of {}'.format (count, item) )

    def getAssemblyPath (self, product, count):
        if product in self.__items:
            take = min (count, self.__items [product] )
            print ('Take {} of {}'.format (take, product) )
            count -= take
            if not count: return
        components = dict ( (comp, count) for comp in product.components)
        for comp, count in self.components:
            if comp not in components: continue
            take = min (count, components [comp] )
            print ('Take {} of {}'.format (take, comp) )
            components [comp] -= take
            if not components [comp]: del components [comp]
            if not components: return
        for prod, count in self.products:
            if prod == product: continue
            shared = set (prod.components) & set (components.keys () )
            dis = min (max (components [comp] for comp in shared), count)
            print ('Disassemble {} of {}.'.format (dis, prod) )
            for comp in shared:
                print ('Take {} of {}.'.format (dis, comp) )
                components [comp] -= take
                if not components [comp]: del components [comp]
                if not components: return
        print ('Missing components:')
        for comp, count in components.items ():
            print ('{} of {}.'.format (count, comp) )

def str_d(d):
    lst = list(d.items())
    lst.sort(key=str)
    return "{" + ", ".join("{}:{}".format(k, v) for (k, v) in lst) + "}"

def dict_incr(d, key, n):
    if key not in d:
        d[key] = n
    else:
        d[key] += n

def dict_decr(d, key, n):
    assert d[key] >= n
    d[key] -= n
    if d[key] == 0:
        del(d[key])

def solver(order, store):
    """
    order is a dict mapping component:count
    store is a dict mapping item:count

    returns a tuple: (cost, solution)
        cost is a cost metric estimating the expense of the solution
        solution is a dict that maps item:count (how to fill the order)

    """
    print("DEBUG: solver: {} {}".format(str_d(order), str_d(store)))
    if not order:
        solution = {}
        cost = 0
        return (cost, solution)

    solutions = []
    for item in store:
        if not isinstance(item, Component):
            continue
        print("...considering: {}".format(item))
        if not item in order:
            continue
        else:
            o = order.copy()
            s = store.copy()
            dict_decr(o, item, 1)
            dict_decr(s, item, 1)
            if not o:
                # we have found a solution!  Return it
                solution = {}
                solution[item] = 1
                cost = 1
                print("BASIS: solver: {} {} / {} {}".format(str_d(order), str_d(store), cost, str_d(solution)))
                return (cost, solution)
            else:
                cost, solution = solver(o, s)
                if cost is None:
                    continue  # this was a dead end
                dict_incr(solution, item, 1)
                cost += 1
                solutions.append((cost, solution))

    for item in store:
        if not isinstance(item, Product):
            continue
        print("...Product components: {} {}".format(item, item.components))
        assert isinstance(item, Product)
        if any(c in order for c in item.components):
            print("...disassembling: {}".format(item))
            o = order.copy()
            s = store.copy()
            dict_decr(s, item, 1)
            for c in item.components:
                dict_incr(s, c, 1)
            cost, solution = solver(o, s)
            if cost is None:
                continue  # this was a dead end
            cost += 1 # cost of disassembly
            solutions.append((cost, solution))
        else:
            print("DEBUG: ignoring {}".format(item))

    if not solutions:
        print("DEBUG: *dead end*")
        return (None, None)
    print("DEBUG: finding min of: {}".format(solutions))
    return min(solutions)



c1 = Component ('alpha')
c2 = Component ('bravo')
c3 = Component ('charlie')
c4 = Component ('delta')

p1 = Product ('A', [c1, c2] )
p2 = Product ('B', [c1, c2, c3] )
p3 = Product ('C', [c1, c3, c4] )

store = Store ()
store += (c2, 100)
store += (c4, 100)
store += (p1, 100)
store += (p2, 100)
store += (p3, 10)
#store.getAssemblyPath (p3, 20)
store.get_assembly_path(p3, 20)

Answer 2

1. Optimal path for N products <=> optimal path for single product.

Indeed, if we need to optimally assemble N of product X, after we optimally (using current stock) assemble one product, question becomes to optimally assemble (N-1) of product X using remaining stock.

=> Therefore, it is sufficient to provide algorithm of optimally assembling ONE product X at a time.

1. Assume we need components x1,..xn for the product (here we only include components not available as components in stock)

For each component xk, find all products that have this component. We will get a list of products for each component - products A1(1),..,A1(i1) have component x1, products A(1),.., A(i2) have component x2, and so forth (some products can be contained in several lists A1,A2,..,An lists).

If any of the lists is empty - there is no solution.

We need minimal set of products, such that a product from that set is contained in each of the lists. The simplest, but not computationally efficient solution is by brute force - try all sets and pick minimal:

• Take union of A1,..,An - call it A (include only unique products in the union).

a. Take single product from A, if it is contained in all A1,..,An - we need only one disassembly (this product). b. Try all combinations of two products from A, if any combination (a1,a2) satisfies condition that either a1 or a2 is contained in each of the lists A1,..,An - it is a solution.

...

for sure, there is a solution at depth n - one component from each of the lists A1,..,An. If we found no solution prior, this is the best solution.

Now, we only need to think about better strategy then brute force check, which I think is possible - I need to think about it, but this brute force approach for sure finds strictly optimal solution.

---

EDIT:

More accurate solution is to sort lists by length. Then when checking set of K products for being solution - only all possible combinations of 1 item from each list from first K lists need to be checked, if no solution there - there is no minimal set of depth K that solves the problem. That type of check will be also computationally no that bad - perhaps it can work????