Integer Programming — Power-Plant Site Selection and Timing: 23-Ind-A1 Operations Research, May 2013, Q4

Question 4: Integer Programming — Power-Plant Site Selection and Timing (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. Sites $i=1,\dots,5$; years $t=1,\dots,20$. Per site $i$: capital cost $K_i$ ($ to build), annual operating cost $O_i$ ($/yr while running), energy capacity $E_i$ (MWh/yr once running). Existing capacity 500,000 MWh/yr. Required system energy demand $R_t$ for each year $t$ (symbolic — the specific cost/energy table is not reproduced in the exam text, so the model is built with named parameters). Constraints: at most one plant per site (ever); at most one plant enters service per year; a plant contributes its full $E_i$ starting the year it enters service.

Find. A binary integer program whose optimal solution is the cost-minimizing set of (site, start-year) plant commitments meeting demand every year.

Approach. Use one binary variable per (site, year) pair meaning "site $i$'s plant begins operating in year $t$"; this single variable set cleanly encodes both the site-selection and timing decisions, and lets construction + accumulated operating cost be written as a linear function of it.

Decision variables. $y_{it}\in\{0,1\}$ for $i=1,\dots,5$, $t=1,\dots,20$: $y_{it}=1$ if the plant at site $i$ is placed into service in year $t$ (and never built otherwise).
At-most-one-plant-per-site. $\displaystyle\sum_{t=1}^{20}y_{it}\le1$ for each $i$ (site is built at most once, in at most one start year).
At-most-one-start-per-year. $\displaystyle\sum_{i=1}^{5}y_{it}\le1$ for each $t$ (only one new plant can come online in any given year, across all sites).
Cumulative energy meets demand. A plant started in year $s\le t$ is still running in year $t$, so cumulative capacity available in year $t$ is $$500{,}000+\sum_{i=1}^{5}\sum_{s=1}^{t}E_i\,y_{is}\ \ \ge\ \ R_t,\qquad t=1,\dots,20.$$
Objective — construction + accumulated operating cost. A plant started in year $t$ operates for the remaining $(20-t+1)$ years of the horizon, so its total lifetime cost contribution is $K_i+O_i\,(21-t)$: $$\boxed{\min Z=\sum_{i=1}^{5}\sum_{t=1}^{20} y_{it}\Big[K_i+O_i\,(21-t)\Big]}$$ subject to steps 2–4 and $y_{it}\in\{0,1\}$.

Element	Formulation
Variables	$y_{it}\in\{0,1\}$, site $i=1..5$, start-year $t=1..20$
Objective	$\min\sum_{i,t}y_{it}\big[K_i+O_i(21-t)\big]$
Constraints	$\sum_t y_{it}\le1\ \forall i$; $\sum_i y_{it}\le1\ \forall t$; $500{,}000+\sum_{i}\sum_{s\le t}E_iy_{is}\ge R_t\ \forall t$

Concept & Theory

Topic. Binary integer programming for facility-siting-with-timing (capacity expansion) problems.

Key relations. A single "start indicator" $y_{it}$ over (site, year) pairs avoids needing separate build/operate/timing variables; cumulative sums $\sum_{s\le t}$ convert a one-time start decision into a running capacity constraint; multiplying $y_{it}$ by its remaining operating years folds an entire operating-cost stream into one linear objective term.

Why this works. Because at most one plant may start per site and per year, the $y_{it}$ formulation is exact (no fractional double-counting), and both "logical" restrictions (one plant per site, one start per year) and the "physical" restriction (cumulative energy $\ge$ demand) are all linear in $y_{it}$ — so the model is a genuine (not just relaxed) 0-1 IP.

Common pitfall. Using a separate binary "site $i$ is built" variable in addition to per-year start variables creates redundancy and requires extra linking constraints; collapsing build-decision and timing-decision into one $y_{it}$ avoids that entirely.

Source. Hillier & Lieberman, Introduction to Operations Research, ch. 12 (Integer Programming — capital-budgeting and facility-location formulations).

Question 4 of 9: Integer Programming — Power-Plant Site Selection and Timing

Question 4: Integer Programming — Power-Plant Site Selection and Timing (20 marks)