November 2017 – Elmar Klausmeier's Weblog

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

$\displaystyle{ 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

$\displaystyle{ 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

$\displaystyle{ \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.

Elmar Klausmeier's Weblog

Computers and Programming

Month: November 2017

Optimal Product Portfolio

1. Prerequisites

2. Problem statement

3. Challenges

Statistics of this Blog: Crossed 60.000 Views