Question? Leave a message!




LINEAR PROGRAMMING

LINEAR PROGRAMMING
ROBERT SEDGEWICK KEVIN WAYNE Algorithms LINEAR PROGRAMMING brewer’s problem ‣ simplex algorithm ‣ implementations ‣ Algorithms FOUR TH EDITION reductions ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduLinear programming What is it Problemsolving model for optimal allocation of scarce resources, among a number of competing activities that encompasses: Shortest paths, maxflow, MST, matching, assignment, ... can take an entire course on LP A x = b, 2person zerosum games, ... maximize 13A + 23B 5A + 15B 480 ≤ subject subject subject to the to the to the 4A + 4B ≤ 160 constraints constraints constraints 35A + 20B ≤ 1190 A , B ≥ 0 Why significant Fast commercial solvers available. Ex: Delta claims that LP Widely applicable problemsolving model. saves 100 million per year. Key subroutine for integer programming solvers. 2Applications Agriculture. Diet problem. Computer science. Compiler register allocation, data mining. Electrical engineering. VLSI design, optimal clocking. Energy. Blending petroleum products. Economics. Equilibrium theory, twoperson zerosum games. Environment. Water quality management. Finance. Portfolio optimization. Logistics. Supplychain management. Management. Hotel yield management. Marketing. Direct mail advertising. Manufacturing. Production line balancing, cutting stock. Medicine. Radioactive seed placement in cancer treatment. Operations research. Airline crew assignment, vehicle routing. Physics. Ground states of 3D Ising spin glasses. Telecommunication. Network design, Internet routing. Sports. Scheduling ACC basketball, handicapping horse races. 3LINEAR PROGRAMMING brewer’s problem ‣ simplex algorithm ‣ implementations ‣ Algorithms reductions ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu Allocation of Resources by Linear Programming by Robert Bland Scientific American, Vol. 244, No. 6, June 1981Toy LP example: brewer’s problem Small brewery produces ale and beer. Production limited by scarce resources: corn, hops, barley malt. corn (480 lbs) hops (160 oz) malt (1190 lbs) Recipes for ale and beer require different proportions of resources. 13 profit per barrel 23 profit per barrel 5Toy LP example: brewer’s problem Brewer’s problem: choose product mix to maximize profits. 34 barrels × 35 lbs malt = 1190 lbs amount of available malt ale beer corn hops malt profit 34 0 179 136 1190 442 0 32 480 128 640 736 19.5 20.5 405 160 1092.5 725 goods are divisible 12 28 480 160 980 800 800 corn (480 lbs) hops (160 oz) malt (1190 lbs) 13 profit per barrel 23 profit per barrel 6Brewer’s problem: linear programming formulation Linear programming formulation. Let A be the number of barrels of ale. Let B be the number of barrels of beer. ale beer profits maximize 13A + 23B 5A + 15B 480 corn ≤ subject subject subject to the to the to the 4A + 4B 160 hops ≤ constraints constraints constraints 35A + 20B 1190 ≤ malt A , B 0 ≥ 7Brewer’s problem: feasible region Inequalities define halfplanes; feasible region is a convex polygon. hops malt 4A + 4B ≤ 160 35A + 20B ≤ 1190 (0, 32) (12, 28) corn beer 5A + 15B ≤ 480 (26, 14) (0, 0) (34, 0) ale 8higher profit Brewer’s problem: objective function (0, 32) (12, 28) 13A + 23B = 1600 beer (26, 14) 13A + 23B = 800 (0, 0) (34, 0) ale 13A + 23B = 442 7 9Brewer’s problem: geometry Optimal solution occurs at an extreme point. intersection of 2 constraints in 2d extreme point (0, 32) (12, 28) beer (26, 14) (0, 0) (34, 0) ale 10 7Standard form linear program Goal. Maximize linear objective function of n nonnegative variables, subject to m linear equations. 2 linear means no x , xy, arccos(x), etc. Input: real numbers a , c , b . ij j i Output: real numbers x . j primal problem (P) matrix version maximize c x + c x + … + c x T 1 1 2 2 n n maximize c x a x + a x + … + a x = b 11 1 12 2 1n n 1 subject subject A x = b subject subject subject subject a21 x1 + a22 x2 + … + a2n xn = b2 to the to the to the to the to the to the x ≥ 0 constraints constraints ⋮ ⋮ ⋮ ⋮ ⋮ constraints constraints constraints constraints a x + a x + … + a x = b m1 1 m2 2 mn n m x , x , … , x 0 1 2 n ≥ Caveat. No widely agreed notion of "standard form." 11Converting the brewer’s problem to the standard form Original formulation. maximize 13A + 23B 5A + 15B 480 ≤ subject subject subject to the to the to the 4A + 4B 160 ≤ constraints constraints constraints 35A + 20B 1190 ≤ A , B 0 ≥ Standard form. Add variable Z and equation corresponding to objective function. Add slack variable to convert each inequality to an equality. Now a 6dimensional problem. maximize Z 13A + 23B − Z = 0 subject subject subject subject 5A + 15B + S SC C = 480 to the to the to the to the 4A + 4B + S S S = 160 H H H constraints constraints constraints constraints 35A + 20B + + S S = 1190 M M A , B , S S , S S S ,, S S 0 C C C C C M M ≥ 12Geometry Inequalities define halfspaces; feasible region is a convex polyhedron. A set is convex if for any two points a and b in the set, so is ½ (a + b). An extreme point of a set is a point in the set that can't be written as ½ (a + b), where a and b are two distinct points in the set. extreme point not convex convex Warning. Don't always trust intuition in higher dimensions. 13Geometry (continued) Extreme point property. If there exists an optimal solution to (P), then there exists one that is an extreme point. Good news: number of extreme points to consider is finite. Bad news : number of extreme points can be exponential local optima are global optima (follows because objective function is linear and feasible region is convex) Greedy property. Extreme point optimal iff no better adjacent extreme point. 14LINEAR PROGRAMMING brewer’s problem ‣ simplex algorithm ‣ implementations ‣ Algorithms reductions ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduLINEAR PROGRAMMING brewer’s problem ‣ simplex algorithm ‣ implementations ‣ Algorithms reductions ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduSimplex algorithm Simplex algorithm. George Dantzig, 1947 Developed shortly after WWII in response to logistical problems, including Berlin airlift. th Ranked as one of top 10 scientific algorithms of 20 century. never decreasing objective function Generic algorithm. Start at some extreme point. Pivot from one extreme point to an adjacent one. Repeat until optimal. How to implement Linear algebra. 17Simplex algorithm: basis A basis is a subset of m of the n variables. Basic feasible solution (BFS). Set n – m nonbasic variables to 0, solve for remaining m variables. Solve m equations in m unknowns. If unique and feasible ⇒ BFS. basic feasible solution BFS ⇔ extreme point. basic infeasible B, S , S H M A, B, S M solution (0, 32) (12, 28) maximize Z A, B, S H (19.41, 25.53) 13A + 23B − Z = 0 subject subject subject subject 5A + 15B + SC = 480 beer A, B, S C to the to the to the to the (26, 14) 4A + 4B + SH = 160 constraints constraints constraints constraints 35A + 20B + S = 1190 M A , B , SC , SH , SM 0 ≥ ale A, S , S S , S , S H C H M C (34, 0) (0, 0) 18Simplex algorithm: initialization maximize Z basis = S , S , S C H M 13A + 23B − Z = 0 A = B = 0 subject subject subject subject Z = 0 5A + 15B + S = 480 C to the to the to the to the S = 480 C 4A + 4B + SH = 160 constraints constraints constraints constraints S = 160 H 35A + 20B + S = 1190 M S = 1190 M A , B , S , S , S 0 C H M ≥ one basic variable per row Initial basic feasible solution. Start with slack variables S , S , S as the basis. C H M no algebra needed Set nonbasic variables A and B to 0. 3 equations in 3 unknowns yields S = 480, S = 160, S = 1190. C H M 19Simplex algorithm: pivot 1 maximize Z pivot basis = S , S , S C H M 13A + 23B − Z = 0 A = B = 0 subject subject subject subject Z = 0 5A + 15B + S = 480 C to the to the to the to the S = 480 C 4A + 4B + SH = 160 constraints constraints constraints constraints S = 160 H 35A + 20B + S = 1190 M S = 1190 M A , B , S , S , S 0 C H M ≥ which basic variable substitute B = (1/15) (480 – 5A – S ) and add B into the basis C does B replace (rewrite 2nd equation, eliminate B in 1st, 3rd, and 4th equations) maximize Z basis = B, S , S H M (16/3) A − (23/15) S − Z = 736 C A = S = 0 C subject subject subject subject Z = 736 (1/3) A + B + (1/15) SC = 32 to the to the to the to the B = 32 (8/3) A − (4/15) S + S = 32 C H constraints constraints constraints constraints S = 32 H (85/3) A − (4/3) S + S = 550 C M S = 550 M A , B , S , S , S 0 C H M ≥ 20Simplex algorithm: pivot 1 positive coefficient maximize Z pivot basis = S , S , S C H M 13A + 23B − Z = 0 A = B = 0 subject subject subject subject Z = 0 5A + 15B + S = 480 C to the to the to the to the S = 480 C 4A + 4B + SH = 160 constraints constraints constraints constraints 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 (corresponding to variable B) Its objective function coefficient is positive. (each unit increase in B from 0 increases objective value by 23) Pivoting on column 1 (corresponding to A) also OK. Q. Why pivot on row 2 Preserves feasibility by ensuring RHS ≥ 0. Minimum ratio rule: min 480/15, 160/4, 1190/20 . 21Simplex algorithm: pivot 2 maximize Z pivot basis = B, S , S H M (16/3) A − (23/15) S − Z = 736 C A = S = 0 C subject subject subject subject (1/3) A + B + (1/15) S = 32 Z = 736 C to the to the to the to the B = 32 (8/3) A − (4/15) S + S = 32 C H constraints constraints constraints constraints S = 32 H (85/3) A − (4/3) S + S = 550 C M S = 550 M A , B , S , S , S 0 C H M ≥ which basic variable substitute A = (3/8) (32 + (4/15) S – S ) and add A into the basis C H does A replace (rewrite 3rd equation, eliminate A in 1st, 2nd, and 4th equations) maximize Z basis = A, B, S M − S − 2 S − Z = 800 C H S = S = 0 C H subject subject subject subject Z = 800 B + (1/10) S + (1/8) S = 28 C H to the to the to the to the B = 28 A − (1/10) S + (3/8) S = 12 C H constraints constraints constraints constraints A = 12 − (25/6) S − (85/8) S + S = 110 C H M S = 110 M A , B , S , S , S 0 C H M ≥ 22Simplex algorithm: optimality Q. When to stop pivoting A. When no objective function coefficient is positive. Q. Why is resulting solution optimal A. Any feasible solution satisfies current system of equations. In particular: Z = 800 – S – 2 S C H Thus, optimal objective value Z ≤ 800 since S , S ≥ 0. C H Current BFS has value 800 ⇒ optimal. maximize Z basis = A, B, S M − S − 2 S − Z = 800 C H S = S = 0 C H subject subject subject subject Z = 800 B + (1/10) S + (1/8) S = 28 C H to the to the to the to the B = 28 A − (1/10) S + (3/8) S = 12 C H constraints constraints constraints constraints A = 12 − (25/6) S − (85/8) S + S = 110 C H M S = 110 M A , B , S , S , S 0 C H M ≥ 23LINEAR PROGRAMMING brewer’s problem ‣ simplex algorithm ‣ implementations ‣ Algorithms reductions ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduLINEAR PROGRAMMING brewer’s problem ‣ simplex algorithm ‣ implementations ‣ Algorithms reductions ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduSimplex tableau Encode standard form LP in a single Java 2D array. maximize Z 13A + 23B − Z = 0 subject subject subject subject 5A + 15B + S = 480 C to the to the to the to the 4A + 4B + S = 160 H constraints constraints constraints constraints 35A + 20B + S = 1190 M A , B , S , S , S 0 C H M ≥ 5 15 1 0 0 480 4 4 0 1 0 160 m A I b 35 20 0 0 1 1190 1 c 0 0 13 23 0 0 0 0 n m 1 initial simplex tableaux 26Simplex tableau Simplex algorithm transforms initial 2D array into solution. maximize Z − S − 2 S − Z = 800 C H subject subject subject subject B + (1/10) S + (1/8) S = 28 C H to the to the to the to the A − (1/10) S + (3/8) S = 12 C H constraints constraints constraints constraints − (25/6) S − (85/8) S + S = 110 C H M A , B , S , S , S 0 C H M ≥ 0 1 1/10 1/8 0 28 1 0 1/10 3/8 0 12 m x 0 0 25/6 85/8 1 110 1 Z ≤ 0 ≤ 0 0 0 1 2 0 800 n m 1 final simplex tableaux 27Simplex algorithm: initial simplex tableaux Construct the initial simplex tableau. m A I b 1 c 0 0 n m 1 public class Simplex constructor private double a; // simplex tableaux private int m, n; // M constraints, N variables public Simplex(double A, double b, double c) m = b.length; n = c.length; a = new doublem+1m+n+1; put A into tableau for (int i = 0; i m; i++) for (int j = 0; j n; j++) aij = Aij; put I into tableau for (int j = n; j m + n; j++) ajnj = 1.0; put c into tableau for (int j = 0; j n; j++) amj = cj; put b into tableau for (int i = 0; i m; i++) aim+n = bi; 28Simplex algorithm: Bland's rule q m+n 0 Find entering column q using Bland's rule: 0 index of first column whose objective function p + coefficient is positive. m + private int bland() for (int q = 0; q m + n; q++) entering column q has positive if (aMq 0) return q; objective function coefficient optimal return 1; 29Simplex algorithm: minratio rule q m+n 0 Find leaving row p using min ratio rule. 0 (Bland's rule: if a tie, choose first such row) p + m + private int minRatioRule(int q) leaving row int p = 1; for (int i = 0; i m; i++) consider only if (aiq = 0) continue; positive entries else if (p == 1) p = i; else if (aim+n / aiq apm+n / apq) row p has min p = i; ratio so far return p; 30Simplex algorithm: pivot q m+n 0 Pivot on element row p, column q. 0 p + m + public void pivot(int p, int q) for (int i = 0; i = m; i++) for (int j = 0; j = m+n; j++) scale all entries but if (i = p j = q) row p and column q aij = apj aiq / apq; for (int i = 0; i = m; i++) zero out column q if (i = p) aiq = 0.0; for (int j = 0; j = m+n; j++) scale row p if (j = q) apj /= apq; apq = 1.0; 31Simplex algorithm: barebones implementation q m+n 0 Execute the simplex algorithm. 0 p + m + public void solve() while (true) int q = bland(); entering column q (optimal if 1) if (q == 1) break; int p = minRatioRule(q); leaving row p (unbounded if 1) if (p == 1) ... pivot on row p, column q pivot(p, q); 32Simplex algorithm: running time Remarkable property. In typical practical applications, simplex algorithm terminates after at most 2 (m + n) pivots. “ Yes. Most of the time it solved problems with m equations in 2m or 3m steps— that was truly amazing. I certainly did not anticipate that it would turn out to be so terrific. I had had no experience at the time with problems in higher dimensions, and I didn't trust my geometrical intuition. For example, my intuition told me that the procedure would require too many steps wandering from one adjacent vertex to the next. In practice it takes few steps. In brief, one's intuition in higher dimensional space is not worth a damn Only now, almost forty years from the time when the simplex method was first proposed, are people beginning to get some insight into why it works as well as it does. ” — George Dantzig 1984 33Simplex algorithm: running time Remarkable property. In typical practical applications, simplex algorithm terminates after at most 2 (m + n) pivots. Pivoting rules. Carefully balance the cost of finding an entering variable with the number of pivots needed. No pivot rule is known that is guaranteed to be polynomial. Most pivot rules are known to be exponential (or worse) in worstcase. SmoothedAnalysisofAlgorithms: WhytheSimplex AlgorithmUsuallyTakesPolynomialTime Daniel A. Spielman ShangHua Teng Department of Mathematics Akamai Technologies Inc. and M.I.T. Department of Computer Science Cambridge, MA 02139 University of Illinois at UrbanaChampaign spielmanmit.edu stengcs.uiuc.edu ABSTRACT 34 1. INTRODUCTION 1.1 Background Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Tocopy otherwise, to republish, topostonserversortoredistribute tolists,requires priorspecific permission and/or a fee. STOC’01, July 68,2001, Hersonissos, Crete, Greece. Copyright 2001 ACM 1581133499/01/0007 ... 5.00. 296Simplex algorithm: degeneracy Degeneracy. New basis, same extreme point. "stalling" is common in practice Cycling. Get stuck by cycling through different bases that all correspond to same extreme point. Doesn't occur in the wild. Bland's rule guarantees finite of pivots. choose lowest valid index for entering and leaving columns 35Simplex algorithm: implementation issues To improve the barebones implementation. requires artful engineering Avoid stalling. requires fancy data structures Maintain sparsity. requires advanced math Numerical stability. run "phase I" simplex algorithm Detect infeasibility. no leaving row Detect unboundedness. Best practice. Don't implement it yourself Basic implementations. Available in many programming environments. Industrialstrength solvers. Routinely solve LPs with millions of variables. Modeling languages. Simplify task of modeling problem as LP. 36LP solvers: industrial strength “ a benchmark production planning model solved using linear programming would have taken 82 years to solve in 1988, using the computers and the linear programming algorithms of the day. Fifteen years later—in 2003—this same model could be solved in roughly 1 minute, an improvement by a factor of roughly 43 million. Of this, a factor of roughly 1,000 was due to increased processor speed, whereas a factor of roughly 43,000 was due to improvements in algorithms ” — Designing a Digital Future ( Report to the President and Congress, 2010 ) 37Brief history 1939. Production, planning. Kantorovich 1947. Simplex algorithm. Dantzig 1947. Duality. von Neumann, Dantzig, GaleKuhnTucker 1947. Equilibrium theory. Koopmans 1948. Berlin airlift. Dantzig 1975. Nobel Prize in Economics. Kantorovich and Koopmans 1979. Ellipsoid algorithm. Khachiyan 1984. Projectivescaling algorithm. Karmarkar 1990. Interiorpoint methods. NesterovNemirovskii, Mehorta, ... Kantorovich George Dantzig von Neumann Koopmans Khachiyan Karmarkar 38LINEAR PROGRAMMING brewer’s problem ‣ simplex algorithm ‣ implementations ‣ Algorithms reductions ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduLINEAR PROGRAMMING brewer’s problem ‣ simplex algorithm ‣ implementations ‣ Algorithms reductions ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduReductions to standard form Minimization problem. Replace min 13A + 15B with max – 13A – 15B. ≥ constraints. Replace 4A + 4B ≥ 160 with 4A + 4B – S = 160, S ≥ 0. H H Unrestricted variables. Replace B with B = B – B , B ≥ 0 , B ≥ 0. 0 1 0 1 nonstandard form KBMBKBx2 13A + 15B +ibmD2iQ, 5A + 15B ≤ 480 4A+4B ≥ 160 35A + 20B = 1190 A ≥ 0 BBbmM`2bi`B+i2/ standard form KtBKBx2 −13A − 15B + 15B 0 1 +ibmD2iQ, 5A + 15B − 15B + S = 480 0 1 C 4A+4B − 4B − S = 160 0 1 H 35A + 20B − 20B = 1190 0 1 A B B S S ≥ 0 0 1 C H 41Modeling Linear “programming” (1950s term) = reduction to LP (modern term). Process of formulating an LP model for a problem. Solution to LP for a specific problem gives solution to the problem. 1. Identify variables. 2. Define constraints (inequalities and equations). 3. Define objective function. software usually performs 4. Convert to standard form. this step automatically Examples. Maxflow. Shortest paths. Bipartite matching. Assignment problem. 2person zerosum games. ... 42maxfl ow problem maxfl ow solution V 6 Max flow from 0 to 5 E Maxflow problem (revisited) 8 02 3.0 2.0 LP solution LP formulation 0 1 2.0 01 2.0 2.0 0 2 3.0 Maximize x + x 35 45 14 1.0 1.0 Input. Weighted digraph G 1 3 3.0 , single source s and single sink t. subject to the constraints 13 3.0 1.0 1 4 1.0 Goal. Find maximum flow from s to t. 0 x 2 x = 2 2 3 1.0 01 01 23 1.0 1.0 2 4 1.0 0 x 3 x = 2 02 02 24 1.0 1.0 3 5 2.0 0 x 3 x = 1 13 13 35 2.0 2.0 4 5 3.0 0 x 1 x = 1 14 14 45 3.0 2.0 0 x 1 x = 1 23 23 Max flow value: 4.0 capacities 0 x 1 x = 1 24 24 0 x 2 x = 2 35 35 maxfl ow problem maxfl ow solution 0 x 3 x = 2 45 45 V x = x + x 01 13 14 Max flow from 0 to 5 6 E x = x + x 8 02 23 24 02 3.0 2.0 LP formulation LP solution 0 1 2.0 x + x = x 01 2.0 2.0 13 23 35 0 2 3.0 Maximize x + x 35 45 14 1.0 1.0 x + x = x 1 3 3.0 14 24 45 subject to the constraints 13 3.0 1.0 1 4 1.0 0 x 2 x = 2 2 3 1.0 01 01 23 1.0 1.0 2 4 1.0 0 x 3 x = 2 02 02 24 1.0 1.0 3 5 2.0 0 x 3 x = 1 13 13 35 2.0 2.0 4 5 3.0 0 x 1 x = 1 14 14 45 3.0 2.0 0 x 1 x = 1 23 23 Max flow value: 4.0 capacities 0 x 1 x = 1 24 24 Example of reducing network fl ow to linear programming 0 x 2 x = 2 35 35 0 x 3 x = 2 45 45 x = x + x 01 13 14 43 x = x + x 02 23 24 x + x = x 13 23 35 x + x = x 14 24 45 Example of reducing network fl ow to linear programmingmaxfl ow problem maxfl ow solution V 6 Max flow from 0 to 5 E Modeling the maxflow problem as a linear program 8 02 3.0 2.0 LP solution LP formulation 0 1 2.0 01 2.0 2.0 0 2 3.0 Maximize x + x 35 45 14 1.0 1.0 Variables. x = flow on edge 1 3 3.0 v→w. vw subject to the constraints 13 3.0 1.0 1 4 1.0 Constraints. Capacity and flow conservation. 0 x 2 x = 2 2 3 1.0 01 01 23 1.0 1.0 2 4 1.0 0 x 3 x = 2 maxfl ow problem maxfl ow solution Objective function. Net flow into t. 02 02 24 1.0 1.0 3 5 2.0 0 x 3 x = 1 V 13 13 35 2.0 2.0 4 5 3.0 6 Max flow from 0 to 5 E 0 x 1 x = 1 14 14 45 3.0 2.0 8 02 3.0 2.0 LP solution LP formula 0 tion x 1 x = 1 0 1 2.0 23 23 Max flow value: 4.0 capacities 01 2.0 2.0 0 2 3.0 0 x 1 x = 1 Maximize x + x 24 24 35 45 14 1.0 1.0 1 3 3.0 subject to the constraints 0 x 2 x = 2 35 35 13 3.0 1.0 1 4 1.0 maxfl ow problem maxfl ow solution 0 x 3 x = 2 0 x 2 x = 2 45 45 2 3 1.0 01 01 23 1.0 1.0 V 2 4 1.0 x = x + x 0 x 3 x = 2 01 13 14 02 02 24 1.0 1.0 Max flow from 0 to 5 6 E 3 5 2.0 x0 = x x + 3 x x = 1 8 13 13 35 2.0 2.0 02 23 24 02 3.0 2.0 4 5 3.0 LP formulation LP solution 0 1 2.0 0 x 1 x = 1 x + x = x 01 2.0 2.0 14 14 45 3.0 2.0 13 23 35 0 2 3.0 capacity constraints Maximize x + x 35 45 0 x 1 x = 1 14 1.0 1.0 x + x = x 23 23 Max flow value: 4.0 1 3 3.0 14 24 45 capacities subject to the constraints 0 x 1 13 3.0 1.0 x = 1 1 4 1.0 24 24 0 x 2 x = 2 2 3 1.0 01 01 23 1.0 1.0 0 x 2 x = 2 35 35 2 4 1.0 0 x 3 x = 2 02 02 24 1.0 1.0 0 x 3 x = 2 45 45 3 5 2.0 0 x 3 x = 1 13 13 35 2.0 2.0 x = x + x 4 5 3.0 01 13 14 0 x 1 x = 1 14 14 45 3.0 2.0 x = x + x flow conservation 02 23 24 0 x 1 x = 1 23 23 Max flow value: 4.0 constraints capacities x + x = x 13 23 35 0 x 1 x = 1 24 24 x + x = x 14 24 45 Example of reducing network fl ow to linear programming 0 x 2 x = 2 35 35 0 x 3 x = 2 45 45 x = x + x 01 13 14 44 x = x + x 02 23 24 x + x = x 13 23 35 x + x = x 14 24 45 Example of reducing network fl ow to linear programming Example of reducing network fl ow to linear programmingMaximum cardinality bipartite matching problem Input. Bipartite graph. Goal. Find a matching of maximum cardinality. set of edges with no vertex appearing twice Interpretation. Mutual preference constraints. People to jobs. Students to writing seminars. Alice Adobe Adobe, Apple, Google Alice, Bob, Dave Bob Apple Adobe, Apple, Yahoo Alice, Bob, Dave A B C D E F Carol Google Google, IBM, Sun Alice, Carol, Frank Dave IBM Adobe, Apple Carol, Eliza Eliza Sun 0 1 2 3 4 5 IBM, Sun, Yahoo Carol, Eliza, Frank Frank Yahoo Google, Sun, Yahoo Bob, Eliza, Frank matching of cardinality 6: Example: job offers A–1, B–5, C–2, D–0, E–3, F–4 45Maximum cardinality bipartite matching problem LP formulation. One variable per pair. Interpretation. x = 1 if person i assigned to job j. ij x + x + x + + x x + x x + x + x + x + x A0 A1 A2 A2 B0 B0 B1 B1 B5 C2 C3 C3 C4 maximize + x + x + x + x + x + x + + x + x + x + + x x D0 D1 D1 E3 E3 E4 E4 E5 F2 F4 F5 at most one job per person at most one person per job ≤ 1 ≤ 1 x + x + x x + x + x A0 A1 A2 A0 B0 D0 x + x + x ≤ 1 x + x + x ≤ 1 B0 B1 B5 A1 B1 D1 s su ub bje jec ct t x + x + x ≤ 1 x + x + x ≤ 1 C2 C3 C4 A2 C2 F2 to to th the e x + x ≤ 1 x + x ≤ 1 D0 D1 C3 E3 co con nstr strain aints ts x + x + x ≤ 1 x + x + x ≤ 1 E3 E4 E5 C4 E4 F4 x + x + x ≤ 1 x + x + x ≤ 1 F2 F4 F5 B5 E5 F5 all x all x all x ≥≥ 0 0 ij ij Theorem. Birkhoff 1946, von Neumann 1953 All extreme points of the above polyhedron have integer (0 or 1) coordinates. not usually so lucky Corollary. Can solve matching problem by solving LP. 46Linear programming perspective Q. Got an optimization problem Ex. Maxflow, bipartite matching, shortest paths, … many, many, more Approach 1: Use a specialized algorithm to solve it. Algorithms 4/e. Vast literature on algorithms. Approach 2: Use linear programming. Many problems are easily modeled as LPs. Commercial solvers can solve those LPs. Might be slower than specialized solution (but you might not care). Got an LP solver Learn to use it 47Universal problemsolving model (in theory) Is there a universal problemsolving model Maxflow. Shortest paths. Bipartite matching. Assignment problem. tractable Multicommodity flow. … Twoperson zerosum games. Linear programming. … Factoring intractable NPcomplete problems. … see next lecture Does P = NP No universal problemsolving model exists unless P = NP. 48LINEAR PROGRAMMING brewer’s problem ‣ simplex algorithm ‣ implementations ‣ Algorithms reductions ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduROBERT SEDGEWICK KEVIN WAYNE Algorithms LINEAR PROGRAMMING brewer’s problem ‣ simplex algorithm ‣ implementations ‣ Algorithms FOUR TH EDITION reductions ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.BenjaminClark
User Type:
Teacher
Country:
United States
Uploaded Date:
21-07-2017