The Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Math Forum » Discussions » sci.math.* » sci.stat.math

Topic: Go from any vertex to any other vertex in one Simplex method pivot.
Replies: 2   Last Post: Jan 20, 2013 5:54 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Peter Spellucci

Posts: 221
Registered: 11/9/09
Re: Go from any vertex to any other vertex in one Simplex method pivot.
Posted: Jan 20, 2013 9:53 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

"" <> 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.

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2017. All Rights Reserved.