CSC 445/545 – Summer 2021
The Network Simplex Method: Initial Impressions
University of Victoria – CSC 445/545 – Summer 2021
1
Bill Bird
Department of Computer Science University of Victoria
July 6, 2021
“ You have meddled with the primal forces of nature,
and you will atone. ”
– Arthur Jensen (portrayed by Ned Beatty) Network (1976)
University of Victoria – CSC 445/545 – Summer 2021
2
Graphs and Networks (1)
-5 i
-5 5e
3
17
7
d 10
4
2
1
2
g 0
a
-3 c
h
4
2
b 6
20
1
1
University of Victoria – CSC 445/545 – Summer 2021
3
Network
f -7
Graphs and Networks (2)
This sequence of lectures covers a particular class of graph-theoretic problems which can be solved by a variant of the Simplex Method.
For historical reasons, these are called “network problems”, even though they are not much different than other graph problems (e.g. the graph algorithms you might have seen in a course like CSC 225).
Moreover, the terminology used by some sources (like the Vanderbei book) is unique to linear programming applications (and does not seem to be consistent with typical graph terminology). This course (and this lecture) will use standard graph theory terminology instead.
University of Victoria – CSC 445/545 – Summer 2021 4
Graphs and Networks (3)
Adding to the confusion, the Vanderbei book uses the term ‘network flow problem’ as a catch-all term for these network-style linear programming problems.
You may remember network flow problems from CSC 226 (e.g. the Ford-Fulkerson or Edmonds-Karp algorithms, or the Max-Flow Min-Cut Theorem). We will actually cover this application (which will be called a ‘max flow problem’ to disambiguate), but the term ‘network flow problem’ does not mean the same thing in this course as in CSC 226.
University of Victoria – CSC 445/545 – Summer 2021 5
Network Fundamentals (1)
i
e
d
a
h
g
c
b
f
The networks we will work with are directed graphs. Formally, a directed graph is a pair G = (V,E) where E is a set of ordered pairs (u,v) where u,v ∈ V. The elements of V are vertices and the elements of E are edges or arcs.
University of Victoria – CSC 445/545 – Summer 2021 6
Network Fundamentals (2)
i
e
d
a
h
g
c
b
f
In general, unless otherwise stated, networks will be assumed to be weakly connected. Recall that a directed graph is weakly connected if the undirected version of the graph (obtained by deleting directions on each edge) is connected.
University of Victoria – CSC 445/545 – Summer 2021 7
Network Fundamentals (3)
i
e
d
a
h
g
c
b
f
In the event that the input network for a particular problem is disconnected, it can be partitioned into connected components (and the problem can be solved separately for each component).
University of Victoria – CSC 445/545 – Summer 2021 8
Network Fundamentals (4)
i
e
d
a
h
g
c
b
f
A spanning tree of a network is defined to be a subgraph of the network which contains all vertices and is both weakly-connected and acyclic.
University of Victoria – CSC 445/545 – Summer 2021 9
Network Fundamentals (5)
i
e
d
a
h
g
c
b
f
Note that the definition of a spanning tree used here does not involve edge directions in any way. This is a bit of a departure from the usual treatment of directed graphs (where edge directions are normally significant in all cases); note that the term ‘spanning tree’ is not normally applied to directed graphs anyway.
University of Victoria – CSC 445/545 – Summer 2021 10
Min Cost Flows (1)
i
e
d
a
h
g
c
b
f
The minimum cost network flow problem can be interpreted as a form of resource distri- bution problem.
University of Victoria – CSC 445/545 – Summer 2021 11
Min Cost Flows (2)
-5 i
-5 e
d 10
a
-3 c
h 4
g 0
b
6
f
-7
0
Each node has an associated supply value, which is the surplus amount of the resource available at that node. Negative supply values represent demand, and the goal is to find a way to move surplus resources from nodes with excess supply to those with demand.
University of Victoria – CSC 445/545 – Summer 2021 12
Min Cost Flows (3)
-5 i
-5 e
d 10
a
-3 c
h 4
g 0
b
6
f
-7
0
The supply imbalance implies a fundamental condition of the problem: Any solution must move resources such that the net supply at each node is zero. Unless otherwise stated (e.g. in an assignment question), we will assume that the sum of all supply values in the network always equals zero.
University of Victoria – CSC 445/545 – Summer 2021 13
Min Cost Flows (4)
-5 i
-5 5e
3
17
7
d 10
4
2
1
2
g 0
a
-3 c
h
4
2
b
6
20
1
1
Each arc has an associated cost value. An unlimited amount of resources can be transported across any arc (in the forward direction of the arc).
University of Victoria – CSC 445/545 – Summer 2021 14
f
-7
Min Cost Flows (5)
-5 i
-5 5e
3
17
7
d 10
4
2
1
2
g 0
a
-3 c
h
4
2
b
6
20
1
1
With the cost values incorporated, the problem of balancing supply and demand becomes an optimization problem: If there are multiple ways to balance supply, we want the one with the lowest total cost.
University of Victoria – CSC 445/545 – Summer 2021 15
f
-7
Min Cost Flows (6)
10 -6 1 g2h4i
7 15
4 -2 d
2
6 18
f
23 e4
c 0
Consider the min-cost flow instance above (with supply and cost values shown).
1 a1b
-6 -6
University of Victoria – CSC 445/545 – Summer 2021 16
Min Cost Flows (7)
Any partial or complete solution to the problem will be called a flow. To avoid overloading a single diagram, we will picture the flow separately from the original cost/supply data.
University of Victoria – CSC 445/545 – Summer 2021 17
Supply/Cost
Flow
gh6i
10 5 f
d 3
3
e6
6 a6b
c 6
10 -6 1 g2h4i
7 15
4 -2 d
2
6 18
f
23 e4
1 a1b
-6 -6
c 0
Min Cost Flows (8)
In the flow shown above, each arc is labelled with the total amount of resources that travel across that arc.
University of Victoria – CSC 445/545 – Summer 2021 18
Supply/Cost
Flow
gh6i
10 5 f
d 3
3
e6
6 a6b
c 6
10 -6 1 g2h4i
7 15
4 -2 d
2
6 18
f
23 e4
1 a1b
-6 -6
c 0
Min Cost Flows (9)
The total cost of a flow can therefore be obtained by multiplying the amount of flow across each arc with the cost associated with that arc, then summing the result over all arcs.
University of Victoria – CSC 445/545 – Summer 2021 19
Supply/Cost
Flow
gh6i
10 5 f
d 3
3
e6
6 a6b
c 6
10 -6 1 g2h4i
7 15
4 -2 d
2
6 18
f
23 e4
1 a1b
-6 -6
c 0
Min Cost Flows (10)
A flow is feasible if the direction of flow across each arc respects the direction of the arc (that is, if no arcs have a negative amount of flow).
University of Victoria – CSC 445/545 – Summer 2021 20
Supply/Cost
Flow
gh6i
10 5 f
d 3
3
e6
6 a6b
c 6
10 -6 1 g2h4i
7 15
4 -2 d
2
6 18
f
23 e4
1 a1b
-6 -6
c 0
Min Cost Flows (11)
A flow is balanced if the net supply at each node (total amount leaving the node minus total amount entering) is equal to the node’s supply value.
University of Victoria – CSC 445/545 – Summer 2021 21
Supply/Cost
Flow
gh6i
10 5 f
d 3
3
e6
6 a6b
c 6
10 -6 1 g2h4i
7 15
4 -2 d
2
6 18
f
23 e4
1 a1b
-6 -6
c 0
Min Cost Flows (12)
The flow above is both feasible and balanced, and has a total cost of 265.
University of Victoria – CSC 445/545 – Summer 2021 22
Supply/Cost
Flow
gh6i
10 5 f
d 3
3
e6
6 a6b
c 6
10 -6 1 g2h4i
7 15
4 -2 d
2
6 18
f
23 e4
1 a1b
-6 -6
c 0
Min Cost Flows (13)
A solution to the minimum cost network flow problem is a feasible and balanced flow with the minimum total cost.
University of Victoria – CSC 445/545 – Summer 2021 23
Supply/Cost
Flow
gh6i
10 5 f
d 3
3
e6
6 a6b
c 6
10 -6 1 g2h4i
7 15
4 -2 d
2
6 18
f
23 e4
1 a1b
-6 -6
c 0
Min Cost Flows (14)
The feasible and balanced flow above has a total cost of 224 (which makes it a better solution than the previous flow).
University of Victoria – CSC 445/545 – Summer 2021 24
Supply/Cost
Flow
gh6i
10 f
5
d 14
8
e 12
a6b
c 12
10 -6 1 g2h4i
7 15
4 -2 d
2
6 18
f
23 e4
1 a1b
-6 -6
c 0
Min Cost Flows and Linear Programs (1)
Task: Encode the minimum cost network flow problem as a linear program.
University of Victoria – CSC 445/545 – Summer 2021 25
Supply/Cost
Flow
gh6i
10 f
5
d 14
8
e 12
a6b
c 12
10 -6 1 g2h4i
7 15
4 -2 d
2
6 18
f
23 e4
1 a1b
-6 -6
c 0
Min Cost Flows and Linear Programs (2)
At a high level, the problem definition easily maps on to the usual criteria for linear programming. Let G = (V , E ) be a directed graph, let supply(v ) denote the supply value of each vertex v ∈ V, cost(e) denote the unit cost of each arc e ∈ E and N(v) denote the set of outbound neighbours of each vertex v.
Objective: Minimize the total cost across all arcs.
Optimization Variables: Amount of flow xuv on each arc (u,v) ∈ E
Constraints: For each vertex v, balance must be maintained between supply, flow in and flow out. That is, we want to enforce the constraint
for each vertex v ∈ V . University of Victoria – CSC 445/545 – Summer 2021
26
xvw − xuv = supply(v)
w∈N(v) v∈N(u)
outgoing flow incoming flow
Min Cost Flows and Linear Programs (3)
The flow balance constraint for each vertex v can be written as xvw − xuv = supply(v)
w∈N(v) v∈N(u)
outgoing flow incoming flow
or, by negating both sides, as
xuv − xvw = −supply(v)
v∈N(u) w∈N(v)
incoming flow outgoing flow
Although form (1) is probably the most intuitive, we will use form (2) in our derivation, since it will make it easier to interpret the dual LP later.
(1)
University of Victoria – CSC 445/545 – Summer 2021
27
(2)
Min Cost Flows and Linear Programs (4)
The resulting minimization problem is
min. xuv ·cost(u,v) (u,v)∈E
s.t. xuv − xvw = −supply(v) for each vertex v ∈ V v∈N(u) w∈N(v)
xuv ≥ 0foreachedge(u,v)∈E
University of Victoria – CSC 445/545 – Summer 2021
28
Min Cost Flows and Linear Programs (5)
10 -6 1 g2h4i
7 15
4 -2 d
2
6 18
f
23 e4
1 a1b
-6 -6
c 0
The minimization problem for the network above is shown on the next slide.
University of Victoria – CSC 445/545 – Summer 2021 29
Min Cost Flows and Linear Programs (6)
min. s.t.
xae +xba +xcb +4xdc +4xdi +8xeb +2xed +2xfe +15xfi +7xgf +2xhg +4xih −xae + xba
=6 =6 =0 =−3 =−6
University of Victoria – CSC 445/545 – Summer 2021
30
xae
− xba + xcb −xcb+xdc
− xdc− xdi
+ xeb
+ xed
− xeb− xed+ xfe
− xfe −
xdi
+ xfi
− xih
xuv ≥ 0forall (u,v
xfi + xgf =2
− xgf + xhg
− xhg + xih
= −10 = 6 = −1
Min Cost Flows and Linear Programs (7)
xae xba xcb xdc xdi xeb xed xfe xfi xgf xhg xih cT = 1 1 1 4 4 8 2 2 15 7 2 4
A =
1
−1−1 1
−1 −1 1
−1 −1 1
−1 1
University of Victoria – CSC 445/545 – Summer 2021
31
−1 1
−11 1
−11
6 6
0
-3 b=-6
2
-10
−1 1 6 1 1 −1 -1
Equality Constraints and Slack Variables (1)
Question: How can we interpret an LP with only equality constraints and variable non-negativity constraints?
University of Victoria – CSC 445/545 – Summer 2021 32
Equality Constraints and Slack Variables (2)
Consider the LP above.
University of Victoria – CSC 445/545 – Summer 2021
33
max. x1 + 2×2 + 3×3
s.t.
x1 + x2 + 2×3 = 13 2×1 − x2 − x3 = 10
x1,x2,x3 ≥ 0
Equality Constraints and Slack Variables (3)
max. x1 s.t. x1
+ 2×2
+ 3×3 + 2×3 − x3
max. s.t.
x1 + 2×2 + 3×3
x1 + x2 + 2×3 −x1 − x2 − 2×3 2×1 − x2 − x3 −2×1 + x2 + x3
x1,x2,x3
≤ 13 ≤ −13 ≤ 10 ≤−10 ≥ 0
+ x2 2×1 − x2
= 13
= 10 x1,x2,x3 ≥ 0
Applying the usual transformation yields the standard form LP on the right.
University of Victoria – CSC 445/545 – Summer 2021
34
Equality Constraints and Slack Variables (4)
max. s.t.
x1 + 2×2 + 3×3
x1 + x2 +2×3 −x1 − x2 −2×3 2×1 − x2 − x3 −2×1+x2+x3
x1,x2,x3
≤13 ≤−13 ≤ 10 ≤ −10 ≥ 0
ζ = w1 = w2 = w3 = w4 =
0 + x1 + 2×2 13−x1 −x2 −13+x1 +x2 10−2×1 +x2 −10 + 2×1 −x2
+ 3×3 − 2×3 + 2×3 +x3 −x3
The initial dictionary is (predictably) infeasible.
University of Victoria – CSC 445/545 – Summer 2021
35
Equality Constraints and Slack Variables (5)
ζ = 0 + x1
w1 = 13 − x1
w2 =−13+ x1
w3 = 10 − 2×1
w4 =−10+2×1
+ 2×2 − x2 +x2 + x2 −x2
+ 3×3 − 2×3 + 2×3 + x3 −x3
Solving the auxiliary problem produces the feasible dictionary on the right.
University of Victoria – CSC 445/545 – Summer 2021 36
ζ = 81 + 2×2 − 1w4 + 7w2 5555
x1 = 33 + 1×2 + 2w4 + 1w2 5555
w1 = 0
w3 = 0
− w2 − w4
− 1w4 + 2w2
− 3×2
x3 = 16 5555
Equality Constraints and Slack Variables (6)
ζ = 0 + x1
w1 = 13 − x1
w2 =−13+ x1
w3 = 10 − 2×1
w4 =−10+2×1
+ 2×2 − x2 +x2 + x2 −x2
+ 3×3 − 2×3 + 2×3 + x3 −x3
Notice that since w2 is defined to be the negation of w1, either both will be basic or both will equal zero.
University of Victoria – CSC 445/545 – Summer 2021 37
ζ = 81 + 2×2 − 1w4 + 7w2 5555
x1 = 33 + 1×2 + 2w4 + 1w2 5555
w1 = 0
w3 = 0
− w2 − w4
− 1w4 + 2w2
− 3×2
x3 = 16 5555
Equality Constraints and Slack Variables (7)
ζ = 0 + x1
w1 = 13 − x1
w2 =−13+ x1
w3 = 10 − 2×1
w4 =−10+2×1
+ 2×2 − x2 +x2 + x2 −x2
+ 3×3 − 2×3 + 2×3 + x3 −x3
If both are basic and non-zero, one will be negative (and therefore the dictionary will be infeasible). Therefore, in any feasible dictionary, both paired slack variables for an equality constraint must be zero.
University of Victoria – CSC 445/545 – Summer 2021 38
ζ = 81 + 2×2 − 1w4 + 7w2 5555
x1 = 33 + 1×2 + 2w4 + 1w2 5555
w1 = 0
w3 = 0
− w2 − w4
− 1w4 + 2w2
− 3×2
x3 = 16 5555
Equality Constraints and Slack Variables (8)
ζ = 0 + x1
w1 = 13 − x1
w2 =−13+ x1
w3 = 10 − 2×1
w4 =−10+2×1
+ 2×2 − x2 +x2 + x2 −x2
+ 3×3 − 2×3 + 2×3 + x3 −x3
Additionally, notice that it is impossible to pivot both variables in a pair (e.g. the pair w1 and w2 or the pair w3 and w4) out of the basis. This is somewhat obvious in the dictionary above, but is also evident in a linear algebraic solution (any basis must contain exactly one of each pair to ensure linear independence).
University of Victoria – CSC 445/545 – Summer 2021 39
ζ = 81 + 2×2 − 1w4 + 7w2 5555
x1 = 33 + 1×2 + 2w4 + 1w2 5555
w1 = 0
w3 = 0
− w2 − w4
− 1w4 + 2w2
− 3×2
x3 = 16 5555
Equality Constraints and Slack Variables (9)
ζ = 0 + x1
w1 = 13 − x1
w2 =−13+ x1
w3 = 10 − 2×1
w4 =−10+2×1
+ 2×2 − x2 +x2 + x2 −x2
+ 3×3 − 2×3 + 2×3 + x3 −x3
As a result, notice that the dictionary above, which nominally has four constraints, really has a basis of size 2 (since two slots will always be occupied by parts of each equality constraint pair). In a sense, this reverses the expansion of the constraint system caused by replacing equality constraints with inequalities.
University of Victoria – CSC 445/545 – Summer 2021 40
ζ = 81 + 2×2 − 1w4 + 7w2 5555
x1 = 33 + 1×2 + 2w4 + 1w2 5555
w1 = 0
w3 = 0
− w2 − w4
− 1w4 + 2w2
− 3×2
x3 = 16 5555
Equality Constraints and Slack Variables (10)
ζ = 0 + x1
w1 = 13 − x1
w2 =−13+ x1
w3 = 10 − 2×1
w4 =−10+2×1
+ 2×2 − x2 +x2 + x2 −x2
+ 3×3 − 2×3 + 2×3 + x3 −x3
This effect is actually a consequence of the constraint doubling (the two inequalities created by splitting an equality constraint are not linearly independent), although the use of separate slack variables for each inequality makes it less obvious.
University of Victoria – CSC 445/545 – Summer 2021 41
ζ = 81 + 2×2 − 1w4 + 7w2 5555
x1 = 33 + 1×2 + 2w4 + 1w2 5555
w1 = 0
w3 = 0
− w2 − w4
− 1w4 + 2w2
− 3×2
x3 = 16 5555
Equality Constraints and Slack Variables (11)
ζ = 0 + x1
w1 = 13 − x1
w2 =−13+ x1
w3 = 10 − 2×1
w4 =−10+2×1
+ 2×2 − x2 +x2 + x2 −x2
+ 3×3 − 2×3 + 2×3 + x3 −x3
Although it is definitely possible to solve LPs of this form with the Simplex Method, if a large number of equality constraints were present in the original LP, a large number of degenerate pivots may be needed while solving the LP.
University of Victoria – CSC 445/545 – Summer 2021 42
ζ = 81 + 2×2 − 1w4 + 7w2 5555
x1 = 33 + 1×2 + 2w4 + 1w2 5555
w1 = 0
w3 = 0
− w2 − w4
− 1w4 + 2w2
− 3×2
x3 = 16 5555
Equality Constraints and Slack Variables (12)
ζ = 0 + x1
w1 = 13 − x1
w2 =−13+ x1
w3 = 10 − 2×1
w4 =−10+2×1
+ 2×2 − x2 +x2 + x2 −x2
+ 3×3 − 2×3 + 2×3 + x3 −x3
Besides implementation concerns, the main observation to make is that the slack variables for equality constraints will always equal zero at a feasible point, and have no real conceptual meaning (in a sense, they are placeholders to reduce the available slots in the basis).
University of Victoria – CSC 445/545 – Summer 2021 43
ζ = 81 + 2×2 − 1w4 + 7w2 5555
x1 = 33 + 1×2 + 2w4 + 1w2 5555
w1 = 0
w3 = 0
− w2 − w4
− 1w4 + 2w2
− 3×2
x3 = 16 5555
Equality Constraints and Slack Variables (13)
In general, an LP which has only equality constraints (but is otherwise in standard form) can be solved without creating any slack variables at all (since splitting equalities into inequalities and creating slack variables would ultimately have no effect on the size of the basis). The equational form matrix of such an LP will be identical to the original constraint matrix.
For example, in an LP like
max. c·x
s.t. Ax = b
x≥0
with n optimization variables and m constraints, the basis would have size m (and every
basic variable would be an optimization variable).
University of Victoria – CSC 445/545 – Summer 2021 44
Equality Constraints and Slack Variables (14)
However, using the constraint matrix directly as the equational form matrix (without creating slack variables) introduces one extra requirement: The matrix A must have full rank (i.e. rank m), since otherwise the basis matrix AB would never be invertible.
This issue does not occur when slack variables are added (since the slack variables “pad” the rank of the equational form matrix to ensure it has full rank). Cases where A does not have full rank are normally caused by redundant constraints (which will manifest as rows of A that are not linearly independent from other rows), and since redundant constraints are superfluous, they can be deleted from A without consequences. This will result in a matrix with full rank.
University of Victoria – CSC 445/545 – Summer 2021 45
Equality Constraints and Duality (1)
max. x1 + 2×2 + 3×3
s.t. x1 + x2 + 2×3 = 13 2×1 − x2 − x3 = 10
x1,x2,x3 ≥ 0
It is possible to construct the dual of LPs containing equality constraints by converting the LP to standard form, taking the dual of that, then simplifying. The dual of the standard form LP will have four non-negative dual variables, which can be simplified to two unconstrained dual variables.
University of Victoria – CSC 445/545 – Summer 2021 46
min. 13y1 + 10y2
s.t. y1+2y2≥1
y1 − y2 ≥ 2 2y1 − y2 ≥ 3
y1,y2 ∈ R
Equality Constraints and Duality (2)
max. x1 + 2×2 + 3×3
s.t. x1 + x2 + 2×3 = 13 2×1 − x2 − x3 = 10
x1,x2,x3 ≥ 0
By introducing slack variables directly into the dual LP, we can convert the ≥ inequalities to equalities (for symmetry with the primal LP). Note that the yi and zi variables could be conceptually meaningful (unlike the wi slack variables from earlier).
University of Victoria – CSC 445/545 – Summer 2021 47
min. 13y1 + 10y2
s.t. y1+2y2−z1=1
y1 − y2 − z2 = 2 2y1 − y2 − z3 = 3
y1,y2 ∈ R z1,z2 ≥ 0
Equality Constraints and Duality (3)
max. x1 + 2×2 + 3×3
s.t. x1 + x2 + 2×3 = 13 2×1 − x2 − x3 = 10
x1,x2,x3 ≥ 0
Question: Why does the introduction of a non-negative zi term to each constraint allow the constraint to be converted to an equality?
University of Victoria – CSC 445/545 – Summer 2021 48
min. 13y1 + 10y2
s.t. y1+2y2−z1=1
y1 − y2 − z2 = 2 2y1 − y2 − z3 = 3
y1,y2 ∈ R z1,z2 ≥ 0
Equality Constraints and Duality (4)
min. x1 + 2×2 + 3×3
s.t. x1 + x2 + 2×3 = 13 2×1 − x2 − x3 = 10
x1,x2,x3 ≥ 0
In the case where the primal problem is a minimization problem (as in a minimum-cost flow problem), the form of the dual is slightly different (notice that each zi is added, not subtracted). The signs of the y variables are unaffected, mostly as a consequence of the way unconstrained variables are derived from the dual representation.
University of Victoria – CSC 445/545 – Summer 2021 49
max. 13y1 + 10y2
s.t. y1+2y2+z1=1
y1 − y2 + z2 = 2 2y1 − y2 + z3 = 3
y1,y2 ∈ R z1,z2 ≥ 0
Network Simplex (1)
If our goal were simply to present network flows as an application of linear programming, we could stop here. There are several other variations of the minimum cost network flow problem that can also be converted to linear programs and solved with the usual method (we will see those shortly).
However, the LPs produced by network flow problems have a unique structure, and there are also graph theoretic properties that are available from the network but not necessarily to the linear programming solver. Additionally, there are properties of the LP formulation of network problems (such as the large number of equality constraints, which lead to degenerate slack variables) that might frustrate a typical LP solver.
University of Victoria – CSC 445/545 – Summer 2021 50
Network Simplex (2)
Since there are so many network-related optimization problems to solve, it is useful to specialize the Simplex Method for this type of problem.
The resulting procedure will be the Network Simplex Method, which uses the same foundations as the Simplex Method (e.g. a basis, the idea of a pivot, etc.) but with a graph theoretic interpretation of each aspect.
University of Victoria – CSC 445/545 – Summer 2021 51