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
xici =2000; i=1
for each vitamin Vj the total amount in all food must satisfy n
xiv(i,j) ≥ wj (1 ≤ j ≤ 13); i=1
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
n
y = xipi. i=1
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 0.07xb + 0.02xa + 0.03xp ≥ 0.51 0.09xb + 0.15xa ≥ 0.51
xb,xa,xp ≥0.
(securing majority of city votes) (securing majority of suburban votes) (securing majority of rural votes)
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
the constraints are of the form
n
aijxj ≤bi, j=1
1≤i≤m; (1) 1 ≤ j ≤ n, (2)
xj ≥ 0,
Let the boldface x represent a (column) vector, x = ⟨x1 . . . xn⟩T.
n cj xj j=1
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 forall1≤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:
and
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.
Ax ≤ b x ≥ 0.
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 ni=1 aijxi = bj can be replaced by two inequalities: ni=1 aij xi ≥ bj and ni=1 aij xi ≤ 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
subject to the constraints
z(x1, x2, x3) = 3×1 + x2 + 2×3
x1 +x2 +3×3 2×1 + 2×2 + 5×3 4×1 +x2 +2×3 x1, x2, x3
(3)
≤ 30 (4) ≤ 24 (5) ≤ 36 (6) ≥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 with constraints: x1 + x2 + 3×3 2×1 + 2×2 + 5×3 4×1 +x2 +2×3 x1, x2, x3
(3) ≤ 30 (4) ≤ 24 (5) ≤ 36 (6) ≥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:
with constraints:
z(x1, x2, x3) = 3×1 + x2 + 2×3 x1 + x2 + 3×3 2×1 + 2×2 + 5×3 4×1 +x2 +2×3 x1, x2, x3
(3) ≤ 30 (4) ≤ 24 (5) ≤ 36 (6) ≥0 (7)
+2y3)≤30y1 +24y2 +36y3 (9)
So we got
x1(y1 +2y2 +4y3)+x2(y1 +2y2 +y3)+x3(3y1 +5y2
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 with constraints: x1 + x2 + 3×3 2×1 + 2×2 + 5×3 4×1 +x2 +2×3 x1, x2, x3
≤ 30 ≤ 24 ≤ 36 ≥0
(3) (4) (5) (6) (7)
(10) ≥3 (11)
≥1 (12)
≥2 (13)
≥0 (14)
we have to look for y1, y2, y3 which solve problem P ∗: minimise: z∗(y1, y2, y3) = 30y1 + 24y2 + 36y3 with constraints: y1 + 2y2 + 4y3
y1 +2y2 +y3 3y1 + 5y2 + 2y3 y1, y2, y3
thenz∗(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
subject to the constraints
P ∗ : minimize
subject to the constraints
or, in matrix form,
P : maximize z(x) = cTx, subject to the constraints
P ∗ : minimize z∗(y) = bTy, subject to the constraints COMP3121/9101
Ax ≤ b and ATy ≥ c and
x ≥ 0; y ≥ 0.
15 / 18
n
z(x) = cjxj,
j=1 n
aijxj ≤ bi; j=1
x1,…,xn ≥0; m
z∗(y) = biyi, i=1
m
aijyi ≥ cj;
i=1
y1,…,ym ≥0,
1 ≤ i ≤ m
1 ≤ j ≤ n
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:
nn
z(x) = cjxj ≤ biyi = z∗(y)
j=1 i=1
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
nnmmnn z(x)=cjxj ≤ aijyi xj = aijxj yi ≤biyi =z∗(y)
j=1 j=1 i=1 i=1 j=1 i=1
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