Integer hull of a polytope

Loading [MathJax]/jax/output/HTML-CSS/jax.js

Han
71 ●4 ●6 ●13

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?

add a comment

1 Answer

Sort by » oldest newest most voted

answered 10 years ago

tmonteil
27483 ●32 ●205 ●519 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()

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 ( 10 years ago )

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 ( 10 years ago )

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

Han ( 10 years ago )

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

Question Tools

2 followers

Stats

Asked: 10 years ago

Seen: 610 times

Last updated: Oct 06 '14

Integer hull of a polytope savecancel

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions