Minimum-Cost Network Flow — Napkin Procurement: 23-Ind-A1 Operations Research, May 2017, Q1

Question 1: Minimum-Cost Network Flow — Napkin Procurement (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 source gives no cost table or numeric demand for this question (only the structural description of the three procurement options and the 5-day horizon) — the model below is built with named symbolic parameters rather than invented numbers, per the project's standard treatment of "formulate, do not solve" questions with no accompanying data table. Turnaround is read literally from the wording: "regular ... full day turnaround" is taken as a genuine full 24-hour cycle, i.e. a napkin sent dirty at the end of day $t$ is not clean again until the end of day $t+1$ and so is usable starting day $t+2$ (2-day lag); "special overnight service" is taken as literally overnight, usable the very next day (1-day lag). This is the standard reading used for this class of laundry-scheduling network flow problem.

Given. A 5-day horizon $t=1,\dots,5$ with daily napkin demand $d_t$ (unspecified numerically); zero clean or dirty napkins on hand at $t=0$; three procurement options each day — buy new at unit cost $c_n$ (available immediately), send dirty napkins to regular laundry at unit cost $c_r$ (2-day lag), or to overnight laundry at unit cost $c_o$ (1-day lag).

Find. A minimum-cost network flow model (nodes, arcs, arc costs, and flow-balance constraints) that decides how many napkins to buy new, send to regular laundry, or send to overnight laundry each day.

Time-expanded network: top row C1…C5 = clean-napkin nodes for each day, bottom row D1…D5 = dirty-napkin nodes. Each $C_t$ also has an unlimited-capacity "buy" arc from a source node at cost $c_n$ (omitted above for legibility). Diagonal arcs are the regular (2-day) and overnight (1-day) laundry services.

Approach. Build a time-expanded network with one clean-napkin node and one dirty-napkin node per day, connect them with buy/use/carry/launder arcs of the given costs and lags, and write the LP as flow-conservation at every node.

Define the nodes and decision variables. For $t=1,\dots,5$: clean-napkin node $C_t$ and dirty-napkin node $D_t$, plus an unlimited source $S$. Flows: $b_t\ge0$ = napkins bought new on day $t$ (arc $S\to C_t$, cost $c_n$); $I^C_t\ge0$ = clean napkins carried unused from day $t$ to $t{+}1$ (arc $C_t\to C_{t+1}$, cost 0); $I^D_t\ge0$ = dirty napkins carried un-sent from day $t$ to $t{+}1$ (arc $D_t\to D_{t+1}$, cost 0); $r_t\ge0$ = napkins sent to regular laundry on day $t$ (arc $D_t\to C_{t+2}$, cost $c_r$, only defined while $t+2\le5$); $o_t\ge0$ = napkins sent to overnight laundry on day $t$ (arc $D_t\to C_{t+1}$, cost $c_o$, only defined while $t+1\le5$).
Clean-node balance (inflow = outflow at every $C_t$, with $I^C_0=0$, no arrival from laundry before it exists): $$I^C_{t-1}+b_t+r_{t-2}\!\cdot\![t\ge3]+o_{t-1}\!\cdot\![t\ge2]=d_t+I^C_t,\qquad t=1,\dots,5$$ This says: clean napkins on hand from yesterday, plus today's purchases, plus anything arriving back from the laundry today, must cover today's demand $d_t$ plus whatever is carried forward unused.
Dirty-node balance (every napkin used on day $t$ becomes dirty and either ships out or waits, with $I^D_0=0$): $$I^D_{t-1}+d_t=r_t\!\cdot\![t\le3]+o_t\!\cdot\![t\le4]+I^D_t,\qquad t=1,\dots,5$$ (For $t=4,5$ the regular-laundry arc does not exist because it could not return before the horizon ends; for $t=5$ neither service can return in time, so any remaining dirty napkins simply sit in $I^D_5$ at no further cost.)
Objective — minimize total procurement cost over the 5-day horizon: $$\boxed{\min Z=\sum_{t=1}^{5}c_n b_t+\sum_{t=1}^{3}c_r r_t+\sum_{t=1}^{4}c_o o_t}$$ subject to the balance equations of Steps 2–3 and $b_t,r_t,o_t,I^C_t,I^D_t\ge0$.

Final results — Question 1
Item	Value
Nodes	$C_1,\dots,C_5$ (clean), $D_1,\dots,D_5$ (dirty), source $S$
Decision variables	$b_t,\ r_t,\ o_t,\ I^C_t,\ I^D_t\ \ge0$
Objective	$\min\sum c_n b_t+\sum c_r r_t+\sum c_o o_t$
Structure	Balanced transshipment / min-cost flow — total supply = total demand = $\sum d_t$

Topic: Min-cost network flow formulation of a multi-period procurement/laundering (lot-sizing) problem.

Key relations: Flow conservation at every node (inflow = outflow + net demand); a min-cost flow network is balanced whenever total supply (all napkins ever bought) equals total demand ($\sum_t d_t$), which is guaranteed here because every used napkin is either re-laundered or left over, never destroyed.

Why this works: Splitting "clean" and "dirty" napkins into separate nodes per day turns a service-with-lag problem into a pure transshipment network: purchase, laundering with its fixed lag, and holding are all just arcs with a cost and (for laundering) a time-shift between their tail and head periods, so the whole schedule becomes one linear min-cost flow problem solvable by network simplex.

Common pitfall: Forgetting that regular laundry sent on day 4 or 5 (and overnight sent on day 5) cannot return within the horizon — including those arcs anyway lets the model "use" napkins that don't yet exist, understating the true cost.

Source: Hillier & Lieberman, Introduction to Operations Research (11th ed.), ch. 9 (network optimization / minimum-cost flow problems).

Question 1 of 8: Minimum-Cost Network Flow — Napkin Procurement

Question 1: Minimum-Cost Network Flow — Napkin Procurement (20 marks)