Ask Your Question
1

Use solve with inequality extracted from polytope

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

Cyrille gravatar image

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

slelievre gravatar image

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 gravatar imagetmonteil ( 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 gravatar imageCyrille ( 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 gravatar imagetmonteil ( 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 gravatar imageCyrille ( 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 gravatar imageslelievre ( 2021-05-29 16:53:42 +0100 )edit

2 Answers

Sort by ยป oldest newest most voted
0

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

slelievre gravatar image

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 more

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 gravatar imageCyrille ( 2021-05-29 20:20:35 +0100 )edit

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

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

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

tmonteil gravatar image

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 more

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 gravatar imageCyrille ( 2021-05-30 09:18:49 +0100 )edit

Your Answer

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

Add Answer

Question Tools

1 follower

Stats

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

Seen: 359 times

Last updated: May 30 '21