Mathematics Of Operations Research - Tullo

1 A N D R E W T U L L O C HM AT H E M AT I C S O F O P -E R AT I O N S R E S E A R C HT R I N I T Y C O L L E G ET H E U N I V E R S I T Y O F C A M B R I D G EContents1 Generalities52 Constrained Hyperplanes83 Linear and Strong Program Slackness134 Simplex Points and Optimal Simplex Simplex Method in Tableau Form164 andrew tulloch5 Advanced Simplex Two-Phase Simplex s Cutting Plane Method176 Complexity of Problems and Complexity197 The Complexity of Linear Lower Bound for the Simplex Idea for a New Method218 Graphs and Cost Flows239 Transportation and Assignment Problems2510 Non-Cooperative Games2711 Strategic ~ff271/teachin/mor OptimizationMinimizef(x)subject toh(x) =b,x functionf:Rn RVectorx Rnof decision vari-ables, Functional constraint whereh:Rn >Rm,b RmRegionalconstraint whereX feasible set isX(b) ={x X:h(x) =b}.An inequality of the formg(x) bcan be written asg(x) +z=b,wherez Rmcalled a slack variable with regional constraintz the Lagrangian of a problem asL(x, ) =f(x) T(h(x) b)( )where Rmis a vector ofLagrange (Lagrangian Sufficiency Theorem).

2 Let x X and Rmsuch thatL(x, ) =infx XL(x , )( )and h(x) =b. Then x is optimal for andrew X(b)f(x ) =minx X(b)[f(x) T(h(x ) b)]( ) minx X[f(x ) T(h(x ) b)]( )=f(x) T(h(x) b)( )=f(x)( ) (b) =infx X(b)f(x).( )Define the Lagrange dual functiong:Rm Rwithg( ) =in fx XL(x, )( )Then, for all Rm,infx X(b)f(x) =infx X(b)L(x, ) infx XL(x, ) =g( )( )That is,g( )is a lower bound on our optimization motivates thedual problemto maximizeg( )subject to Y, whereY={ Rm:g( )> }. (Duality).From( ), we see that the optimal value of theprimal is always greater than the optimal value of the dual. This HyperplanesFixb Rmand consider as a function ofc Rm. Further considerthe hyperplane given by :Rm Rwith (c) = T(b c)( )Now, try to find (b)as of Operations Research 9(i) For each , find =max{ : (c) (c), c Rm}( )(ii) Choose to maximize :Rm Rasupporting hyperplaneto atbif (c) = (b) T(b c)( )and (c) (b) T(b c)( )for allc following are equivalent(i) There exists a (non-vertical) supporting hyperplane to at b,(ii) XXXXXXXXXXXXXXXXXXXXXXXXXX3 Linear and Strong convex if for all [0, 1],x,y Simplies that x+ (1 )y :S Ris convex if for allx,y Sand [0, 1], f(x) + (1 )f(y) f( x+ (1 ) , the area under the function is a convex Sis an interior point ofSif there existse>0such{y: y x 2 e} Sis an extreme point ofSif for ally,z SandS (0, 1),x= y+ (1 )zimpliesx=y= (Supporting Hyperplane).)

3 Suppose that our function isconvex and b lies in the interior of the set of points where is finite. Thenthere is a (non-vertical) supporting hyperplane to at X(b) ={x X:h(x) b}, (b) =infx X(b)f(x).Then is convex if X, f , and h are ,b2 Rmsuch that (b1), (b2)are defined. Let [0, 1]andb= b1+ (1 )b2. Considerx1 X(b1),x2 X(b2)and letx= x1+ (1 ) andrew tullochBy convexity ofY,x X. By convexity ofh,h(x) =h( x1+ (1 )x2) h(x1) + (1 )h(x2) b1+ (1 )b2=bThusx X(b), and by convexity off, (b) f(x)=f( x1+ (1 )x2) f(x1) + (1 )f(x2) (b1) + (1 ) (b2) form of a linear program ismin{cTx:Ax b,x 0}( )Standard form of a linear program ismin{cTx:Ax=b,x 0}( ) Program DualityIntroduce slack variables to turn problemPinto the formmin{cTx:Ax z=b,x,z 0}( )We haveX={(x,z):x,z 0} Rm+n. The Lagrangian isL((x,z), ) =cTx T(Ax z b)( )= (cT TA)x+ Tz+ Tb( ) Mathematics of Operations Research 13and has a finite minimum if and only if Y={ :cT TA 0, 0}( )For a fixed Y, the minimum ofLis satisfied when(cT TA)x=0 and Tz=0, and thusg( ) =inf(x,z) XL((x,z), ) = Tb( )We obtain that the dual problemmax{ Tb:AT c, 0}( )and it can be shown (exercise) that the dual of the dual of a linearprogram is the original x and be feasible forPand its dual.

