Worked solutions

Exercise 1: Integer production

Maximize 3x+2y with x+y≤4, 2x+y≤6.5, and nonnegative integer x,y. Find the optimum and verify it by enumeration.

Solution. For y=0,1,2,3,4 the best allowed x is 3,2,2,1,0 respectively, with values 9,8,10,9,8. Therefore the unique optimum is (2,2), value 10. It uses resources 4 and 6, within limits 4 and 6.5.

Exercise 2: Sales cap 6

Reset the plant model to baseline, then replace a+b≤10 with a+b≤6. Compare all four opening patterns.

Solution. Neither gives 0. A only: a=6, net 48−10=38. B only: b=6, net 36−8=28. Both: with the tighter sales cap, contribution is maximized by a=6,b=0, so net 48−18=30. Opening B is allowed without producing B but wastes its fixed cost. Best is A only, profit 38.

Exercise 3: At most one line

Use baseline data and add yA+yB≤1. What is the best opening and production plan?

Solution. Both is excluded. Neither gives 0, A only gives 38, B only gives 40. Choose yA=0,yB=1,a=0,b=8. Labor use 8≤12 and sales 8≤10. Profit 48−8=40.

Exercise 4: A module costing 8

Use baseline plant data plus an optional module adding 4 labor units. Its weekly cost is 8. Compare buy and do not buy.

Solution. Without buying, best profit is 46 at (a,b)=(2,8). Buying changes labor capacity to 16. Open both and produce (6,4): labor 16, sales 10, operating profit 48+24−18=54, then subtract module cost 8 to get 46. Both purchase states are optimal. One returned vector does not establish uniqueness.

Exercise 5: A minimum batch of 4

Reset to baseline and add a≥4yA. Compare opening patterns and determine the optimum.

Solution. A only still gives 38. B only still gives 40. With both open and a≥4, the labor limit is binding and b≤12−2a. Contribution 8a+6b≤72−4a, which decreases with a, so choose a=4,b=4. Net profit is 32+24−18=38. Choose B only with profit 40.

Exercise 6: A remaining optimality gap

A maximization MILP has feasible incumbent value 46 and a valid global upper bound 48. What can be concluded?

Solution. The unknown optimum lies in [46,48]. A better feasible plan may exist, but its improvement is at most 2 objective units. This is not yet proof that 46 is exactly optimal. A node upper bound is not a feasible integer value; do not report 48 as an achieved profit.

1. Linking

yA=0 gives a≤0 and a≥0, so a=0. yA=1 gives 3≤a≤6. Opening does not force full capacity.

2. Relaxation

The relaxed yA=1/3 is not binary. It pays only 10/3 rather than 10 for opening A. Relaxation enlarges the feasible set, so 158/3≈52.667 is a valid upper bound, but this plan is inadmissible for the MILP, whose optimum is 46.

3. Purchase

Gross operating improvement =54−46=8. Cost=9. Incremental net benefit=8−9=−1. Buy gives 45; do not buy gives 46. Reject the purchase; best total profit stays 46.

4. Pruning

For maximization, node bounds 45 and 46 cannot improve incumbent 46, so prune them when seeking one optimum. Bound 48 may improve it and needs further work. The global certificate is 46≤optimum≤48. A bound of 48 does not prove a feasible integer solution at 48 exists. Keeping all alternative optima would require more care with equality pruning.