user_guide:tutorials:latest:matching_polytopes

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

user_guide:tutorials:latest:matching_polytopes [2020/01/22 09:02] (current)
Line 1: Line 1:
 +===== Matching Polytopes =====
 +
 +In this tutorial we will use ''​polymake''​ to construct and analyse matching polytopes.
 +
 +First we construct a graph, the complete graph on four nodes:
 +
 +<code perl>
 +> $K4=new props::​Graph(4);​
 +> for (my $i=0; $i<4; ++$i) {
 +>   for (my $j=$i+1; $j<4; ++$j) {
 +>     ​$K4->​edge($i,​$j);​
 +>   }
 +> }
 +</​code>​
 +(See also the [[apps_graph|Tutorial on Graphs]] for more on the construction of graphs.)
 +
 +Next we like to have the node-edge-incidence matrix of our graph. Since the latest release of ''​polymake''​ does not yet support this, we have to write the function ourselves:
 +
 +<code perl>
 +> sub node_edge_incidences {
 +>     my $g=shift;
 +>    my $A=new Matrix<​Int>​($g->​nodes,​ $g->​edges);​
 +>     my $k=0;
 +>    for (my $i=0; $i<​$g->​nodes-1;​ ++$i) {
 +>        foreach (@{$g->​adjacent_nodes($i)}) {
 +>            if ($_>$i) {
 +>                $A->​[$i]->​[$k]=1;​
 +>                $A->​[$_]->​[$k]=1;​
 +>                ++$k;
 +>            }
 +>        }
 +>    }
 +>    return $A;
 +> }
 +</​code>​
 +Now we can construct the node-edge-incidence matrix of our graph ''​K4'':​
 +
 +<code perl>
 +> $A=node_edge_incidences($K4);​
 +> print $A;
 +1 1 1 0 0 0
 +1 0 0 1 1 0
 +0 1 0 1 0 1
 +0 0 1 0 1 1
 +</​code>​
 +With this we can now construct the constraint matrix consisting of an upper part for the nonnegativity constraints x<​sub>​e<​html></​sub><​html></​html>​≥<​html></​html></​html>​0 ...
 +
 +<code perl>
 +> $I=new Matrix<​Int>​([[1,​0,​0,​0,​0,​0],​[0,​1,​0,​0,​0,​0],​[0,​0,​1,​0,​0,​0],​[0,​0,​0,​1,​0,​0],​[0,​0,​0,​0,​1,​0],​[0,​0,​0,​0,​0,​1]]);​
 +> $Block1=new Matrix<​Int>​(new Vector<​Int>​([0,​0,​0,​0,​0,​0]) | $I);
 +</​code>​
 +... and a lower part for the constraints <​html><​html></​html>​Σ<​html></​html><​sub></​html>​e</​sub>​ x<​sub>​e<​html></​sub><​html></​html>​≤<​html></​html></​html>​1 for each vertex v<​html><​html></​html>​∈<​html></​html></​html>​V,​ where the sum is over all edges e containing v:
 +
 +<code perl>
 +> $Block2=new Matrix<​Int>​(new Vector<​Int>​([1,​1,​1,​1]) | -$A);
 +</​code>​
 +Now we can put both parts together and define the polytope:
 +
 +<code perl>
 +> $Ineqs=new Matrix<​Rational>​($Block1 / $Block2);
 +> $P=new Polytope<​Rational>​(INEQUALITIES=>​$Ineqs);​
 +</​code>​
 +The matching polytope of ''​K4''​ is the integer hull of ''​P'':​
 +
 +<code perl>
 +> $P_I=new Polytope<​Rational>​(POINTS=>​$P->​LATTICE_POINTS);​
 +</​code>​
 +We can analyse some elementary properties of ''​P_I''​ ...
 +
 +<code perl>
 +> print $P_I->​POINTS;​
 +1 0 0 0 0 0 0
 +1 0 0 0 0 0 1
 +1 0 0 0 0 1 0
 +1 0 0 0 1 0 0
 +1 0 0 1 0 0 0
 +1 0 0 1 1 0 0
 +1 0 1 0 0 0 0
 +1 0 1 0 0 1 0
 +1 1 0 0 0 0 0
 +1 1 0 0 0 0 1
 +> print $P_I->​FACETS;​
 +0 0 0 0 0 0 1
 +0 1 0 0 0 0 0
 +1 0 0 0 -1 -1 -1
 +1 -1 0 0 -1 -1 0
 +1 0 -1 0 -1 0 -1
 +1 -1 -1 0 -1 0 0
 +1 0 0 -1 0 -1 -1
 +1 -1 0 -1 0 -1 0
 +1 0 -1 -1 0 0 -1
 +1 -1 -1 -1 0 0 0
 +0 0 0 0 0 1 0
 +0 0 1 0 0 0 0
 +0 0 0 0 1 0 0
 +0 0 0 1 0 0 0
 +> print $P_I->​N_FACETS;​
 +14
 +</​code>​
 +... and compare them with the according properties of the defining polytope ''​P'':​
 +
 +<code perl>
 +> print $P->​VERTICES;​
 +1 0 0 0 1 0 0
 +1 0 1 0 0 0 0
 +1 1/2 1/2 0 1/2 0 0
 +1 0 0 0 0 0 0
 +1 1 0 0 0 0 0
 +1 1/2 0 1/2 0 1/2 0
 +1 0 1/2 1/2 0 0 1/2
 +1 0 0 0 1/2 1/2 1/2
 +1 0 0 0 0 1 0
 +1 0 0 1 0 0 0
 +1 0 0 0 0 0 1
 +1 1 0 0 0 0 1
 +1 0 1 0 0 1 0
 +1 0 0 1 1 0 0
 +> print $P->​VOLUME;​
 +1/72
 +> print $P_I->​VOLUME;​
 +1/90
 +</​code>​
 +Next we analyse the combinatorics of ''​P_I'':​ {{ :​tutorial:​ilp:​gale.png?​300|The Gale diagram of ''​facet0''​}}
 +
 +<code perl>
 +> print $P_I->​AMBIENT_DIM,​ " ", $P_I->​DIM;​
 +6 6
 +> print $P_I->​F_VECTOR;​
 +10 39 78 86 51 14
 +> print $P_I->​FACET_SIZES;​
 +8 8 6 6 6 6 6 6 6 6 8 8 8 8
 +> $facet0=facet($P_I,​0);​
 +> print $facet0->​AMBIENT_DIM,​ " ", $facet0->​DIM;​
 +6 5
 +> print rows_labeled($facet0->​VERTICES_IN_FACETS);​
 +0:0 1 2 3 4 5 6
 +1:1 2 4 6 7
 +2:2 4 5 6 7
 +3:1 3 4 6 7
 +4:3 4 5 6 7
 +5:0 2 3 4 5 7
 +6:0 1 2 3 4 7
 +7:0 1 3 5 6 7
 +8:0 1 2 5 6 7
 +> $facet0->​GALE;​
 +</​code>​
 +The Gale diagram of ''​facet0''​ is depicted on the right.
 +
  
  • user_guide/tutorials/latest/matching_polytopes.txt
  • Last modified: 2020/01/22 09:02
  • (external edit)