30th November 2017

Assume one owns \(n>0\) different products, \(n\in\mathbb{N}\), usually \(n\approx 100\). Each product has a cost \(c_i>0\), \(c_i\in\mathbb{R}\), associated with this ownership, \(i=1,\ldots, n\). Let \(N=\left\{1,\ldots,n\right\}\), and \(\mathbb{P}(N)\) be the powerset of \(N\), i.e., the set of all subsets. The powerset \(\mathbb{P}(N)\) has \(2^n\) elements.

There are two real-valued functions \(f\) and \(g\) operating on \(\mathbb{P}(N)\), i.e., \(f,g\colon\mathbb{P}(N)\to\mathbb{R^+}\). Function \(g(I)\) denotes the sum of the cost of the product set given by \(I\in\mathbb{P}(N)\), \(g\) is therefore easy to evaluate. I.e.,

$$
g(I) = \sum_{i\in I} c_i
$$

Function \(f(I)\) denotes the buying cost if one can dispose the set of products given by \(I\in\mathbb{P}(N)\). This means, it costs money to get rid of the products given by set \(I\). As the products have interrelationships, \(f\) is more costly to evaluate than \(g\) and is given by some table lookup. Function \(f\) does not depend on \(c_i\).

Some notes on \(f\): Assume a non-negative matrix \(A=(a_{ij})\), where \(a_{ij}\) denotes the cost to decouple the \(i\)-th product from the \(j\)-th. Then

$$
f(I) = \sum_{i\in I} \sum_{j\in N} a_{ij}
$$

Usually \(a_{ij}=0\), if \(i<j\), i.e., \(A\) is upper triangular, because decoupling product \(i\) from product \(j\) does not need to be done again for decoupling the other direction from \(j\) to \(i\). More zeros in above sum are necessary if decoupling product \(i\) is sufficient if done once and once only. In practical application cases \(f\) depends on a real-valued parameter \(\gamma\in[0,1]\) giving different solution scenarios.

Example: For three products let \(c_1=8, c_2=4, c_3=5\), thus cost of ownership is \(g(\emptyset)=0\), \(g(\left\{1\right\})=8\), \(g(\left\{1,2\right\})=8+4=12\), \(g(\left\{1,3\right\})=8+5=13\), \(g(\left\{1,2,3\right\})=8+4+5=17\), and so on for the rest of \(2^3-5=3\) sets. Function \(f\) gives positive values in a similar fashion, although, as mentioned before, these values are not related to \(c_i\).

Find the set \(I\) of products which gives the least cost, i.e., find \(I\) for

$$
\min_{I\in\mathbb{P}(N)}\left(f(I)-g(I)\right)
$$

Rationale: One invests \(f(I)\) to get rid of the products in set \(I\) but saves ownership costs given by \(g(I)\).

\(I\) does not need to be unique. If \(f\) depends on \(\gamma\) then \(I\) will likely also depend on \(\gamma\).

As \(n\) can be "large", evaluating all possible combinations becomes prohibitive on todays computers. Maybe one of our gentle readers knows a method to find the optimum, or maybe just a nearby solution to above problem, or a probabilistic approach. Any comment is welcome.

**Categories: **mathematics
**Author: **Elmar Klausmeier