Question? Leave a message!




LINEAR PROGRAMMING

LINEAR PROGRAMMING
LINEAR PROGRAMMING I a refreshing example ‣ standard form ‣ fundamental questions ‣ geometry ‣ linear algebra ‣ simplex algorithm ‣ Lecture slides by Kevin Wayne Last updated on 5/15/17 10:33 AMLinear programming Linear programming. Optimize a linear function subject to
 linear inequalities. n T (P) max c x (P) max c x ∑ j j j=1 s. t. Ax = b n x ≥ 0 s. t. a x = b 1≤i≤m ∑ ij j i j=1 x ≥ 0 1≤ j≤n j € € 2Linear programming Linear programming. Optimize a linear function subject to
 linear inequalities. Generalizes: Ax = b, 2-person zero-sum games, shortest path,
 max flow, assignment problem, matching, multicommodity flow,
 MST, min weighted arborescence, … Why significant? Design poly-time algorithms. ・ Design approximation algorithms. ・ Solve NP-hard problems using branch-and-cut. ・ Ranked among most important scientific advances of 20th century. 3LINEAR PROGRAMMING I a refreshing example ‣ standard form ‣ fundamental questions ‣ geometry ‣ linear algebra ‣ simplex algorithm ‣ Reference: The Allocation of Resources by Linear Programming, Scientific American, by Bob BlandBrewery problem Small brewery produces ale and beer. Production limited by scarce resources: corn, hops, barley malt. ・ Recipes for ale and beer require different proportions of resources. ・ Corn
 Hops
 Malt
 Profit
 Beverage (pounds) (ounces) (pounds) () Ale (barrel) 5 4 35 13 Beer (barrel) 15 4 20 23 constraint 480 160 1190 How can brewer maximize profits? Devote all resources to ale: 34 barrels of ale ⇒ 442 ・ Devote all resources to beer: 32 barrels of beer ⇒ 736 ・ 7.5 barrels of ale, 29.5 barrels of beer ⇒ 776 ・ 12 barrels of ale, 28 barrels of beer ⇒ 800 ・ 5Brewery problem objective function Beer Ale Profit max 13A + 23B Corn s. t. 5A + 15B ≤ 480 Hops 4A + 4B ≤ 160 Malt 35A + 20B ≤ 1190 A , B ≥ 0 constraint € decision variable 6Reference 7LINEAR PROGRAMMING I a refreshing example ‣ standard form ‣ fundamental questions ‣ geometry ‣ linear algebra ‣ simplex algorithm ‣Standard form LP "Standard form" LP. Input: real numbers a , c , b . ・ ij j i Output: real numbers x . ・ j n = decision variables, m = constraints. ・ Maximize linear objective function subject to linear inequalities. ・ n T (P) max c x (P) max c x ∑ j j j=1 s. t. Ax = b n x ≥ 0 s. t. a x = b 1≤i≤m ∑ ij j i j=1 x ≥ 0 1≤ j≤n j € € 2 Linear. No x , x y, arccos(x), etc. Programming. Planning (term predates computer programming). 9Brewery problem: converting to standard form Original input. max 13A + 23B s. t. 5A + 15B ≤ 480 4A + 4B ≤ 160 35A + 20B ≤ 1190 A , B ≥ 0 Standard form. € Add slack variable for each inequality. ・ Now a 5-dimensional problem. ・ max 13A + 23B s. t. 5A + 15B + S = 480 C 4A + 4B + S = 160 H 35A + 20B + S = 1190 M A , B , S , S , S ≥ 0 C H M 10 € Equivalent forms Easy to convert variants to standard form. T (P) max c x s. t. Ax = b x ≥ 0 € Less than to equality. x + 2y – 3z ≤ 17 ⇒ x + 2y – 3z + s = 17, s ≥ 0 Greater than to equality. x + 2y – 3z ≥ 17⇒ x + 2y – 3z – s = 17, s ≥ 0 Min to max. min x + 2y – 3z ⇒ max –x – 2y + 3z + – + – Unrestricted to nonnegative. x unrestricted ⇒ x = x – x , x ≥ 0, x ≥ 0 11LINEAR PROGRAMMING I a refreshing example ‣ standard form ‣ fundamental questions ‣ geometry ‣ linear algebra ‣ simplex algorithm ‣Fundamental questions m×n m n n LP. For A ∈ ℜ , b ∈ ℜ , c ∈ ℜ , α ∈ ℜ, does there exist x ∈ ℜ such that: 
 T Ax = b, x ≥ 0, c x ≥ α ? Q. Is LP in NP? Q. Is LP in co-NP? Q. Is LP in P? Q. Is LP in P ? ℜ Blum–Shub–Smale model Input size. n = number of variables. ・ m = number of constraints. ・ L = number of bits to encode input. ・ 13LINEAR PROGRAMMING I a refreshing example ‣ standard form ‣ fundamental questions ‣ geometry ‣ linear algebra ‣ simplex algorithm ‣Brewery problem: feasible region Hops
 Malt
 4A + 4B ≤ 160 35A + 20B ≤ 1190 (0, 32) (12, 28) Corn
 5A + 15B ≤ 480 (26, 14) Beer Ale (0, 0) (34, 0) 15Profit Brewery problem: objective function (0, 32) (12, 28) 13A + 23B = 1600 (26, 14) Beer 13A + 23B = 800 Ale (0, 0) (34, 0) 13A + 23B = 442 16Brewery problem: geometry Brewery problem observation. Regardless of objective function coefficients, an optimal solution occurs at a vertex. (0, 32) (12, 28) vertex (26, 14) Beer Ale (0, 0) (34, 0) 17Convexity Convex set. If two points x and y are in the set, then so is
 λ x + (1− λ) y for 0 ≤ λ ≤ 1. not a vertex iff ∃ d ≠ 0 s.t. x ± d in set convex combination Vertex. A point x in the set that can't be written as a strict
 convex combination of two distinct points in the set. vertex x y convex not convex Observation. LP feasible region is a convex set. 18Purificaiton Theorem. If there exists an optimal solution to (P), then there exists one that is a vertex. T (P) max c x s. t. Ax = b x ≥ 0 Intuition. If x is not a vertex, move in a non-decreasing direction until you € reach a boundary. Repeat. x' = x + α d x + d x x - d 19Purificaiton Theorem. If there exists an optimal solution to (P), then there exists one that is a vertex. Pf. Suppose x is an optimal solution that is not a vertex. ・ There exist direction d ≠ 0 such that x ± d ∈ P. ・ A d = 0 because A(x ± d) = b. ・ T Assume c d ≤ 0 (by taking either d or –d). ・ Consider x + λ d, λ 0 : ・ Case 1. there exists j such that d 0 j Increase λ to λ until first new component of x + λ d hits 0. ・ x + λ d is feasible since A(x + λ d) = Ax = b and x + λ y ≥ 0. ・ x + λ d has one more zero component than x. ・ T T T T T c x' = c (x + λ d) = c x + λ c d ≤ c x. ・ d = 0 whenever x = 0 because x ± d ∈ P k k 20Purificaiton Theorem. If there exists an optimal solution to (P), then there exists one that is a vertex. Pf. Suppose x is an optimal solution that is not a vertex. ・ There exist direction d ≠ 0 such that x ± d ∈ P. ・ A d = 0 because A(x ± d) = b. ・ T Assume c d ≤ 0 (by taking either d or –d). ・ Consider x + λ d, λ 0 : ・ Case 2. d ≥ 0 for all j j x + λd is feasible for all λ ≥ 0 since A(x + λd) = b and x + λd ≥ x ≥ 0. ・ T T As λ → ∞, c (x + λd) → ∞ because c d 0. • ・ T if c d = 0, choose d so that case 1 applies 21LINEAR PROGRAMMING I a refreshing example ‣ standard form ‣ fundamental questions ‣ geometry ‣ linear algebra ‣ simplex algorithm ‣Intuition m Intuition. A vertex in ℜ is uniquely specified by m linearly independent equations. 4A + 4B ≤ 160 35A + 20B ≤ 1190 4A + 4B = 160
 35A + 20B = 1190 (26, 14) 23Basic feasible solution Theorem. Let P = x : Ax = b, x ≥ 0 . For x ∈ P, define B = j : x 0 .
 j Then, x is a vertex iff A has linearly independent columns. B Notation. Let B = set of column indices. Define A to be the subset
 B of columns of A indexed by B. " % " % 2 1 3 0 7 ' ' A = 7 3 2 1 , b = 16 ' ' Ex. ' ' 0 0 0 5 0 & & " % 2 " % 2 3 € ' 0 ' ' x = , B = 1, 3, A = 7 2 B ' 1' ' 0 0 & ' 0 & 24 € Basic feasible solution Theorem. Let P = x : Ax = b, x ≥ 0 . For x ∈ P, define B = j : x 0 .
 j Then, x is a vertex iff A has linearly independent columns. B Pf. ⇐ Assume x is not a vertex. ・ There exist direction d ≠ 0 such that x ± d ∈ P. ・ A d = 0 because A(x ± d) = b. ・ Define B' = j : d ≠ 0 . ・ j A has linearly dependent columns since d ≠ 0. ・ B' Moreover, d = 0 whenever x = 0 because x ± d ≥ 0. ・ j j Thus B' ⊆ B, so A is a submatrix of A . ・ B' B Therefore, A has linearly dependent columns. ・ B 25Basic feasible solution Theorem. Let P = x : Ax = b, x ≥ 0 . For x ∈ P, define B = j : x 0 .
 j Then, x is a vertex iff A has linearly independent columns. B Pf. ⇒ Assume A has linearly dependent columns. ・ B There exist d ≠ 0 such that A d = 0. ・ B n Extend d to ℜ by adding 0 components. ・ Now, A d = 0 and d = 0 whenever x = 0. ・ j j For sufficiently small λ, x ± λ d ∈ P ⇒ x is not a vertex. • ・ 26Basic feasible solution Theorem. Given P = x : Ax = b, x ≥ 0 , x is a vertex iff there exists
 B ⊆ 1, …, n such B = m and: A is nonsingular. ・ B -1 x = A b ≥ 0. ・ B B basic feasible solution x = 0. ・ N Pf. Augment A with linearly independent columns (if needed). • B " % " % 2 1 3 0 7 ' ' A = 7 3 2 1 , b = 16 ' ' ' ' 0 0 0 5 0 & & " % 2 " % 2 3 0 ' 0 ' ' x = , B = 1, 3, 4 , A = 7 2 1 B ' € 1 ' ' 0 0 5 & ' 0 & € m×n Assumption. A ∈ ℜ has full row rank. 27Basic feasible solution: example Basic feasible solutions. Basis
 A, B, S 
 M (12, 28) B, S , S 
 H M (0, 32) Infeasible
 A, B, S 
 H (19.41, 25.53) max 13A + 23B A, B, S 
 Beer C s. t. 5A + 15B + S = 480 C (26, 14) 4A + 4B + S = 160 H 35A + 20B + S = 1190 M A , B , S , S , S ≥ 0 C H M Ale A, S , S 
 H C S , S , S 
 H M C (34, 0) (0, 0) € 28Fundamental questions m×n m n n 
 LP. For A ∈ ℜ , b ∈ ℜ , c ∈ ℜ , α ∈ ℜ, does there exist x ∈ ℜ T such that: Ax = b, x ≥ 0, c x ≥ α ? Q. Is LP in NP? A. Yes. n m ≤ C(n, m) = ≤ n . Number of vertices ・ ( ) m Cramer's rule ⇒ can check a vertex in poly-time. ・ € n n n × Cramer's rule. For B ∈ ℜ invertible, b ∈ ℜ ,
 the solution to Bx = b is given by: det(B ) i x = i det(B) replace ith column of B with b 29 € LINEAR PROGRAMMING I a refreshing example ‣ standard form ‣ fundamental questions ‣ geometry ‣ linear algebra ‣ simplex algorithm ‣Simplex algorithm: intuition Simplex algorithm. George Dantzig 1947 Move from BFS to adjacent BFS, without decreasing objective function. replace one basic variable with another edge Greedy property. BFS optimal iff no adjacent BFS is better. Challenge. Number of BFS can be exponential 31Simplex algorithm: initialization maxZ subject to Basis = S , S , S 
 13A + 23B − Z = 0 C H M A = B = 0
 5A + 15B + S = 480 C Z = 0
 S = 480 
 4A + 4B + S = 160 C H S = 160 
 H 35A + 20B + S = 1190 M S = 1190 M A , B , S , S , S ≥ 0 C H M € 32Simplex algorithm: pivot 1 maxZ subject to Basis = S , S , S 
 13A + 23B − Z = 0 C H M A = B = 0
 5A + 15B + S = 480 C Z = 0
 S = 480 
 4A + 4B + S = 160 C H S = 160 
 H 35A + 20B + S = 1190 M S = 1190 M A , B , S , S , S ≥ 0 C H M Substitute: B = 1/15 (480 – 5A – S ) C € maxZ subject to 16 23 A − S − Z = −736 C 3 15 Basis = B, S , S 
 H M 1 1 A = S = 0
 A + B + S = 32 C C 3 15 Z = 736
 8 4 A − S + S = 32 C H 3 15 B = 32 
 85 4 A − S + S = 550 S = 32 
 C M 3 3 H S = 550 M A , B , S , S , S ≥ 0 C H M 33 € Simplex algorithm: pivot 1 maxZ subject to Basis = S , S , S 
 13A + 23B − Z = 0 C H M A = B = 0
 5A + 15B + S = 480 C Z = 0
 S = 480 
 4A + 4B + S = 160 C H S = 160 
 H 35A + 20B + S = 1190 M S = 1190 M A , B , S , S , S ≥ 0 C H M € Q. Why pivot on column 2 (or 1)? A. Each unit increase in B increases objective value by 23. Q. Why pivot on row 2? A. Preserves feasibility by ensuring RHS ≥ 0. min ratio rule: min 480/15, 160/4, 1190/20 34Simplex algorithm: pivot 2 maxZ subject to Basis = B, S , S 
 H M 16 23 A − S − Z = −736 C 3 15 A = S = 0
 C 1 1 A + B + S = 32 Z = 736
 C 3 15 B = 32 
 8 4 A − S + S = 32 C H 3 15 S = 32 
 H 85 4 A − S + S = 550 C M 3 3 S = 550 M A , B , S , S , S ≥ 0 C H M € Substitute: A = 3/8 (32 + 4/15 S – S ) C H maxZ subject to Basis = A, B, S 
 M − S − 2 S − Z = −800 C H S = S = 0
 C H 1 1 B + S + S = 28 C H 10 8 Z = 800
 1 3 B = 28 
 A − S + S = 12 C H 10 8 A = 12 
 25 85 − S − S + S = 110 C H M 6 8 S = 110 M A , B , S , S , S ≥ 0 C H M 35 € Simplex algorithm: optimality Q. When to stop pivoting? A. When all coefficients in top row are nonpositive. Q. Why is resulting solution optimal? A. Any feasible solution satisfies system of equations in tableaux. In particular: Z = 800 – S – 2 S , S ≥ 0, S ≥ 0. ・ C H C H Thus, optimal objective value Z ≤ 800. ・ Current BFS has value 800 ⇒ optimal. ・ maxZ subject to Basis = A, B, S 
 M − S − 2 S − Z = −800 C H S = S = 0
 C H 1 1 B + S + S = 28 C H 10 8 Z = 800
 1 3 B = 28 
 A − S + S = 12 C H 10 8 A = 12 
 25 85 − S − S + S = 110 C H M 6 8 S = 110 M A , B , S , S , S ≥ 0 C H M 36 € Simplex tableaux: matrix form Initial simplex tableaux. T T c x + c x = Z B B N N A x + A x = b B B N N x , x ≥ 0 B N Simplex tableaux corresponding to basis B. T T −1 T −1 T -1 subtract c A times constraints B B (c − c A A )x = Z − c A b € N B B N N B B −1 −1 -1 multiply by A Ix + A A x = A b B B B N N B x , x ≥ 0 B N -1 € x = A b ≥ 0 B B T T -1 c – c A A ≤ 0 N B B N x = 0 N optimal basis basic feasible solution 37Simplex algorithm: corner cases Simplex algorithm. Missing details for corner cases. Q. What if min ratio test fails? Q. How to find initial basis? Q. How to guarantee termination? 38Unboundedness Q. What happens if min ratio test fails? all coefficients in entering
 column are nonpositive maxZ subject to + 2x + 20x − Z = 2 4 5 x − 4x − 8x = 3 1 4 5 x + 5x − 12x = 4 2 4 5 x = 5 3 x , x , x , x , x ≥ 0 1 2 3 4 5 € " % " % x 3 + 8x 1 5 A. Unbounded objective function. ' ' x 4 + 12x 2 5 ' ' Z = 2 + 20x ' = ' x 5 5 3 ' ' x 0 4 ' ' ' ' x 0 & & 5 € 39 € Phase I simplex method Q. How to find initial basis? T (P) max c x s. t. Ax = b x ≥ 0 € A. Solve (P'), starting from basis
 m (P ") max z ∑ consisting of all the z variables. i i i=1 s. t. Ax +Iz = b x, z ≥ 0 € Case 1: min 0 ⇒ (P) is infeasible. ・ Case 2: min = 0, basis has no z variables ⇒ okay to start Phase II. ・ i Case 3a: min = 0, basis has z variables. Pivot z variables out of basis.
 ・ i i If successful, start Phase II; else remove linear dependent rows. 40Simplex algorithm: degeneracy Degeneracy. New basis, same vertex. Degenerate pivot. Min ratio = 0. maxZ subject to 3 1 x − 20x + x − 6x − Z = 0 4 5 6 7 4 2 1 x + x − 8x − x + 9x = 0 1 4 5 6 7 4 1 1 x + x − 12x − x + 3x = 0 2 4 5 6 7 2 2 x + x = 1 3 6 x , x , x , x , x , x , x ≥ 0 1 2 3 4 5 6 7 41 € Simplex algorithm: degeneracy Degeneracy. New basis, same vertex. Cycling. Infinite loop by cycling through different bases that all correspond to same vertex. Anti-cycling rules. Bland's rule: choose eligible variable with smallest index. ・ Random rule: choose eligible variable uniformly at random. ・ Lexicographic rule: perturb constraints so nondegenerate. ・ 42Lexicographic rule Intuition. No degeneracy ⇒ no cycling. Perturbed problem. much much greater,
 i say ε = δ for small δ i & ε 1 T " (P ) max c x % ( ε 2 % ( s. t. Ax = b + ε where ε = , such that ε ≻ ε ≻ ≻ ε 1 2 n % ( x ≥ 0 % ( ε ' n € € Lexicographic rule. Apply perturbation virtually by manipulating ε symbolically: 17 + 5ε + 11ε + 8ε ≤ 17 + 5ε + 14ε + 3ε 1 2 3 1 2 3 € 43Lexicographic rule Intuition. No degeneracy ⇒ no cycling. Perturbed problem. much much greater,
 i say ε = δ for small δ i & ε 1 T " (P ) max c x % ( ε 2 % ( s. t. Ax = b + ε where ε = , such that ε ≻ ε ≻ ≻ ε 1 2 n % ( x ≥ 0 % ( ε ' n € € -1 Claim. In perturbed problem, x = A (b + ε) is always nonzero. B B th Pf. The j component of x is a (nonzero) linear combination of the B components of b + ε ⇒ contains at least one of the ε terms. i which can't cancel Corollary. No cycling. 44Simplex algorithm: practice Remarkable property. In practice, simplex algorithm typically terminates after at most 2(m + n) pivots. but no polynomial pivot rule known Issues. Avoid stalling. ・ Choose the pivot. ・ Maintain sparsity. ・ Ensure numerical stability. ・ Preprocess to eliminate variables and constraints. ・ Commercial solvers can solve LPs with millions of variables and tens of thousands of constraints. 45
Website URL
Comment