Integer hull of a polytope

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 close merge delete

Sort by » oldest newest most voted

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()
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.

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.