Revision history [back]

According to wikipedia (but this is well known), A klee-Minty cube in $D$-dimension is defined by

$x_1\leq 5$

$4 x_1 + x_2 \leq 25$

$8 x_1 + 4 x_2 + x_3 \leq 125$

$16 x_1 + 8 x_2 + 4 x_3 + x_4 \leq 625\$

$32 x_1+ 16 x_2 + 8 x_3 + 4 x_4 + x_5 \leq 3125$

$\vdots \vdots$

$2^D x_1 + 2^{D-1} x_2 + 2^{D-2} x_3 + \ldots + 4 x_{D-1} + x_D \leq 5^D$

$x_1 \geq 0$

$x_2 \geq 0$

$x_3 \geq 0$

$x_4 \geq 0$

$x_5 \geq 0$

This poloyhedron has $2^D$ vertices. How can I find them. I have tried the following code

A= matrix(QQ, 10,5,[0,0,0,0,-1, 0,0,0,-1,-4, 0,0,-1,-4,-8, 0,-1,-4,-8,-16, -1,-4,-8,-16,-32,
                   1,0,0,0,0, 0,1,0,0,0, 0,0,1,0,0, 0,0,0,1,0, 0,0,0,0,1])
show(LatexExpr(r"\text{A = }"),A)
b=vector(QQ,[5,254,125,625,3125,0,0,0,0,0])
show(LatexExpr(r"\text{b = }"),b)
c=vector(QQ,[2^4,2^3,2^2,2^1,2^0])
show(LatexExpr(r"\text{c = }"),c)
AA=matrix(list(list([b])+list(transpose(A))))
show(transpose(AA))
pol = Polyhedron(ieqs = AA)
pol.Hrepresentation()

But I am far away from the account and some of the vertices are in the negative part of the hyperplan (which is impossible). Need some help to decipher my mistake. Thanks

According to wikipedia (but this is well known), A klee-Minty cube in $D$-dimension is defined by

$x_1\leq 5$

$4 x_1 + x_2 \leq 25$

$8 x_1 + 4 x_2 + x_3 \leq 125$

$16 x_1 + 8 x_2 + 4 x_3 + x_4 \leq 625\$

$32 x_1+ 16 x_2 + 8 x_3 + 4 x_4 + x_5 \leq 3125$

$\vdots \vdots$

$2^D x_1 + 2^{D-1} x_2 + 2^{D-2} x_3 + \ldots + 4 x_{D-1} + x_D \leq 5^D$

$x_1 \geq 0$

$x_2 \geq 0$

$x_3 \geq 0$

$x_4 \geq 0$

$x_5 \geq 0$

This poloyhedron polyhedron has $2^D$ vertices. How can I find them. I have tried the following code for $D=5$ --- that is 32 vertices.

A= matrix(QQ, 10,5,[0,0,0,0,-1, 0,0,0,-1,-4, 0,0,-1,-4,-8, 0,-1,-4,-8,-16, -1,-4,-8,-16,-32,
                   1,0,0,0,0, 0,1,0,0,0, 0,0,1,0,0, 0,0,0,1,0, 0,0,0,0,1])
show(LatexExpr(r"\text{A = }"),A)
b=vector(QQ,[5,254,125,625,3125,0,0,0,0,0])
show(LatexExpr(r"\text{b = }"),b)
c=vector(QQ,[2^4,2^3,2^2,2^1,2^0])
show(LatexExpr(r"\text{c = }"),c)
AA=matrix(list(list([b])+list(transpose(A))))
show(transpose(AA))
pol = Polyhedron(ieqs = AA)
pol.Hrepresentation()

But I am far away from the account and some of the vertices are in the negative part of the hyperplan (which is impossible). Need some help to decipher my mistake. Thanksmistake(s). Thanks.

According to wikipedia Wikipedia (but this is well known), A klee-Minty Klee-Minty cube in $D$-dimension $D$ dimensions is defined by by

$x_1\leq 5$

$4 x_1 + x_2 \leq 25$

$8 x_1 + 4 x_2 + x_3 \leq 125$

$16 x_1 + 8 x_2 + 4 x_3 + x_4 \leq 625\$625$

$32 x_1+ 16 x_2 + 8 x_3 + 4 x_4 + x_5 \leq 3125$

$\vdots \vdots$

