Modeling II: networks, flows and process superstructures

Week 3 · 2105623 Optimization of Chemical Processes

Soorathep Kheawhom

24 August 2026

Three lectures

Outline

Networks and the node balance — one template, four classical problems, transportation and transshipment
Paths, cuts and integrality — shortest path, maximum flow, the minimum cut, total unimodularity
Process superstructures — the same mathematics with units for nodes, and where a binary variable becomes unavoidable

Session plan, 180 minutes

Today

10 min Opening: recap of Week 2, one question from HW1, today’s objectives
30 min Lecture 1: networks as a modeling language, the node balance, transportation and transshipment
20 min Activity 1 — draw the network
30 min Lecture 2: shortest path, maximum flow, the minimum cut, total unimodularity
15 min Break
25 min Activity 2 — transportation in OpenSolver
25 min Lecture 3: process superstructures, continuous route splits, where binaries would enter
20 min Activity 3 — sketch a superstructure
5 min Wrap-up, and what is due next week

Tools today: OpenSolver for the matrix models, Pyomo for the graph models. Notebook w03-modeling2-networks.ipynb; workbook w03-transportation.xlsx.

By the end you should be able to

Learning objectives

Write the node balance that every network flow model shares, and recognise the node-arc incidence matrix E behind it.
Formulate four problems as one template — transportation, transshipment, shortest path and maximum flow are four choices of data inside minimum cost flow.
Explain integrality for free using total unimodularity, and state exactly what destroys it.
Read node potentials and arc reduced costs from the LP duals, and identify a minimum cut from a maximum flow solution.
Represent competing process routes as a superstructure, and say which decisions are continuous and which need a binary variable.

CLO 1 (formulation) and CLO 4 (implementation and solution in Pyomo). Reference: Williams Ch. 5; Rao Ch. 3; Edgar, Himmelblau and Lasdon Ch. 7.

From Week 2 patterns to a network

Why networks deserve their own week

The four reusable patterns of Week 2

index set
balance equation
capacity constraint
linking constraint

A network model is those four patterns applied to a graph.

The index set is the arc set. The balance equation is written once per node. The capacity constraint is one bound per arc. And the graph itself is the linking structure.

A very large class is a network in disguise Distribution, logistics, pipeline routing, assignment, project scheduling, flowsheet synthesis.
The structure buys three things Integral answers for free, duals with an immediate physical reading, and specialised algorithms orders of magnitude faster than general LP.
You already know the equation The node balance is literally a steady-state material balance. Chemical engineers have been writing it since second year.

One template: the minimum cost flow problem

Everything today is a choice of data inside this

Minimum cost flow

Let G = (N, A) be a directed graph. For arc (i,j) ∈ A let f_ij ≥ 0 be the flow, c_ij the unit cost, u_ij the capacity. For node n ∈ N let b_n be the net supply.

minimise Σ_(i,j)∈A c_ij f_ij

subject to Σ_j f_nj − Σ_i f_in = b_n for every n ∈ N

0 ≤ f_ij ≤ u_ij

The sign of b Positive at a source, negative at a sink, zero at a pure transit node.
Feasibility of the whole class requires the net supplies to sum to zero.
In matrix form the balance is E f = b, with E the node-arc incidence matrix.

The engineering reading. Outflow − inflow = net generation. This is the steady-state material balance around a unit, written once per node instead of once per unit.

The node-arc incidence matrix

Rows are nodes, columns are arcs

Definition

E_n,(i,j) = +1 if n = i (arc leaves n)

E_n,(i,j) = −1 if n = j (arc enters n)

E_n,(i,j) = 0 otherwise

Every column has exactly one +1 and one −1, and therefore sums to zero.

The rows are linearly dependent: they sum to the zero vector, which is exactly why Σ_n b_n = 0 is required.

Four classical problems, one template

Problem	Graph	Data choice
Transportation	bipartite, sources to sinks	unit shipping cost, no capacities, b from supply and demand
Transshipment	any graph, transit nodes allowed	unit cost, arc limits, b_n = 0 at transit nodes
Shortest path	any graph	arc length as cost, b = +1 at the origin and −1 at the destination
Maximum flow	plus a super source and super sink	zero cost except −1 on a return arc, arc limits, b = 0

