Allocating songs to both sides of a CD

Question

1) There are $8$ songs on a $2$-sided CD, of the following durations: $8$, $3$, $5$, $5$, $9$, $6$, $7$ and $12$ minutes. Each side has a capacity of $30$ minutes. However, we want to distribute the songs so that each side is about the same number of minutes. Formulate this problem as an integer programming problem. Clearly define your variables, objective and constraints.

I'm thinking about

MIN( S(X) - T(X))

where S(X) = side 1 and T(X) = side 2? but don't know how to formulate this with the constraints?

2) Formulate the following

  MAX            2x - 79y
  Subject To     0 ≤ x ≤ 20 and 0 ≤ y ≤ 30

and at least one of the following inequalities holds:

−2x1 + 3x2 ≥ 0
 5x1 − 4x2 ≥ 0
 7x1 + 8x2 ≤ 40.

Answer 1

Hint: this is an instance of the optimization version of the partition problem. Choose $8$ binary decision variables $x_i \in \{\pm 1\}$ such that

$$8 x_1 + 3 x_2 + 5 x_3 + 5 x_4 + 9 x_5 + 6 x_6 + 7 x_7 + 12 x_8$$

is as close to zero as possible. You may want to use the function $y \mapsto 2 y - 1$ so that the decision variables take values in $\{0,1\}$. Since you have to use IP, choosing the objective function is tricky.

Answer 2

I have formulated one for you and I have solved it using excel solver. Not the data that you provided but for a sum of all minutes which are divisible by 2 and the tricky objective function that the other responder was alluding. Goodluck.