
Re: Go from any vertex to any other vertex in one Simplex method pivot.
Posted:
Jan 20, 2013 9:53 AM


"analyst41@hotmail.com" <analyst41@hotmail.com> writes: >Consider the LP > >Max Z =3D x1 + x2 > >such that > >0<=3Dx1 <=3D1 >0<=3Dx2 <=3D 1. > >If you start from (Z,x1,x2) =3D (0,0,0) to go the optimum (Z,x1,x2) =3D >(2,1,1) you need two pivots, because you can't go 'through" the unit >square under the Simplex method. > >If you do the variable transformation > > y1 =3D x1 +x2 > y2 =3D x1 =96 x2 > > x1 =3D (y1 + y2)/2 > x2 =3D (y1 =96 y2)/2 > >The LP becomes > >Max Z =3D y1 > >Such that > >0<=3D y1+y2 <=3D 2 >0 <=3D (y1 =96 y2)<=3D 2 > >After introduing slack variables t1,t2,s1,s2, we get > >Z y1 =3D 0 > t1  y1  y2 =3D 0 > s1 + y1 + y2 =3D 2 > t2  y1 + y2 =3D 0 > s2 + y1  y2 =3D 2 > >The BFS corresponding to this table > >(Z,t1,t2,s1,s2,y1,y2) =3D (0,0,0,2,2,0,0) corresponds to (Z,x1,x2) =3D >(0,0,0) in the original LP. > >Now a single pivot on y1 in row 3 produces the optimal table > >Z +s1 +y2 =3D 2 > t1 +s1 =3D 2 > s1 +y1 +y2 =3D 2 > t2 +s1 +2y2 =3D 2 > s1 + s2 2y2 =3D 0 > >The BFS corresponding to this table > >(Z,t1,t2,s1,s2,y1,y2) =3D (2,2,2,0,0,2,0) corresponds to (Z,x1,x2) =3D >( 2,1,1) in the original LP. > >Thus, the optimum is reached in one pivot. > >Any ideas to generalize to n dimensions would be appreciated.
based on the dual variables you could do _in the original problem!_ what is known as ''multiple inactivation'' in NLP. Indeed, change of the basis consists in 'inacvtivating' one constraint (outgoing variable) and immediately activating a newly active constraint (the incoming variable). In the usual LP, going from one vertex to the next results in a rank one update of the basis matrix (and/or its inverse). If you do multiple inactivating, a corresponding multiple rank update must be done, and little is won. also, with multpiple inactivation, the next point is not necessarily a vertex hence you get a considerable different algorithm. this might be the reason that no one considers this in current software. hth peter