4 Then x and areoptimal if and only if(cT TA)x=0( ) T(Ax b) =0( ) , are optimal, thencTx= Tb by strong duality( )=infx X(cTx T(Ax b)) cTx T(Ax b) primal and dual optimality cTx( )Then the inequalities must be equalities. Thus Tb=cTx T(Ax b) = (cT TA)x =0+ Tb( )andcTx T(Ax b) =0=cTx( )14 andrew tullochIf(cT TA)x=0 and T(Ax b) =0, thencTx=cT T(Ax b) = (cT Ta)x+ Tb= Tb( )and so by weak duality,xand are SolutionsMaximizecTxsubject toAx=b,x 0,A Rm a solutionx RnofAx=bbasicif it has at mostmnon-zeroentries, that is, there existsB {1, .. ,n}with|B|=mandxi=0 ifi/ basic solutionxwithx 0 is called abasic feasible solution(bfs). Points and Optimal SolutionsWe make the following assumptions:(i) The rows ofAare linearly independent(ii) Every set ofmcolumns ofAare linearly independent.(iii) Every basic solution is non-degenerate - that is, it has exactlymnon-zero is abfsof Ax=b if and only if it is an extreme point ofthe set X(b) ={x:Ax=b,x 0}.

5 The problem has a finite optimum (feasible and bounded),then it has an optimal solution that is andrew Simplex TableauLetA Rm n,b Rm. LetBbe a basis (in thebfssense), andx Rn, such thatAx=b. ThenABxB+ANxN=b( )whereAB Rm mandAN Rm (n m)respectively consist of thecolumns ofAindexed byBand those not indexed byB. Moreover,ifxis a basic solution, then there is a basicBsuch thatxN=0 andABxB=b, and ifxis a basic feasible solution, there is a basisBsuchthatxn=0,ABxB=b, andxB everyxwithAx=band every basisB, we havexB=A 1B(b ANxN)( )as we assume thatABhas full rank. Thus,f(x) =cTx=cTBxB+cTNxN( )=cTBA 1B(b ANXN) +cTNxN( )=CTBA 1Bb+ (cTN cTBA 1 BAN)xN( )Assume we can guarantee thatA 1Bb=0. Thenx?withx?B=A 1 Bbandx?N=0 is abfswithf(x?) =CTBA 1Bb( )Assume that we are maximizingcTx. There are two different cases:(i) IfCTN CTBA 1 BAN 0, thenf(x) cTBA 1 Bbfor every feasiblex, sox?is optimal.(ii) If(cTN cTBA 1 BAN)i>0, then we can increase the objective valueby increasing the corresponding row of(xN) Simplex Method in Tableau Form5 Advanced Simplex Two-Phase Simplex MethodFinding an initialbfsis easy if the constraints have the formAx=bwhereb 0, asAx+z=b,(x,z) = (0,b)( ) s Cutting Plane MethodUsed in integer programming (IP).

