Minimum-cost network flow: a linear programming example, solved and checked
The minimum-cost network flow is a classic linear programming problem. Here it is solved by a real solver (HIGHS) and checked: every constraint, the dual, and the optimality certificate. Change the numbers below and solve your own.
Solve your own version free, no account needed
The problem
Ship 8 units from node 1 to node 4. Arcs (cost in $ per unit, capacity in units): 1->2 (2, 5), 1->3 (4, 6), 2->3 (1, 4), 2->4 (6, 4), 3->4 (2, 7). Minimize total cost.
How the model was built
The objective as written from the problem, before the numbers are multiplied out:
- x12 is the number of units shipped on the arc 1 → 2, and so on. The objective is cost per unit × units, added over the arcs.
- x12 + x13 = 8: all 8 units leave node 1.
- x12 − x23 − x24 = 0: at node 2, units in = units out. The next line is the same rule at node 3.
- x24 + x34 = 8: all 8 units arrive at node 4.
- x12 ≤ 5 and the lines after it: each arc's capacity.
The model
Each line has a plain-language note on the right.
| make as small as possible: total shipping cost ($) | |
| limit 1: left side must equal 8 | |
| limit 2: left side must equal 0 | |
| limit 3: left side must equal 0 | |
| limit 4: left side must equal 8 | |
| units shipped on arc 1->2 (units) is at most 5 | |
| units shipped on arc 1->3 (units) is at most 6 | |
| units shipped on arc 2->3 (units) is at most 4 | |
| units shipped on arc 2->4 (units) is at most 4 | |
| units shipped on arc 3->4 (units) is at most 7 | |
| units shipped on arc 1->2 (units) cannot be negative | |
| units shipped on arc 1->3 (units) cannot be negative | |
| units shipped on arc 2->3 (units) cannot be negative | |
| units shipped on arc 2->4 (units) cannot be negative | |
| units shipped on arc 3->4 (units) cannot be negative |
In matrix form
With its numbers:
What is being decided
There are 5 decision variables.
| Variable | Type | Meaning |
|---|---|---|
| x12 | real number | units shipped on arc 1->2 (units) |
| x13 | real number | units shipped on arc 1->3 (units) |
| x23 | real number | units shipped on arc 2->3 (units) |
| x24 | real number | units shipped on arc 2->4 (units) |
| x34 | real number | units shipped on arc 3->4 (units) |
Goal and limits
Minimize total shipping cost ($) subject to 14 constraints, of which 10 are simple bounds on a single variable.
Problem type
LP, complexity level 2: a linear program. Solved with HIGHS at the Medium solver tier.
The answer at a glance
The optimal value of each decision, as the solver returned it.
Which constraints hold the answer in place
Binding (no slack left): constraints 1, 2, 3, 4, 5, 7, 9 (see the table). Changing a binding constraint changes the answer; a slack one can move a little without effect.
| # | Constraint | Value | Limit | Slack | Binding |
|---|---|---|---|---|---|
| 1 | x12 + x13 = 8 | 8 | 8 | 0 | yes |
| 2 | x12 - x23 - x24 = 0 | 0 | 0 | 0 | yes |
| 3 | x13 + x23 - x34 = 0 | 0 | 0 | 0 | yes |
| 4 | x24 + x34 = 8 | 8 | 8 | 0 | yes |
| 5 | x12 <= 5 | 5 | 5 | 0 | yes |
| 6 | x13 <= 6 | 3 | 6 | 3 | |
| 7 | x23 <= 4 | 4 | 4 | 0 | yes |
| 8 | x24 <= 4 | 1 | 4 | 3 | |
| 9 | x34 <= 7 | 7 | 7 | 0 | yes |
| 10 | x12 >= 0 | 5 | 0 | 5 | |
| 11 | x13 >= 0 | 3 | 0 | 3 | |
| 12 | x23 >= 0 | 4 | 0 | 4 | |
| 13 | x24 >= 0 | 1 | 0 | 1 | |
| 14 | x34 >= 0 | 7 | 0 | 7 |
Why this is optimal
A proof you can check by hand. Multiply each constraint in the table by its weight and add them up: the result is a lower limit on the objective that holds for every plan meeting the constraints. Our answer reaches that limit exactly, so no plan does better. A negative weight turns a limit around (for example ≥ into ≤) before adding. Every step was checked in exact fractions, not rounded decimals.
| # | Constraint | Weight |
|---|---|---|
| 1 | x12 + x13 = 8 | 4 |
| 2 | x12 - x23 - x24 = 0 | -2 |
| 4 | x24 + x34 = 8 | 4 |
| 7 | x23 ≤ 4 | -1 |
| 9 | x34 ≤ 7 | -2 |
Algebraic model (low level)
Decision variables, objective and every constraint written out; this is exactly what the solver receives.
Standard form
As a linear program: minimize cᵀx subject to A x ≤ b (the inequality rows) and A_eq x = b_eq (the equations); a maximization is written as minimizing the negative.
Model code (cvxpy)
The same model in cvxpy, ready to run.
import cvxpy as cp
x12 = cp.Variable(name='x12') # units shipped on arc 1->2 (units)
x13 = cp.Variable(name='x13') # units shipped on arc 1->3 (units)
x23 = cp.Variable(name='x23') # units shipped on arc 2->3 (units)
x24 = cp.Variable(name='x24') # units shipped on arc 2->4 (units)
x34 = cp.Variable(name='x34') # units shipped on arc 3->4 (units)
objective = cp.Minimize(2*x12 + 4*x13 + x23 + 6*x24 + 2*x34)
constraints = [
x12 + x13 == 8,
x12 - x23 - x24 == 0,
x13 + x23 - x34 == 0,
x24 + x34 == 8,
x12 <= 5,
x13 <= 6,
x23 <= 4,
x24 <= 4,
x34 <= 7,
x12 >= 0,
x13 >= 0,
x23 >= 0,
x24 >= 0,
x34 >= 0,
]
problem = cp.Problem(objective, constraints)
problem.solve(solver='HIGHS')
print(problem.status, problem.value)
print('x12 =', x12.value)
print('x13 =', x13.value)
print('x23 =', x23.value)
print('x24 =', x24.value)
print('x34 =', x34.value)The dual problem
Every constraint of the original (primal) problem gets a price, and every primal variable becomes a constraint on those prices. Strong duality: primal and dual optima are equal (46).
| Dual variable | Prices | Value |
|---|---|---|
| y1 | price of constraint 'x12 + x13 = 8' (objective change per extra unit of its right-hand side) | 4 |
| y2 | price of constraint 'x12 - x23 - x24 = 0' (objective change per extra unit of its right-hand side) | -2 |
| y3 | price of constraint 'x13 + x23 - x34 = 0' (objective change per extra unit of its right-hand side) | 0 |
| y4 | price of constraint 'x24 + x34 = 8' (objective change per extra unit of its right-hand side) | 4 |
| y5 | price of constraint 'x12 <= 5' (objective change per extra unit of its right-hand side) | 0 |
| y6 | price of constraint 'x13 <= 6' (objective change per extra unit of its right-hand side) | 0 |
| y7 | price of constraint 'x23 <= 4' (objective change per extra unit of its right-hand side) | -1 |
| y8 | price of constraint 'x24 <= 4' (objective change per extra unit of its right-hand side) | 0 |
| y9 | price of constraint 'x34 <= 7' (objective change per extra unit of its right-hand side) | -2 |
Solve your own
This is the model as the app reads it. Change any number and solve it in the free box on the front page (no account needed).
minimize 2*x12 + 4*x13 + 1*x23 + 6*x24 + 2*x34
subject to
x12 + x13 = 8
x12 - x23 - x24 = 0
x13 + x23 - x34 = 0
x24 + x34 = 8
x12 <= 5
x13 <= 6
x23 <= 4
x24 <= 4
x34 <= 7
x12, x13, x23, x24, x34 >= 0
# x12 = units shipped on arc 1->2 (units)
# x13 = units shipped on arc 1->3 (units)
# x23 = units shipped on arc 2->3 (units)
# x24 = units shipped on arc 2->4 (units)
# x34 = units shipped on arc 3->4 (units)
# objective = total shipping cost ($)Checked: the app's answer matches the reference answer in our test set, which two solvers (HIGHS, CLARABEL) agree on. Built 2026-11-10.
Related examples
Try ProvenDecisions free: type, photograph or say an optimization problem; every answer is checked by a solver.