ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 06 Oct 2014 23:43:31 -0500Integer hull of a polytopehttp://ask.sagemath.org/question/24404/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?Mon, 06 Oct 2014 03:30:12 -0500http://ask.sagemath.org/question/24404/integer-hull-of-a-polytope/Answer by tmonteil for <p>I'm trying to generate the matching polytope for general graphs by using <code>MixedIntegerLinearProgram</code> and <code>Polyhedron</code>.</p>
<p>Generally, starting with the incidence matrix of a given graph $G$, I can accomplish this task by either setting variables in <code>MixedIntegerLinearProgram</code> to be <code>binary</code> or adding the odd set constraints to <code>MixedIntegerLinearProgram</code>. </p>
<p>But now I'm trying to get the matching polytope by simply taking the <strong>Integer Hull</strong> of the polytope defined by incidence matrix of $G$ without setting variables to be <code>binary</code> or adding the odd set constraints to <code>MixedIntegerLinearProgram</code>.</p>
<p>So is there a <code>integer_hull</code> function in sage or how can I get the integer hull from a given convex hull?</p>
http://ask.sagemath.org/question/24404/integer-hull-of-a-polytope/?answer=24406#post-id-24406For 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()
Mon, 06 Oct 2014 04:27:06 -0500http://ask.sagemath.org/question/24404/integer-hull-of-a-polytope/?answer=24406#post-id-24406Comment by Han for <p>For the <code>binary</code> part, when you define the variable as <code>blah = p.new_variable(binary=True)</code>, just replace it by <code>blah = p.new_variable(integer=True, nonnegative=True)</code> or <code>blah = p.new_variable(integer=True, nonnegative=False)</code>.</p>
<p>If you do not want to add some odd constraints, just to not add them.</p>
<p>To get the integer hull, you can do:</p>
<pre><code>sage: P = p.polyhedron()
sage: Hull = P.integral_points()
</code></pre>
http://ask.sagemath.org/question/24404/integer-hull-of-a-polytope/?comment=24416#post-id-24416Thank you for the explanation. It's really helpful.Mon, 06 Oct 2014 23:43:31 -0500http://ask.sagemath.org/question/24404/integer-hull-of-a-polytope/?comment=24416#post-id-24416Comment by tmonteil for <p>For the <code>binary</code> part, when you define the variable as <code>blah = p.new_variable(binary=True)</code>, just replace it by <code>blah = p.new_variable(integer=True, nonnegative=True)</code> or <code>blah = p.new_variable(integer=True, nonnegative=False)</code>.</p>
<p>If you do not want to add some odd constraints, just to not add them.</p>
<p>To get the integer hull, you can do:</p>
<pre><code>sage: P = p.polyhedron()
sage: Hull = P.integral_points()
</code></pre>
http://ask.sagemath.org/question/24404/integer-hull-of-a-polytope/?comment=24409#post-id-24409Actually ``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.Mon, 06 Oct 2014 06:46:07 -0500http://ask.sagemath.org/question/24404/integer-hull-of-a-polytope/?comment=24409#post-id-24409Comment by Han for <p>For the <code>binary</code> part, when you define the variable as <code>blah = p.new_variable(binary=True)</code>, just replace it by <code>blah = p.new_variable(integer=True, nonnegative=True)</code> or <code>blah = p.new_variable(integer=True, nonnegative=False)</code>.</p>
<p>If you do not want to add some odd constraints, just to not add them.</p>
<p>To get the integer hull, you can do:</p>
<pre><code>sage: P = p.polyhedron()
sage: Hull = P.integral_points()
</code></pre>
http://ask.sagemath.org/question/24404/integer-hull-of-a-polytope/?comment=24408#post-id-24408Thank 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.Mon, 06 Oct 2014 06:37:24 -0500http://ask.sagemath.org/question/24404/integer-hull-of-a-polytope/?comment=24408#post-id-24408