Analysis of Algorithms, I
CSOR W4231
Computer Science Department
Copyright By PowCoder代写 加微信 powcoder
Columbia University Linear programming
1 Introduction
2 The structure of a linear program
4 Examples
5 Taking the dual of an LP
1 Introduction
2 The structure of a linear program
4 Examples
5 Taking the dual of an LP
Why linear programming?
1. Vast range of applications
Resource allocation
Production planning
Military strategy forming
Graph theoretic problems
Error correction
2. Establish the existence of polynomial-time (efficient) algorithms
3. Guide the design of approximation algorithms for computationally hard problems (coming up in the next two weeks)
4. Duality allows to unify abstract views of seemingly unrelated results and is useful in algorithm design
1 Introduction
2 The structure of a linear program
4 Examples
5 Taking the dual of an LP
An introductory example: profit maximization
A boutique chocolatier has two products: an assortment of chocolates
an assortment of truffles
Their profit is
1. $1 per box of chocolates 2. $6 per box of truffles
They can produce a total of at most 400 boxes per day. The daily demand for these products is limited
1. at most 200 boxes of chocolates per day 2. at most 300 boxes of truffles per day
What are the optimal levels of production?
The linear program (LP) for profit maximization
1. Let x1 be the number of boxes of chocolates and x2 the number of boxes of truffles produced daily.
2. Objective: maximize x1 + 6×2
3. Constraints: x1 ≥ 0, x2 ≥ 0 (special constraints);
x1 ≤200,×2 ≤300,×1+x2 ≤400 Linear program for chocolatier’s profit
max x1 + 6×2 x1 ≥0,×2 ≥0
subject to x1 ≤ 200 x2 ≤ 300
x1 + x2 ≤ 400
The general problem
1. a set of variables
2. a set of linear constraints on the variables (equalities or inequalities)
3. a linear objective function to maximize (or minimize)
an assignment of real values to the variables such that 1. the constraints are satisfied;
2. the objective function is maximized (or minimized)
A more succinct linear algebraic formulation of a linear program will appear in a later slide.
Terminology
Solution: an assignment of real values to the variables
Feasible solution: a solution that satisfies all the
constraints (including the special ones)
Feasible region: the set of all feasible solutions
Optimal solution: a feasible solution that maximizes (minimizes) the objective function if the LP is a maximization (minimization) LP
Cost or value of a solution: the value of the objective function for this solution
Optimal value of the LP: the value of an optimal solution
The geometry of the solution: feasible region
The geometry of the solution: objective function
c=1500 c=1200
Optimum point Profit= $1900
The geometry of the solution in words
The set of all feasible solutions is the set of points in the (x1,x2) plane that satisfy all five constraints.
A linear equation in x1 and x2 defines a line on that plane.
A linear inequality defines a half-space on that plane (one
side of the line).
⇒ The set of all feasible solutions is the intersection of the five half-spaces.
Goal: Find the point in this polygon that maximizes the objective function (the profit).
Feasible region and optimal solution
The optimum is achieved at a vertex of the feasible region.
Exceptions
1. The linear program is infeasible e.g.,x≤1,x≥2
2. The optimum value is unbounded
max x1 + x2 x1 ≥0,×2 ≥0
Solving LPs: the simplex method [Dantzig1947]
For more information on simplex, take, e.g., Optimization I (IEOR 6613).
Some history on LP solvers
Simplex method [Dantzig1947]
fast in practice
exponential worst case performance Ellipsoid method [Khachiyan1979]
provably polynomial-time algorithm
slow in practice
Interior-point method [Karmarkar]
polynomial-time algorithm
fast in practice
Interior-point methods is a field of active research
1 Introduction
2 The structure of a linear program
4 Examples
5 Taking the dual of an LP
An alternative proof that $1900 is optimal
Recall the LP from slide 7. max
x1 ≥0,×2 ≥0 subject to
x2 ≤ 300 x1 + x2 ≤ 400
Using the constraints to upper bound the objective
Multiply the first inequality by 0
Multiply the second inequality by 5 Multiply the third inequality by 1 Add the new inequalities; then
x1 + 6×2 ≤ 1900
⇒ the objective function cannot exceed 1900!
⇒ thus we indeed found the optimal solution Where did we get the multipliers 0, 5 and 1?
Upper bounding the objective function
The constraints themselves can help us derive an upper bound.
Multiplier Inequality
y1 x1≤200 y2 x2≤300 y3 x1+x2 ≤ 400
Multipliers yi must be non-negative (why?) Add the multiplied inequalities together:
y1x1 + y2x2 + y3(x1 + x2) ≤ 200y1 + 300y2 + 400y3
An upper bound for the objective
We want to upper bound the original objective 1×1 + 6×2
using the linear combination
y1x1 + y2x2 + y3(x1 + x2) ≤ 200y1 + 300y2 + 400y3
⇒ (y1 +y3)x1 +(y2 +y3)x2 ≤200y1 +300y2 +400y3 (1)
An upper bound for the objective
We want to upper bound the original objective 1×1 + 6×2
using the linear combination
y1x1 + y2x2 + y3(x1 + x2) ≤ 200y1 + 300y2 + 400y3
⇒ (y1 +y3)x1 +(y2 +y3)x2 ≤200y1 +300y2 +400y3 (1)
Sincex1,x2 ≥0,ifweconstrainy1+y3 ≥1andy2+y3 ≥6, then the right-hand side in (1) is an upper bound for our objective.
The dual LP
What is the best possible upper bound for our objective? Minimize equation (1) subject to constraints on y1, y2, y3.
This is yet another LP!
min 200y1 + 300y2 + 400y3
y1 ≥0,y2 ≥0,y3 ≥0
subject to y1 + y3 ≥ 1
y2 + y3 ≥ 6
This new LP is called the dual of the original, which is called the primal.
Weak duality
By construction, any feasible solution for the dual LP is an upper bound on the original primal LP.
Let VP be the optimal objective value for the primal (a maximization)
Let VD be the optimal objective value for the dual (a minimization)
Theorem 2 (Weak Duality).
The upper bounding strategy can also be used for more general kinds of optimization problems, and weak duality again holds.
Strong duality
Suppose we found a pair of primal and dual feasible values that are equal.
Then they must both be optimal.
E.g., in our chocolatier’s profit maximization problem
(x1,x2) = (100,300) is a feasible solution for the primal LP
(y1, y2, y3) = (0, 5, 1) is a feasible solution for the dual LP
they have the same value of 1900.
⇒ Thus these solutions certify each other’s optimality. Amazingly, this is always possible for LPs with bounded optima.
Theorem 3 (Strong Duality).
Strong duality consequences
Primal Dual
Primal feasible opt opt Dual feasible
This duality gap is zero
Objective function
We can alternatively solve the dual to find the optimal objective value.
An optimal dual solution can be used to derive an optimal primal solution (complementary slackness).
The dual may have structure making it easier to solve at scale (e.g., via parallel optimization).
1 Introduction
2 The structure of a linear program
4 Examples
5 Taking the dual of an LP
Higher-dimensional LPs
Suppose that the chocolatier introduces a third product, seasonal truffles, such that
seasonal truffles yield a profit of $13 per box
≤ 100 boxes of seasonal truffles may be produced. What are the new optimal levels of production?
What if we add a fourth line of production? A hundred-th?
High-dimensional problem Simplex still works!
LP for more products
x1 ≥0,×2 ≥0,×3 ≥0 subject to
x1 + 6×2 + 13×3
x1 +x2 +x3 ≤400
Production planning for a carpet company
The company has 30 employees.
Each employee makes 20 carpets per month. Monthly employee salary is $2000.
Initially, no surplus of carpets.
Your data shows that carpet demand is extremely seasonal: monthly demand di ranges from 440 to 920. Fluctuations in demand may be handled as follows
1. Overtime
they are paid 80% more than regular workers
workers can put in at most 30% overtime.
2. Hiring and firing
these cost $320 and $400 respectively per worker
3. Storing surplus production
costs $8 per month
no stored carpets at the end of the year Goal: minimize yearly expenses for company
Variables for carpet company production planning
wi = number of workers during i-th month; w0 = 30
hi,fi = number of workers hired and fired, respectively, at
beginning of month i
xi = number of carpets made during i-th month
oi = number of carpets made by overtime in i-th month
si = number of carpets stored at end of month i; s0 = 0
LP for carpet company production planning
Constraints (one constraint for every month 1 ≤ i ≤ 12) wi,hi,fi,xi,oi,si ≥ 0
xi=20wi+oi
wi=wi−1+hi−fi
si=si−1+xi−di oi ≤ 6wi
Objective:
min 2000wi +320hi +400fi +8si +180oi
What if solution is not integral?
1 Introduction
2 The structure of a linear program
4 Examples
5 Taking the dual of an LP
LPs in matrix-vector notation
We may rewrite any LP as follows (think about it!).
1. It is either a maximization or a minimization
2. All constraints are inequalities in the same direction 3. All variables are non-negative
This results in an LP of the following form max cTx
subject to Ax ≤ b
The dual in matrix-vector notation
Then the dual is given as follows (prove this!). min bTy
subject to AT y ≥ c
By construction, we know that the any feasible solution to the primal is upper bounded by any feasible solution to the dual (weak duality). Hence
What if the primal is unbounded? What if the dual is unbounded?
Feasibility vs Optimality
Finding a feasible solution of a linear program is generally computationally as difficult as finding an optimal solution.
For example, consider the primal in slide 32. Any feasible solution to the following LP (restricted to x) is an optimal solution to the primal.
max cTx x≥0,y≥0
subject to Ax ≤ b AT y ≥ c
Textbook dualization recipe
Note that b ∈ Rm, c ∈ Rn, A ∈ Rm×n
Right-hand side
Constraints
j-th constraint has ≤
i-th constraint has ≥ ≤ =
yj ≥ 0 yj ≤ 0 yj ∈ R
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com