1. Prerequisites
Assume one owns different products,
, usually
. Each product has a cost
,
, associated with this ownership,
. Let
, and
be the powerset of
, i.e., the set of all subsets. The powerset
has
elements.
There are two real-valued functions and
operating on
, i.e.,
. Function
denotes the sum of the cost of the product set given by
,
is therefore easy to evaluate. I.e.,
Function denotes the buying cost if one can dispose the set of products given by
. This means, it costs money to get rid of the products given by set
. As the products have interrelationships,
is more costly to evaluate than
and is given by some table lookup. Function
does not depend on
.
Some notes on : Assume a non-negative matrix
, where
denotes the cost to decouple the
-th product from the
-th. Then
Usually , if
, i.e.,
is upper triangular, because decoupling product
from product
does not need to be done again for decoupling the other direction from
to
. More zeros in above sum are necessary if decoupling product
is sufficient if done once and once only. In practical application cases
depends on a real-valued parameter
giving different solution scenarios.
Example: For three products let , thus cost of ownership is
,
,
,
,
, and so on for the rest of
sets. Function
gives positive values in a similar fashion, although, as mentioned before, these values are not related to
.
2. Problem statement
Find the set of products which gives the least cost, i.e., find
for
Rationale: One invests to get rid of the products in set
but saves ownership costs given by
.
does not need to be unique. If
depends on
then
will likely also depend on
.
3. Challenges
As 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.