Transportation: the bipartite special case

Three precursor plants, four cell gigafactories

The model

minimise Σ_i∈S Σ_j∈D c_ij x_ij

subject to Σ_j x_ij ≤ s_i for every plant i

Σ_i x_ij ≥ d_j for every gigafactory j

x_ij ≥ 0

c_ij, USD/t	G1	G2	G3	G4
R1	18	24	31	40
R2	27	19	22	33
R3	38	30	25	21

Supplies 450, 380, 300 t/week; demands 300, 260, 330, 240. Total supply 1,130 t equals total demand, so the instance is balanced.

Transportation: the optimum, and what the duals say

The MODI potentials come free from the LP dual

Minimum shipping cost = 23,570.00 USD/week

x_ij, t	G1	G2	G3	G4
R1	300	150	0	0
R2	0	110	270	0
R3	0	0	60	240

All seven constraints bind: the instance is balanced, so nothing is left over anywhere.

The u–v potentials

u = (0, −5, −2) USD/t v = (18, 24, 27, 23) USD/t

c_ij − u_i − v_j = 0 on every lane carrying flow

c_ij − u_i − v_j ≥ 0 on every empty lane

v is a delivered value What one extra tonne at a gigafactory is worth; u is one more tonne of capacity at a plant.
R1 is the marginal plant Its dual is zero although its supply row binds — a degenerate vertex, and the Week 8 hook.

Transshipment: transit nodes and arc capacities

The same template, written verbatim on a bigger graph

Two coastal terminals H1 and H2. Material moves plant to terminal, terminal to terminal, and terminal to gigafactory. Two direct lanes remain.

The instance

9 nodes, 18 arcs. Every arc now has a capacity, and the terminals are pure transit nodes with b_n = 0.

b = (450, 380, 300, 0, 0, −300, −260, −330, −240)

Optimal cost = 25,850.00 USD/week

R1 → H1 saturates at 400 t and R3 → H2 at 300 t. The plan is not unique — several flow patterns cost exactly this much.

The two totals are not comparable, and that matters

A comparison students always try to make

Transportation 23,570.00 against transshipment 25,850.00 USD/week. The obvious conclusion — terminals cost money — is wrong, because the two models are not two options for the same system.

The direct problem has unlimited lane capacity and no terminal handling.
The transshipment network puts a capacity on every arc and forces most flow through a terminal.
The comparison that means something is between transshipment options: for example, what widening R1 → H1 is worth.

Modeling rule. State what a model does not include before comparing its objective with anything.

Node potentials and arc reduced costs

c̄_ij = c_ij − (π_i − π_j)

c̄_ij > 0 the arc must be empty

c̄_ij < 0 the arc must be saturated

c̄_ij = 0 any flow between the bounds

These are the optimality conditions of the minimum cost flow problem, and they are read directly off the LP duals of the node balances.

π is fixed only up to an added constant — only the difference π_i − π_j ever appears. Two solvers can report two different potential vectors and agree on every reduced cost.

Activity 1 · draw the network

20 min · pairs · paper

Two refineries, two consolidation hubs, four gigafactories. R1 ships 450 t/week, R2 380. G1 needs 200, G2 190, G3 260, G4 180 — total supply equals total demand at 830 t/week. Refineries ship only to hubs, except one surviving direct lane R1 → G1. The hubs may re-ship to each other in either direction, and each may ship to any gigafactory. Hubs hold no stock.

Arc data: cost in USD/t, capacity in t/week

arc	c	u	arc	c	u	arc	c	u
R1→H1	12	400	H1→H2	5	200	H2→G1	22	250
R1→H2	20	250	H2→H1	5	200	H2→G2	13	300
R2→H1	16	300	H1→G1	8	350	H2→G3	9	350
R2→H2	14	350	H1→G2	11	300	H2→G4	12	300
R1→G1	30	150	H1→G3	17	250	H1→G4	26	200

Your task

Draw the node-arc diagram by hand. Label every arc with its cost and capacity.
Mark each node with its net supply b_n.
Write the node balance for hub H1 in full algebra, in the convention outflow − inflow = b_n.

