Go from any vertex to any other vertex in one Simplex method pivot.

[anal...@hotmail.com]

Consider the LP

Max Z = x1 + x2

such that

0<=x1 <=1
0<=x2 <= 1.

If you start from (Z,x1,x2) = (0,0,0) to go the optimum (Z,x1,x2) =
(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 = x1 +x2
y2 = x1 – x2

x1 = (y1 + y2)/2
x2 = (y1 – y2)/2

The LP becomes

Max Z = y1

Such that

0<= y1+y2 <= 2
0 <= (y1 – y2)<= 2

After introduing slack variables t1,t2,s1,s2, we get

Z -y1 = 0
t1 - y1 - y2 = 0
s1 + y1 + y2 = 2
t2 - y1 + y2 = 0
s2 + y1 - y2 = 2

The BFS corresponding to this table

(Z,t1,t2,s1,s2,y1,y2) = (0,0,0,2,2,0,0) corresponds to (Z,x1,x2) =
(0,0,0) in the original LP.

Now a single pivot on y1 in row 3 produces the optimal table

Z +s1 +y2 = 2
t1 +s1 = 2
s1 +y1 +y2 = 2
t2 +s1 +2y2 = 2
-s1 + s2 -2y2 = 0

The BFS corresponding to this table

(Z,t1,t2,s1,s2,y1,y2) = (2,2,2,0,0,2,0) corresponds to (Z,x1,x2) =
( 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.

[Peter Spellucci]

"anal...@hotmail.com" <anal...@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

[Paul]

In general, of course, you don't know the destination vertex (else you would not need to solve the problem).

Interior point methods (http://en.wikipedia.org/wiki/Interior_point_method) "go through" the feasible region, but there is non-trivial work to be done recovering a vertex solution at the other end. They're faster for some LPs but not for all.

Paul