Integer Programming — Power-Plant Expansion Plan: 23-Ind-A1 Operations Research, December 2016, Q8

Question 8: Integer Programming — Power-Plant Expansion Plan (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.

Check: the exam text states the per-site construction cost, operating cost and energy/year, and the year-by-year demand, are "given" — but no numeric table for Question 8 appears anywhere in the source (confirmed against the printed paper: the question runs straight to its closing sentence with no table). Consistent with this subject's recurring pattern, the model below is built with NAMED symbolic parameters rather than invented numbers — a defensible, fully-specified IP model is the deliverable a "develop the model" instruction actually asks for.

Given. 5 candidate sites $i=1,\dots,5$; planning horizon $t=1,\dots,20$ years; construction cost $K_i$, annual operating cost $O_i$, and annual energy output $E_i$ for a plant at site $i$ (all site-specific, unstated numerically in the source); year-$t$ energy demand $D_t$ (unstated numerically); existing generation $500{,}000$ kWh/yr; at most one plant enters service per year; a plant produces its full $E_i$ starting the year it is commissioned and every year after.

Find. An integer programming model (decision variables, objective, constraints) that selects which sites to build and when, to minimize total construction + operating cost over the 20-year horizon while meeting demand every year.

Approach. Use a binary "site $i$ commissioned in year $t$" decision variable; a plant's operating cost accrues for every remaining year once built, and cumulative installed energy (existing + all plants commissioned so far) must cover each year's demand.

Define decision variables. For $i=1,\dots,5$, $t=1,\dots,20$: $$x_{it}=\begin{cases}1 & \text{if the plant at site }i\text{ is placed into service in year }t\\0 & \text{otherwise}\end{cases}$$
Each site is built at most once (it may also never be built, if not needed), and at most one plant enters service in any given year (across all sites): $$\sum_{t=1}^{20}x_{it}\le1\quad\forall i=1,\dots,5,\qquad \sum_{i=1}^{5}x_{it}\le1\quad\forall t=1,\dots,20.$$
Cumulative demand-coverage constraint. A plant commissioned in year $\tau$ contributes $E_i$ to every year $t\ge\tau$, so total available energy by year $t$ is the existing $500{,}000$ plus every plant commissioned on or before $t$: $$500{,}000+\sum_{i=1}^{5}E_i\sum_{\tau=1}^{t}x_{i\tau}\ \ge\ D_t\qquad\forall t=1,\dots,20.$$
Objective — total construction plus operating cost. A plant commissioned in year $\tau$ incurs its one-time construction cost $K_i$ plus its operating cost $O_i$ for every year it runs, $(20-\tau+1)$ years: $$\text{Minimize}\ \ Z=\sum_{i=1}^{5}\sum_{\tau=1}^{20}\big[K_i+(21-\tau)\,O_i\big]\,x_{i\tau}$$
Assemble the complete IP model. $$\text{Minimize } Z=\sum_{i,\tau}\big[K_i+(21-\tau)O_i\big]x_{i\tau}$$ $$\text{s.t.}\quad \sum_{t}x_{it}\le1\ \forall i,\quad \sum_{i}x_{it}\le1\ \forall t,\quad 500{,}000+\sum_i E_i\sum_{\tau\le t}x_{i\tau}\ge D_t\ \forall t,$$ $$x_{it}\in\{0,1\}\ \ \forall i,t.$$ This fully specifies "which sites, in which years" as required — it is a model to be solved by a MIP solver with the site/demand data plugged in, not solved symbolically here, per the instruction ("develop the model").

Final results — Question 8 (model summary, not solved)
Item	Value
Decision variables	$x_{it}\in\{0,1\}$, $i=1..5$, $t=1..20$ (100 binaries)
Objective	Minimize total construction + operating cost, $\sum[K_i+(21-\tau)O_i]x_{i\tau}$
Constraint families	build-at-most-once per site; at-most-one-commissioning per year; cumulative demand coverage (3 families)
Existing capacity	500,000 kWh/yr (baseline, always available)
Solved numerically?	No — site/demand data not supplied in the source; model developed symbolically

Topic: Capacity-expansion / facility-timing integer program.

Key relations: Binary "commission in period $t$" variables $x_{it}$; cumulative-capacity constraint $\text{existing}+\sum_i E_i\sum_{\tau\le t}x_{i\tau}\ge D_t$ ties a one-time build decision to every later period's demand; total cost $=\sum(\text{construction}+\text{years operated}\times\text{annual operating cost})$.

Why this works: Because a plant, once built, produces every year afterward, the "does site $i$ help meet year $t$'s demand" question depends on the ENTIRE history of commissioning decisions up to $t$, not just decision $t$ itself — the cumulative sum $\sum_{\tau\le t}x_{i\tau}$ is exactly what encodes "once built, stays built" inside a single linear constraint per year.

Common pitfall: Writing the demand constraint with only that year's own commissioning decision ($x_{it}$) instead of the cumulative sum through year $t$, which would incorrectly "forget" capacity built in earlier years.

Source: Hillier & Lieberman, Introduction to Operations Research (11th ed.), ch. 12 (Integer Programming) — facility-location / capacity-expansion formulations.

Question 8 of 8: Integer Programming — Power-Plant Expansion Plan

Question 8: Integer Programming — Power-Plant Expansion Plan (20 marks)