Integer Programming Formulation — Cassette Side Arrangement: 23-Ind-A1 Operations Research, December 2019, Q9

Question 9: Integer Programming Formulation — Cassette Side Arrangement (15 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Check: the conditions are: exactly two ballads per side, at least 3 hit songs on side 1, song 5 or song 6 on side 1, and “if song 2 and 4 are on side 1, then song 5 must be on side 2”. Song 7’s Type cell is genuinely blank in the printed table; it is treated as neither a ballad nor a hit (it counts toward duration only).

Given. Eight songs with length and type (Ballad / Hit / both / neither):

Given data — song length and type
Song	Type	Length (min)
1	Ballad	4
2	Hit	5
3	Ballad	3
4	Hit	2
5	Ballad	4
6	Hit	3
7	(blank in source)	5
8	Ballad and Hit	4

Conditions: each side totals 14–16 minutes; each side has exactly two ballads; side 1 has at least 3 hit songs; song 5 or song 6 (or both) is on side 1; if songs 2 and 4 are both on side 1, song 5 must be on side 2.

Find. An integer (binary) program whose feasibility determines whether a valid two-sided arrangement exists — formulation only.

Approach. Model the assignment of each song to a side with one binary variable per song, then translate each stated condition into a linear constraint: the two duration windows directly, the ballad/hit counts as weighted sums, the "5 or 6" requirement as a simple lower bound, and the compound conditional ("if 2 and 4, then not-5") using the standard big-M-free linearization for a 3-variable implication.

Define the decision variables and parameters. For each song $i=1,\dots,8$, let $$y_i=\begin{cases}1 & \text{song }i\text{ is placed on side 1}\\0 & \text{song }i\text{ is placed on side 2}\end{cases}$$ Let $L_i$ = length of song $i$; $B_i=1$ if song $i$ is a ballad (songs 1, 3, 5, 8) else 0; $H_i=1$ if song $i$ is a hit (songs 2, 4, 6, 8) else 0. (Song 8 has $B_8=H_8=1$; song 7 has $B_7=H_7=0$.)
Duration constraints, both sides (side 2's length is $\sum L_i(1-y_i)$): $$14\le\sum_{i=1}^{8}L_iy_i\le16,\qquad 14\le\sum_{i=1}^{8}L_i(1-y_i)\le16$$
Exactly two ballads per side. $$\sum_{i=1}^{8}B_iy_i=2,\qquad \sum_{i=1}^{8}B_i(1-y_i)=2$$ (with 4 ballads total, either equation forces the other, but both are stated for clarity.)
At least 3 hit songs on side 1. $$\sum_{i=1}^{8}H_iy_i\ge3$$
Song 5 or song 6 on side 1. $$y_5+y_6\ge1$$
Conditional constraint — "if songs 2 and 4 are both on side 1, song 5 must be on side 2." Written logically this is $(y_2=1\wedge y_4=1)\Rightarrow y_5=0$; the standard linearization forbids all three being 1 simultaneously while leaving every other combination free: $$y_2+y_4+y_5\le2$$ (if $y_2=y_4=1$, this forces $y_5\le0$, i.e. song 5 on side 2; if either $y_2$ or $y_4$ is 0, the constraint is automatically satisfied regardless of $y_5$.)
Assemble the complete model (a pure feasibility IP — no objective function is needed since the question only asks whether a satisfying arrangement exists; a constant objective such as "minimize 0" makes this explicit for a solver): $$\boxed{\begin{aligned} \text{Minimize}\quad & 0\\ \text{s.t.}\quad & 14\le\textstyle\sum L_iy_i\le16,\qquad 14\le\textstyle\sum L_i(1-y_i)\le16\\ & \textstyle\sum B_iy_i=2,\qquad \textstyle\sum B_i(1-y_i)=2\\ & \textstyle\sum H_iy_i\ge3\\ & y_5+y_6\ge1\\ & y_2+y_4+y_5\le2\\ & y_i\in\{0,1\}\quad i=1,\dots,8 \end{aligned}}$$

Check: the model above is feasible — solving it (not required by the question, done here only to confirm the formulation is sound) finds, e.g., side 1 = {2, 5, 6, 8} (16 min, ballads {5,8}, hits {2,6,8}) and side 2 = {1, 3, 4, 7} (14 min, ballads {1,3}), satisfying every constraint; exhaustive search over all $2^8$ assignments finds exactly 3 satisfying arrangements. This cross-check is reported; it is not part of the requested deliverable.

Final results — Question 9 (model summary, not solved)
Item	Value
Decision variables	$y_1,\dots,y_8\in\{0,1\}$ (1 = side 1)
Objective	none required (pure feasibility); "minimize 0"
Constraints	2 duration windows, 2 ballad-count, 1 hit-count, 1 either/or, 1 conditional
Feasibility check (bonus, not requested)	feasible — 3 satisfying arrangements exist, e.g. side 1={2,5,6,8}

Topic: 0–1 (binary) integer-programming formulation of a feasibility / assignment problem with logical (conditional) constraints.

Key relations: A two-way partition uses one binary variable per item with the complementary side written as $(1-y_i)$; a logical implication $(A\wedge B)\Rightarrow\lnot C$ among binary variables linearizes to $y_A+y_B+y_C\le2$ (forbidding the single combination that violates it) with no auxiliary big-M variable needed because all three variables are already binary.

Why this works: Because the model only needs to determine EXISTENCE of a feasible arrangement (not an optimal one), the objective is a constant — the entire question content lives in the constraint set, and a solver reports "infeasible" or an actual 0/1 vector rather than an optimized value.

Common pitfall: Linearizing the conditional with a big-M term ($y_5\le M(1-y_2)+M(1-y_4)$) when a tight, big-M-free form is available for a 3-binary-variable implication — the big-M form is not wrong, but it is unnecessarily loose and a common source of numerical/formulation errors in general IP models.

Source: Hillier & Lieberman, Introduction to Operations Research (11th ed.), ch. 12 (integer programming, binary-variable formulations of logical conditions).

Question 9 of 9: Integer Programming Formulation — Cassette Side Arrangement

Question 9: Integer Programming Formulation — Cassette Side Arrangement (15 marks)