# An artist published M albums. How to make a selection from the album so that all my N favorite songs are covered, while minimizing my cost?

This is a real life question.. I have a list of N favorite songs from an artist. Out of all M albums from the artist ever published,I want to buy a few albums to cover all of my N favorite songs, but I also want to minimize my spending. How to set up this problem as an optimization problem and how to solve it?

I feel this is an binary optimization program, as I either buy an album or not buy it.

This problem is called integer programming. You could formalize it as follows:

$$\min_{w} C(w) = \min_w \sum_{m=1}^Mw_mc_m,$$

where $$c_m$$ is the cost of album $$m$$ and $$w_m\in\lbrace 0;1 \rbrace$$ indicates if you buy album $$m$$. Note that minimizing the total cost $$\min C(w)$$ is equivalent to $$\max -C(w)$$. The objective is subject to the following restraints:

$$n=1,\ldots,N:\ 1 \leq \sum_{m=1}^M w_m \mathbf{I}_{m,n}$$

where $$\mathbf{I}_{m,n}$$ is $$1$$ if album $$m$$ contains song $$n$$.

Now you would need to put the constraints into matrix form $$\mathbf{I}$$ (by filling the matrix appropriatly with zeros and ones, rows corresponding to songs and columns to songs).

E.g., you can solve the problem in R with the package lpSolve.