Past Paper Question:
(Record Company Problem) The Record-a-Song Company has contracted with a rising star to record eight songs. The durations of the difference songs are $8, 3, 5, 5, 9, 6, 7,$ and $12$ minutes, respectively.
Record-a-Song uses a two-sided cassette tape for the recording. Each side has a capacity of $30$ minutes.
The company would like to distribute the songs between the two sides such that the length of the songs on each sides is about the same.
Aim:
Formulate this problem as an integer programming problem. Clearly define your variables, objective and constraints.
(You are NOT required to solve this integer programming problem.)
I've put in bold the information above that I think would be usfull if this were linear programing problem.
The thinks the numbers in the first paragraph would form the coefficients to some inequality, the second paragraph would be the right hand side limiting that inequality: $$8x_1+3x_2+5x_3+5x_4+9x_5+9x_6+6x_7+7x_8+12x_9\leq 30$$ $(x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8,x_9)\in\mathbb B$?
Not sure where the information of the third paragraph would come in, or what the objective function is.
What is the general method to formulate a worded problem and how do you know if your on the right tracks?
Let $x_{ij}=1$ if and only if song $i\in S$ of duration $d_i$ is assigned to side $j$ of the tape, $j=1,2$.
You want to minimize the difference between the durations on both sides, that is, minimize $$ Z=|\sum_{i\in S}d_i x_{i1}-\sum_{i\in S}d_i x_{i2}| $$ subject to:
Total durations cannot exceed capacity $30$: $$ \sum_{i\in S}d_i x_{ij}\le 30 \quad \forall j=1,2 $$
Each song must be assigned to either side $1$ or $2$: $$ x_{i1}+x_{i2}=1\quad \forall i\in S $$
Of course, you need to linearize the objective function, this is easy: replace the objective function by $Z=\varepsilon$ and add the following constraints: $$ \sum_{i\in S}d_i x_{i1}-\sum_{i\in S}d_i x_{i2} \le \varepsilon\\ \sum_{i\in S}d_i x_{i2}-\sum_{i\in S}d_i x_{i1} \le \varepsilon $$