Analysis of Algorithms
V. Adamchik CSCI 570 Spring 2020
Lecture 11
University of Southern California
Linear Programming
Reading: chapter 8
Linear Programming
In this lecture we describe linear programming that is used to express a wide variety of different kinds of problems. LP can solve the max-flow problem and the shortest distance, find optimal strategies in games, and many other things.
We will primarily discuss the setting and how to code up various problems as linear programs.
Solving by Reduction
Formally, to reduce a problem Y to a problem X (we write Y ≤p X) we want a function f that maps Y to X such that:
• f is a polynomial time computable
• ∀instance y ∈ Y is solvable if and only if f(y) ∈ X is solvable.
A Production Problem
A company wishes to produce two types of souvenirs: type-A will result in a profit of $1.00, and type-B in a profit of $1.20.
To manufacture a type-A souvenir requires 2 minutes on machine I and 1 minute on machine II.
A type-B souvenir requires 1 minute on machine I and 3 minutes on machine II.
There are 3 hours available on machine I and 5 hours available on machine II.
How many souvenirs of each type should the company make in order to maximize its profit?
A Production Problem
Type-A
Type-B
Time Available
Profit/Unit Machine I Machine II
$1.00 2 min 1 min
$1.20 1 min 3 min
180 min 300 min
A Linear Program
We want to maximize the objective function subject to the system of inequalities:
200 100
A Production Problem y
2x + y ≤ 180 x +3y ≤ 300 x≥ 0
y ≥0
100 200 300
x
A Production Problem
We want to find the feasible point that is farthest in the “objective” direction P=x + 1.2 y
We can see that P is maximized at the vertex C(48, 84) and has a value of 148.8
y 200
100
S
2x + y ≤ 180 x + 3y ≤300 x≥ 0
y ≥ 0
x +3 y = 300
x
C(48, 84)
100
P = x + 1.2 y
200 300
2 x + y = 180
Fundamental Theorem
If a linear programming problem has a solution, then it must occur at a vertex, or corner point, of the feasible set S associated with the problem.
If the objective function P is optimized at two adjacent vertices of S, then it is optimized at every point on the line segment joining these vertices, in which case there are infinitely many solutions to the problem.
Existence of Solution
Suppose we are given a LP problem with a feasible set S and an objective function P. There are 3 cases to consider
Standard LP form
We say that a maximization linear program with n variables is in standard form if for every variable xk we have the inequality xk ≥ 0 and all other m linear inequalities. A LP in standard form is written as
max (c1x1 + … + cnxn )
subject to
a11x1 + … + a1nxn ≤ b1
am1x1 + … + amnxn ≤ bm x1 ≥ 0, …, xn ≥ 0
…
Standard LP in Matrix Form
The vector c is the column vector (c1, . . . , cn).
The vector x is the column vector (x1, . . . , xn).
The matrix A is the n × m matrix of coefficients of the left-hand sides of the inequalities, and
b= (b1, . . . , bm) is the vector of right-hand sides of the inequalities.
subject to
x≥0
max(cT x)
Ax≤ b
Exercise: Convert to Matrix Form
max(x1 + 1.2 x2) 2×1 +x2 ≤180
x1 + 3×2 ≤ 300 x1 ≥ 0
x2 ≥ 0
Algorithms for LP
The standard algorithm for solving LPs is the Simplex Algorithm, due to Dantzig, 1947.
This algorithm starts by finding a vertex of the polytope, and then moving to a neighbor with increased cost as long as this is possible. By linearity and convexity, once it gets stuck it has found the optimal solution.
Unfortunately simplex does not run in polynomial time it does well in practice, but poorly in theory.
Algorithms for LP
In 1974 Khachian has shown that LP could be done in polynomial time by something called the Ellipsoid Algorithm (but it tends to be fairly slow in practice).
In 1984, Karmarkal discovered a faster polynomial-time algorithm called “interior-point”. While simplex only moves along the outer faces of the polytope, “interior- point” algorithm moves inside the polytope.
MATLAB
https://www.mathworks.com/help/optim/ug/linprog.html
Discussion Problem 1
A cargo plane can carry a maximum weight of 100 tons and a maximum volume of 60 cubic meters. There are three materials to be transported, and the cargo company may choose to carry any amount of each, up to the maximum available limits given below.
Material 1
Material 2 Material 3
Density
2 tons/m3
1 tons/m3 3 tons/m3
Volume
40 m3
30 m3 20 m3
Price
$1,000 per m3
$2,000 per m3 $12,000 per m3
Write a linear program that optimizes revenue within the constraints.
Discussion Problem 2
There are n people and n jobs. You are given a cost matrix, C, where cij represents the cost of assigning person i to do job j. You need to assign all the jobs to people and also only one job to a person. You also need to minimize the total cost of your assignment. Write a linear program that minimizes the total cost of your assignment.
Discussion Problem 3
Convert the following LP to standard form
max (5×1 − 2×2 + 9×3)
3×1 + x2 + 4×3 = 8 2×1 + 7×2 − 6×3 ≤ 4 x1 ≤ 0, x3 ≥ 1
Discussion Problem 4
Explain why LP cannot contain constrains in the form of strong inequalities.
max(7×1 – x2 + 5×3) x1 + x2 + 4×3 < 8 3x1 - x2 + 2x3 > 3 2×1 +5×2 -x3 ≤-7
x1, x2 ,x3 ≥ 0
Exercise: Max-Flow as LP
Write a max-flow problem as a linear program.
s
a3c
4
2 1
2 2b3d4
t
Exercise: Shortest Path as LP
Write a shortest st-path problem as a linear program.
2
1 11 9 5
4 5
S
86
2 4 13 3 11
t
du
dv
2
1 11 9 5
4 5
S
86
2 4 13 3 11
t
Discussion Problem 5
Write a 0-1 Knapsack Problem as a linear program.
Given n items with weights w1, w2, …, wn and values v1, v2, …, vn. Put these items in a knapsack of capacity W to get the maximum total value in the knapsack.
m Givenw W
k m
k=1 optimizev →max
k k=1
Knapsack as LP
Knapsack as LP
Dual LP
To every linear program there is a dual linear program
Duality
Definition. The dual of the standard maximum problem
max cTx
Ax ≤ b and x ≥ 0
is defined to be the standard minimum problem
min bTy
ATy ≥ c and y ≥ 0
Exercise: duality
max(7×1 – x2 + 5×3) x1 + x2 + 4×3 ≤ 8 3×1 – x2 + 2×3 ≤ 3 2×1 + 5×2 – x3 ≤ -7
x1, x2 ,x3 ≥ 0
Write the dual problem.
Consider the LP:
max ( cT x)
Ax≤ b x≥0
min ( bT y)
AT y ≥ c y ≥0
primal LP
dual LP
From Primal to Dual
Consider the max LP constrains a11x1+…+a1nxn ≤ b1
am1x1+…+amnxn ≤ bm
1) Multiply each equation by a new variable yk ≥ 0. 2) Add up those m equations.
3) Collect terms wrt to xk.
4) Chooseyk inawaythatAT y≥c.
…
Weak Duality
max ( cT x)
Ax ≤b x ≥0
min ( bT y)
AT y ≥ c y ≥0
primal linear program
dual linear program
Weak Duality. The optimum of the dual is an upper bound to the optimum of the primal.
opt(primal) ≤ opt(dual)
Weak Duality
max ( cT x)
Ax ≤b x ≥0
min ( bT y)
AT y ≥ c y ≥0
Theorem (The weak duality).
Let P and D be primal and dual LP correspondingly.
If x is a feasible solution for P and y is a feasible solution for D, then cTx ≤ bTy.
Proof (in matrix form).
Weak Duality: opt(primal) ≤ opt(dual)
Corollary 1. If a standard problem and its dual are both feasible, then both are feasible bounded.
Corollary 2. If one problem has an unbounded solution, then the dual of that problem is infeasible.
Strong Duality
max ( cT x)
Ax ≤b x ≥0
min ( bT y)
AT y ≥ c y ≥0
Theorem (The strong duality).
Let P and D be primal and dual LP correspondingly. If P and D are feasible, then cTx = bTy.
The proof of this theorem is not as easy and beyond the scope of this course.
Possibilities for the Feasibility
max ( cT x)
Ax ≤b x ≥0
min ( bT y)
AT y ≥ c y ≥0
P\D
F.B.
F.U.
I.
F.B.
F.U.
I.
feasible bounded – F.B. feasible unbounded – F.U. infeasible – I.
Consider the LP:
max(3×1 + 8×2 + x3)
x1 + 4×2 – 2×3 ≤ 20 x1 +x2 +x3 ≥7
x2 +x3 =3
x2 ≥ -1
x3 ≤ 5
Write the dual problem.
Discussion Problem 6
Knapsack as LP
Nonlinear Optimization
max f(x)
hi(x) ≤ 0, i = 1,2 , …, m. xk ≥ 0, k = 1,2 , …, n.
Here xT =(x1, x2, …, xn), f and/or h are nonlinear functions. The problem is solved using Lagrange multipliers.
Primal in x:
Dual in λ:
Lagrange Duality (KKT-1951)
max f(x) subject to
hk(x) ≤ 0
min g(λ) subject to
λk ≥ 0
L(x, λ) = f(x) + λ h (x)
g(λ)=min L(x,λ) x
Weak Duality:
Let P and D be the optimum of primal and dual problems respectively. Then opt(P) ≤ opt(D).
Equality (strong duality) holds for convex functions.
kk k