∇ProvenDecisions
Ctrl K

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.

Answer. The smallest objective value is 46, at x12 = 5, x13 = 3, x23 = 4, x24 = 1, x34 = 7. All 14 constraints are satisfied exactly. Exactly proven optimal.

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:

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.

VariableTypeMeaning
x12real numberunits shipped on arc 1->2 (units)
x13real numberunits shipped on arc 1->3 (units)
x23real numberunits shipped on arc 2->3 (units)
x24real numberunits shipped on arc 2->4 (units)
x34real numberunits 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.

x125x133x234x241x347

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.

#ConstraintValueLimitSlackBinding
1x12 + x13 = 8880yes
2x12 - x23 - x24 = 0000yes
3x13 + x23 - x34 = 0000yes
4x24 + x34 = 8880yes
5x12 <= 5550yes
6x13 <= 6363
7x23 <= 4440yes
8x24 <= 4143
9x34 <= 7770yes
10x12 >= 0505
11x13 >= 0303
12x23 >= 0404
13x24 >= 0101
14x34 >= 0707

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.

#ConstraintWeight
1x12 + x13 = 84
2x12 - x23 - x24 = 0-2
4x24 + x34 = 84
7x23 ≤ 4-1
9x34 ≤ 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 variablePricesValue
y1price of constraint 'x12 + x13 = 8' (objective change per extra unit of its right-hand side)4
y2price of constraint 'x12 - x23 - x24 = 0' (objective change per extra unit of its right-hand side)-2
y3price of constraint 'x13 + x23 - x34 = 0' (objective change per extra unit of its right-hand side)0
y4price of constraint 'x24 + x34 = 8' (objective change per extra unit of its right-hand side)4
y5price of constraint 'x12 <= 5' (objective change per extra unit of its right-hand side)0
y6price of constraint 'x13 <= 6' (objective change per extra unit of its right-hand side)0
y7price of constraint 'x23 <= 4' (objective change per extra unit of its right-hand side)-1
y8price of constraint 'x24 <= 4' (objective change per extra unit of its right-hand side)0
y9price 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 ($)

Change the numbers and solve it

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

All 50 solved examples

Try ProvenDecisions free: type, photograph or say an optimization problem; every answer is checked by a solver.

What do you want to optimize?

Type the math, describe it in words, snap a photo or say it. ProvenDecisions builds the model, solves it, checks it and walks you through it.

One constraint per line, or separated by commas. Add integer: x, y or binary: z for whole-number decisions. LaTeX works too.

Try: