Combinatorial optimization - is there a formal name for this problem?

Question

I am looking for a formal name and an algorithmic approach to the following problem.

Given is a set of services each coming with a price:

• {s1, 300}
• {s2, 400}
• {s3, 800}

Additionally there is a set of servicepackages each with a price that may differ from the total cost of the individual services:

• {p1, {s1, s2}, 600}
• {p2, {s2, s3}, 1050}
• {p3, {s1, s3}, 950}
• {p4, {s1, s2, s3}, 1250}

Now given a list of services (each service may appear many times) you want performed find the combination of packages and individual services with the lowest price. You can only use a package if you can completely fill it with services. A package may be ordered many times.

For example: Services to order :{s1,s2,s1,s3,s2,s3,s1}

possible Solutions:

• {p4, p4, s1} : 2800
• {p1, p1, p3, s3} : 2950

In this case the first solution would be the winner.

An exhaustive approach will quickly explode because it is O(n!) or even worse.

What is the formal name of this problem (if there is one)? How would you algorithmically approach that problem for hundreds of services and packages?

Answer 1

I don't know the name of your problem, if there is one.

But, concerning the complexity: The decision-version of your problem seems to be strongly NP-complete. You can easily reduce ExactCoverBy3Sets to it:

Given a ground set $X = \{1, \ldots, 3q\}$ and a set $\mathcal{C}$ of 3-element subsets $C_i$ of $X$. Is there a subcollection $\mathcal{C'} \subseteq \mathcal{C}$ of disjoint subsets that cover $X$ ?

Assume we have $3q$ services $1,\ldots,3q$, each with a price of $q+1$. Furthermore, for each $C_i$, we have a package of the corresponding three elements at a price of $1$. Now, given the list $1,\ldots,3q$ of services to order, there is a solution with cost at most $q$ if and only if there is a solution to the given instance of ExactCoverBy3Sets. Since there are no double orders and since "You can only use a package if you can completely fill it with services", the sets are disjoint and cover the whole ground set $X$.

So, you won't succeed in finding a polynomial (exact) algorithm or an FPTAS. However, you can search for approximation algorithms for the above problem and/or the related problems SetPacking and MinimumCover (cf. Garey/Johnson, "Computers and Intractibility", Problems SP2, SP3 and SP5).