Pairs. At 15 min, three diagrams are held up and compared. Hand back one sheet per pair.

Activity 1 · [ANSWER] · the balances are the model

Different pictures, one incidence structure

Node balance at H1

f_H1,H2 + f_H1,G1 + f_H1,G2 + f_H1,G3 + f_H1,G4

− ( f_R1,H1 + f_R2,H1 + f_H2,H1 ) = 0

The diagram is a communication device. The balance equations are the mathematics.

Different pairs drew the same network with different layouts, orderings and crossings. None of that is the model. The model is the incidence structure: which arcs exist, and which nodes each one joins.

Two errors to look for. Writing b_H1 as a supply because the hub is drawn in the middle. And forgetting the reverse arc H2 → H1, which is a separate arc with its own non-negative flow, not a negative flow on H1 → H2.

Shortest path is a minimum cost flow

The only thing that changes is b

Send exactly one unit

Interpret c_ij as length, and drop the capacities:

b_origin = +1, b_dest = −1, b_n = 0 elsewhere.

Nothing else changes. The optimal flow is a single path, because the incidence matrix forces an integral basic optimal solution, and the only integral unit flows are paths.

First payoff of total unimodularity. An inherently combinatorial object — a path — comes out of a linear program.

Worked instance: fastest route R1 → G4

Arc costs re-read as transit times in hours.

Route	hours
R1 → H1 → H2 → G4	29
R1 → H2 → G4	32
R1 → H1 → G4	38

LP optimal length 29 h on R1 → H1 → H2 → G4

Matching a from-scratch Dijkstra implementation exactly. The cheap inter-terminal arc (5 h) beats both direct terminal routes — and the LP produced a 0–1 flow without being told to.

Maximum flow: a capacity question, not a cost question

Both terminals are under berth maintenance

Construction

Add a super source SRC with an arc to each plant of capacity equal to its supply, and a super sink SNK with an arc from each gigafactory of capacity equal to its demand.

maximise Σ_j t_j

s.t. inflow(n) + s_n = outflow(n) + t_n

0 ≤ f_ij ≤ u_ij, 0 ≤ s_i ≤ supply_i, 0 ≤ t_j ≤ d_j

The scenario. Berth maintenance halves the capacity of every terminal-to-gigafactory arc. How much can the network still deliver?

Maximum weekly throughput 1,100 t against 1,130 t of demand

t/week	G1	G2	G3	G4
demand	300	260	330	240
delivered	300	260	300	240

The entire 30 t shortfall lands on G3, and only on G3.

Max-flow min-cut The maximum flow equals the minimum capacity of a cut separating SRC from SNK: LP duality specialised to a network.
Read off the duals The cut is identified from the capacity duals.

The minimum cut, and the only investment that helps

The cut is the list of assets worth money

Adding capacity anywhere except on an arc of the cut changes nothing at all.

To recover the missing 30 t you must widen H1 → G3 or H2 → G3. No other investment will do it.

Why this is the useful output. A debottlenecking study that reports only the throughput number has thrown away the answer. The cut is the list of assets worth money, and everything not in the cut is worth exactly zero at the margin.

Confirmed both from the LP duals and by enumerating all 512 cuts of the nine-node network.

Total unimodularity: integers for free

A property of the matrix, not of the costs

Definition and theorem

E is totally unimodular (TU) if every square submatrix has determinant 0, +1 or −1. The node-arc incidence matrix of a directed graph is TU.

Hoffman and Kruskal. If E is TU and b, u are integral, then every basic feasible solution of { f : E f = b, 0 ≤ f ≤ u } is integral. The simplex method returns a basic solution, so it returns an integer answer.

Why. A basic solution solves B f_B = b′ for a nonsingular square submatrix B. By Cramer’s rule f_B = B⁻¹b′ with det B = ±1, so B⁻¹ has integer entries.

No integer variables, ever Transportation, transshipment, shortest path, maximum flow and assignment never need them. Solve the LP, get integers, at LP speed.
It belongs to the constraint matrix Not to the costs. Changing the costs cannot make the answer fractional.
Everything so far Every flow reported this afternoon came out integral from a pure LP solve.

