Integer hull of a polytope

asked 2014-10-06 10:30:12 +0100

Han
71 ●4 ●6 ●13

updated 2014-10-06 10:31:52 +0100

I'm trying to generate the matching polytope for general graphs by using MixedIntegerLinearProgram and Polyhedron.

Generally, starting with the incidence matrix of a given graph $G$, I can accomplish this task by either setting variables in MixedIntegerLinearProgram to be binary or adding the odd set constraints to MixedIntegerLinearProgram.

But now I'm trying to get the matching polytope by simply taking the Integer Hull of the polytope defined by incidence matrix of $G$ without setting variables to be binary or adding the odd set constraints to MixedIntegerLinearProgram.

So is there a integer_hull function in sage or how can I get the integer hull from a given convex hull?

answered 2014-10-06 11:27:06 +0100

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

For the binary part, when you define the variable as blah = p.new_variable(binary=True), just replace it by blah = p.new_variable(integer=True, nonnegative=True) or blah = p.new_variable(integer=True, nonnegative=False).

If you do not want to add some odd constraints, just to not add them.

To get the integer hull, you can do:

sage: P = p.polyhedron()
sage: Hull = P.integral_points()

edit flag offensive delete link

Comments

Thank you so much. I didn't know the function `integral_points()`. Just defining a new polyhedron on the integral points gives rise to the desired integer hull.

Han ( 2014-10-06 13:37:24 +0100 )edit

Actually ``integral_points()`` is not a function, but a method of the object ``P`` that is a polyhedron. To find all methods that can be applied to ``P``, it suffice to type ``P.<tab>`` and you will get the list, so you do not have to know about the existence of some method to discover it.

tmonteil ( 2014-10-06 13:46:07 +0100 )edit

Thank you for the explanation. It's really helpful.

Han ( 2014-10-07 06:43:31 +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.

Integer hull of a polytope

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Integer hull of a polytope edit

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Integer hull of a polytope