Network flow problems

Страница в процессе перевода.

This tutorial was generated using Literate.jl. Download the source as a .jl file.

This tutorial was originally contributed by Arpit Bhatia.

In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge.

Often in operations research, a directed graph is called a network, the vertices are called nodes and the edges are called arcs.

A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, unless it is a source, which has only outgoing flow, or sink, which has only incoming flow.

A network can be used to model traffic in a computer network, circulation with demands, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes.

This tutorial requires the following packages:

using JuMP
import HiGHS

The shortest path problem

Suppose that each arc of a graph is assigned a scalar cost , and suppose that we define the cost of a forward path to be the sum of the costs of its arcs.

Given a pair of nodes, the shortest path problem is to find a forward path that connects these nodes and has minimum cost.

where is if is the starting node, if is the ending node, and otherwise.

G = [
    0 100 30 0 0
    0 0 20 0 0
    0 0 0 10 60
    0 15 0 0 50
    0 0 0 0 0
]
n = size(G)[1]
b = [1, -1, 0, 0, 0]
shortest_path = Model(HiGHS.Optimizer)
set_silent(shortest_path)
@variable(shortest_path, x[1:n, 1:n], Bin)
# Arcs with zero cost are not a part of the path as they do no exist
@constraint(shortest_path, [i = 1:n, j = 1:n; G[i, j] == 0], x[i, j] == 0)
# Flow conservation constraint
@constraint(shortest_path, [i = 1:n], sum(x[i, :]) - sum(x[:, i]) == b[i],)
@objective(shortest_path, Min, sum(G .* x))
optimize!(shortest_path)
@assert is_solved_and_feasible(shortest_path)
objective_value(shortest_path)

55.0

value.(x)

5×5 Matrix{Float64}:
 0.0  0.0  1.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  1.0  0.0
 0.0  1.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0

The assignment problem

Suppose that there are persons and objects that we have to match on a one-to-one basis. There is a benefit or value for matching person with object , and we want to assign persons to objects so as to maximize the total benefit.

There is also a restriction that person can be assigned to object only if belongs to a given set of pairs .

Mathematically, we want to find a set of person-object pairs from such that the objects are all distinct, and the total benefit is maximized.

G = [
    6 4 5 0
    0 3 6 0
    5 0 4 3
    7 5 5 5
]
n = size(G)[1]
assignment = Model(HiGHS.Optimizer)
set_silent(assignment)
@variable(assignment, y[1:n, 1:n], Bin)
# One person can only be assigned to one object
@constraint(assignment, [i = 1:n], sum(y[:, i]) == 1)
# One object can only be assigned to one person
@constraint(assignment, [j = 1:n], sum(y[j, :]) == 1)
@objective(assignment, Max, sum(G .* y))
optimize!(assignment)
@assert is_solved_and_feasible(assignment)
objective_value(assignment)

20.0

value.(y)

4×4 Matrix{Float64}:
 -0.0  1.0  -0.0   0.0
  0.0  0.0   1.0   0.0
  1.0  0.0   0.0  -0.0
 -0.0  0.0   0.0   1.0

The max-flow problem

In the max-flow problem, we have a graph with two special nodes: the , denoted by , and the , denoted by .

The objective is to move as much flow as possible from into while observing the capacity constraints.

G = [
    0 3 2 2 0 0 0 0
    0 0 0 0 5 1 0 0
    0 0 0 0 1 3 1 0
    0 0 0 0 0 1 0 0
    0 0 0 0 0 0 0 4
    0 0 0 0 0 0 0 2
    0 0 0 0 0 0 0 4
    0 0 0 0 0 0 0 0
]
n = size(G)[1]
max_flow = Model(HiGHS.Optimizer)
@variable(max_flow, f[1:n, 1:n] >= 0)
# Capacity constraints
@constraint(max_flow, [i = 1:n, j = 1:n], f[i, j] <= G[i, j])
# Flow conservation constraints
@constraint(max_flow, [i = 1:n; i != 1 && i != 8], sum(f[i, :]) == sum(f[:, i]))
@objective(max_flow, Max, sum(f[1, :]))
optimize!(max_flow)
@assert is_solved_and_feasible(max_flow)
objective_value(max_flow)

6.0

value.(f)

8×8 Matrix{Float64}:
 -0.0   3.0   2.0  1.0  -0.0  -0.0  -0.0  -0.0
  0.0   0.0   0.0  0.0   2.0   1.0   0.0   0.0
  0.0   0.0   0.0  0.0   1.0  -0.0   1.0   0.0
 -0.0  -0.0  -0.0  0.0  -0.0   1.0  -0.0  -0.0
  0.0   0.0   0.0  0.0   0.0   0.0   0.0   3.0
  0.0   0.0   0.0  0.0   0.0   0.0   0.0   2.0
  0.0   0.0   0.0  0.0   0.0   0.0   0.0   1.0
  0.0   0.0   0.0  0.0   0.0   0.0   0.0   0.0