TU is fragile: one innocuous side constraint

Terminal H1 may handle at most 35 % of everything leaving the plants

The added requirement

Σ_(i,H1)∈A f_i,H1 ≤ 0.35 · Σ_i∈S Σ_(i,j)∈A f_ij

This row is not part of the incidence structure: it has coefficients 1 and −0.35 spread across arcs that share no node.

Cost rises from 25,850.00 to 26,195.00 USD/week — and four arcs come out at exactly half a tonne.

f_R1,H1 = 365.5 f_R1,H2 = 84.5 f_H1,G2 = 95.5 f_H2,G2 = 164.5

What destroys total unimodularity

A percentage-share or blending-ratio constraint across arcs.
A fixed-charge binary linked to a flow.
A joint capacity shared by arcs that do not meet at a node.
Any row whose coefficients are not {0, +1, −1} in the incidence pattern.

The modeling consequence. If half a tonne is physically meaningless you now need integer variables, and the model changes class from LP to MILP: Week 5 for the formulation, Week 11 for the algorithm. Know before adding a row whether you are about to pay that price.

Break

15 minutes.

Next: open w03-transportation.xlsx and have OpenSolver loaded. Activity 2 starts at 1:45. You will reproduce a stated optimum, then break the supply–demand balance on purpose.

Activity 2 · transportation in OpenSolver

25 min · computer · individual

Part 1 — reproduce the optimum

Open w03-transportation.xlsx, sheet Transportation. Complete the yellow cells: row sums G12:G14, column sums C15:F15, objective C19 as one SUMPRODUCT.

OpenSolver with CBC: objective $C$19, Min, changing $C$12:$F$14, constraints $G$12:$G$14 <= $I$12:$I$14 and $C$15:$F$15 >= $C$17:$F$17.

The objective cell must read 23,570.00 USD/week.

If it does not, you have a formula error — and that is the point.

Part 2 — break the balance on purpose

Reduce total supply below total demand — for example set R2 to 200 t. Re-solve, and record exactly what the solver reports.
Add a dummy source with a large penalty cost on every lane, give it the missing tonnage, and re-solve. Record the new objective and which gigafactory the dummy serves.

Tick Sensitivity Analysis — u_i and v_j are the MODI potentials, free from the LP dual. Individual, 25 min, hand back nothing.

Activity 2 · [ANSWER] · the dummy source

The cost of not serving a customer, previously implicit

Part 1

Objective C19 = 23,570.00 USD/week, identical to the notebook. R1 ships 300 to G1 and 150 to G2; R2 ships 110 to G2 and 270 to G3; R3 ships 60 to G3 and 240 to G4.

Sensitivity report

u = (0, −5, −2) v = (18, 24, 27, 23) USD/t

Dual objective = 23,570.00 → strong duality holds

Part 2

Supply below demand. With Σs_i < Σd_j and demand written with ≥, the model is infeasible — no plan exists, because the model has been told that every tonne of demand must be served.

Dummy source. A fictitious plant whose shipping cost is a penalty M restores feasibility. Its shipments are the tonnes not served: 19,610.00 + 180M, and the dummy serves G3 — all 180 t, for every value of M.

What does the dummy cost represent? The cost of not serving a customer, previously implicit. Choosing M is a business decision. And the dummy reveals which customer is cheapest to disappoint — often more useful than the cost itself.

From places to units: the process superstructure

Same mathematics, different meaning of the objects

Nodes are process units. Arcs are material streams.

It is the standard way to pose a process synthesis question — “which flowsheet should we build” — rather than an operating question, “how should we run the flowsheet we have”.

The idea

Build one network that contains every candidate route at once, and let the optimizer decide how much material goes down each route. A route that is not worth using simply receives zero flow.

Nothing here needs a binary variable. The split of a stream between competing units is a continuous variable bounded below by zero, and the optimizer drives the uninteresting splits to zero by itself.

The Week 2 vocabulary covers it

index set over units and streams
balance around every unit and every mixing or splitting node
capacity constraint on every unit
linking constraint wherever two routes share a downstream unit

The hydrogen superstructure

100 t/day of purified hydrogen for cathode-precursor reduction

