Optimum product disassembly / assembly path

Question

I have a store Σ, which contains products (denoted by latin mayuscules) and components (denoted by greek minuscules). A product consists of a set of components (but not more than one of each distinct component). For instance:

A = {β, γ}, B = {α}, C = {α, β, γ}

A store contains both products and components:

Σ = {(10, A), (5, B), (20, β)}

(Meaning 10 items of A, 5 items of B and 20 items of β).

You can transform the store by disassembling a product, for instance by disassembling 2 items of C, {(10, C)} transforms into {(8, C), (2, α), (2, β), (2, γ)}.

You can transform the store by assembling a product, for instance by assembling 1 item of B, {(10, α), (10, β)} transforms into {(1, B), (9, α), (10, β)}.

Given an arbitrary store, and an amount n of a required product X, how can I determine the optimal sequence(s) of transformations needed, to obtain a store that contains (n, X)? A sequence is optimal if and only if there exists no other sequence which consists of less transformations.

I am not good at mathematical syntax, please do see my post about the same topic on SO.

EDIT

Dear Milcak

I tried your solution, but obviously I am doing something wrong. Let'say we have in store three products $A_1 = \{\alpha, \beta, \gamma\}$, $A_2 = \{\alpha, \gamma, \delta\}$ and $A_3 = \{\beta, \delta\}$. We need to extract one product $X = \{\alpha, \beta, \delta\}$. Now using your notation this would be: $$ X = (1, 1, 1) \\ A_1 = (1, 1, 0) \\ A_2 = (1, 0, 1) \\ A_3 = (0, 1, 1) $$

This gives the equation:

$$ \begin{pmatrix} 1 1 0 \\ 1 0 1 \\ 0 1 1 \end{pmatrix} \begin{pmatrix} z_1\\ z_2\\ z_3 \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} $$

Which I think is the same as:

$$z_1 + z_2 = 1 \\ z_1 + z_3 = 1 \\ z_2 + z_3 = 1 $$

Now the solution is (hopefully) $Z = ( \frac 1 2 , \frac 1 2 , \frac 1 2 )$.

You say:

then pick $y_i$'s so that they are non-negative integers, and that their sum is minimized, which is equivalent to finding the closest integral lattice point to $z$ such that $y_i \ge z_i$ and $y_i \ge 0$ for all $i$.

This yields $Y = (1, 1, 1)$, but doesn't this means I need one of each of the $A_i$? Wouldn't the solutions be $(1, 1, 0)$, $(1, 0, 1)$ and $(0, 1, 1)$?

I am sure I misunderstood some parts of your answer. Could you please expand your answer, undoing my brain knots? Thank you very much.

Answer 1

Here you are looking for an optimal solution for a system of linear inequalities.

First some simplifications:

• we may assume that we only need to assemble one final product $X$. If we needed $nX$, then we need $n$-times as much components as for $X$. But no matter how we get the components to assemble $nX$, we will have to spend $n$ transformations for the final assembly. Thus if we need $nX$, we may just assume that $X$ needs $n$ times more of each component. In other words, we only care to minimize the amount times we disassemble products.

• secondly, we need to only consider the components of $X$. Suppose we have $k_1$ components total, and $X$ consists of some $k \le k_1$ different components. Then we may write $X = ( x_1, \dots, x_k, 0, \dots, 0 )$ (with $k_1 - k$ $0$'s). Then if another product $A$ has components $(a_1, \dots, a_k, a_{k+1}, \dots, a_{k_1} )$, we need not consider what the $ a_{k+1}, \dots, a_{k_1}$ are.

So now, say we have products $A_1, ..., A_n$ where $A_i = (a^i_1, \dots, a^i_k)$. Then we are looking for non-negative integers $y_1, \dots, y_n$ such that $\sum_{i=1}^n y_i$ is minimized, and:

\begin{equation} \begin{pmatrix} a^1_1 & \dots & a^n_1 \\ \vdots& \ddots & \vdots \\ a^1_k & \dots & a^n_k \end{pmatrix} \begin{pmatrix} y_1\\ \vdots\\ y_n \end{pmatrix} \ge \begin{pmatrix} x_1\\ \vdots\\ x_k \end{pmatrix} \end{equation}

where "$\ge$" refers to the lexicographical ordering.

Since we assume that you can indeed build $X$ from the other products, we know that this will always have a solution (quite a few, actually).

Now, you can solve the above inequality as if it were an equality, for this however, you may need to extend the quantities of products to contain rational numbers. You get a solution $z= (z_1, \dots, z_n)$; then pick $y$ so that:

• $y_i$'s are non-negative integers
• $\sum y_i = \left\lceil \sum z_i \right\rceil$ (as $z$ is optimal, an integer solution may only be worse)
• $\sum |y_i - z_i|$ is minimized

EDIT

I have edited the end requirements for $y$. I apologize, for my previous error - I have misunderstood the relevance of "$z$". It is clear that this is the optimal solution (over the rationals). Hence $y$ must be close to it, however, not necessarily that $y_i \ge z_i$ for all $i$.

Since $z$ is optimal, any integral solution will require at least $\sum z_i$ transformations. For $y$ to be closest to $z$ we need $\sum |y_i - z_i|$ minimized.

We have $ \left\lceil \sum z_i \right\rceil = \left\lfloor \sum z_i \right\rfloor + l \le \left\lfloor \sum z_i \right\rfloor +n - 1$. Thus $y$ is of the form $(\lfloor z_1 \rfloor + \delta_1, \dots, \lfloor z_n \rfloor + \delta_n)$, where $l$ of the $\delta_i$'s are $1$ and the others $0$.

In your example $\lfloor z_i \rfloor = 0$ for all $i$. Then since $ \left\lceil \sum z_i \right\rceil = 2$, we have $y = (\delta_1, \delta_2, \delta_3)$, with one $\delta = 0$ and others $= 1$. That gives you your three answers, since each coordinate of $z$ is $1/2$.

---

I can try and prove this tomorrow, but for now you have at least a basic framework - $y = (\lfloor z_1 \rfloor + \delta_1, \dots, \lfloor z_n \rfloor + \delta_n)$ as defined above is clearly correct, and if the condition "$\sum |y_i - z_i|$ is minimized" may be flawed, the correct answer is now limited to $\binom {n}{l}$ possibilities: i.e. choosing which $\delta$'s are $1$'s. In general, this should be a small amount of cases, so it should be easy to check by brute force.

I will update tomorrow.