CSE 548: (Design And) Analysis Of Algorithms - Linear .

IntroCSE 548: (Design and) Analysis of AlgorithmsLinear ProgrammingR. Sekar1 / 14

IntroOverviewOverviewA technique for modeling a diverse range of optimization problemsLP is more of a modeling technique: You are not being asked todevelop new “LP algorithms,” but to model existing problems using LP.Existing solvers can solve these problemsWe cover the intuition behind the solver, but not in great depth.2 / 14

e 7.1 (a) The feasible region for a linear program. (b) Contour lines of the obon: x1 6x2 c for different values of the profit c.Example 1: Profit Maximization(b)x24003002001000x2400 100Optimum pointProfit 1900300c 1500200c 1200100c 600200300400x10Product P1 generates 1/unit, P2 generates 6/unitMax 200 units of P1 and 300 of P2 can be sold100200300x400Max x1 6x2x1 200, x2 300h, and x2 boxes of Nuit, at a more substantial profit of 6 apiece; x 1 and x2 are unCompanyproduce Buta totalx1 constraints x2 400 onthat wewish tocandetermine.thisofis400notunitsall; there are also somet must(Cannotbe accommodated(besidestheobviousone,x,x 0).First,daily1 2produce negative number of units!)x1the, x2 0 dese exclusive chocolates is limited to at most 200 boxes of Pyramide and 300 boAlso,the currentcanproduce a shouldtotal of beat most400 boxes of chocolate pNote:It is easyworkforceto see thata maximumat a vertex3 / 14

etter objective value. In this way it does hill-climbing onfromneighborto neighbor so as to steadily increase profitSimplexMethodjectory.Intro300Profit 1900OverviewApplicable to convex problems, i.e.,conjunctions, and linear constraints, i.e.,no squaring/multiplication of variables.Feasible regions are convex polygons 1400200SimplexStart at the origin100 00100 200200Switch to neighboring vertex if objectivefunction f (x̄) is higherRepeat until you reach a local maximawhich will be a global maximaConsideritthetoline c passingo better neighbor, simplex declaresbef (x̄)optimalandthrough the vertex. Rest of the polygonply global optimality? By simple geometry—think of themust be below this line.ex. Since all the vertex’s neighbors lie below the line, the4 / 14