SMR and ATR produce a crude stream that must be purified; ELY produces hydrogen already pure enough. Two purifiers: PSA, which recovers more but costs more to run, and a membrane (MEM), cheaper and recovering less. Crude from either reformer may go to either purifier in any proportion.

Unit	F_u^max t/d	k_u USD/t	η_u
SMR	90	1300	—
ATR	70	1550	—
ELY	40	3400	—
PSA	100	200	0.88
MEM	80	100	0.80

Throughputs are the LP optimum. ELY is present in the model and receives zero flow — that is the answer, not an omission.

The algebraic model, and why there is no split fraction

The cheapest lesson of superstructure modeling

Linear superstructure

minimise Σ_u∈U k_u F_u [USD/day]

s.t. F_SMR + F_ATR = F_PSA + F_MEM crude balance

η_PSAF_PSA + η_MEMF_MEM + F_ELY = D product balance

0 ≤ F_u ≤ F_u^max for every u ∈ U

There is no split fraction in this formulation, and there does not need to be one.

The split of crude between PSA and MEM is F_PSA / (F_SMR + F_ATR), and it is recovered after the solve, not imposed before it. Writing splits as ratios introduces a division and makes the model nonlinear for no gain.

The two balances are the linking constraints. The crude balance links the reformer block to the purifier block; the product balance links all three routes to the single requirement. Delete them and the model separates into five unrelated one-variable problems with no feasible answer.

The LP selects routes with no binary variable

The answer can be predicted before it is produced

Cost of one tonne of purified hydrogen, by route

Route	USD per t pure
SMR → PSA	1704.55
SMR → MEM	1750.00
ATR → PSA	1988.64
ATR → MEM	2062.50
ELY (no purification)	3400.00

Computed by hand as ( k_prod + k_pur ) / η_pur, so the LP answer can be predicted before it is produced.

Minimum operating cost = 177,250.00 USD/day — that is 1,772.50 USD per tonne of purified hydrogen.

SMR runs full at 90 t/day; all of that plus 10 t/day of ATR crude goes through PSA at its full 100 t/day; the remaining 15 t/day of ATR crude goes through MEM; ELY stays at zero. The recovered split of crude is 100/115 to PSA and 15/115 to MEM.

The dual of the product balance is 2,062.50 USD/t — exactly the cost of the ATR → MEM route, the most expensive route actually carrying flow. The marginal tonne of product is made by the marginal route: a Week 2 shadow price transferred to a flowsheet.

Where binaries would enter, and what they cost

Capital charges change the flowsheet, not just the cost

Unit selection: the fixed-charge pair

y_u = 1 if unit u is built, 0 otherwise.

minimise Σ_u k_uF_u + Σ_u f_uy_u

s.t. F_u ≤ F_u^max y_u, y_u ∈ {0,1}

plus the balances and bounds as before.

Equivalent daily capital charge f_u (USD/day): SMR 22,000 · ATR 15,000 · ELY 9,000 · PSA 12,000 · MEM 30,000.

	USD/day
MILP optimum	248,720.00
LP relaxation of it	222,232.14
integrality gap	26,487.86 (10.65 %)

The MILP builds SMR, PSA and ELY only.

ATR and the membrane are dropped, and electrolysis — which the LP refused to use at all — is switched on to make up the 20.8 t/day that SMR and PSA cannot cover.

The point of process synthesis. A route with a high running cost can still be correct if it avoids a large capital commitment. Formulation strength is Week 5; branch and bound is Week 11.

One nonlinearity, and the class changes again

Verification is not optional

Load-dependent recovery

A real adsorber or membrane recovers a larger fraction when run below design, because contact time per tonne is longer. A first-order representation:

η_u(F_u) = η_u⁰ − s_uF_u → η_uF_u = η_u⁰F_u − s_uF_u²

Coefficients reproduce the design values exactly: 0.92 − 0.0004(100) = 0.88 for PSA, 0.84 − 0.0005(80) = 0.80 for MEM.

The product balance becomes a quadratic equality, so the feasible set is not convex — an NLP with no global guarantee, or with binaries a nonconvex MINLP, the hardest class in this course.

