Solution. Let \(y_j \in \{0, 1\}\) open site \(j\) and \(x_j \geq 0\) be the units stored there. Minimise \(100y_1 + 120y_2 + 90y_3 + 2x_1 + 1.5x_2 + 2.5x_3\) subject to \(x_1 + x_2 + x_3 = 80\), \(x_j \leq c_jy_j\) with \(c = (50, 60, 40)\). Opening sites \(1\) and \(2\) (capacity \(110\)) with \(x_2 = 60\), \(x_1 = 20\) costs \(220 + 90 + 40 = 350\); sites \(2\) and \(3\) with \(x_2 = 60\), \(x_3 = 20\) cost \(210 + 90 + 50 = 350\) as well; sites \(1\) and \(3\) hold only \(90\) and cost \(190 + 100 + 75 = 365\) with \(x_1 = 50\), \(x_3 = 30\). So the optimum is \(350\), attained in two ways.

Solution. The value per unit weight is \(2.5\), \(2.17\), \(2.33\), \(1.6\). The LP relaxation fills by ratio: \(y_1 = 1\), \(y_3 = 1\) (weight \(7\)), then \(y_2 = \frac 36 = \frac 12\), value \(10 + 7 + 6.5 = 23.5\). Among integer choices of weight at most \(10\): \(\{1, 2\}\) weight \(10\), value \(23\); \(\{1, 3\}\) value \(17\); \(\{2, 3\}\) weight \(9\), value \(20\); \(\{1, 4\}\) value \(18\); \(\{3, 4\}\) value \(15\); \(\{2, 4\}\) weighs \(11\), and every triple weighs more than \(10\). The optimum is \(y_1 = y_2 = 1\), value \(23\), with LP bound \(23.5\).

Solution. Introduce \(y \in \{0, 1\}\) with \(x_A \leq 100y\) and \(x_B \geq 10y\). If \(x_A > 0\) then \(y = 1\) and \(x_B \geq 10\); if \(y = 0\) then \(x_A = 0\) and \(x_B \geq 0\) only.

Solution. The right-hand side \(3\) is an integer, so this row gives no cut: \(x_1\) is already integral at the LP optimum. A Gomory cut needs a row whose basic variable is fractional, here the \(x_2\) row.

Solution. The root (\(21\)) branches into \(x_2 \leq 1\) (\(20.67\)) and \(x_2 \geq 2\) (\(18\)). Best bound expands \(20.67\) first, giving \((3, 1)\) with \(19\) and \((4, 0)\) with \(20\). The incumbent \(20\) now exceeds the open bound \(18\), which is pruned. Five LPs are solved, the same as depth first; on larger problems best bound usually solves fewer.

Solution. Priority \(1\): profit \(\geq 1000\) is attainable (for example \(x_1 = 25\)). Priority \(2\): minimise overtime \(3x_1 + 4x_2 - 60\) subject to \(40x_1 + 30x_2 \geq 1000\). Labour per rupee of profit is \(\frac 3{40} = 0.075\) for \(x_1\) and \(\frac 4{30} = 0.133\) for \(x_2\), so use \(x_1\) only: \(x_1 = 25\), labour \(75\), overtime \(15\), which misses the overtime goal by \(5\) hours. No plan meets both goals: the profit goal forces at least \(75\) hours.