Depot Location, Integrality Gap, and a Misread Bound
A distributor serves four customer zones with weekly demands 40, 35, 25, and 30 tonnes. Three candidate depots may be opened: X has fixed cost $900/week and capacity 80 tonnes; Y has fixed cost $700 and capacity 70; Z has fixed cost $1,100 and capacity 90. Transport costs per tonne from X to zones 1-4 are 4, 6, 8, 5; from Y they are 7, 3, 5, 6; from Z they are 6, 7, 4, 3. A planner proposes opening X and Y and assigning zone 1 to X, zone 2 to Y, zone 3 to Y, and zone 4 to X. The LP relaxation of the facility-location MILP has objective $1,780, while the proposed integer plan costs $2,140. A junior analyst says the $360 gap proves the proposed plan is not optimal and that the LP solution should be used instead because it is cheaper.
1. Formulate the facility-location model as a mixed-integer linear program. Define sets, parameters, variables, objective, and constraints, and explain why the capacity-linking constraint should not use an arbitrary big-M.
Read the worked answer
Let i index candidate depots {X,Y,Z} and j index customer zones {1,2,3,4}. Let d_j be demand, f_i fixed cost, cap_i capacity, and c_ij unit transport cost.
Variables: y_i = 1 if depot i is opened, 0 otherwise; x_ij = tonnes shipped from i to j.
Minimize ∑_i f_i y_i + ∑_i ∑_j c_ij x_ij
subject to: ∑_i x_ij = d_j for each j (demand satisfaction) ∑_j x_ij ≤ cap_i y_i for each i (capacity and linking) x_ij ≥ 0, y_i ∈ {0,1}.
The linking constraint should use cap_i y_i, not an arbitrary M y_i. If M is larger than cap_i, a fractional y_i can still permit flow up to M, so the LP relaxation is weaker and branch-and-bound may work harder. Using cap_i is the tightest valid value because no depot can ship more than its capacity. An even stronger disaggregated form is x_ij ≤ min(d_j, cap_i) y_i for each i,j. Also include ∑_i cap_i y_i ≥ ∑_j d_j if not implied; here total demand is 130.
2. Check the planner's proposed plan for feasibility and compute its total weekly cost. What can and cannot be concluded from this calculation?
Read the worked answer
Open X and Y. Assignments: zone 1 (40) to X; zone 2 (35) to Y; zone 3 (25) to Y; zone 4 (30) to X.
Loads: X = 40 + 30 = 70 ≤ 80, feasible. Y = 35 + 25 = 60 ≤ 70, feasible.
Transport cost: X: 40×4 + 30×5 = 160 + 150 = 310. Y: 35×3 + 25×5 = 105 + 125 = 230. Total transport = 540. Fixed cost = 900 + 700 = 1,600. Total = $2,140 per week.
The plan is feasible and costs $2,140. What cannot be concluded from one plan is that it is optimal; one must still compare other depot combinations and assignments or solve the MILP. But the fact that its cost exceeds the LP relaxation bound of $1,780 does not make it suboptimal. An integer plan normally costs more than the LP relaxation because the LP can open fractional depots and split fixed costs. The proposed plan may well be the optimal integer solution; the LP objective is only a lower bound.
3. Explain the integrality gap to the junior analyst and propose at least one valid strengthening or cut that could improve the LP bound.
Read the worked answer
The LP relaxation allows y_i to be fractional, for example opening 0.6 of X and 0.8 of Y. That can satisfy demand at a cost below any real plan because the model pays only a fraction of the fixed cost. The $360 gap is an integrality gap, not evidence that the integer plan is wrong. The LP solution may be unimplementable: no one can open 0.6 of a depot. Using the LP solution as an operating plan is a category error; it is useful only as a bound and for branch-and-bound.
A simple valid cut: total demand is 130 tonnes and the largest depot capacity is 90, so one depot cannot cover all demand. Therefore ∑_i y_i ≥ 2. This cut is valid for every feasible integer solution and can raise the LP bound when the relaxation opens only one depot fractionally. Another strengthening is to replace x_ij ≤ cap_i y_i with x_ij ≤ min(d_j, cap_i) y_i, and to add flow-cover inequalities for subsets of customers whose total demand exceeds the capacity of a single open depot. To prove optimality, solve the MILP or branch-and-bound and report the best integer solution plus the final bound, not the raw LP relaxation.