MINLP optimum = 247,496.00 USD/day

Marginally below the MILP value: PSA at 90 t/day rather than its design 100 recovers 0.884 instead of 0.880, so it needs less electrolysis behind it.

A nonconvex MINLP solver can return a local solution and report it as optimal. The notebook therefore enumerates all 32 selection patterns and solves the NLP behind each. Week 4 is where this becomes the whole lesson.

Activity 3 · sketch a superstructure

20 min · groups of 3 to 4 · one sheet

A site must deliver 100 t/day of purified hydrogen. Three production routes are candidates — steam methane reforming, autothermal reforming and water electrolysis. The first two produce a crude stream; electrolysis produces hydrogen already pure enough. Two purification technologies are candidates for the crude stream: pressure swing adsorption and a membrane unit. Crude from either reformer may go to either purifier in any proportion.

Your task, on one sheet

Draw the superstructure — every unit, every candidate stream, the mixing and splitting nodes, and the product node.
Mark every decision as continuous (how much through each route) or discrete (whether to build a unit at all), with two clearly different symbols.
State which constraints change if unit selection is added, and write the one new constraint family in algebra.

Do not compute anything. The deliverable is the structure and the classification of the decisions.

Groups of 3 to 4. Two groups present at the board at 15 min. Hand back one sketch per group.

Activity 3 · [ANSWER] · the one row that adds a binary

5 units, 7 candidate streams, 2 balances

Continuous Every unit throughput, and therefore every split. Splits are outputs of the solve, not inputs.
Discrete Only whether a unit is built at all. Nothing else here is discrete.

What changes when selection is added

New: F_u ≤ F_u^max y_u, y_u ∈ {0,1} — one row per unit

Objective gains Σ_u f_uy_u — a cost that does not scale with throughput

Unchanged: both balances and the bounds.

Revisited twice. Week 5 formulates the discrete version and asks how tight the link should be; Week 11 shows how branch and bound closes the gap — 10.65 % here.

Summary

What today established

Concepts

One template covers the family Choose the graph, the costs, the capacities and the net supplies, and all four classical problems follow.
The node balance is the model the same conservation law as a material balance around a unit.
Integers for free by total unimodularity — and the property belongs to the matrix, not to the costs.
TU is fragile One share constraint or one fixed-charge binary, and fractional vertices reappear.
Duals carry the engineering content Node potentials price material by location; the minimum cut is the only place extra capacity is worth anything.
A superstructure is a network of units Route choice is continuous; only “build or not” is discrete.

Numbers established today

Transportation optimum	23,570.00 USD/wk
Transshipment optimum	25,850.00 USD/wk
Shortest path R1 → G4	29 h
Maximum flow / demand	1,100 / 1,130 t
Minimum cut capacity	1,100 t, 5 arcs
With a 35 % share limit	26,195.00 USD/wk
Superstructure LP	177,250.00 USD/d
Product balance dual	2,062.50 USD/t
Superstructure MILP	248,720.00 USD/d
Its LP relaxation	222,232.14 USD/d
Integrality gap	26,487.86 (10.65 %)
Superstructure MINLP	247,496.00 USD/d

Next: Week 4 — blending, pooling and quality specifications.

Before next week

Reading, homework, and one installation

Reading

Williams Model Building in Mathematical Programming, Ch. 5, network models.
Edgar, Himmelblau and Lasdon Ch. 7, the sections on transportation and network flow.
Rao Ch. 3, the transportation problem as a special-structure LP.

Notebook to finish

w03-modeling2-networks.ipynb, plus Exercises 1, 2 and 4. Exercise 4 re-verifies max-flow min-cut on a modified instance and is the one that repays the effort.

HW1 is due at the start of Week 4, Monday 31 August.

It covers Weeks 1 to 3 — linear and network model construction. Its Problem 5 asks for the transshipment model of Problem 2 in Pyomo, over an arc set.

Install before Week 4. Week 4 crosses from the spreadsheet to Python and needs a nonlinear solver. Install ipopt now with

conda install -c conda-forge ipopt

or run the IDAES extensions installer. You will also want pip install highspy for the linear solves. Test before the session with SolverFactory('ipopt').available().