as much, which imposes another constraint x 2 3x3 600. Whate polyhedron for a three-variable linear program.of production?Herex2is the updated linear program.Example 2: On to more products .max x1 6x2 13x3x1 200Optimumx2 300x1 x2 x3 400x2 3x3 600x1 , x 2 , x 3 0x1The space of solutions is now three-dimensional.Search follows these Eachsteps: linear eqand each inequality a half-space on one side of the plane. The feasib(0, 0, 0) (Figure(200, 0, 0)(200, 200,200)figuof seven half-spaces, a polyhedron7.2). Lookingat the 200polyhedron? 1400inequality corresponds to 0each face of thec. As cA profit of c corresponds to the1 6x3 100) plane(200, 0,x200) 2 13x(0, 300,moves parallel to itself, further and furtherintothepositive 2800 3100 orthan1925 / 14

bandwidth is exceeded and that each connection gets a bandwidth of at leanications network between three users A, B, and C. Bandwidths areExample 3: Communication NetworkuserAmax 3xAB 3x AB 2xBC 2x BC 4xAC 4x ACxAB x AB xBC x BC 1012xAB x ABxBC x BCabuser1310B xAC xAB x BC 116 xAC x ABx ABc xBC x BCx ACx ACx ACx AC 12[edge (a, A)] 6[edge (a, b)] 8[edge (c, C)] 13[edge (b, c)] xAC 11xAB x AB8xBC x BCuserCxAC x ACxAB , x AB , xBC , x BC , xAC , x AC[edge (b, B)][edge (a, c)] 2 2 2 0A–B,B–CaandA–Ctrafficpay 3, 2,Eventinyexampleone 4/unitis hardto solveitonone’s own (try it!), ;for instance,mightrkers m 2 units per connectioner to make sense, and the overall cost would then increase correspond0x andto ferthe variablesonfairlylargevalues,xAB take x AB 7,xand x BC 1.5,xAC 0.5, x AC 4.5BC(double-digit)unlikelyare xother0 1.5,0 4.5 inSol:tox affect 0,thingsx 0 too7, xmuch. xThere LPs,0.5, xhowever,ABABBCBCACAC6 / 14

Matrix-vector notationA linear function like x1 6x2 can be written as the dot product of two vectors 1x1c and x ,x26denoted c · x or cT x. Similarly, linear constraints can be compiled into matrix-vector form: 2001 0 200x1x1 0 1 300 .x2 300x24001 1x1 x2 400 Ax bHere each row of matrix A corresponds to one constraint: its dot product with x is at mostthe value in the corresponding row of b. In other words, if the rows of A are the vectorsa1 , . . . , am , then the statement Ax b is equivalent toai · x bi for all i 1, . . . , m.With these notational conveniences, a generic LP can be expressed simply asmax cT xAx bx 0.7 / 14

IntroOverviewOptimality of SolutionMultiply (3) by 5 and (4) by 1 and add:Max x1 6x2(1)5·x2 1·(x1 x2 ) 5·300 1·400x1 200(2)x2 300(3)x1 x2 400(4)x1 6·x2 1900Magically, we have a proof that the maximumpossible value for profit is 1900x1 , x2 0(5)This is a certificate of optimality for thesolution found by LP!8 / 14

IntroOverviewConstructing Dual ProblemIntroduce a multiplier yi for each equation:MultiplierInequalityy1x1 200y2x2 300y3x1 x2 400After muliplying and adding, we get(y1 y3 )x1 (y2 y3 )x2 200y1 300y2 400y3To get optimality proof, we need y1 y3 1, y2 y3 6. In other words,we have the dual problem:Min200y1 300y2 400y3y1 y3 1y2 y3 6y1 , y2 , y3 09 / 14

IntroOverviewDualitygure 7.10 A generic primal LP in matrix-vector form, and its dual.Primal LP:Dual LP:max cT xmin yT bAx byT A cTx 0y 0Theorem (Duality)If a linear program has a bounded optimum, then so does it dual,and the two optima coincide.gure 7.11 In the most general case of linear programming, we have a send a set E of equalities (a total of m I E constraints) over n varibset N are constrained to be nonnegative. The dual has m I E valy those corresponding to I have nonnegativity constraints.10 / 14

IntroOverviewSimplex Algorithm“Pebble falling down:”If you rotate the axes so that the normal to the hyperplanerepresented by the objective function faces down,then simplex operation resembles that of a pebble starting fromone vertex, sliding down to the next vertex down and the nextvertex down,until it reaches the minimum.For simplicity, we consider only those cases where there is a uniquesolution, i.e., ignore degenerate cases.11 / 14

IntroOverviewSimplex AlgorithmWhat is the space of feasible solutions?A convex polyhedron in n-dimensions (n number of variables)What is a vertex?A point of intersection of n inequalities (“hyperplanes”)What is a neighboring vertex?Two vertices are neighbors if they share n 1 inequalities.Vertex found by solving n simultaneous equationsHow many times can it fall? There are m inequalities and n variables, som nn vertices can bethere.This is an exponential number, but simplex works exceptionally well inpractice.12 / 14

IntroOverviewure 7.12 A polyhedron defined by seven inequalities.Simplex Algorithmx2max x1 A2 7 CBx1 x 2 3 4 x3x2 1 5 x16 13 / 14

IntroOverviewHistory and Main LP AlgorithmsFourier (1800s) Informal/implicit useKantorovich (1930) Applications to problems in EconomicsKoopmans (1940) Application to shipping problemsDantzig (1947) Simplex method.Nobel Prize (1975) Kantorovich and Koopmans, not DantzigKhachiyan (1979) Ellipsoid algorithm, polynomial time but not competitive inpractice.Karmarkar (1984) Interior point method, polynomial time, good practicalperformance.14 / 14

A linear equation in x 1 and x 2 denes a line in the two-dimensional (2D) plane, and a linear inequality designates a half-space, the region on one side of the line. Thus the set of all feasible solutions of this linear program, that is, the points (x 1,x2) which satisfy all constraints, is the intersection of ve half-spaces.