30th November 2017, 2 min read

Optimal Product Portfolio

1. Prerequisites

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

There are two real-valued functions $f$ and $g$ operating on $P (N)$ , i.e., $f, g : P (N) \to R^{+}$ . Function $g (I)$ denotes the sum of the cost of the product set given by $I \in 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 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_{i j})$ , where $a_{i j}$ 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_{i j}

Usually $a_{i j} = 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 $γ \in [0, 1]$ giving different solution scenarios.

Example: For three products let $c_{1} = 8, c_{2} = 4, c_{3} = 5$ . The cost of ownership is thus:

\begin{aligned} g (\emptyset) & = 0, \\ g ({1}) & = 8, \\ g ({1, 2}) & = 8 + 4 = 12, \\ g ({1, 3}) & = 8 + 5 = 13, \\ g ({1, 2, 3}) & = 8 + 4 + 5 = 17, \end{aligned}

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}$ .

2. Problem statement

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

min_{I \in P (N)} (f (I) - g (I))

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 $γ$ then $I$ will likely also depend on $γ$ .

3. Challenges

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.