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

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?

• Sounds like some kind of combinatorial auction? – David Richerby Jul 2 '15 at 13:35

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