Optimal Product Portfolio

This post was automatically copied from Optimal Product Portfolio on eklausmeier.goip.de.

1. Prerequisites

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

2. Problem statement

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

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.