2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.