More on Linear Programming
Aleks Ignjatovic
.edu.au
THE UNIVERSITY OF
NEW SOUTH WALES
School of Computer Science and Engineering
The University of New South Wales
Sydney 2052, Australia
We now move to one of the most important cases of convex programming,
called Linear Programming, (LP), in which the objective is a linear function
and the convex domain over which the extremum is sought is defined by con-
straints which are also linear functions. We follow closely our old COMP3121
textbook by Cormen, Leiserson, Rivest and Stein, introduction to Algorithms.
We start by defining a common representations of Linear Programming opti-
mization problems.
In the standard form the objective to be maximized is given by
f(x) =
n∑
j=1
cj xj ,
and the constraints are of the form
gi(x) ≤ bi, 1 ≤ i ≤ m; (1)
xj ≥ 0, 1 ≤ j ≤ n, (2)
where
gi(x) =
n∑
j=1
aijxj ; 1 ≤ i ≤ m. (3)
Note that x represents a vector, x = 〈x1, . . . , xn〉, and aij are reals. The above
somewhat messy formulation can be reformulated in a much more compact ma-
trix form. To get a very compact representation of linear programs let us intro-
duce a partial ordering on vectors x ∈ Rn by x ≤ y if and only if such inequalities
hold coordinate-wise, i.e., if and only if xj ≤ yj for all 1 ≤ i ≤ n. Recall that vec-
tors are written as a single column matrices; thus, letting c = 〈c1, . . . , cn〉 ∈ Rn
and b = 〈b1, . . . bm〉 ∈ Rm, and letting A be the matrix A = (aij) of size m× n,
we get that the above problem can be formulated simply as:
maximize cTx
subject to the following two (matrix-vector) constraints:1 Ax ≤ b and x ≥ 0.
Thus, to specify a Linear Programming optimization problem we just have
to provide a triplet (A, b, c), and the information that the triplet represents an
LP problem in the standard form.
Wile in general the “natural formulation” of a problem into a Linear Pro-
gram does not necessarily produce the non-negativity constrains (2) for all of
the variables, in the standard form such constraints are indeed required for all
of the variables. This poses no problem, because each occurrence of an uncon-
strained variable xj can be replaced by the expression x
′
j − x
∗
j where x
′
j , x
∗
j are
new variables satisfying the constraints x′j ≥ 0, x
∗
j ≥ 0.
1Note that the inequality involved in the constraints is the partial ordering on vectors
which we have just introduced above. Also, we are slightly abusing the notation because in
the non-negativity constraint, 0 actually represents a vector 0 ∈ Rn with all coordinates equal
to 0.
1
Any vector x which satisfies the two constraints is called a feasible solution,
regardless of what the corresponding objective value cTx might be. Note that
the set of feasible solutions, i.e., the domain over which we seek to maximize the
objective, is a convex set because it is an intersection of the half spaces defined
by each of the constraints.
As an example, let us consider the following optimization problem:
maximize 3×1 + x2 + 2×3 (4)
subject to the constraints
x1 + x2 + 3×3 ≤ 30 (5)
2×1 + 2×2 + 5×3 ≤ 24 (6)
4×1 + x2 + 2×3 ≤ 36 (7)
x1, x2, x3 ≥ 0 (8)
How large can the value of the objective z(x1, x2, x3) = 3×1 + x2 + 2×3 be,
without violating the constraints? If we add inequalities (5) and (6), we get
3×1 + 3×2 + 8×3 ≤ 54
Since all variables are constrained to be non-negative, we are assured that
3×1 + x2 + 2×3 ≤ 3×1 + 3×2 + 8×3 ≤ 54
The far left hand side of this equation is just the objective (4); thus z(x1, x2, x3)
is bounded above by 54, i.e., z(x1, x2, x3) ≤ 54.
Can we obtain a tighter bound? We could try to look for coefficients
y1, y2, y3 ≥ 0 to be used to for a linear combination of the constraints:
y1(x1 + x2 + 3×3) ≤ 30y1
y2(2×1 + 2×2 + 5×3) ≤ 24y2
y3(4×1 + x2 + 2×3) ≤ 36y3
Then, summing up all these inequalities and factoring, we get
x1(y1 + 2y2 + 4y3) + x2(y1 + 2y2 + y3) + x3(3y1 + 5y2 + 2y3)
≤ 30y1 + 24y2 + 36y3 (9)
If we compare this with our objective (4) we see that if we choose y1, y2 and y3
so that:
y1 + 2y2 + 4y3 ≥ 3
y1 + 2y2 + y3 ≥ 1
3y1 + 5y2 + 2y3 ≥ 2
2
then
x1(y1 + 2y2 + 4y3) + x2(y1 + 2y2 + y3) + x3(3y1 + 5y2 + 2y3) ≥ 3×3 + x2 + 2×3
Combining this with (9) we get:
30y1 + 24y2 + 36y3 ≥ 3×1 + x2 + 2×3 = z(x1, x2, x3)
Consequently, in order to find as tight upper bound for our objective z(x1, x2, x3)
we have to look for y1, y2, y3 which produce the smallest possible value of
z∗(y1, y2, y3) = 30y1 + 24y2 + 36y3, but which do not violate the constraints
y1 + 2y2 + 4y3 ≥ 3 (10)
y1 + 2y2 + y3 ≥ 1 (11)
3y1 + 5y2 + 2y3 ≥ 2 (12)
y1, y2, y3 ≥ 0 (13)
Thus, trying to find the best upper bound for our objective z(x1, x2, x3) obtained
by forming a linear combination of the constraints only reduces the original
maximization problem to a minimization problem:
minimize 30y1 + 24y2 + 36y3
subject to the constraints (10-13)
Such minimization problem P ∗ is called the dual problem of the initial problem
P .
Let us now repeat the whole procedure with P ∗ in place of P , i.e., let us find
the dual program (P ∗)∗ of P ∗. We are now looking for non negative multipliers
z1, z2, z3 ≥ 0 to multiply inequalities (10-12) and obtain
z1(y1 + 2y2 + 4y3) ≥ 3z1
z2(y1 + 2y2 + y3) ≥ z2
z3(3y1 + 5y2 + 2y3) ≥ 2z3
Summing these up and factoring produces
y1(z1 + z2 + 3z3) + y2(2z1 + 2z2 + 5z3) + y3(4z1 + z2 + 2z3) ≥ 3z1 + z2 + 2z3
(14)
If we choose these multiples so that
z1 + z2 + 3z3 ≤ 30 (15)
2z1 + 2z2 + 5z3 ≤ 24 (16)
4z1 + z2 + 2z3 ≤ 36 (17)
we will have:
y1(z1 + z2 + 3z3) + y2(2z1 + 2z2 + 5z3) + y3(4z1 + z1 + 2z3) ≤ 30y1 + 24y2 + 36y3
Combining this with (14) we get
3z1 + z2 + 2z3 ≤ 30y1 + 24y2 + 36y3
3
Consequently, finding the dual program (P ∗)∗ of P ∗ amounts to maximizing
the objective 3z1 + z2 + 2z3 subject to the constraints (15-17). But notice that,
except for having different variables, (P ∗)∗ is exactly our starting program P !
Thus, the dual program (P ∗)∗ for program P ∗ is just P itself, i.e., (P ∗)∗ = P .
So, at the first sight, looking for the multipliers y1, y2, y3 did not help much,
because it only reduced a maximization problem to an equally hard minimization
problem. Well, perhaps it still maybe easier to somehow solve both problems
at the same, and this is precisely what the SIMPLEX algorithms does.2
To find the maximal value of 3×1 + x2 + 2×3 subject to the constraints
x1 + x2 + 3×3 ≤ 30
2×1 + 2×2 + 5×3 ≤ 24
4×1 + x2 + 2×3 ≤ 36
let us start with x1 = x2 = x3 = 0 and ask ourselves: how much can we increase
x1 without violating the constraints? Since x1 +x2 +3×3 ≤ 30 we can introduce
a new variable x4 such that x4 ≥ 0 and
x4 = 30− (x1 + x2 + 3×3) (18)
Since such variable measures how much “slack” we got between the actual value
of x1+x2+3×3 and its upper limit 30, such x4 is called a slack variable. Similarly
we introduce new variables x5, x6 requiring them to satisfy x5, x6 ≥ 0 and let
x5 = 24− 2×1 − 2×2 − 5×3 (19)
x6 = 36− 4×1 − x2 − 2×3 (20)
Since we started with the values x1 = x2 = x3 = 0, this implies that these new
slack variables must have values x4 = 30, x5 = 24, x6 = 36, or as a single
vector, the initial basic feasible solution is (
x1
0 ,
x2
0 ,
x3
0 ,
x4
30,
x5
24,
x6
36). Note that “fea-
sible” refers merely to the fact that all of the constraints are satisfied.3
Now we see that (18) implies that x1 cannot exceed 30, and (19) implies
that 2×1 ≤ 24, i.e., x1 ≤ 12, while (20) implies that 4×1 ≤ 36, i.e., x1 ≤ 9. Since
all of these conditions must be satisfied we conclude that x1 cannot exceed 9,
which is the upper limit coming from the constraint (20).
If we set x1 = 9, this forces x6 = 0. We now swap the roles of x1 and x6:
since we cannot increase x1 any more, we eliminate x1 from the right hand sides
of the equations (18-20) and from the objective, introducing instead variable x6
2It is now useful to remember how we proved that the Ford – Fulkerson Max Flow algorithm
in fact produces a maximal flow, by showing that it terminates only when we reach the capacity
of a (minimal) cut!
3Clearly, setting all variables to 0 does not always produce a basic feasible solution because
this might violate some of the constraints; this would happen, for example, if we had a
constraint of the form −x1 +x2 +x3 ≤ −3; choosing an initial basic feasible solution requires
a separate algorithm to “bootstrap” the SIMPLEX algorithm – see for the details our (C-L-
R-S) textbbok.
4
to the right hand side of the constraints and into the objective. To do that, we
solve equation (20) for x1:
x1 = 9−
x2
4
−
x3
2
−
x6
4
and eliminate x1 from the right hand side of the remaining constraints and the
objective to get:
z = 3
(
9−
x2
4
−
x3
2
−
x6
4
)
+ x2 + 2×3
= 27−
3
4
x2 −
3
2
x3 −
3
4
x6 + x2 + 2×3
= 27 +
1
4
x2 +
1
2
x3 −
3
4
x6
x5 = 24− 2
(
9−
x2
4
−
x3
2
−
x6
4
)
− 2×2 − 5×3
= 6 +
x2
2
+ x3 +
x6
2
− 2×2 − 5×3
= 6−
3
2
x2 − 4×3 +
x6
2
x4 = 30−
(
9−
x2
4
−
x3
2
−
x6
4
)
− x2 − 3×3
= 21 +
x2
4
+
x3
2
+
x6
4
− x2 − 3×3
= 21−
3
4
x2 +
5
2
x3 +
x6
4
To summarise: the “new” objective is
z = 27 +
1
4
x2 +
1
2
x3 −
3
4
x6
and the “new constraints” are
x1 = 9−
x2
4
−
x3
2
−
x6
5
(21)
x4 = 21−
3
4
x2 −
5
2
x3 +
x6
4
(22)
x5 = 6−
3
2
x2 − 4×3 +
x6
2
(23)
Our new basic feasible solution replacing (
x1
0 ,
x1
0 ,
x3
0 ,
x4
30,
x5
24,
x6
36) is obtained by set-
ting all the variables on the right to zero, thus obtaining (
x1
9 ,
x2
0 ,
x3
0 ,
x4
21,
x5
6 ,
x6
0 ).
NOTE: These are EQUIVALENT constraints and objectives; the old ones were
only transformed to an equivalent form. Any values of the variables will produce
exactly the same value in both forms of the objective and they will satisfy the
first set of constraints if and only if they satisfy the second set.
So x1 and x6 have switched their roles; x1 acts as a new basic variable,
and the new basic feasible solution is: (
x1
9 ,
x1
0 ,
x3
0 ,
x4
21,
x5
6 ,
x6
0 ); the new value of the
objective is z = 27 + 1
4
0 + 1
2
0− 3
4
0 = 27. We will continue this process of find-
ing basic feasible solutions which increase the value of the objective, switching
5
which variables are used to measure the slack and which are on the right hand
side of the constraint equations and in the objective. The variables on the left
are called the basic variables and the variables on the right are the non basic
variables.
We now choose another variable with a positive coefficient in the objective,
say x3 (we could also have chosen x2). How much can we increase it?
From (21) we see that x3
2
must not exceed 9, otherwise x1 will become
negative. Thus x3 cannot be larger than 18. Similarly,
5
2
x3 cannot exceed
21, otherwise x4 will become negative, and so x3 ≤ 425 ; similarly, 4×3 cannot
exceed 6, ie, x3 ≤ 32 . Thus, in order for all constraints to remain valid, x3
cannot exceed 3
2
. Thus we increase x3 to
3
2
; equation (23) now forces x5 to zero.
We now eliminate x3 from the right hand side of the constraints and from the
objective, taking it as a new basic variable:
4×3 = 6−
3
2
x2 − x5 +
x6
2
i.e.,
x3 =
3
2
−
3
8
x2 −
1
4
x5 +
1
8
x6 (24)
After eliminating x3 by substitution using (24), the objective now becomes:
z =27−
1
4
x2 +
1
2
(
3
2
−
3
8
x2 −
1
4
x5 +
1
8
x6
)
−
3
4
x6 =
111
4
+
1
16
x2 −
1
8
x5 −
11
6
x6 (25)
Using (24) to eliminate x3 from the constraints, after simplifications we get the
new constraints:
x1 =
33
4
−
x2
16
+
x5
8
−
5×6
16
(26)
x3 =
3
2
−
3×2
8
−
x5
4
+
x6
8
(27)
x4 =
69
4
+
3×2
16
+
5×3
8
−
x6
16
(28)
Our new basic solution is again obtained using the fact that all variables on the
right and in the objective, including the newly introduced non-basic variable
x5, are equal to zero, i.e., the new basic feasible solution is (
x1
33
4
,
x2
0 ,
x3
3
2
,
x4
69
4
,
x5
0 ,
x6
0 )
and the new value of the objective is z = 111
4
.
Comparing this with the previous basic feasible solution (
x1
9 ,
x1
0 ,
x3
0 ,
x4
21,
x5
6 ,
x6
0 ) we
see that in the new basic feasible solution the value of x1 dropped from 9 to
33/4; however, this now has no effect on the value of the objective because x1
no longer appears in the objective; all the variables appearing in the objective
(thus, the non-basic variables) always have value 0.
We now see that the only variable in the objective (25) appearing with a
positive coefficient is x2. How much can we increase it without violating the new
6
constraints? The first constraint (26) implies that x2
16
≤ 33
4
, i.e., that x2 ≤ 132;
the second constraint (27) implies that 3×2
8
≤ 3
2
, i.e., that x2 ≤ 4. Note that
the third constraint (28) does not impose any restrictions on how large x2 can
be, for as long as it is positive; thus, we conclude that the largest possible value
of x2 which does not cause violation of any of the constraints is x2 = 4, which
corresponds to constraint (27). The value x2 = 4 forces x3 = 0; we now switch
the roles of x2 and x3 (this operation of switching the roles of two variables is
called pivoting) by solving (27) for x2:
x2 = 4−
8×2
3
−
2×5
3
+
x6
3
and then using this to eliminate x2 from the objective, obtaining
z = 28−
x3
6
−
x5
6
−
2×6
3
as well as from the constraints, obtaining after simplification
x1 = 8 +
x3
6
+
x5
6
−
x6
3
(29)
x2 = 4−
8×3
3
−
2×5
3
+
x6
3
(30)
x4 = 18−
x3
2
+
x5
2
(31)
which produces the new basic feasible solution (
x1
8 ,
x2
4 ,
x3
0 ,
x4
18,
x5
0 ,
x6
0 ) with the new
value of the objective z = 28. Note that in the new objective all the variables
appear with a negative coefficient; thus our procedure terminates, but did it
find the maximum value of the objective? Maybe with a different choices of
variables in pivoting we would have come up with another basic feasible solution
which would have different basic variables, also with all non basic variables in
the objective appearing with a negative coefficient, but for which the obtained
value of the objective is larger?
This is not the case: just as in the case of the Ford Fulkerson algorithm
for Max Flow, once the pivoting terminates, the solution must be optimal re-
gardless of which particular variables where swapped in pivoting, because the
pivoting terminates when the corresponding basic feasible solution of the pro-
gram becomes equal to a basic feasible solution of the dual program. Since
every feasible solution of the dual is larger than every feasible solution of the
starting (or primal) program, we get that the SIMPLEX algorithm must return
the optimal value after it terminates. We now explain this in more detail.
7
1 LP Duality
General setup
Comparing our initial program P with its dual P ∗:
P : maximize 3×1 + x2 + 2×3,
subject to the constraints
x1 + x2 + 3×3 ≤ 30
2×1 + 2×3 + 5×3 ≤ 24
4×1 + x2 + 2×3 ≤ 36
x1, x2, x3 ≥ 0;
P ∗ : minimize 30y1 + 24y2 + 36y3,
subject to the constraints
y1 + 2y2 + 4y3 ≥ 3
y1 + 2y2 + y3 ≥ 1
3y1 + 5y2 + 2y3 ≥ 2
y1, y2, y3 ≥ 0.
we see that the original, primal Linear Program P and its dual Linear Program
are related as follows
P : maximize z(x) =
n∑
j=1
cjxj ,
subject to the constraints
n∑
j=1
aijxj ≤ bi; 1 ≤ i ≤ m
x1, . . . , xn ≥ 0;
P ∗ : minimize z∗(y) =
m∑
i=1
biyi,
subject to the constraints
m∑
i=1
aijyi ≥ cj ; 1 ≤ j ≤ n
y1, . . . , ym ≥ 0,
or, in matrix form,
P : maximize z(x) = cTx, subject to the constraints Ax ≤ b and x ≥ 0;
P ∗ : minimize z∗(y) = bT y, subject to the constraints AT y ≥ c and y ≥ 0.
8
Weak Duality Theorem If x = 〈x1, . . . , xn〉 is any basic feasible solution
for P and y = 〈y1, . . . , ym〉 is any basic feasible solution for P ∗, then:
z(x) =
n∑
j=1
cjxj ≤
n∑
i=1
biyi = z
∗(y)
Proof: Since x and y are basic feasible solutions for P and P ∗ respectively, we
can use the constraint inequalities, first from P ∗ and then from P to obtain
z(x) =
n∑
j=1
cjxj ≤
n∑
j=1
(
m∑
i=1
aijyi
)
xj =
m∑
i=1
n∑
j=1
aijxj
yi ≤ n∑
i=1
biyi = z
∗(y)
Thus, every feasible solution of P ∗ is an upper bound for the set of all feasible
solutions of P , and every feasible solution of P is a lower bound for the set of
feasible solutions for P ∗; see the figure below.
Solutions for P
Solutions for P*
Consequently, if we find a feasible solution of P which is also a feasible solution
for P ∗, such solution must be maximal feasible solution for P and minimal fea-
sible solution for P ∗.
We now show that when the SIMPLEX algorithms terminates that it pro-
duces a basic feasible solution x for P , and, implicitly, a basic feasible solution
y for the dual P ∗ for which z(x) = z∗(y); by the above, this will imply that
z(x) is the maximal value for the objective of P and that z∗(y) is the minimal
value of the objective for P ∗.
Assume that the SIMPLEX algorithm has terminated; let B be such that
the basic variables (variables on the left hand side of the constraint equations) in
the final form of P are variables xi for which i ∈ B; let N = {1, 2, . . . , n+m}\B;
then xj for j ∈ N are all the non-basic variables in the final form of P . Since the
SIMPLEX algorithm has terminated, we have also obtained a set of coefficients
cj ≤ 0 for j ∈ N , as well as v such that the final form of the objective is
z(x) = v +
∑
j∈N
cjxj
If we set all the final non-basic variables xj , j ∈ N , to zero, we obtain a basic
feasible solution x for which z(x) = v.
9
Let us define cj = 0 for all j ∈ B; then
z(x) =
n∑
j=1
cjxj
= v +
n+m∑
j=1
cjxj
= v +
n∑
j=1
cjxj +
n+m∑
i=n+1
cixi
= v +
n∑
j=1
cjxj +
m∑
i=1
cn+ixn+i
Since the variables xn+i, (1 ≤ i ≤ m), are the initial slack variables, they satisfy
xn+i = bi −
∑n
j=1 aijxj ; thus we get
z(x) =
n∑
j=1
cjxj
= v +
n∑
j=1
cjxj +
m∑
i=1
cn+i
bi − n∑
j=1
aijxj
= v +
n∑
j=1
cjxj +
m∑
i=1
cn+ibi −
m∑
i=1
n∑
j=1
cn+iaijxj
= v +
n∑
j=1
cjxj +
m∑
i=1
cn+ibi −
n∑
j=1
m∑
i=1
cn+iaijxj
= v +
m∑
i=1
cn+ibi +
n∑
j=1
(
cj −
m∑
i=1
cn+iaij
)
xj
The above equations hold true for all values of x; thus, comparing the first and
the last equation we conclude that
v +
m∑
i=1
cn+ibi = 0;
cj −
m∑
i=1
cn+iaij = cj , (1 ≤ j ≤ n).
i.e.,
m∑
i=1
bi(−cn+i) = v;
m∑
i=1
aij(−cn+i) = cj + (−cj), (1 ≤ j ≤ n).
10
We now see that if we set yi = −cn+i for all 1 ≤ i ≤ m, then, since the
SIMPLEX terminates when all coefficients of the objective are either negative
or zero, then such y satisfies:
m∑
i=1
biyi = v;
m∑
i=1
aijyi = cj − cj ≥ cj , (1 ≤ j ≤ n),
yi ≥ 0, (1 ≤ i ≤ m).
Thus, such y is a basic feasible solution for the dual program P ∗ for which
the dual objective has the same value v which the original, primal program P
achieves for the basic feasible solution x. Thus, by the Weak Duality Theorem,
we conclude that v is the maximal feasible value of P and minimal feasible value
for P ∗.
Note also that the basic and non basic variables of the final primal form of
the problem and of its dual are complementary: for every 1 ≤ i ≤ m, variable
xn+i is basic for the final form of the primal if and only if yi is non basic for the
final form of the dual; (similarly, for every 1 ≤ j ≤ n, variable xj is basic for
the final form of the primal if and only if ym+j is not basic for the final form
of the dual). Since the basic variables measure the slack of the corresponding
basic feasible solution, we get that if x and y are the extremal feasible solutions
11
for P and P ∗, respectively, then for all 1 ≤ j ≤ n and all 1 ≤ i ≤ m,
either xj = 0 or ym+j = 0, i.e.,
m∑
i=0
aijyi = cj ;
either yi = 0 or xn+i = 0, i.e.,
n∑
j=0
aijxj = bi.
Note that any equivalent form of P which is obtained through a pivoting
operation is uniquely determined by its corresponding set of basic variables.
Assuming that we have n variables and m equations, then there are
(
n+m
m
)
choices for the set of basic variables. Using the Stirling formula
n! ≈
√
2πn
(n
e
)n
⇒ lnn! ≈
ln(2πn)
2
+ n lnn− n = n lnn− n+O(lnn)
we get
ln
(
n+m
m
)
= ln
(m+ n)!
m!n!
= ln(m+ n)!− lnm!− lnn!
= (m+ n) ln(m+ n)− (m+ n)− n lnn−m lnm+m+ n
= m(ln(m+ n)− lnm) + n(ln(m+ n)− lnn)
≥ m+ n
Thus, the total number of choices for the set of the basic variables is
(
n+m
m
)
>
em+n. This implies that the SIMPLEX algorithm could potentially run in ex-
ponential time, and in fact, one can construct examples of LP on which the
run time of the SIMPLEX algorithm is exponential. However, in practice the
SIMPLEX algorithm is extremely efficient, even for large problems with thou-
sands of variables and constraints, and it tends to outperform algorithms for LP
which do run in polynomial time (the Ellipsoid Method and the Interior Points
Method).
1.1 Examples of dual programs: max flow
We would now like to formulate the Max Flow problem in a flow network as a
Linear Program.
Thus, assume we are given a flow network G with capacities κij of all edges
(i, j) ∈ G. The max flow problem seeks to maximize the flows through a network
12
flow graph G, subject to the constraints:
C∗
fij ≤ κij ; (i, j) ∈ G; (flow smaller than pipe’s capacity)∑
i : (i,j)∈G fij =
∑
k : (j,k)∈G fjk; j ∈ G; (incoming flow equals outgoing)
fij ≥ 0; (i, j) ∈ G (no negative flows).
To eliminate the equality in the second constraint in C∗ while introducing only
one rather than two inequalities, we use a “trick”: we make the flow circular, by
connecting the sink t with the source s with a pipe of infinite capacity. Thus,
we now have a new graph G′, G ⊂ G′, with an additional edge (t, s) ∈ G′ with
capacity ∞.
We can now formulate the Max Flow problem as a Linear Program by replacing
the equality in the second constraint with a single but equivalent inequality:
P: maximize: fts
subject to the constraints:
fij ≤ κij ; (i, j) ∈ G;∑
i : (i,j)∈G′
fij −
∑
k : (j,k)∈G′
fjk ≤ 0; j ∈ G;
fij ≥ 0; (i, j) ∈ G′.
Thus, the coefficients cij of the primal P are zero for all variables fij except
for fts which is equal to 1, i.e.,
z(f) =
∑
ij
0 · fij + 1 · fts (1.1)
To obtain the dual of P we look for coefficients dij , (i, j) ∈ G corresponding
to the first set of constraints, and coefficients pj , j ∈ G corresponding to the
second set of constraints to use as multipliers of the constraints:
fijdij ≤ κij dij ; (i, j) ∈ G;∑
i : (i,j)∈G′
fijpj −
∑
k : (j,k)∈G′
fjkpj ≤ 0; j ∈ G.
13
note the two special cases of the second inequality involving fts are∑
i : (i,t)∈G
fitpt − ftspt ≤ 0;
ftsps −
∑
k : (s,k)∈G
fskps ≤ 0.
Summing these inequalities and factoring out, we get∑
(i,j)∈G
(dij − pi + pj)fij + (pt − ps)fts ≤
∑
(i,j)∈G
κijdij
Thus, the dual objective is the right hand side of the above inequality, and, as
before, the dual constraints are obtained by comparing the coefficients of the
left hand side with the coefficients of the objective:
P ∗ : minimize:
∑
(i,j)∈G κijdij
subject to the constraints:
dij − pi + pj ≥ 0 (i, j) ∈ G
ps − pt ≥ 1
dij ≥ 0 (i, j) ∈ G
pi ≥ 0 i ∈ G
Let us write the constraints of P using new slack variables ψij , ϕj :
ψij = κij − fij ; (i, j) ∈ G;
ϕj =
∑
k : (j,k)∈G′
fjk −
∑
i : (i,j)∈G′
fij ; j ∈ G;
fij ≥ 0; (i, j) ∈ G′;
ψij ≥ 0; (i, j) ∈ G′;
ϕj ≥ 0; j ∈ G
Note now an important feature of both P and P ∗: all variables fij , ψij , ϕj in P
(and also all variables dij , pi in P
∗) appear only with the coefficient ±1. One
can now see that, if we solve the above constraint equations for any subset of
the set of all variables {fij , ψij , ϕj : (i, j) ∈ G∗, j ∈ G} as the set of the basic
variables, all the coefficients cij in the new objective which multiply ψij or ϕj
and which are obtained after the corresponding substitutions removing the ba-
sic variables from the objective will have coefficients either 0 or 1.1 This means
that in the corresponding basic feasible solution of P ′ at which the minimal
value of the dual program is obtained, also all values dij of dij and all values pj
of pj will be either 0 or 1.
What is the interpretation of such solution of the dual Linear Program P ∗?
Let us consider the set A of all vertices j of G for which pj = 1 and the set B of
1This corresponds to the fact that such constraints define a polyhedra whose all vertices
have coordinates which are all either 0 or 1.
14
all vertices j for which pj = 0. Then A∪B = G and A∩B = ∅. The constraint
ps − pt ≥ 1 of P ∗ implies that ps = 1 and pt = 0, i.e., s ∈ A and t ∈ B. Thus,
A and B define a cut in the flow network. Since at points p, d the objective∑
(i,j)∈G κijdij achieves the minimal value, the constraint dij − pi + pj ≥ 0 im-
plies that dij = 1 if and only if pi = 1 and pj = 0, i.e., if and only the edge
(i, j) has crossed from set A into set B. Thus, the minimum value of the dual
objective
∑
(i,j)∈G κijdij precisely corresponds to the capacity of the cut defined
by A,B. Since such value is equal to the maximal value of the flow defined by
the primal problem, we have obtained a maximal flow and minimal cut in G!
As we have mentioned, the extreme values of linear optimization problems
are always obtained on the vertices of the corresponding constraint polyhedra.
In this particular case all vertices are with 0, 1 coordinates; however, in general
this is false. For example, NP hard problems formulated as Linear Program-
ming problems always result in polyhedra with non-integer vertices.
Theorem: Solving an Integer Linear Program (ILP), i.e., an LP with additional
constraints that the values of all variables must be integers is NP hard, i.e., there
cannot be a polynomial time algorithm for solving ILPs (unless an extremely
unlikely thing happens, namely that P = NP ).
15