Use solve with inequality extracted from polytope

analysis

asked 2021-05-28 10:32:38 +0100

Cyrille
1407 ●34 ●76 ●138

updated 2021-05-29 16:59:41 +0100

slelievre
17684 ●22 ●160 ●349 http://carva.org/samue...

Starting from a polytope, I would like to extract the inequalities of its hyperplane representation and solve them with Sage's solve.

Define the dodecahedron and obtain its hyperplane representation.

sage: D = polytopes.dodecahedron()
sage: DH = D.Hrepresentation()

Pick the first inequality:

sage: DH[0]
An inequality (0, -1/2, -1/4*sqrt5 - 1/4) x + 1 >= 0

Try to feed it to solve:

sage: sol = solve(DH[0], x[1])

This doesn't work. So what can I do?

edit retag flag offensive close merge delete

Comments

Could you please provide the constructions of all objects so that we could reproduce ?

tmonteil ( 2021-05-28 12:55:15 +0100 )edit

Sorry for my distraction the polyhedron was not in the cell. I have corrected my question.

Cyrille ( 2021-05-28 15:07:07 +0100 )edit

What do you want to achieve at the end ? Even if you could transform this inequality into a symbolic inequality, there will be infinitely many solutions (a whole half-space).

tmonteil ( 2021-05-28 15:54:46 +0100 )edit

It's to demonstrate step by step Fourier -Motzkin elimination. I have done it with your help for one variable. I want to be able to do it as I do it on a sheet of paper. I want after to plot the 3 D polyhedra then its projections in 2D abd then in 2D.

Cyrille ( 2021-05-28 23:32:45 +0100 )edit

Instead of "this doesn't work", say what error you get, and what you were hoping to get.

slelievre ( 2021-05-29 16:53:42 +0100 )edit

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2021-05-29 16:58:19 +0100

slelievre
17684 ●22 ●160 ●349 http://carva.org/samue...

updated 2021-05-30 10:55:02 +0100

It seems you would like to extract the inequalities of the hyperplane representation of a polytope as symbolic inequalities (in Sage's symbolic ring).

Maybe this helps.

sage: D = polytopes.dodecahedron()

sage: DH = D.Hrepresentation()
sage: DH[0]
An inequality (0, -1/2, -1/4*sqrt5 - 1/4) x + 1 >= 0

sage: ieq = DH[0]
sage: ieq
An inequality (0, -1/2, -1/4*sqrt5 - 1/4) x + 1 >= 0

sage: ieq.A()
(0, -1/2, -1/4*sqrt5 - 1/4)
sage: parent(ieq.A())
Vector space of dimension 3 over Number Field in sqrt5 with
defining polynomial x^2 - 5 with sqrt5 = 2.236067977499790?

sage: ieq.b()
1

sage: x, y, z = SR.var('x, y, z')

sage: symbolic_ieq = ieq.A() * vector([x, y, z]) + ieq.b() >= 0
sage: symbolic_ieq
-1/4*z*(sqrt(5) + 1) - 1/2*y + 1 >= 0

sage: solve(symbolic_ieq, x)
[[y == -1/2*z*(sqrt(5) + 1) + 2],
 [z < -2*y/(sqrt(5) + 1) + 4/(sqrt(5) + 1)]]

Using indexed variables instead:

sage: x = vector(SR.var('x', 3))
sage: x
(x0, x1, x2)
sage: symbolic_ieq = ieq.A() * x + ieq.b() >= 0
sage: symbolic_ieq
-1/4*x2*(sqrt(5) + 1) - 1/2*x1 + 1 >= 0
sage: solve(symbolic_ieq, x[0])
[[x1 == -1/2*x2*(sqrt(5) + 1) + 2],
 [x2 < -2*x1/(sqrt(5) + 1) + 4/(sqrt(5) + 1)]]

edit flag offensive delete link

Comments

It's exactly my problem and finaly I have an other way to extract it element by element. But there is some thing extremely weird here. My code (the one used to ask the question) which seems exactly the same as yours, has not the same behaviour than yours in the same notebook. I have made some screen capture but I do not know how to include it in the question.

Cyrille ( 2021-05-29 20:20:35 +0100 )edit

Expanded answer to address using indexed variables x0, x1, x2 instead of x, y, z.

slelievre ( 2021-05-30 10:55:46 +0100 )edit

add a comment

answered 2021-05-30 00:14:42 +0100

tmonteil
27413 ●31 ●204 ●517 http://wiki.sagemath.o...

I still do not understand what you are looking for, but maybe knowing that a polytope can be turned into a linear problem might help :

sage: D = polytopes.dodecahedron()
sage: p,x = D.to_linear_program(return_variable=True)
sage: p
Linear Program (no objective, 3 variables, 12 constraints)
sage: p.show()
Maximization:

Constraints:
  1/2 x2 + 1/4*sqrt5 + 1/4 x3 <= 1
  -1/2 x2 + 1/4*sqrt5 + 1/4 x3 <= 1
  1/2 x1 + 1/4*sqrt5 + 1/4 x2 <= 1
  1/2 x1 - 1/4*sqrt5 + 1/4 x2 <= 1
  1/4*sqrt5 + 1/4 x1 + 1/2 x3 <= 1
  1/4*sqrt5 + 1/4 x1 - 1/2 x3 <= 1
  -1/2 x1 + 1/4*sqrt5 + 1/4 x2 <= 1
  -1/2 x1 - 1/4*sqrt5 + 1/4 x2 <= 1
  -1/4*sqrt5 - 1/4 x1 + 1/2 x3 <= 1
  1/2 x2 - 1/4*sqrt5 + 1/4 x3 <= 1
  -1/2 x2 - 1/4*sqrt5 + 1/4 x3 <= 1
  -1/4*sqrt5 - 1/4 x1 - 1/2 x3 <= 1
Variables:
  x1 = x_0 is a continuous variable (min=-oo, max=+oo)
  x2 = x_1 is a continuous variable (min=-oo, max=+oo)
  x3 = x_2 is a continuous variable (min=-oo, max=+oo)

edit flag offensive delete link

Comments

This is very usefull since it's a good way to generate a lot of exercices in linear programming. But the answer of Samuel is the good one. I will send you what I am doing at the end. For the moment I need a way to send you to screen capture to show you that at least on my computer there is a strange effect. It is perhaps caused by the catch but I do not believe.

Cyrille ( 2021-05-30 09:18:49 +0100 )edit

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Use solve with inequality extracted from polytope

Comments

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Use solve with inequality extracted from polytope edit

Comments

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Use solve with inequality extracted from polytope