Algorithms: COMP3121/9101
THE UNIVERSITY OF
NEW SOUTH WALES
Algorithms:
COMP3121/9101
School of Computer Science and Engineering
University of New South Wales
10. LINEAR PROGRAMMING
COMP3121/9101 1 / 18
Linear Programming problems – Example 1
Problem:
You are given a list of food sources f1, f2, . . . , fn;
for each source fi you are given:
its price per gram pi;
the number of calories ci per gram, and
for each of 13 vitamins V1, V2, . . . , V13 you are given the content
v(i, j) of milligrams of vitamin Vj in one gram of food source fi.
Your task: to find a combination of quantities of food sources such that:
the total number of calories in all of the chosen food is equal to a
recommended daily value of 2000 calories;
the total intake of each vitamin Vj is at least the recommended
daily intake of wj milligrams for all 1 ≤ j ≤ 13;
the price of all food per day is as low as possible.
COMP3121/9101 2 / 18
Linear Programming problems – Example 1 cont.
To obtain the corresponding constraints let us assume that we take xi
grams of each food source fi for 1 ≤ i ≤ n. Then:
the total number of calories must satisfy
n∑
i=1
xici = 2000;
for each vitamin Vj the total amount in all food must satisfy
n∑
i=1
xiv(i, j) ≥ wj (1 ≤ j ≤ 13);
an implicit assumption is that all the quantities must be
non-negative numbers,
xi ≥ 0, 1 ≤ i ≤ n.
Our goal is to minimise the objective function which is the total cost
y =
n∑
i=1
xipi.
Note that all constraints and the objective function, are linear.
COMP3121/9101 3 / 18
Linear Programming problems – Example 2
Problem:
Assume now that you are politician and you want to make certain
promises to the electorate which will ensure that your party will win in
the forthcoming elections.
You can promise that you will build
a certain number of bridges, each 3 billion a piece;
a certain number of rural airports, each 2 billion a piece, and
a certain number of olympic swimming pools each a billion a piece.
You were told by your wise advisers that
each bridge you promise brings you 5% of city votes, 7% of
suburban votes and 9% of rural votes;
each rural airport you promise brings you no city votes, 2% of
suburban votes and 15% of rural votes;
each olympic swimming pool promised brings you 12% of city votes,
3% of suburban votes and no rural votes.
In order to win, you have to get at least 51% of each of the city,
suburban and rural votes.
You wish to win the election by cleverly making a promise that appears
that it will blow as small hole in the budget as possible, i.e., that the
total cost of your promises is as low as possible.
COMP3121/9101 4 / 18
Linear Programming problems – Example 2
We can let the number of bridges to be built be xb, number of airports
xa and the number of swimming pools xp.
We now see that the problem amounts to minimising the objective
y = 3xb + 2xa + xp, while making sure that the following constraints are
satisfied:
0.05xb + 0.12xp ≥ 0.51 (securing majority of city votes)
0.07xb + 0.02xa + 0.03xp ≥ 0.51 (securing majority of suburban votes)
0.09xb + 0.15xa ≥ 0.51 (securing majority of rural votes)
xb, xa, xp ≥ 0.
However, there is a very significant difference with the first example:
you can eat 1.56 grams of chocolate, but
you cannot promise to build 1.56 bridges, 2.83 airports and 0.57
swimming pools!
The second example is an example of an Integer Linear
Programming problem, which requires all the solutions to be integers.
Such problems are MUCH harder to solve than the “plain” Linear
Programming problems whose solutions can be real numbers.
COMP3121/9101 5 / 18
Linear Programming problems
In the standard form the objective to be maximised is given by
n∑
j=1
cj xj
the constraints are of the form
n∑
j=1
aijxj ≤ bi, 1 ≤ i ≤ m; (1)
xj ≥ 0, 1 ≤ j ≤ n, (2)
Let the boldface x represent a (column) vector, x = 〈x1 . . . xn〉T.
To get a more compact representation of linear programs we introduce a
partial ordering on vectors x ∈ Rn by x ≤ y if and only if the
corresponding inequalities hold coordinate-wise, i.e., if and only if
xj ≤ yj for all 1 ≤ j ≤ n.
COMP3121/9101 6 / 18
Linear Programming
Letting c = 〈c1 . . . cn〉T ∈ Rn and b = 〈b1 . . . bm〉T ∈ 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:
Ax ≤ b
and
x ≥ 0.
Thus, to specify a Linear Programming optimisation problem we just
have to provide a triplet (A, b, c);
This is the usual form which is accepted by most standard LP solvers.
COMP3121/9101 7 / 18
Linear Programming
The value of the objective for any value of the variables which makes the
constraints satisfied is called a feasible solution of the LP problem.
Equality constraints of the form
∑n
i=1 aijxi = bj can be replaced by two
inequalities:
∑n
i=1 aijxi ≥ bj and
∑n
i=1 aijxi ≤ bj ; thus, we can assume
that all constraints are inequalities.
In general, a “natural formulation” of a problem as a Linear Program
does not necessarily produce the non-negativity constrains for all of the
variables.
However, in the standard form such constraints are required for all of the
variables.
This poses no problem, because each occurrence of an unconstrained
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.
If x = (x1, . . . , xn) is a vector, we let |x| = (|x1|, . . . , |xn|). Some
problems are naturally translated into constraints of the form |Ax| ≤ b.
This also poses no problem because we can replace such constraints with
two linear constraints: Ax ≤ b and −Ax ≤ b because |x| ≤ y if and only
if x ≤ y and −x ≤ y.
COMP3121/9101 8 / 18
Linear Programming – Standard Form
Standard Form: maximize cTx subject to Ax ≤ b and x ≥ 0.
Any vector x which satisfies the two constraints is called a feasible
solution, regardless of what the corresponding objective value cTx might
be.
As an example, let us consider the following optimisation problem:
maximize z(x1, x2, x3) = 3×1 + x2 + 2×3 (3)
subject to the constraints
x1 + x2 + 3×3 ≤ 30 (4)
2×1 + 2×2 + 5×3 ≤ 24 (5)
4×1 + x2 + 2×3 ≤ 36 (6)
x1, x2, x3 ≥ 0 (7)
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 (4) and (5), we get
3×1 + 3×2 + 8×3 ≤ 54 (8)
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
COMP3121/9101 9 / 18
Linear Programming – Standard Form
maximize: z(x1, x2, x3) = 3×1 + x2 + 2×3 (3)
with constraints: x1 + x2 + 3×3 ≤ 30 (4)
2×1 + 2×2 + 5×3 ≤ 24 (5)
4×1 + x2 + 2×3 ≤ 36 (6)
x1, x2, x3 ≥ 0 (7)
Thus the objective 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
COMP3121/9101 10 / 18
Linear Programming – Standard Form
maximize: z(x1, x2, x3) = 3×1 + x2 + 2×3 (3)
with constraints: x1 + x2 + 3×3 ≤ 30 (4)
2×1 + 2×2 + 5×3 ≤ 24 (5)
4×1 + x2 + 2×3 ≤ 36 (6)
x1, x2, x3 ≥ 0 (7)
So we got
x1(y1 + 2y2 + 4y3) + x2(y1 + 2y2 + y3) + x3(3y1 + 5y2 + 2y3) ≤ 30y1 + 24y2 + 36y3
(9)
If we compare this with our objective (3) we see that if we choose y1, y2
and y3 so that:
y1 + 2y2 + 4y3 ≥ 3
y1 + 2y2 + y3 ≥ 1
3y1 + 5y2 + 2y3 ≥ 2
then
3×3 + x2 + 2×3 ≤ x1(y1 + 2y2 + 4y3) + x2(y1 + 2y2 + y3) + x3(3y1 + 5y2 + 2y3)
Combining this with (9) we get:
30y1 + 24y2 + 36y3 ≥ 3×1 + x2 + 2×3 = z(x1, x2, x3)
COMP3121/9101 11 / 18
Linear Programming – Standard Form
Consequently, in order to find as tight upper bound for our objective
z(x1, x2, x3) of the problem P :
maximize: z(x1, x2, x3) = 3×1 + x2 + 2×3 (3)
with constraints: x1 + x2 + 3×3 ≤ 30 (4)
2×1 + 2×2 + 5×3 ≤ 24 (5)
4×1 + x2 + 2×3 ≤ 36 (6)
x1, x2, x3 ≥ 0 (7)
we have to look for y1, y2, y3 which solve problem P ∗:
minimise: z∗(y1, y2, y3) = 30y1 + 24y2 + 36y3 (10)
with constraints: y1 + 2y2 + 4y3 ≥ 3 (11)
y1 + 2y2 + y3 ≥ 1 (12)
3y1 + 5y2 + 2y3 ≥ 2 (13)
y1, y2, y3 ≥ 0 (14)
then z∗(y1, y2, y3) = 30y1 + 24y2 + 36y3 ≥ 3×1 + x2 + 2×3 = z(x1, x2, x3)
will be a tight upper bound for z(x1, x2, x3)
The new problem P ∗ is called the dual problem for the problem P .
COMP3121/9101 12 / 18
Linear Programming – Standard Form
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 z1, z2, z3 ≥ 0 to multiply inequalities (11)-(13)
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
(15)
If we choose multipliers z1, z2, z3 so that
z1 + z2 + 3z3 ≤ 30 (16)
2z1 + 2z2 + 5z3 ≤ 24 (17)
4z1 + z2 + 2z3 ≤ 36 (18)
we will have:
y1(z1 + z2 + 3z3) + y2(2z1 + 2z2 + 5z3) + y3(4z1 + z1 + 2z3) ≤ 30y1 + 24y2 + 36y3
Combining this with (15) we get
3z1 + z2 + 2z3 ≤ 30y1 + 24y2 + 36y3
COMP3121/9101 13 / 18
Linear Programming – Standard Form
Consequently, finding the dual program (P ∗)∗ of P ∗ amounts to
maximising the objective 3z1 + z2 + 2z3 subject to the constraints
z1 + z2 + 3z3 ≤ 30
2z1 + 2z2 + 5z3 ≤ 24
4z1 + z2 + 2z3 ≤ 36
But note 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 maximisation problem to an equally
hard minimisation problem.
It 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.
COMP3121/9101 14 / 18
Linear Programming – primal/dual problem forms
The original, primal Linear Program P and its dual Linear Program can be
easily described in the most general case:
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) = bTy, subject to the constraints ATy ≥ c and y ≥ 0.
COMP3121/9101 15 / 18
Weak Duality Theorem
Recall that any vector x which satisfies the two constraints, Ax ≤ b and x ≥ 0
is called a feasible solution, regardless of what the corresponding objective
value cTx might be.
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, the value of (the objective of P ∗ for) any feasible solution of P ∗ is an
upper bound for the set of all values of (the objective of P for) all feasible
solutions of P , and
every feasible solution of P is a lower bound for the set of feasible solutions for
P ∗.
COMP3121/9101 16 / 18
Weak Duality Theorem
Solutions for P
Solutions for P*
Thus, if we find a feasible solution for P which is equal to a feasible
solution to P ∗, such solution must be the maximal feasible value of the
objective of P and the minimal feasible value of the objective of P ∗.
If we use a search procedure to find an optimal solution for P we know
when to stop: when such a value is also a feasible solution for P ∗.
This is why the most commonly used LP solving method, the SIMPLEX
method, produces optimal solution for P , because it stops at a value of
the primal objective which is also a value of the dual objective.
See the Lecture Notes for the details and an example of how the
SIMPLEX algorithm runs.
COMP3121/9101 17 / 18
PUZZLE!!
Five sisters are alone in their house. Sharon is reading a book, Jennifer
is playing chess, Cathrine is cooking and Ana is doing laundry. What is
Helen, the fifth sister, doing?
COMP3121/9101 18 / 18