6 This is a linear program where inaddition some of the variables are required to be that for a given integer program we have found an op-timal fractional solutionx?with basisBand letaij= (A 1 BAj)andai0= (A 1Bb)be the entries of the final tableau. Ifx?is not integral,the for some rowi,ai0is not integral. For every feasible solutionx,xi= j Nbaijcxj xi+ j Naijxj=ai0.( )Ifxis integral, then the left hand side is integral as well, and theinequality must still hold if the right hand side is rounded ,xi+ j Nbaijcxj bai0c.( )Then, we can add this constraint to the problem and solve theaugmented program. One can show that this procedure converges ina finite number of of Problems and ComplexityWe measure complexity as a function of input size. The input ofa linear programming problem:c Rn,A Rm n,b Rmisrepresented in(n+m n+m) kbits if we represent each two functionsf:R Randg:R Rwritef(n) =O(g(n))( )if there existsc,n0such that for alln n0,f(n) c g(n)( ).

7 (similarly for , and ( +O))7 The Complexity of Linear Lower Bound for the Simplex exists a LP of sizeO(n2), a pivoting rule, and aninitial BFS such that the simplex method requires2n the unit cube inRn, given by constraints 0 xi 1fori=1, .. ,n. Define a spanning path inductively as follows. Indimension1, go fromx1=0 tox1=1. In dimensionk, setxk=0 andfollow the path for dimension 1, .. ,k 1. Then setx=1, and followthe path for dimension 1, .. ,k 1 objectivexncurrently increases only once. Instead considerthe perturbed unit cube given by the constraintse x1 1,exi 1 xi 1 exi 1withe (0,12). Idea for a New Methodmin{cTx:Ax=b,x 0}( )max{bT :AT c}( )By strong duality, each of these problems has a bounded optimal22 andrew tullochsolution if and only if the following set of constraints is feasible:cTx=bT ( )Ax=b( )x 0( )AT c( )It is thus enough to decide, for a givenA Rm nandb Rm,whether{x Rn:Ax b}6= . symmetric matrixD Rn nis called positivedefinite ifxTDx>0 for everyx Rn.

8 Alternatively, all eigenvaluesof the matrix are strictly setE Rngiven byE=E(z,D) ={x Rn:(x z)TD(x z) 1}( )for a positive definite symmetricD Rn nandz Rnis called anellipsoid with {x Rn:Ax b}for someA Rm nandb decide whetherP6= , we generate a sequence{Et}of ellipsoidsEtwith centersxt. Ifxt P, thenPis non-empty and the methodstops. Ifxt/ P, then one of the constraints is violated - so there existsa rowjofAsuch thataTjxt<bj. Therefore,Pis contained in thehalf-space{x Rn:aTjx aTjxt, and in particular the intersection ofthis half-space withEt, which we will call a E=E(z,D)be an ellipsoid inRnand a Rn6= the half-space H={x Rn|aTx aTz}, and letz =z+1n+1Da aTDa( )D =n2n2 1(D 2n+1 DaaTDaTDa)( )Then D is symmetric and positive definite, and therefore E =E(z ,D )is an ellipsoid. Moreover, E H E and Vol(E )<e 12(n+1)Vol(E).8 Graphs and a directed graph (network)G= (V,E),Vthe set of vertices,E V Va set of edges. Undirected ifEis Cost FlowsFill in this stuff from lecturesFill in this stuff from lectures9 Transportation and Assignment Problems10 Non-Cooperative (von Neumann,1928).}

9 Let P Rm n. Thenmaxx Xminy Yp(x,y) =miny Ymaxx Xp(x,y)( )11 Strategic Xis a best response toy Yifp(x,y) =maxx Xp(x ,y).(x,y) X Yis a Nash equilibrium ifxis a bestresponse toyandyis a best response (x,y) X Y is an equilibrium of the matrix game P ifand only ifminy Yp(x,y ) =maxx Xminy Yp(x ,y )( )andmaxx X p(x ,y) =miny Ymaxx Xp(x ,y ).( ) (x,y),(x ,y ) X Y be equilibria of the matrix gamewith payoff matrix P. Then p(x,y) =p(x ,y )and(x,y )and(x ,y)areequilibria as (Nash,1951).Every bimatrix game has an