$2^D x_1 + 2^{D-1} x_2 + 2^{D-2} x_3 + \ldots + 4 x_{D-1} + x_D \leq 5^D$

$x_1 \geq 0$

$x_2 \geq 0$

$x_3 \geq 0$

$x_4 \geq 0$

$x_5 \geq 0$

This polyhedron has $2^D$ vertices. How can I find them. them?

I have tried the following code for $D=5$ $D = 5$ --- that is 32 vertices. vertices.

A= A = matrix(QQ, 10,5,[0,0,0,0,-1, 0,0,0,-1,-4, 0,0,-1,-4,-8, 0,-1,-4,-8,-16, -1,-4,-8,-16,-32,
                   1,0,0,0,0, 0,1,0,0,0, 0,0,1,0,0, 0,0,0,1,0, 0,0,0,0,1])
10, 5,
           [0, 0, 0, 0, -1,
            0, 0, 0, -1, -4,
            0, 0, -1, -4, -8,
            0, -1, -4, -8, -16,
            -1, -4, -8, -16, -32,
            1, 0, 0, 0, 0,
            0, 1, 0, 0, 0,
            0, 0, 1, 0, 0,
            0, 0, 0, 1, 0,
            0, 0, 0, 0, 1])
show(LatexExpr(r"\text{A = }"),A)
b=vector(QQ,[5,254,125,625,3125,0,0,0,0,0])
}"), A)
b = vector(QQ, [5, 254, 125, 625, 3125, 0, 0, 0, 0, 0])
show(LatexExpr(r"\text{b = }"),b)
c=vector(QQ,[2^4,2^3,2^2,2^1,2^0])
}"), b)
c = vector(QQ, [2^4, 2^3, 2^2, 2^1, 2^0])
show(LatexExpr(r"\text{c = }"),c)
AA=matrix(list(list([b])+list(transpose(A))))
}"), c)
AA = matrix(list(list([b]) + list(transpose(A))))
show(transpose(AA))
pol = Polyhedron(ieqs = AA)
Polyhedron(ieqs=AA)
pol.Hrepresentation()

But I am far away from the account and some of the vertices vertices are in the negative part of the hyperplan hyperplane (which is impossible). impossible). Need some help to decipher my mistake(s). Thanks.

According to Wikipedia (but this is well known), A Klee-Minty cube in $D$ dimensions is defined by

$x_1\leq 5$

$4 x_1 + x_2 \leq 25$

$8 x_1 + 4 x_2 + x_3 \leq 125$

$16 x_1 + 8 x_2 + 4 x_3 + x_4 \leq 625$

$32 x_1+ 16 x_2 + 8 x_3 + 4 x_4 + x_5 \leq 3125$

$\vdots \vdots$

$2^D x_1 + 2^{D-1} x_2 + 2^{D-2} x_3 + \ldots + 4 x_{D-1} + x_D \leq 5^D$

$x_1 \geq 0$

$x_2 \geq 0$

$x_3 \geq 0$

$x_4 \geq 0$

$x_5 \geq 0$

This polyhedron has $2^D$ vertices. How can I find them?

I have tried the following code for $D = 5$ --- that is 32 vertices.

A = matrix(QQ, 10, 5,
           [0, 0, 0, 0, -1,
            0, 0, 0, -1, -4,
            0, 0, -1, -4, -8,
            0, -1, -4, -8, -16,
            -1, -4, -8, -16, -32,
            1, 0, 0, 0, 0,
            0, 1, 0, 0, 0,
            0, 0, 1, 0, 0,
            0, 0, 0, 1, 0,
            0, 0, 0, 0, 1])
show(LatexExpr(r"\text{A = }"), A)
b = vector(QQ, [5, 254, 125, 625, 3125, 0, 0, 0, 0, 0])
show(LatexExpr(r"\text{b = }"), b)
c = vector(QQ, [2^4, 2^3, 2^2, 2^1, 2^0])
show(LatexExpr(r"\text{c = }"), c)
AA = matrix(list(list([b]) + list(transpose(A))))
show(transpose(AA))
pol = Polyhedron(ieqs=AA)
pol.Hrepresentation()

But I am far away from the account and some of the vertices are in the negative part of the hyperplane (which is impossible). Need some help to decipher my mistake(s). Thanks.