Problem 12-16 (Rardin 1e) Consider the single knapsack constrained binary optimization problem (with all variables binary 0/1):

maximize 40 x1 + 5 x2 + 50 x3 + 8 x4

subject to 18 x1 + 3 x2 + 20 x3 + 5 x4 <= 25

which has LP relaxation optimum x* = (5/18, 0, 1, 0).

0) Determine whether each of the following is a valid inequality for this problem, and if so, whether it would strengthen the LP relaxation to add the inequality as a new constraint: (b) x1 + x2 + x3 + x4 <= 4 and (d) 18 x1 + 20 x3 <= 20.

1) The 2nd inequality suggests a minimal cover inequality x1 + x3 <= 1. (See Definition 12.48 in Rardin 2e.) Find another.

2) Perform a branch & bound using breadth-first search, evaluating left to right where, as done in class, the left child node has a variable constrained below the floor of its current fractional value and the right child node has that variable constrained above the ceiling of its current value. At each of your additional four nodes, you should be able to greedily solve the LP relaxation solution in your head by trying to pack the variables that give the biggest ratio of objective value per constraint cost.

3) Comment on the computational savings (in terms of skipped nodes) if we allow a 6% error tolerance.

4) Since this problem can be easily rounded, comment on the additional computational savings (in terms of skipped nodes) achieved by rounding relaxation solutions under a 6% error tolerance.