Ask Your Question

Integer hull of a polytope

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

Han gravatar image

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

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?

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

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

tmonteil gravatar image

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 more


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 gravatar imageHan ( 2014-10-06 13:37:24 +0200 )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 gravatar imagetmonteil ( 2014-10-06 13:46:07 +0200 )edit

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

Han gravatar imageHan ( 2014-10-07 06:43:31 +0200 )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



Asked: 2014-10-06 10:30:12 +0200

Seen: 527 times

Last updated: Oct 06 '14