Question 7 of 9: Integer-Programming Formulation — Automotive Plant Assignment

Question 7: Integer-Programming Formulation — Automotive Plant Assignment (20 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.

Given. 4 plants, 3 models (X, Y, Z), each requiring 500,000 cars/yr; each plant makes at most one model; fixed and variable costs per the table above; logical restriction: plants 3 and 4 both operating $\Rightarrow$ plant 1 must also operate.

Find. Define the decision variables and formulate (do not solve) the mixed-integer program that minimizes total annual (fixed + variable) production cost.

Approach. Use a binary "plant $i$ assigned to model $m$" variable to capture the fixed cost and the single-model restriction, a continuous production-quantity variable linked to it by a big-$M$ constraint, demand constraints per model, and rewrite the "if 3&4 then 1" English rule as one linear inequality on the binaries.

1. Decision variables. Binary $y_{im}=1$ if plant $i\in\{1,2,3,4\}$ is assigned to produce model $m\in\{X,Y,Z\}$ (0 otherwise); continuous $q_{im}\ge0$ = cars of model $m$ produced at plant $i$ (only meaningful when $y_{im}=1$).
2. Single-model-per-plant restriction (a plant is used for at most one model): $$\sum_{m\in\{X,Y,Z\}}y_{im}\le1,\qquad i=1,\dots,4$$
3. Linking constraint (production only occurs at a plant actually assigned that model; $M=500{,}000$, the full annual demand, is a safe big-$M$): $$q_{im}\le M\,y_{im},\qquad \text{all }i,m$$
4. Demand-satisfaction constraint (each model's 500,000-car demand is met across whichever plants make it): $$\sum_{i=1}^{4}q_{im}=500{,}000,\qquad m\in\{X,Y,Z\}$$
5. Logical restriction — "if plants 3 AND 4 are used, plant 1 must be used." Let $u_i=\sum_m y_{im}\in\{0,1\}$ denote whether plant $i$ is used at all. The implication $(u_3=1\text{ and }u_4=1)\Rightarrow u_1=1$ linearizes as: $$u_3+u_4-u_1\le1 \quad\Longleftrightarrow\quad \sum_m y_{3m}+\sum_m y_{4m}-\sum_m y_{1m}\le1$$ (if both $u_3=u_4=1$, the left side is $2-u_1\le1$, forcing $u_1\ge1$, i.e. $u_1=1$; if either is 0 the constraint is automatically slack.)
6. Objective — minimize total fixed + variable production cost, using the given cost table ($F_i$ = fixed cost of plant $i$, $c_{im}$ = variable cost/car): $$\boxed{\min Z=\sum_{i=1}^{4}F_i u_i+\sum_{i=1}^{4}\sum_{m}c_{im}\,q_{im}}$$ subject to Steps 2–5, $y_{im}\in\{0,1\}$, $q_{im}\ge0$. Per the question, this model is formulated but not solved.