Integer Optimization

Question

I have an integer optimization problem that I've been pondering for the last several days. Here's an abbreviated version:

I have several wav song files with variable sizes (601201 kilobytes for example) and I want to know how to optimally arrange them into several CDs (with a given capacity in kilobytes). The objective is to minimize the number of CDs and at the same time maximize the free space on the last CD. Minimizing the number of CDs is not a problem. I'm really concerned about the second part.

This kind of question seems like it would have relevance in many different areas and as such, I feel that I should be able to find information about it. However, I don't know what exactly to search for. Has anyone ever heard of this type of problem and if so, can you point me in the right research direction?

Thanks

Answer 1

Since you have found that you only need 19 CDs, I would suggest the following model:

$max \ C_{19}-\sum_{i=1}^n c_{i}\cdot y_{i19}$

The objective function calculate the remaining space on CD 19. It has to be maximized.

• The sum of seizes of the songs on $CD_j$ cannot be greater than the capacity of $CD_j$:

$\sum_{i=1}^n c_{i}\cdot y_{ij} \leq C_{j} \quad \forall \ j \in 1,2,..,19$

• Song i can only be on one CD

$\sum_{j=1}^{19} y_{ij}=1\ \forall \ i \in 1,2,...,n$

i: Index for song i

j: Index for CD j

$c_{i}$: Size of song i

$y_{ij}=\begin{cases} 1, \ \text{if song i is on CD j } \\ 0, \text{else} \end{cases}$

$C_j$: capacity of CD j