This computes the vertices and the edges of a polyhedron defined by
A x <= b
 or by
A x <= b,   x>=0
or by
A x <= b,   0<=x<=1
or by
A0 x =b0,  A1 x <= b1,  x>=0
or by
A0 x =b0,  A1 x <= b1,   0<=x<=1
 
The user has to provide the matrix A and the vector b and then run one of the routines (according to the case)

generatevertices[A,b]
generatevertices0[A,b]
generatevertices01[A,b]
generateverticeseq0[A0,b0,A1,b1]
generateverticeseq01[A0,b0,A1,b1]

IT MAY TAKE A LOT OF TIME, especially when the system is degenerate.
The result is stored in the array vertices
The edges are computed by the routine findedges and stored in the array edges.
 If the variable printoutlevel is set to 2  the current computation state is displayed, if it set to 1  only a partial display is provided. If it is set to 0  the routines run without printing any message. Setting printoutlevel to 0 speeds up the computation a little

printoutlevel = 1

A bidimensional projection of the polyhedron can be also drawn.

randrawit computes two random orthonormal axes in the affine hull  and projects the polyhedron on the bidimensional plane of the two orthonormal axes
drawit[a1,a2]  projects the polyhedron on the bidimensional plane of the two axes a1,a2
ThreeDimDrawit  shows a  polyhedron defined in R3

Facets of the convex hull of X={x1,x2,x3,...,xk} can be computed by the routine
generatefacets[X]
ONLY IF THE CONVEX HULL IS A CONVEX BODY
The result is stored in the list facets={coeff,rhs} 
and the polyehdron is defined by
coeff  x  <= rhs
facets can be shown in algebraic form by running showfacets[facets]
X must NOT be defined by floating point numbers

!! FOR LONG COMPUTATIONS  alternative random generation of vertices or facets is also provided. 
It is not guaranteed that all vertices or all facets are generated. However by generating first the vertices and using these values to generate the facets, it is possible to check whether the facets are exactly  the input inequalities. In this case the random generation has not missed any vertex nor facet. 
Similarly if we are interested in facets of a given point set, we first compute facets, then use these as inequalities to generate vertices and finally check these vertices against the initial point set.
Explanations in loco.

Routines

graphical routines

randrawit:=Module[
{plane,plane1,nb,redv,redges,bbb,aaa,m},
m=Length[vertices[[1]]];
plane1=Table[Random[],{m}];
nb=nszzzz;
AppendTo[nb,plane1];
plane2=Table[Random[],{m}];
AppendTo[nb,plane2];
plane=Take[GramSchmidt[nb,Length[nszzzz]+1],-2];
redv=vertices.Transpose[plane];
redges=Table[{plane.edges[[i,1]],plane.edges[[i,2]]},
       {i,Length[edges]}];
bbb=Graphics[Table[
      Line[{redges[[i,1]],redges[[i,2]]}],
    {i,Length[redges]}]];
aaa=Graphics[{PointSize[0.02],Table[Point[redv[[i]]],
       {i,Length[redv]}]}];
Show[aaa,bbb,AspectRatio->Automatic];

]

drawit[pl1_,pl2_]:=Module[
{plane,plane1,plane2,nb,redv,redges,bbb,aaa},
plane1=pl1;
nb=nszzzz;
AppendTo[nb,plane1];
plane2=pl2;
AppendTo[nb,plane2];
plane=Take[GramSchmidt[nb,Length[nszzzz]+1],-2];
redv=vertices.Transpose[plane];
redges=Table[{plane.edges[[i,1]],plane.edges[[i,2]]},
       {i,Length[edges]}];
bbb=Graphics[Table[
      Line[{redges[[i,1]],redges[[i,2]]}],
    {i,Length[redges]}]];
aaa=Graphics[{PointSize[0.02],Table[Point[redv[[i]]],
       {i,Length[redv]}]}];
Show[aaa,bbb,AspectRatio->Automatic];

]

ThreeDimDrawit:=Module[
{plane,plane1,plane2,nb,redv,redges,bbb,aaa,axes,maxcoord,dilcoeff,ax1,ax2,ax3,redax1,redax2,redax3},
maxcoord=Max[vertices];
dilcoeff=1.1;
ax1=maxcoord dilcoeff{{1,0,0},{0,0,0}};
ax2=maxcoord dilcoeff{{0,1,0},{0,0,0}};
ax3=maxcoord dilcoeff{{0,0,1},{0,0,0}};
plane1={-2,4,0};
nb=nszzzz;
AppendTo[nb,plane1];
plane2={-1,-1,3};
AppendTo[nb,plane2];
plane=Take[GramSchmidt[nb,Length[nszzzz]+1],-2];
redv=vertices.Transpose[plane];
redax1=Map[plane.# &,ax1];
redax2=Map[plane.# &,ax2];
redax3=Map[plane.# &,ax3];
redges=Table[{plane.edges[[i,1]],plane.edges[[i,2]]},
       {i,Length[edges]}];
bbb=Graphics[Table[
      Line[{redges[[i,1]],redges[[i,2]]}],
    {i,Length[redges]}]];
aaa=Graphics[{PointSize[0.02],Table[Point[redv[[i]]],
       {i,Length[redv]}]}];
axes=Graphics[{Line[redax1],Line[redax2],Line[redax3]}];
Show[aaa,bbb,axes,AspectRatio->Automatic];

]

generatvertices0

generatevertices0[AA_,bbb_]:=Module[
{A,AAA,y,W,x,unlimited,min,q,ratio,n,m,c,cr,cb,v,
tolerance=0.0001,optimal,p,B,
newbase,snewbase,cand,tab,u,bbase,base,bb,b},

(*findbase0[A_,b_]:=Module[{n,sol,m},
    n=Length[A[[1]]];m=Length[A];
    sol=LinearProgramming[Table[0,{n}],-A,-b];
    Transpose[
        Take[Select[Transpose[{Range[m],b-A.sol}],#[[2]]==0 &],n]][[1]]
    ];*)
    
       
   findbase0[A_,b_]:=Module[{n,sol,m,cc,indind,zerind},
      n=Length[A[[1]]];m=Length[A];
      cc=Table[0,{n}];
      sol=LinearProgramming[cc,-A,-b];
      zerind=
        Transpose[
            Select[Transpose[{Range[m],b-A.sol}],#[[2]]==0&]][[1]];
      indind=linindcol[Transpose[A[[zerind]]]];
      Take[zerind[[indind]],n]
      ];
      
    
    
entercolumn:=
      Module[{i},
         For[i=1,
             (i<=n) && (cr[[i]]>=-tolerance),
             i++, Null
            ];
          optimal=False;
         If[i==n+1,optimal=True,p=i]   
        ];
   
  
  leavecolumn:=
Module[{i,ratio,min},
      y = W . Transpose[A][[ p ]];
      min = 1000000;
      For[i=1, i<=m, i++,
          If[ y[[i]]>tolerance,
              ratio = x[[i]]/y[[i]];
              If[ratio < min,
                 min = ratio; q = i]
            ]  
          ];
       unlimited=(min==1000000)
   ];
  
  pivot:=Module[{},
base[[q]] = p;
B = Transpose[Transpose[A][[ base ]]];
W = Inverse[B];
x = W. b;
cb = c[[ base ]];
u = cb . W;
v=u . b;
cr = c - u . A;];
  
  
firstpivot:=Module[{},
B = Transpose[Transpose[A][[ base ]]];
W = Inverse[B];
x = W. b;
cb = c[[ base ]];
u = cb . W;
v=u . b;
cr = c - u . A;
unlimited=False;];

simplex:=Module[{},
firstpivot;
entercolumn;
While[!optimal && !unlimited,
       leavecolumn;
       If[!unlimited,
           pivot;
           entercolumn;
         ]
      ];];
          
generatebases[bb_]:=Module[{WW},
WW=Inverse[Transpose[Transpose[A][[ bb ]]]];
u = c[[ bb ]] . WW; 
baselist[[pnt,2]]=u;
cr = c - u . A;
tab=WW.A;
adjbases={};
Do[newbase=bb;
Module[{i,ratio,min},
      min = 1000000;
      cand={};
      For[i=1, i<=n, i++,
          If[ tab[[iq,i]]<-tolerance && !MemberQ[bb,i],
              ratio = cr[[i]]/(-tab[[iq,i]]);
              If[ratio < min,
                 min = ratio;cand={i}
                 ,If[ratio==min,AppendTo[cand,i]]
                 ]
            ]  
      ];
];
Do[newbase[[iq]]=cand[[jp]];
snewbase=Sort[newbase]; 
AppendTo[adjbases,snewbase];
AppendTo[edges,{u,snewbase}];
,{jp,Length[cand]}]
,{iq,Length[bb]}]; 
]; 


    edges={};
    AAA=Join[AA,-IdentityMatrix[Length[AA[[1]]]]];
    A=Transpose[AAA];
    c=Join[bbb,Table[0,{Length[AA[[1]]]}]];
    m=Length[A];
    n=Length[A[[1]]];
    base=findbase0[AAA,c];
    b=Transpose[Transpose[A][[ base ]]].Table[1,{m}];
    simplex; 
    If[unlimited
       ,Print["No feasible solutions !"]
       ,bintree={{1,0,0}};
        baselist={{base,{}}};
        pnt=1;
        While[pnt<=Length[baselist]
             ,base=baselist[[pnt,1]];
               generatebases[base];
              Do[bbase=adjbases[[ia]];
                 searchtree[bbase];
                 If[!found
                    ,instree[bbase,pointer,r];
                    ]
                ,{ia,Length[adjbases]}
                ];
                Which[printoutlevel==0,Null,
                      printoutlevel==1,
                           If[Mod[pnt,50]==0, Print[  Length[baselist]-pnt] ] ,
                      printoutlevel==2,
                          Print[ "generating base ",base ,"  -  ",
                                   Length[baselist]-pnt,"  more to be processed"]
                       ];
              pnt++;
            ]
       ];
      vertices=Union[Transpose[baselist][[2]]];
];

generatvertices01

generatevertices01[AA_,bbb_]:=Module[
{A,AAA,y,W,x,unlimited,min,q,ratio,n,m,c,cr,cb,v,
tolerance=0.0001,optimal,p,B,
newbase,snewbase,cand,tab,u,bbase,base,bb,b},

(*findbase0[A_,b_]:=Module[{n,sol,m},
    n=Length[A[[1]]];m=Length[A];
    sol=LinearProgramming[Table[0,{n}],-A,-b];
    Transpose[
        Take[Select[Transpose[{Range[m],b-A.sol}],#[[2]]==0 &],n]][[1]]
    ];*)
    
findbase0[A_,b_]:=Module[{n,sol,m,cc,indind,zerind},
    n=Length[A[[1]]];m=Length[A];
    cc=Table[0,{n}];
    sol=LinearProgramming[cc,-A,-b];
    zerind=
        Transpose[
            Select[Transpose[{Range[m],b-A.sol}],#[[2]]==0&]][[1]];
    indind=linindcol[Transpose[A[[zerind]]]];
    Take[zerind[[indind]],n]
      ];
      
    
    
entercolumn:=
      Module[{i},
         For[i=1,
             (i<=n) && (cr[[i]]>=-tolerance),
             i++, Null
            ];
          optimal=False;
         If[i==n+1,optimal=True,p=i]   
        ];
   
  
  leavecolumn:=
Module[{i,ratio,min},
      y = W . Transpose[A][[ p ]];
      min = 1000000;
      For[i=1, i<=m, i++,
          If[ y[[i]]>tolerance,
              ratio = x[[i]]/y[[i]];
              If[ratio < min,
                 min = ratio; q = i]
            ]  
          ];
       unlimited=(min==1000000)
   ];
  
  pivot:=Module[{},
base[[q]] = p;
B = Transpose[Transpose[A][[ base ]]];
W = Inverse[B];
x = W. b;
cb = c[[ base ]];
u = cb . W;
v=u . b;
cr = c - u . A;];
  
  
firstpivot:=Module[{},
B = Transpose[Transpose[A][[ base ]]];
W = Inverse[B];
x = W. b;
cb = c[[ base ]];
u = cb . W;
v=u . b;
cr = c - u . A;
unlimited=False;];

simplex:=Module[{},
firstpivot;
entercolumn;
While[!optimal && !unlimited,
       leavecolumn;
       If[!unlimited,
           pivot;
           entercolumn;
         ]
      ];];
          
generatebases[bb_]:=Module[{WW},
WW=Inverse[Transpose[Transpose[A][[ bb ]]]];
u = c[[ bb ]] . WW; 
baselist[[pnt,2]]=u;
cr = c - u . A;
tab=WW.A;
adjbases={};
Do[newbase=bb;
Module[{i,ratio,min},
      min = 1000000;
      cand={};
      For[i=1, i<=n, i++,
          If[ tab[[iq,i]]<-tolerance && !MemberQ[bb,i],
              ratio = cr[[i]]/(-tab[[iq,i]]);
              If[ratio < min,
                 min = ratio;cand={i}
                 ,If[ratio==min,AppendTo[cand,i]]
                 ]
            ]  
      ];
];
Do[newbase[[iq]]=cand[[jp]];
snewbase=Sort[newbase]; 
AppendTo[adjbases,snewbase];
AppendTo[edges,{u,snewbase}];
,{jp,Length[cand]}]
,{iq,Length[bb]}]; 
]; 


    edges={};
    AAA=Join[AA,IdentityMatrix[Length[AA[[1]]]],-IdentityMatrix[Length[AA[[1]]]]];
    A=Transpose[AAA];
    c=Join[bbb,Table[1,{Length[AA[[1]]]}],Table[0,{Length[AA[[1]]]}]];
    m=Length[A];
    n=Length[A[[1]]];
    base=findbase0[AAA,c];
    b=Transpose[Transpose[A][[ base ]]].Table[1,{m}];
    simplex;
    If[unlimited
       ,Print["No feasible solutions !"]
       ,bintree={{1,0,0}};
        baselist={{base,{}}};
        pnt=1;
        While[pnt<=Length[baselist]
             ,base=baselist[[pnt,1]];
               generatebases[base];
              Do[bbase=adjbases[[ia]];
                 searchtree[bbase];
                 If[!found
                    ,instree[bbase,pointer,r];
                    ]
                ,{ia,Length[adjbases]}
                ];
               Which[printoutlevel==0,Null,
                      printoutlevel==1,
                           If[Mod[pnt,50]==0, Print[  Length[baselist]-pnt] ] ,
                      printoutlevel==2,
                          Print[ "generating base ",base ,"  -  ",
                                   Length[baselist]-pnt,"  more to be processed"]
                       ];
              pnt++;
            ]
       ];
      vertices=Union[Transpose[baselist][[2]]];
];

generatvertices

generatevertices[AA_,bbb_]:=Module[
{A,AAA,y,W,x,unlimited,min,q,ratio,n,m,c,cr,cb,v,
tolerance=0.0001,optimal,p,B,
newbase,snewbase,cand,tab,u,bbase,base,bb,b},

(*findbase0[A_,b_]:=Module[{n,sol,m,cc},
    n=Length[A[[1]]];m=Length[A];
    cc=Join[Table[1,{n/2}],Table[-1,{n/2}]];
    sol=LinearProgramming[cc,-A,-b];
    Transpose[
        Take[Select[Transpose[{Range[m],b-A.sol}],#[[2]]==0 &],n/2]][[1]]
    ];*)
    
    
  findbase0[A_,b_]:=
    Module[{n,sol,m,cc,indind,zerind,r},n=Length[A[[1]]];m=Length[A];
      r=Table[Random[Integer,{1,100}],{n/2}];
      cc=Join[r,-r];
      sol=LinearProgramming[cc,-A,-b]; 
      zerind=
        Transpose[
            Select[Transpose[{Range[m],b-A.sol}],#[[2]]==0&]][[1]];
      indind=linindcol[Transpose[A[[zerind]]]]; 
      Take[zerind[[indind]],n/2]];
      
entercolumn:=
      Module[{i},
         For[i=1,
             (i<=n) && (cr[[i]]>=-tolerance),
             i++, Null
            ];
          optimal=False;
         If[i==n+1,optimal=True,p=i]   
        ];
   
  
  leavecolumn:=
Module[{i,ratio,min},
      y = W . Transpose[A][[ p ]];
      min = 1000000;
      For[i=1, i<=m, i++,
          If[ y[[i]]>tolerance,
              ratio = x[[i]]/y[[i]];
              If[ratio < min,
                 min = ratio; q = i]
            ]  
          ];
       unlimited=(min==1000000)
   ];
  
  pivot:=Module[{},
base[[q]] = p;
B = Transpose[Transpose[A][[ base ]]];
W = Inverse[B];
x = W. b;
cb = c[[ base ]];
u = cb . W;
v=u . b;
cr = c - u . A;];
  
  
firstpivot:=Module[{},
B = Transpose[Transpose[A][[ base ]]];
W = Inverse[B];
x = W. b;
cb = c[[ base ]];
u = cb . W;
v=u . b;
cr = c - u . A;
unlimited=False;];

simplex:=Module[{},
firstpivot;
entercolumn;
While[!optimal && !unlimited,
       leavecolumn;
       If[!unlimited,
           pivot;
           entercolumn;
         ]
      ];];
          
generatebases[bb_]:=Module[{WW},
WW=Inverse[Transpose[Transpose[A][[ bb ]]]];
u = c[[ bb ]] . WW; 
baselist[[pnt,2]]=u;
cr = c - u . A;
tab=WW.A;
adjbases={};
Do[newbase=bb;
Module[{i,ratio,min},
      min = 1000000;
      cand={};
      For[i=1, i<=n, i++,
          If[ tab[[iq,i]]<-tolerance && !MemberQ[bb,i],
              ratio = cr[[i]]/(-tab[[iq,i]]);
              If[ratio < min,
                 min = ratio;cand={i}
                 ,If[ratio==min,AppendTo[cand,i]]
                 ]
            ]  
      ];
];
Do[newbase[[iq]]=cand[[jp]];
snewbase=Sort[newbase]; 
AppendTo[adjbases,snewbase];
AppendTo[edges,{u,snewbase}];
,{jp,Length[cand]}]
,{iq,Length[bb]}]; 
]; 


    edges={};
    A=Transpose[AA];
    AAA=Transpose[Join[A,-A]];
    c=bbb;
    m=Length[A];
    n=Length[A[[1]]];
    base=findbase0[AAA,bbb];
     b=Transpose[Transpose[A][[ base ]]].Table[1,{m}];
    simplex;
    If[unlimited
       ,Print["No feasible solutions !"]
       ,bintree={{1,0,0}};
        baselist={{base,{}}};
        pnt=1;
        While[pnt<=Length[baselist]
             ,base=baselist[[pnt,1]];
               generatebases[base];
              Do[bbase=adjbases[[ia]];
                 searchtree[bbase];
                 If[!found
                    ,instree[bbase,pointer,r];
                    ]
                ,{ia,Length[adjbases]}
                ];
                Which[printoutlevel==0,Null,
                      printoutlevel==1,
                           If[Mod[pnt,50]==0, Print[  Length[baselist]-pnt] ] ,
                      printoutlevel==2,
                          Print[ "generating base ",base ,"  -  ",
                                   Length[baselist]-pnt,"  more to be processed"]
                       ];
              pnt++;
            ]
       ];
      vertices=Union[Transpose[baselist][[2]]];
   
];

generatverticeseq01

generateverticeseq01[A0_,b0_,A1_,b1_]:=Module[
{A,AAA,y,W,x,unlimited,min,q,ratio,n,n1,m,c,cr,cb,v,
tolerance=0.0001,optimal,p,B,
newbase,snewbase,cand,tab,u,bbase,base,bb,b},


findbaseeq[A_,b_,nn_]:=
    Module[{extA,extb,n,sol,m,indind,zerind},n=Length[A[[1]]];m=Length[A];
      extA=Join[A,-Take[A,nn]];
      extb=Join[b,-Take[b,nn]];
      sol=LinearProgramming[Table[0,{n}],-extA,-extb]; 
      zerind=
        Transpose[
            Select[Transpose[{Range[m],b-A.sol}],#[[2]]==0&]][[1]];
      indind=linindcol[Transpose[extA[[zerind]]]]; 
      Take[zerind[[indind]],n]];
      
      
entercolumn:=
      Module[{i},
         For[i=1,
             (i<=n) && (cr[[i]]>=-tolerance),
             i++, Null
            ];
          optimal=False;
         If[i==n+1,optimal=True,p=i]   
        ];
   

  leavecolumn:=
Module[{i,ratio,min},
      y = W . Transpose[A][[ p ]];
      min = 1000000;
      For[i=1, i<=m, i++,
          If[ y[[i]]>tolerance,
              ratio = x[[i]]/y[[i]];
              If[ratio < min,
                 min = ratio; q = i]
            ]  
          ];
       unlimited=(min==1000000)
   ];
  


  pivot:=Module[{},
base[[q]] = p;
B = Transpose[Transpose[A][[ base ]]];
W = Inverse[B];
x = W. b;
cb = c[[ base ]];
u = cb . W;
v=u . b;
cr = c - u . A;];
  
    
firstpivot:=Module[{},
B = Transpose[Transpose[A][[ base ]]];
W = Inverse[B];
x = W. b;
cb = c[[ base ]];
u = cb . W;
v=u . b;
cr = c - u . A;
unlimited=False;];


simplex:=Module[{},
firstpivot;
entercolumn;
While[!optimal && !unlimited,
       leavecolumn;
       If[!unlimited,
           pivot;
           entercolumn;
         ]
      ];];
      
          
generatebases[bb_]:=Module[{WW},
WW=Inverse[Transpose[Transpose[A][[ bb ]]]];
u = c[[ bb ]] . WW; 
baselist[[pnt,2]]=u;
cr = c - u . A;
tab=WW.A;
adjbases={};
Do[newbase=bb;
Module[{i,ratio,min},
      min = 1000000;
      cand={};
      For[i=n1, i<=n, i++,
          If[ tab[[iq,i]]<-tolerance && !MemberQ[bb,i],
              ratio = cr[[i]]/(-tab[[iq,i]]);
              If[ratio < min,
                 min = ratio;cand={i}
                 ,If[ratio==min,AppendTo[cand,i]]
                 ]
            ]  
      ];
];
Do[newbase[[iq]]=cand[[jp]];
snewbase=Sort[newbase]; 
AppendTo[adjbases,snewbase];
AppendTo[edges,{u,snewbase}];
,{jp,Length[cand]}]
,{iq,n1,Length[bb]}]; 
]; 


    edges={};
    AAA=Join[A0,A1,IdentityMatrix[Length[A0[[1]]]],-IdentityMatrix[Length[A0[[1]]]]];
    A=Transpose[AAA];
    c=Join[b0,b1,Table[1,{Length[A0[[1]]]}],Table[0,{Length[A0[[1]]]}]];
    m=Length[A];
    n=Length[A[[1]]];n1=Length[A0]+1;
    base=findbaseeq[AAA,c,n1-1]; 
    b=Transpose[AAA[[ base ]]].Table[1,{m}];
    simplex;
    If[unlimited
       ,Print["No feasible solutions !"]
       ,bintree={{1,0,0}};
        baselist={{base,{}}};
        pnt=1;
        While[pnt<=Length[baselist]
             ,base=baselist[[pnt,1]];
               generatebases[base];
              Do[bbase=adjbases[[ia]];
                 searchtree[bbase];
                 If[!found
                    ,instree[bbase,pointer,r];
                    ]
                ,{ia,Length[adjbases]}
                ];
                Which[printoutlevel==0,Null,
                      printoutlevel==1,
                           If[Mod[pnt,50]==0, Print[  Length[baselist]-pnt] ] ,
                      printoutlevel==2,
                          Print[ "generating base ",base ,"  -  ",
                                   Length[baselist]-pnt,"  more to be processed"]
                       ];
              pnt++;
            ]
       ];
      vertices=Union[Transpose[baselist][[2]]];
  ];

generatverticeseq0

generateverticeseq0[A0_,b0_,A1_,b1_]:=Module[
{A,AAA,y,W,x,unlimited,min,q,ratio,n,n1,m,c,cr,cb,v,
tolerance=0.0001,optimal,p,B,
newbase,snewbase,cand,tab,u,bbase,base,bb,b},


findbaseeq[A_,b_,nn_]:=
    Module[{extA,extb,n,sol,m,indind,zerind},n=Length[A[[1]]];m=Length[A];
      extA=Join[A,-Take[A,nn]];
      extb=Join[b,-Take[b,nn]];
      sol=LinearProgramming[Table[0,{n}],-extA,-extb]; 
      zerind=
        Transpose[
            Select[Transpose[{Range[m],b-A.sol}],#[[2]]==0&]][[1]];
      indind=linindcol[Transpose[extA[[zerind]]]]; 
      Take[zerind[[indind]],n]];
      
      
entercolumn:=
      Module[{i},
         For[i=1,
             (i<=n) && (cr[[i]]>=-tolerance),
             i++, Null
            ];
          optimal=False;
         If[i==n+1,optimal=True,p=i]   
        ];
   

  leavecolumn:=
Module[{i,ratio,min},
      y = W . Transpose[A][[ p ]];
      min = 1000000;
      For[i=1, i<=m, i++,
          If[ y[[i]]>tolerance,
              ratio = x[[i]]/y[[i]];
              If[ratio < min,
                 min = ratio; q = i]
            ]  
          ];
       unlimited=(min==1000000)
   ];
  


  pivot:=Module[{},
base[[q]] = p;
B = Transpose[Transpose[A][[ base ]]];
W = Inverse[B];
x = W. b;
cb = c[[ base ]];
u = cb . W;
v=u . b;
cr = c - u . A;];
  
    
firstpivot:=Module[{},
B = Transpose[Transpose[A][[ base ]]];
W = Inverse[B];
x = W. b;
cb = c[[ base ]];
u = cb . W;
v=u . b;
cr = c - u . A;
unlimited=False;];


simplex:=Module[{},
firstpivot;
entercolumn;
While[!optimal && !unlimited,
       leavecolumn;
       If[!unlimited,
           pivot;
           entercolumn;
         ]
      ];];
      
          
generatebases[bb_]:=Module[{WW},
WW=Inverse[Transpose[Transpose[A][[ bb ]]]];
u = c[[ bb ]] . WW; 
baselist[[pnt,2]]=u;
cr = c - u . A;
tab=WW.A;
adjbases={};
Do[newbase=bb;
Module[{i,ratio,min},
      min = 1000000;
      cand={};
      For[i=n1, i<=n, i++,
          If[ tab[[iq,i]]<-tolerance && !MemberQ[bb,i],
              ratio = cr[[i]]/(-tab[[iq,i]]);
              If[ratio < min,
                 min = ratio;cand={i}
                 ,If[ratio==min,AppendTo[cand,i]]
                 ]
            ]  
      ];
];
Do[newbase[[iq]]=cand[[jp]];
snewbase=Sort[newbase]; 
AppendTo[adjbases,snewbase];
AppendTo[edges,{u,snewbase}];
,{jp,Length[cand]}]
,{iq,n1,Length[bb]}]; 
]; 


    edges={};
    AAA=Join[A0,A1,-IdentityMatrix[Length[A0[[1]]]]];
    A=Transpose[AAA];
    c=Join[b0,b1,Table[0,{Length[A0[[1]]]}]];
    m=Length[A];
    n=Length[A[[1]]];n1=Length[A0]+1;
    base=findbaseeq[AAA,c,n1-1]; 
    b=Transpose[AAA[[ base ]]].Table[1,{m}];
    simplex;
    If[unlimited
       ,Print["No feasible solutions !"]
       ,bintree={{1,0,0}};
        baselist={{base,{}}};
        pnt=1;
        While[pnt<=Length[baselist]
             ,base=baselist[[pnt,1]];
               generatebases[base];
              Do[bbase=adjbases[[ia]];
                 searchtree[bbase];
                 If[!found
                    ,instree[bbase,pointer,r];
                    ]
                ,{ia,Length[adjbases]}
                ];
                Which[printoutlevel==0,Null,
                      printoutlevel==1,
                           If[Mod[pnt,50]==0, Print[  Length[baselist]-pnt] ] ,
                      printoutlevel==2,
                          Print[ "generating base ",base ,"  -  ",
                                   Length[baselist]-pnt,"  more to be processed"]
                       ];
              pnt++;
            ]
       ];
      vertices=Union[Transpose[baselist][[2]]];
  ];

generatefacets

generatefacets[xx_]:=Module[{A1,b1,x0,den,mul,aa},
   x0=Map[Apply[Plus,#] &,Transpose[xx]]/Length[xx];
   A1=Map[# -x0 &,xx];
   b1=Table[1,{Length[xx]}];
   generatevertices[A1,b1];
   coeff=vertices;
   rhs=Map[1+#.x0 &,vertices];
   aa=MapThread[Append[#1,#2] &,{coeff,rhs}];
   facets=Transpose[Map[{Drop[#,-1],#[[-1]]}&,
     Map[#/Apply[GCD,#]  &,Map[ Apply[LCM,Map[Denominator,#]]  # &, aa] ]]];
  ]

showfacets[f_] := 
      Do[If[f[[2, i]]  > 0,  
          Print[f[[1, i]] . 
              Array[x, {Length[f[[1, 1]]]}], " <= ",  
            f[[2, i]] ], 
 
          Print[-f[[1, i]] . 
                Array[x, {Length[f[[1, 1]]]}], " >= ",  -f[[2, 
                  i]]]], {i, Length[f[[1]]]}]

random generation

generaterandomfacet[A_, b_, x0_, float_, tol_] := 
      Module[{yy, zz, nf, facet, coeff, rhs}, 
If[
          float, 
yy = 
            Chop[LinearProgramming[
                Table[Random[Real, {-1, 1}], {Length[A[[1]]]}], A, b, 
                Table[-Infinity, {Length[
                      A[[1]]]}]]]; 
zz = 
            1 + x0 . yy; 
nf = 
            Append[yy, Chop[zz]]; 
nf = 
            Map[Rationalize[#, tol]  &, 
              nf/Max[Abs[nf]]];
, 
yy = 
            LinearProgramming[
              Table[Random[
                  Integer, {-1000, 1000}], {Length[A[[1]]]}], A, b, 
              Table[-Infinity, {Length[
                    A[[1]]]}]]; 
zz = 
            1 + x0 . yy; 
nf = 
            Append[yy, 
              zz];

]; 
 
        nf = nf Apply[LCM, Map[Denominator, nf]]; 
 
        nf = nf /Apply[GCD, nf]; 
coeff = 
          Drop[nf, -1]; 
rhs = 
          nf[[-1]]; 
{coeff, 
          rhs}
]

onerandomfacet[X_, float_, tol_] := 
      Module[{x0, A, b}, 
x0 = 
          Map[Apply[Plus, #] &, Transpose[X]]/
            Length[X]; 
A = -Map[# - x0  &, 
              X] ; 
b = 
          Table[-1, {Length[X]}]; 
showfacets[
          Map[{#}  &, 
            generaterandomfacet[A, b, x0, float, 
              tol]]]
]

randomfacets[X_, t_, float_, tol_] := 
      Module[{x0, A, b, newfacet}, 
x0 = 
          Map[Apply[Plus, #] &, Transpose[X]]/
            Length[X]; 
A = -Map[# - x0  &, 
              X] ; 
b = 
          Table[-1, {Length[X]}]; 
newfacet = 
          generaterandomfacet[A, b, x0, float, 
            tol]; 
somefacets = {newfacet}; 
showfacets[
          Map[{#}  &, newfacet]]; 
Do[ 
          newfacet = 
            generaterandomfacet[A, b, x0, float, 
              tol]; 
nevergenerated = 
            Not[MemberQ[Transpose[somefacets][[1]], 
                newfacet[[1]]]] ; 
   If[
            nevergenerated , 
AppendTo[somefacets, 
              newfacet]; 
showfacets[
              Map[{#}  &, 
                newfacet]];
   ]
, {t}]
]

randomvertices01[A_, b_, t_, float_, tol_] := 
      Module[{newvertex }, 
somevertices = {}; 
Do[ 
          newvertex = 
            generaterandomvertex01[A, b, float, 
              tol]; 
nevergenerated = 
            Not[MemberQ[somevertices, 
                newvertex]] ; 
   If[
            nevergenerated , 
AppendTo[somevertices, 
              newvertex]; 
Print[
              newvertex];
   ]
, {t}]
]

generaterandomvertex01[A_, b_, float_, tol_] := 
      Module[{yy, zz, nf, facet, coeff, rhs}, 
If[float, 
          yy = Chop[
              LinearProgramming[
                Table[Random[
                    Real, {-1, 1}], {Length[
                      A[[1]]]}], -A, -b, 
                Table[{0, 
                    1}, {Length[A[[1]]]}]]]; 
yy = 
            Map[Rationalize[#, tol]  &, 
              yy ]
, 
yy = 
            LinearProgramming[
              Table[Random[
                  Integer, {-1000, 1000}], {Length[
                    A[[1]]]}], -A, -b, 
              Table[{0, 
                  1}, {Length[
                    A[[1]]]}]]

]
]

randomverticeseq01[A0_, b0_, A1_, t_, b1_, float_, tol_] := 
      Module[{newvertex }, 
somevertices = {}; 
Do[ 
          newvertex = 
            generaterandomvertexeq01[A0, b0, A1, b1, float, 
              tol]; 
nevergenerated = 
            Not[MemberQ[somevertices, 
                newvertex]] ; 
   If[
            nevergenerated , 
AppendTo[somevertices, 
              newvertex]; 
Print[
              newvertex];
   ]
, {t}]
]

generaterandomvertexeq01[A0_, b0_, A1_, b1_, float_, tol_] := 
      Module[{yy, zz, nf, facet, coeff, rhs}, 
If[float, 
          yy = Chop[
              LinearProgramming[
                Table[Random[Real, {-1, 1}], {Length[A0[[1]]]}], 
                Join[A1, A0], 
                Join[Transpose[{b1, Table[-1, {Length[b1]}]}], 
                  Transpose[{b0, Table[0, {Length[b0]}]}]], 
                Table[{0, 
                    1}, {Length[A0[[1]]]}]]]; 
yy = 
            Map[Rationalize[#, tol]  &, 
              yy ]
, 
yy = 
            LinearProgramming[
 
              Table[Random[
                  Integer, {-1000, 1000}], {Length[
                    A0[[1]]]}], 
  Join[A1, 
                A0], 
   Join[
                Transpose[{b1, Table[-1, {Length[b1]}]}], 
                Transpose[{b0, Table[0, {Length[b0]}]}]],      Table[{0, 
                  1}, {Length[
                    A0[[1]]]}]]

]
]

randomverticeseq0[A0_, b0_, A1_, t_, b1_, float_, tol_] := 
      Module[{newvertex }, 
somevertices = {}; 
Do[ 
          newvertex = 
            generaterandomvertexeq0[A0, b0, A1, b1, float, 
              tol]; 
nevergenerated = 
            Not[MemberQ[somevertices, 
                newvertex]] ; 
   If[
            nevergenerated , 
AppendTo[somevertices, 
              newvertex]; 
Print[
              newvertex];
   ]
, {t}]
]

generaterandomvertexeq0[A0_, b0_, A1_, b1_, float_, tol_] := 
      Module[{yy, zz, nf, facet, coeff, rhs}, 
If[
          float, 
yy = 
            Chop[LinearProgramming[
                Table[Random[Real, {-1, 1}], {Length[A0[[1]]]}], 
                Join[A1, A0], 
                Join[Transpose[{b1, Table[-1, {Length[b1]}]}], 
                  Transpose[{b0, 
                      Table[0, {Length[b0]}]}]]]]; 
yy = 
            Map[Rationalize[#, tol]  &, 
              yy ]
, 
yy = 
            LinearProgramming[
              Table[Random[
                  Integer, {-1000, 1000}], {Length[A0[[1]]]}], 
              Join[A1, A0], 
              Join[Transpose[{b1, Table[-1, {Length[b1]}]}], 
                Transpose[{b0, 
                    Table[0, {Length[
                          b0]}]}]]]
]
]

randomvertices0[A_, b_, t_, float_, tol_] := 
      Module[{newvertex }, 
somevertices = {}; 
Do[ 
          newvertex = 
            generaterandomvertex0[A, b, float, 
              tol]; 
nevergenerated = 
            Not[MemberQ[somevertices, 
                newvertex]] ; 
   If[
            nevergenerated , 
AppendTo[somevertices, 
              newvertex]; 
Print[
              newvertex];
   ]
, {t}]
]

generaterandomvertex0[A_, b_, float_, tol_] := 
      Module[{yy, zz, nf, facet, coeff, rhs}, 
If[
          float, 
yy = 
            Chop[LinearProgramming[
                Table[Random[
                    Real, {-1, 1}], {Length[
                      A[[1]]]}], -A, -b]]; 
yy = Map[Rationalize[#, tol]  &, 
              yy ]
, 
yy = 
            LinearProgramming[
              Table[Random[
                  Integer, {-1000, 1000}], {Length[
                    A[[1]]]}], -A, -b]
]
]

randomvertices[A_, b_, t_, float_, tol_] := 
      Module[{newvertex }, 
somevertices = {}; 
Do[ 
          newvertex = 
            generaterandomvertex[A, b, float, 
              tol]; 
nevergenerated = 
            Not[MemberQ[somevertices, 
                newvertex]] ; 
   If[
            nevergenerated , 
AppendTo[somevertices, 
              newvertex]; 
Print[
              newvertex];
   ]
, {t}]
]

generaterandomvertex[A_, b_, float_, tol_] := 
      Module[{yy, zz, nf, facet, coeff, rhs}, 
If[
          float, 
yy = 
            Chop[LinearProgramming[
                Table[Random[
                    Real, {-1, 1}], {Length[
                      A[[1]]]}], -A, -b, 
                Table[-Infinity, {Length[
                      A[[1]]]}]]]; 
yy = 
            Map[Rationalize[#, tol]  &, 
              yy ]
, 
yy = 
            LinearProgramming[
              Table[Random[
                  Integer, {-1000, 1000}], {Length[
                    A[[1]]]}], -A, -b, 
              Table[-Infinity, {Length[
                    A[[1]]]}]]
]
]

other routines

feasible[a_]:=Module[{feas,i},
                 feas=True;
                 Do[feas=feas&&(a[[i]]>=0),{i,Length[a]}];
                 feas]

feasible2[x_]:=Module[{feas,i},
                 For[feas=True;i=1,
                     feas && (i<=Length[A]),
                     i++,
                     If[!MemberQ[base,i]
                       ,feas=feas&&(A[[i]].x<=b[[i]])
                       ];
                     ];feas
                   ]

adjacent[a_,b_]:=Module[{status,i},
            status=0;
            Do[If[MemberQ[b,a[[i]]],Null,status++],{i,Length[a]}];
            (status==1)]

orthonorm[a_,b_]:=Module[{comp,c},
         comp=Table[a.b[[j]],{j,Length[b]}];
         c=a-Sum[comp[[j]] b[[j]],{j,Length[b]}];
         c/Sqrt[c.c]
         ]

GramSchmidt[vect_,kk_]:=Module[{a,kh,nv},
             kh=kk;
             If[kh==1,
                nv=N[{vect[[1]]/Sqrt[vect[[1]].vect[[1]]]}];
                kh=2;
                ,
                nv=N[Take[vect,kh-1]];
                ];
              Do[a=orthonorm[vect[[i]],nv];
                 AppendTo[nv,a];,{i,kh,Length[vect]}];
               nv
               
]

increment[a_,m_]:=Module[{n,b},
      If[a=={},end=True,
        end=False;
        b=a;
        n=Length[b];
        If[b[[n]]<m
           ,++b[[n]];b
           ,b=Drop[b,-1];
            b=increment[b,m-1];
            If[!end,Append[b,b[[n-1]]+1]]
          ]
        ]
]

compare[b1_,b2_]:=Module[{n,i},
     n=Length[b1];
     For[i=0,
         (i<=n) && b1[[i]]==b2[[i]],
         i++];
     If[i==n+1
       ,0
       ,If[b1[[i]]>b2[[i]]
          ,1
          ,-1
          ]
       ]
]

instree[bb_,pp_,rr_]:=Module[{},
     AppendTo[baselist,{bb,{}}];
     bintree[[pointer,(rr+5)/2]]=Length[bintree]+1;
     AppendTo[bintree,{Length[baselist],0,0}]
]

searchtree[bb_]:=Module[{endtree},
       pointer=1;
       endtree=False;
       found=False;
       While[!endtree && !found,
              r=compare[bb,baselist[[bintree[[pointer,1]],1]]];
              Which[r==0
                   ,found=True
                   ,r==1
                   ,If[bintree[[pointer,3]]==0
                       ,endtree=True
                       ,pointer=bintree[[pointer,3]]
                       ]
                    ,r==-1
                    ,If[bintree[[pointer,2]]==0
                       ,endtree=True
                       ,pointer=bintree[[pointer,2]]
                       ]
                     ]
               ]
               
]

findedges:=Module[
{r,trueedges,dvert},
If[printoutlevel==2,Print["finding ",Length[edges]," adjacent bases"] ];
Do[searchtree[edges[[i,2]]];
  edges[[i,2]]=baselist[[pointer,2]]; 
,{i,Length[edges]}];
trueedges={};
If[printoutlevel==2,Print["reducing them to true edges"] ];
Do[r=compare[edges[[i,1]],edges[[i,2]]];
   Which[r==1
        ,AppendTo[trueedges,Reverse[edges[[i]]]]
        ,r==0
        ,Null
        ,r==-1
        ,AppendTo[trueedges,edges[[i]]]
        ] 
,{i,Length[edges]}];
edges=Union[trueedges];
If[printoutlevel==2,Print["These are the ",Length[edges]," edges:"];
Print[edges]];
(* This computes the affine space and the dimension *)
dvert=Table[vertices[[i]]-vertices[[1]],
      {i,2,Length[vertices]}];
nszzzz=NullSpace[dvert];
If[nszzzz!={},   nszzzz=GramSchmidt[nszzzz,1]];
Print["The polyhedron dimension is ",Length[vertices[[1]]]-Length[nszzzz]] ; 
]

linindcol[A_] := 
      Module[{n, m, basis, k, AT, vectb, d, c, start}, 
n = 
          Length[A]; 
AT = 
          Transpose[A]; 
m = 
          Length[AT]; 
k = 1; 
        start = False; 
While[ 
          k  <= m   &&  
            start == False, 
           If[
            AT[[k]] . AT[[k]] == 
              0
          , k++
        , 
            start = True]
          ]; 
vectb = {AT[[k]]}; 
basis = {k}; 
k++; 
While[
          Length[basis] < n  &&  
            k ≤ 
              m, 
               d = 
            LinearSolve[vectb . Transpose[vectb], 
              vectb . AT[[k]]]; 
c = 
            AT[[k]] - Transpose[vectb] . d; 
If[
            c . c ≠ 0 , AppendTo[basis, k]; 
            AppendTo[vectb, 
              AT[[k]]]
       ]; 
k++
]; 
basis
]

Examples

Permutation polyhedron

A1=-{{1,0,0,0},
     {0,1,0,0},
     {0,0,1,0},
     {0,0,0,1},
     {1,1,0,0},
     {1,0,1,0},
     {1,0,0,1},
     {0,1,1,0},
     {0,1,0,1},
     {0,0,1,1},
     {0,1,1,1},
     {1,0,1,1},
     {1,1,0,1},
     {1,1,1,0},
     {1,1,1,1},
     {-1,-1,-1,-1}};

b1=-{1,1,1,1,3,3,3,3,3,3,6,6,6,6,10,-10}

generatevertices[A1,b1]

findedges

randrawit

drawit[{0, 3, -1, 0}, {-2, 1, 2, 0}]

Polyhedron in R3

A1={{2,2,1},
     {1,3,1},{3,0,3}};

b1={3,3,5}

printoutlevel = 0;

generatevertices01[A1,b1]

findedges

ThreeDimDrawit

Stable set polyhedra

Clique inequality plus an edge

A1={{1,1,1,0},{0,0,1,1}};

b1={1,1}

generatevertices0[A1,b1]

findedges

vertices

edges

drawit[{0, -1, 1, -1}, {1, 2, -1, 0}]

randrawit

Odd hole inequality with a five node circuit

A1={{1,1,0,0,0},{0,1,1,0,0},{0,0,1,1,0},{0,0,0,1,1},{1,0,0,0,1},{1,1,1,1,1}};

b1={1,1,1,1,1,2}

generatevertices0[A1,b1]

findedges

vertices

drawit[{0, 1, -1, 1, -1}, {1, 1, 1, 1, 2}]

randrawit

TSP

Computed data for   nn=5

fivenodevertices={{0,0,1,1,1,0,1,1,0,0},{0,0,1,1,1,1,0,0,1,0},{0,1,0,1,0,1,1,1,0,0},{0,1,0,1,1,1,0,0,0,1},{0,1,1,0,0,1,1,0,1,0},{0,1,1,0,1,0,1,0,0,1},{1,0,0,1,0,1,0,1,1,0},{1,0,0,1,1,0,0,1,0,1},{1,0,1,0,0,0,1,1,1,0},{1,0,1,0,1,0,0,0,1,1},{1,1,0,0,0,0,1,1,0,1},{1,1,0,0,0,1,0,0,1,1}};

fivenodeedges={{{0,0,1,1,1,0,1,1,0,0},{0,0,1,1,1,1,0,0,1,0}},{{0,0,1,1,1,0,1,1,0,0},{0,1,0,1,0,1,1,1,0,0}},{{0,0,1,1,1,0,1,1,0,0},{0,1,0,1,1,1,0,0,0,1}},{{0,0,1,1,1,0,1,1,0,0},{0,1,1,0,0,1,1,0,1,0}},{{0,0,1,1,1,0,1,1,0,0},{0,1,1,0,1,0,1,0,0,1}},{{0,0,1,1,1,0,1,1,0,0},{1,0,0,1,0,1,0,1,1,0}},{{0,0,1,1,1,0,1,1,0,0},{1,0,0,1,1,0,0,1,0,1}},{{0,0,1,1,1,0,1,1,0,0},{1,0,1,0,0,0,1,1,1,0}},{{0,0,1,1,1,0,1,1,0,0},{1,0,1,0,1,0,0,0,1,1}},{{0,0,1,1,1,0,1,1,0,0},{1,1,0,0,0,0,1,1,0,1}},{{0,0,1,1,1,1,0,0,1,0},{0,1,0,1,0,1,1,1,0,0}},{{0,0,1,1,1,1,0,0,1,0},{0,1,0,1,1,1,0,0,0,1}},{{0,0,1,1,1,1,0,0,1,0},{0,1,1,0,0,1,1,0,1,0}},{{0,0,1,1,1,1,0,0,1,0},{0,1,1,0,1,0,1,0,0,1}},{{0,0,1,1,1,1,0,0,1,0},{1,0,0,1,0,1,0,1,1,0}},{{0,0,1,1,1,1,0,0,1,0},{1,0,0,1,1,0,0,1,0,1}},{{0,0,1,1,1,1,0,0,1,0},{1,0,1,0,0,0,1,1,1,0}},{{0,0,1,1,1,1,0,0,1,0},{1,0,1,0,1,0,0,0,1,1}},{{0,0,1,1,1,1,0,0,1,0},{1,1,0,0,0,1,0,0,1,1}},{{0,1,0,1,0,1,1,1,0,0},{0,1,0,1,1,1,0,0,0,1}},{{0,1,0,1,0,1,1,1,0,0},{0,1,1,0,0,1,1,0,1,0}},{{0,1,0,1,0,1,1,1,0,0},{0,1,1,0,1,0,1,0,0,1}},{{0,1,0,1,0,1,1,1,0,0},{1,0,0,1,0,1,0,1,1,0}},{{0,1,0,1,0,1,1,1,0,0},{1,0,0,1,1,0,0,1,0,1}},{{0,1,0,1,0,1,1,1,0,0},{1,0,1,0,0,0,1,1,1,0}},{{0,1,0,1,0,1,1,1,0,0},{1,1,0,0,0,0,1,1,0,1}},{{0,1,0,1,0,1,1,1,0,0},{1,1,0,0,0,1,0,0,1,1}},{{0,1,0,1,1,1,0,0,0,1},{0,1,1,0,0,1,1,0,1,0}},{{0,1,0,1,1,1,0,0,0,1},{0,1,1,0,1,0,1,0,0,1}},{{0,1,0,1,1,1,0,0,0,1},{1,0,0,1,0,1,0,1,1,0}},{{0,1,0,1,1,1,0,0,0,1},{1,0,0,1,1,0,0,1,0,1}},{{0,1,0,1,1,1,0,0,0,1},{1,0,1,0,1,0,0,0,1,1}},{{0,1,0,1,1,1,0,0,0,1},{1,1,0,0,0,0,1,1,0,1}},{{0,1,0,1,1,1,0,0,0,1},{1,1,0,0,0,1,0,0,1,1}},{{0,1,1,0,0,1,1,0,1,0},{0,1,1,0,1,0,1,0,0,1}},{{0,1,1,0,0,1,1,0,1,0},{1,0,0,1,0,1,0,1,1,0}},{{0,1,1,0,0,1,1,0,1,0},{1,0,1,0,0,0,1,1,1,0}},{{0,1,1,0,0,1,1,0,1,0},{1,0,1,0,1,0,0,0,1,1}},{{0,1,1,0,0,1,1,0,1,0},{1,1,0,0,0,0,1,1,0,1}},{{0,1,1,0,0,1,1,0,1,0},{1,1,0,0,0,1,0,0,1,1}},{{0,1,1,0,1,0,1,0,0,1},{1,0,0,1,1,0,0,1,0,1}},{{0,1,1,0,1,0,1,0,0,1},{1,0,1,0,0,0,1,1,1,0}},{{0,1,1,0,1,0,1,0,0,1},{1,0,1,0,1,0,0,0,1,1}},{{0,1,1,0,1,0,1,0,0,1},{1,1,0,0,0,0,1,1,0,1}},{{0,1,1,0,1,0,1,0,0,1},{1,1,0,0,0,1,0,0,1,1}},{{1,0,0,1,0,1,0,1,1,0},{1,0,0,1,1,0,0,1,0,1}},{{1,0,0,1,0,1,0,1,1,0},{1,0,1,0,0,0,1,1,1,0}},{{1,0,0,1,0,1,0,1,1,0},{1,0,1,0,1,0,0,0,1,1}},{{1,0,0,1,0,1,0,1,1,0},{1,1,0,0,0,0,1,1,0,1}},{{1,0,0,1,0,1,0,1,1,0},{1,1,0,0,0,1,0,0,1,1}},{{1,0,0,1,1,0,0,1,0,1},{1,0,1,0,0,0,1,1,1,0}},{{1,0,0,1,1,0,0,1,0,1},{1,0,1,0,1,0,0,0,1,1}},{{1,0,0,1,1,0,0,1,0,1},{1,1,0,0,0,0,1,1,0,1}},{{1,0,0,1,1,0,0,1,0,1},{1,1,0,0,0,1,0,0,1,1}},{{1,0,1,0,0,0,1,1,1,0},{1,0,1,0,1,0,0,0,1,1}},{{1,0,1,0,0,0,1,1,1,0},{1,1,0,0,0,0,1,1,0,1}},{{1,0,1,0,0,0,1,1,1,0},{1,1,0,0,0,1,0,0,1,1}},{{1,0,1,0,1,0,0,0,1,1},{1,1,0,0,0,0,1,1,0,1}},{{1,0,1,0,1,0,0,0,1,1},{1,1,0,0,0,1,0,0,1,1}},{{1,1,0,0,0,0,1,1,0,1},{1,1,0,0,0,1,0,0,1,1}}}

{{{0,0,1,1,1,0,1,1,0,0},{0,0,1,1,1,1,0,0,1,0}},{{0,0,1,1,1,0,1,1,0,0},{0,1,0,1,0,1,1,1,0,0}},{{0,0,1,1,1,0,1,1,0,0},{0,1,0,1,1,1,0,0,0,1}},{{0,0,1,1,1,0,1,1,0,0},{0,1,1,0,0,1,1,0,1,0}},{{0,0,1,1,1,0,1,1,0,0},{0,1,1,0,1,0,1,0,0,1}},{{0,0,1,1,1,0,1,1,0,0},{1,0,0,1,0,1,0,1,1,0}},{{0,0,1,1,1,0,1,1,0,0},{1,0,0,1,1,0,0,1,0,1}},{{0,0,1,1,1,0,1,1,0,0},{1,0,1,0,0,0,1,1,1,0}},{{0,0,1,1,1,0,1,1,0,0},{1,0,1,0,1,0,0,0,1,1}},{{0,0,1,1,1,0,1,1,0,0},{1,1,0,0,0,0,1,1,0,1}},{{0,0,1,1,1,1,0,0,1,0},{0,1,0,1,0,1,1,1,0,0}},{{0,0,1,1,1,1,0,0,1,0},{0,1,0,1,1,1,0,0,0,1}},{{0,0,1,1,1,1,0,0,1,0},{0,1,1,0,0,1,1,0,1,0}},{{0,0,1,1,1,1,0,0,1,0},{0,1,1,0,1,0,1,0,0,1}},{{0,0,1,1,1,1,0,0,1,0},{1,0,0,1,0,1,0,1,1,0}},{{0,0,1,1,1,1,0,0,1,0},{1,0,0,1,1,0,0,1,0,1}},{{0,0,1,1,1,1,0,0,1,0},{1,0,1,0,0,0,1,1,1,0}},{{0,0,1,1,1,1,0,0,1,0},{1,0,1,0,1,0,0,0,1,1}},{{0,0,1,1,1,1,0,0,1,0},{1,1,0,0,0,1,0,0,1,1}},{{0,1,0,1,0,1,1,1,0,0},{0,1,0,1,1,1,0,0,0,1}},{{0,1,0,1,0,1,1,1,0,0},{0,1,1,0,0,1,1,0,1,0}},{{0,1,0,1,0,1,1,1,0,0},{0,1,1,0,1,0,1,0,0,1}},{{0,1,0,1,0,1,1,1,0,0},{1,0,0,1,0,1,0,1,1,0}},{{0,1,0,1,0,1,1,1,0,0},{1,0,0,1,1,0,0,1,0,1}},{{0,1,0,1,0,1,1,1,0,0},{1,0,1,0,0,0,1,1,1,0}},{{0,1,0,1,0,1,1,1,0,0},{1,1,0,0,0,0,1,1,0,1}},{{0,1,0,1,0,1,1,1,0,0},{1,1,0,0,0,1,0,0,1,1}},{{0,1,0,1,1,1,0,0,0,1},{0,1,1,0,0,1,1,0,1,0}},{{0,1,0,1,1,1,0,0,0,1},{0,1,1,0,1,0,1,0,0,1}},{{0,1,0,1,1,1,0,0,0,1},{1,0,0,1,0,1,0,1,1,0}},{{0,1,0,1,1,1,0,0,0,1},{1,0,0,1,1,0,0,1,0,1}},{{0,1,0,1,1,1,0,0,0,1},{1,0,1,0,1,0,0,0,1,1}},{{0,1,0,1,1,1,0,0,0,1},{1,1,0,0,0,0,1,1,0,1}},{{0,1,0,1,1,1,0,0,0,1},{1,1,0,0,0,1,0,0,1,1}},{{0,1,1,0,0,1,1,0,1,0},{0,1,1,0,1,0,1,0,0,1}},{{0,1,1,0,0,1,1,0,1,0},{1,0,0,1,0,1,0,1,1,0}},{{0,1,1,0,0,1,1,0,1,0},{1,0,1,0,0,0,1,1,1,0}},{{0,1,1,0,0,1,1,0,1,0},{1,0,1,0,1,0,0,0,1,1}},{{0,1,1,0,0,1,1,0,1,0},{1,1,0,0,0,0,1,1,0,1}},{{0,1,1,0,0,1,1,0,1,0},{1,1,0,0,0,1,0,0,1,1}},{{0,1,1,0,1,0,1,0,0,1},{1,0,0,1,1,0,0,1,0,1}},{{0,1,1,0,1,0,1,0,0,1},{1,0,1,0,0,0,1,1,1,0}},{{0,1,1,0,1,0,1,0,0,1},{1,0,1,0,1,0,0,0,1,1}},{{0,1,1,0,1,0,1,0,0,1},{1,1,0,0,0,0,1,1,0,1}},{{0,1,1,0,1,0,1,0,0,1},{1,1,0,0,0,1,0,0,1,1}},{{1,0,0,1,0,1,0,1,1,0},{1,0,0,1,1,0,0,1,0,1}},{{1,0,0,1,0,1,0,1,1,0},{1,0,1,0,0,0,1,1,1,0}},{{1,0,0,1,0,1,0,1,1,0},{1,0,1,0,1,0,0,0,1,1}},{{1,0,0,1,0,1,0,1,1,0},{1,1,0,0,0,0,1,1,0,1}},{{1,0,0,1,0,1,0,1,1,0},{1,1,0,0,0,1,0,0,1,1}},{{1,0,0,1,1,0,0,1,0,1},{1,0,1,0,0,0,1,1,1,0}},{{1,0,0,1,1,0,0,1,0,1},{1,0,1,0,1,0,0,0,1,1}},{{1,0,0,1,1,0,0,1,0,1},{1,1,0,0,0,0,1,1,0,1}},{{1,0,0,1,1,0,0,1,0,1},{1,1,0,0,0,1,0,0,1,1}},{{1,0,1,0,0,0,1,1,1,0},{1,0,1,0,1,0,0,0,1,1}},{{1,0,1,0,0,0,1,1,1,0},{1,1,0,0,0,0,1,1,0,1}},{{1,0,1,0,0,0,1,1,1,0},{1,1,0,0,0,1,0,0,1,1}},{{1,0,1,0,1,0,0,0,1,1},{1,1,0,0,0,0,1,1,0,1}},{{1,0,1,0,1,0,0,0,1,1},{1,1,0,0,0,1,0,0,1,1}},{{1,1,0,0,0,0,1,1,0,1},{1,1,0,0,0,1,0,0,1,1}}}

degree inequalities with nn=4

nn = 4;

A0 = 
      Transpose[
        Flatten[Table[
            Table[If[k == i  ||  k == j, 1, 0], {k, nn}], {i, 
              nn - 1}, {j, i + 1, nn}], 1]]

MatrixForm[A0]

b0=Table[2,{nn}];

A1 = {}; b1 = {}

generateverticeseq01[A0, b0, A1, b1]

findedges

vertices

randrawit

a facet of the degree inequality polyhedron with nn=5

nn = 5;

A0 = 
      Transpose[
        Flatten[Table[
            Table[If[k == i  ||  k == j, 1, 0], {k, nn}], {i, 
              nn - 1}, {j, i + 1, nn}], 1]]

AppendTo[A0, Table[0, {Length[A0[[1]]]}]]

A0[[nn + 1, 1]] = 1

MatrixForm[A0]

b0=Table[2,{nn}];

AppendTo[b0, 1]

A1 = {}; b1 = {}

generateverticeseq01[A0, b0, A1, b1]

findedges

vertices

randrawit

Perfect matching

Computed data for nn=6

vertices = {{0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 
            0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 1, 0, 0, 0, 
            0, 0, 0, 1, 0, 0}, {0, 0, 0, (1/2), (1/2), (1/2), (1/2), 0, 0, (1/2), 
            0, 0, 0, 0, (1/2)}, {0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 
            0}, {0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0}, {0, 0, 0, 1, 
            0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0}, {0, 0, (1/2), 0, (1/2), (1/2), 0, 
            (1/2), 0, 0, (1/2), 0, 0, (1/2), 0}, {0, 0, (1/2), (1/2), 0, (1/2), 0, 
            0, (1/2), 0, 0, (1/2), (1/2), 0, 0}, {0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
            1, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 
            0}, {0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1}, {0, (1/2), 0, 
            0, (1/2), 0, (1/2), (1/2), 0, 0, 0, (1/2), (1/2), 0, 0}, {0, (1/2), 0, 
            (1/2), 0, 0, (1/2), 0, (1/2), 0, (1/2), 0, 0, (1/2), 0}, {0, (1/2), 
            (1/2), 0, 0, 0, 0, (1/2), (1/2), (1/2), 0, 0, 0, 0, (1/2)}, {0, 1, 0, 
            0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 1, 0, 
            0, 0, 0, 0, 1, 0}, {0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
            1}, {(1/2), 0, 0, 0, (1/2), 0, 0, 0, (1/2), (1/2), (1/2), 0, (1/2), 0, 
            0}, {(1/2), 0, 0, (1/2), 0, 0, 0, (1/2), 0, (1/2), 0, (1/2), 0, (1/2), 
            0}, {(1/2), 0, (1/2), 0, 0, 0, (1/2), 0, 0, 0, (1/2), (1/2), 0, 0, 
            (1/2)}, {(1/2), (1/2), 0, 0, 0, (1/2), 0, 0, 0, 0, 0, 0, (1/2), (1/2), 
            (1/2)}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0}, {1, 0, 0, 
            0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 
            1, 0, 0, 0, 0, 1}};

nonfractional[a_] := 
      Fold[     #1  &&  (#2 == 0  ||  #2  == 
                  1 )  &   ,  True, a  ]

vertices = Select[vertices,  nonfractional]

edges = {{{0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 
              1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0}}, {{0, 0, 0, 0, 1, 0, 0, 1, 0, 
              1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 
              0}}, {{0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 
              (1/2), (1/2), (1/2), (1/2), 0, 0, (1/2), 0, 0, 0, 0, (1/2)}}, {{0, 0, 
              0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 0, 
              0, 1, 1, 0, 0, 0, 0, 0}}, {{0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 
              0, 0, 0}, {0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0}}, {{0, 
              0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 1, 
              0, 0, 0, 0, 0, 0, 0, 1, 0}}, {{0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 
              0, 0, 0, 0}, {0, 0, (1/2), 0, (1/2), (1/2), 0, (1/2), 0, 0, (1/2), 
              0, 0, (1/2), 0}}, {{0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 
              0}, {0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0}}, {{0, 0, 0, 
              0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 1, 
              0, 0, 0, 1, 0, 0, 0}}, {{0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 
              0, 0}, {0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1}}, {{0, 0, 
              0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0}, {0, (1/2), 0, 0, (1/2), 
              0, (1/2), (1/2), 0, 0, 0, (1/2), (1/2), 0, 0}}, {{0, 0, 0, 0, 1, 0, 
              0, 1, 0, 1, 0, 0, 0, 0, 0}, {0, (1/2), (1/2), 0, 0, 0, 0, (1/2), 
              (1/2), (1/2), 0, 0, 0, 0, (1/2)}}, {{0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 
              0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 
              0}}, {{0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0}, {0, 1, 0, 
              0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0}}, {{0, 0, 0, 0, 1, 0, 0, 1, 
              0, 1, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 
              0, 1}}, {{0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0}, {(1/2), 
              0, 0, 0, (1/2), 0, 0, 0, (1/2), (1/2), (1/2), 0, (1/2), 0, 0}}, {{0, 
              0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0}, {(1/2), 0, 0, (1/2), 
              0, 0, 0, (1/2), 0, (1/2), 0, (1/2), 0, (1/2), 0}}, {{0, 0, 0, 0, 1, 
              0, 0, 1, 0, 1, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
              0, 1, 1, 0, 0}}, {{0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 
              0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0}}, {{0, 0, 0, 
              0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 
              0, 1, 0, 0, 0, 0, 1}}, {{0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 
              0, 0}, {0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0}}, {{0, 0, 
              0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 0, (1/2), (1/2), 
              (1/2), (1/2), 0, 0, (1/2), 0, 0, 0, 0, (1/2)}}, {{0, 0, 0, 0, 1, 0, 
              1, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 
              0, 0, 0, 0}}, {{0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 
              0}, {0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0}}, {{0, 0, 0, 
              0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 1, 0, 0, 
              0, 0, 0, 0, 0, 1, 0}}, {{0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 
              0, 0}, {0, 0, (1/2), 0, (1/2), (1/2), 0, (1/2), 0, 0, (1/2), 0, 0, 
              (1/2), 0}}, {{0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 
              0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0}}, {{0, 0, 0, 0, 1, 0, 
              1, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 
              1, 0, 0, 0}}, {{0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 
              0}, {0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1}}, {{0, 0, 0, 
              0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0}, {0, (1/2), 0, 0, (1/2), 0, 
              (1/2), (1/2), 0, 0, 0, (1/2), (1/2), 0, 0}}, {{0, 0, 0, 0, 1, 0, 1, 
              0, 0, 0, 1, 0, 0, 0, 0}, {0, (1/2), 0, (1/2), 0, 0, (1/2), 0, 
              (1/2), 0, (1/2), 0, 0, (1/2), 0}}, {{0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 
              1, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 
              0}}, {{0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 1, 0, 
              0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0}}, {{0, 0, 0, 0, 1, 0, 1, 0, 
              0, 0, 1, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 
              0, 1}}, {{0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0}, {(1/2), 
              0, 0, 0, (1/2), 0, 0, 0, (1/2), (1/2), (1/2), 0, (1/2), 0, 0}}, {{0, 
              0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0}, {(1/2), 0, (1/2), 0, 
              0, 0, (1/2), 0, 0, 0, (1/2), (1/2), 0, 0, (1/2)}}, {{0, 0, 0, 0, 1, 
              0, 1, 0, 0, 0, 1, 0, 0, 0, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
              0, 1, 1, 0, 0}}, {{0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 
              0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0}}, {{0, 0, 0, 
              0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 
              0, 1, 0, 0, 0, 0, 1}}, {{0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 
              0, 0}, {0, 0, 0, (1/2), (1/2), (1/2), (1/2), 0, 0, (1/2), 0, 0, 0, 
              0, (1/2)}}, {{0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0}, {0, 
              0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0}}, {{0, 0, 0, 0, 1, 1, 
              0, 0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 
              1, 0, 0, 0}}, {{0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 
              0}, {0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0}}, {{0, 0, 0, 
              0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, (1/2), 0, (1/2), 
              (1/2), 0, (1/2), 0, 0, (1/2), 0, 0, (1/2), 0}}, {{0, 0, 0, 0, 1, 1, 
              0, 0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, (1/2), (1/2), 0, (1/2), 0, 0, 
              (1/2), 0, 0, (1/2), (1/2), 0, 0}}, {{0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 
              0, 0, 1, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 
              0}}, {{0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 1, 
              0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0}}, {{0, 0, 0, 0, 1, 1, 0, 0, 
              0, 0, 0, 0, 1, 0, 0}, {0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
              0, 1}}, {{0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0}, {0, 
              (1/2), 0, 0, (1/2), 0, (1/2), (1/2), 0, 0, 0, (1/2), (1/2), 0, 
              0}}, {{0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0}, {0, 1, 0, 
              0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0}}, {{0, 0, 0, 0, 1, 1, 0, 0, 
              0, 0, 0, 0, 1, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
              1, 0}}, {{0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0}, {0, 1, 
              0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1}}, {{0, 0, 0, 0, 1, 1, 0, 
              0, 0, 0, 0, 0, 1, 0, 0}, {(1/2), 0, 0, 0, (1/2), 0, 0, 0, (1/2), 
              (1/2), (1/2), 0, (1/2), 0, 0}}, {{0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 
              0, 1, 0, 0}, {(1/2), (1/2), 0, 0, 0, (1/2), 0, 0, 0, 0, 0, 0, 
              (1/2), (1/2), (1/2)}}, {{0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 
              0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0}}, {{0, 0, 0, 
              0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 
              0, 0, 1, 0, 0, 1, 0}}, {{0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 
              0, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1}}, {{0, 0, 
              0, (1/2), (1/2), (1/2), (1/2), 0, 0, (1/2), 0, 0, 0, 0, (1/2)}, {0, 
              0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0}}, {{0, 0, 0, (1/2), 
              (1/2), (1/2), (1/2), 0, 0, (1/2), 0, 0, 0, 0, (1/2)}, {0, 0, 0, 1, 
              0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0}}, {{0, 0, 0, (1/2), (1/2), (1/2), 
              (1/2), 0, 0, (1/2), 0, 0, 0, 0, (1/2)}, {0, 0, 0, 1, 0, 1, 0, 0, 
              0, 0, 0, 0, 0, 1, 0}}, {{0, 0, 0, (1/2), (1/2), (1/2), (1/2), 0, 0, 
              (1/2), 0, 0, 0, 0, (1/2)}, {0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 
              0, 0, 1}}, {{0, 0, 0, (1/2), (1/2), (1/2), (1/2), 0, 0, (1/2), 0, 0, 
              0, 0, (1/2)}, {0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
              1}}, {{0, 0, 0, (1/2), (1/2), (1/2), (1/2), 0, 0, (1/2), 0, 0, 0, 0, 
              (1/2)}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1}}, {{0, 0, 
              0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 1, 
              0, 0, 0, 0, 1, 0, 0, 0}}, {{0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 
              0, 0, 0}, {0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0}}, {{0, 
              0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0}, {0, 0, (1/2), (1/2), 
              0, (1/2), 0, 0, (1/2), 0, 0, (1/2), (1/2), 0, 0}}, {{0, 0, 0, 1, 0, 
              0, 0, 0, 1, 1, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
              1, 0, 0, 0, 0}}, {{0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 
              0}, {0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0}}, {{0, 0, 0, 
              1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 1, 0, 0, 
              0, 0, 0, 0, 0, 0, 1}}, {{0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 
              0, 0}, {0, (1/2), 0, (1/2), 0, 0, (1/2), 0, (1/2), 0, (1/2), 0, 0, 
              (1/2), 0}}, {{0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0}, {0, 
              (1/2), (1/2), 0, 0, 0, 0, (1/2), (1/2), (1/2), 0, 0, 0, 0, 
              (1/2)}}, {{0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0}, {0, 1, 
              0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0}}, {{0, 0, 0, 1, 0, 0, 0, 
              0, 1, 1, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 
              0, 1, 0}}, {{0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0}, {0, 
              1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1}}, {{0, 0, 0, 1, 0, 0, 
              0, 0, 1, 1, 0, 0, 0, 0, 0}, {(1/2), 0, 0, 0, (1/2), 0, 0, 0, 
              (1/2), (1/2), (1/2), 0, (1/2), 0, 0}}, {{0, 0, 0, 1, 0, 0, 0, 0, 1, 
              1, 0, 0, 0, 0, 0}, {(1/2), 0, 0, (1/2), 0, 0, 0, (1/2), 0, (1/2), 
              0, (1/2), 0, (1/2), 0}}, {{0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 
              0, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0}}, {{0, 0, 
              0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 0, 0, 0, 
              0, 0, 0, 1, 0, 0, 1, 0}}, {{0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 
              0, 0, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1}}, {{0, 
              0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0}, {0, 0, 0, 1, 0, 1, 
              0, 0, 0, 0, 0, 0, 0, 1, 0}}, {{0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 
              1, 0, 0, 0}, {0, 0, (1/2), (1/2), 0, (1/2), 0, 0, (1/2), 0, 0, 
              (1/2), (1/2), 0, 0}}, {{0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 
              0}, {0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0}}, {{0, 0, 0, 
              1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 1, 
              0, 0, 0, 1, 0, 0, 0}}, {{0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 
              0, 0}, {0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1}}, {{0, 0, 
              0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0}, {0, (1/2), 0, 0, (1/2), 
              0, (1/2), (1/2), 0, 0, 0, (1/2), (1/2), 0, 0}}, {{0, 0, 0, 1, 0, 0, 
              1, 0, 0, 0, 0, 1, 0, 0, 0}, {0, (1/2), 0, (1/2), 0, 0, (1/2), 0, 
              (1/2), 0, (1/2), 0, 0, (1/2), 0}}, {{0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 
              0, 1, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 
              0}}, {{0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0}, {0, 1, 0, 
              0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0}}, {{0, 0, 0, 1, 0, 0, 1, 0, 
              0, 0, 0, 1, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 
              0, 1}}, {{0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0}, {(1/2), 
              0, 0, (1/2), 0, 0, 0, (1/2), 0, (1/2), 0, (1/2), 0, (1/2), 0}}, {{0, 
              0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0}, {(1/2), 0, (1/2), 0, 
              0, 0, (1/2), 0, 0, 0, (1/2), (1/2), 0, 0, (1/2)}}, {{0, 0, 0, 1, 0, 
              0, 1, 0, 0, 0, 0, 1, 0, 0, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
              0, 1, 1, 0, 0}}, {{0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 
              0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0}}, {{0, 0, 0, 
              1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 
              0, 1, 0, 0, 0, 0, 1}}, {{0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
              1, 0}, {0, 0, (1/2), 0, (1/2), (1/2), 0, (1/2), 0, 0, (1/2), 0, 0, 
              (1/2), 0}}, {{0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0}, {0, 
              0, (1/2), (1/2), 0, (1/2), 0, 0, (1/2), 0, 0, (1/2), (1/2), 0, 
              0}}, {{0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0}, {0, 0, 1, 
              0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0}}, {{0, 0, 0, 1, 0, 1, 0, 0, 
              0, 0, 0, 0, 0, 1, 0}, {0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 
              0, 0}}, {{0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0}, {0, 0, 
              1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1}}, {{0, 0, 0, 1, 0, 1, 0, 
              0, 0, 0, 0, 0, 0, 1, 0}, {0, (1/2), 0, (1/2), 0, 0, (1/2), 0, 
              (1/2), 0, (1/2), 0, 0, (1/2), 0}}, {{0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 
              0, 0, 0, 1, 0}, {0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 
              0}}, {{0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0}, {0, 1, 0, 
              0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0}}, {{0, 0, 0, 1, 0, 1, 0, 0, 
              0, 0, 0, 0, 0, 1, 0}, {0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 
              0, 1}}, {{0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0}, {(1/2), 
              0, 0, (1/2), 0, 0, 0, (1/2), 0, (1/2), 0, (1/2), 0, (1/2), 0}}, {{0, 
              0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0}, {(1/2), (1/2), 0, 0, 
              0, (1/2), 0, 0, 0, 0, 0, 0, (1/2), (1/2), (1/2)}}, {{0, 0, 0, 1, 0, 
              1, 0, 0, 0, 0, 0, 0, 0, 1, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
              0, 1, 1, 0, 0}}, {{0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 
              0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0}}, {{0, 0, 0, 
              1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 
              0, 1, 0, 0, 0, 0, 1}}, {{0, 0, (1/2), 0, (1/2), (1/2), 0, (1/2), 0, 
              0, (1/2), 0, 0, (1/2), 0}, {0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 
              0, 0, 0}}, {{0, 0, (1/2), 0, (1/2), (1/2), 0, (1/2), 0, 0, (1/2), 0, 
              0, (1/2), 0}, {0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 
              0}}, {{0, 0, (1/2), 0, (1/2), (1/2), 0, (1/2), 0, 0, (1/2), 0, 0, 
              (1/2), 0}, {0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1}}, {{0, 
              0, (1/2), 0, (1/2), (1/2), 0, (1/2), 0, 0, (1/2), 0, 0, (1/2), 
              0}, {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0}}, {{0, 0, 
              (1/2), 0, (1/2), (1/2), 0, (1/2), 0, 0, (1/2), 0, 0, (1/2), 0}, {1, 
              0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0}}, {{0, 0, (1/2), (1/2), 
              0, (1/2), 0, 0, (1/2), 0, 0, (1/2), (1/2), 0, 0}, {0, 0, 1, 0, 0, 
              0, 0, 0, 1, 0, 1, 0, 0, 0, 0}}, {{0, 0, (1/2), (1/2), 0, (1/2), 0, 
              0, (1/2), 0, 0, (1/2), (1/2), 0, 0}, {0, 0, 1, 0, 0, 0, 0, 1, 0, 
              0, 0, 1, 0, 0, 0}}, {{0, 0, (1/2), (1/2), 0, (1/2), 0, 0, (1/2), 0, 
              0, (1/2), (1/2), 0, 0}, {0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
              0, 1}}, {{0, 0, (1/2), (1/2), 0, (1/2), 0, 0, (1/2), 0, 0, (1/2), 
              (1/2), 0, 0}, {0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 
              0}}, {{0, 0, (1/2), (1/2), 0, (1/2), 0, 0, (1/2), 0, 0, (1/2), (1/2), 
              0, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0}}, {{0, 0, 
              1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 
              1, 0, 0, 0, 1, 0, 0, 0}}, {{0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 
              0, 0, 0}, {0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1}}, {{0, 
              0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0}, {0, (1/2), 0, (1/2), 
              0, 0, (1/2), 0, (1/2), 0, (1/2), 0, 0, (1/2), 0}}, {{0, 0, 1, 0, 0, 
              0, 0, 0, 1, 0, 1, 0, 0, 0, 0}, {0, (1/2), (1/2), 0, 0, 0, 0, 
              (1/2), (1/2), (1/2), 0, 0, 0, 0, (1/2)}}, {{0, 0, 1, 0, 0, 0, 0, 0, 
              1, 0, 1, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 
              0, 0}}, {{0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0}, {0, 1, 
              0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0}}, {{0, 0, 1, 0, 0, 0, 0, 
              0, 1, 0, 1, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
              0, 0, 1}}, {{0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 
              0}, {(1/2), 0, 0, 0, (1/2), 0, 0, 0, (1/2), (1/2), (1/2), 0, (1/2), 
              0, 0}}, {{0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0}, {(1/2), 
              0, (1/2), 0, 0, 0, (1/2), 0, 0, 0, (1/2), (1/2), 0, 0, (1/2)}}, {{0, 
              0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0}, {1, 0, 0, 0, 0, 0, 
              0, 0, 0, 0, 0, 1, 1, 0, 0}}, {{0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 
              0, 0, 0, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 
              0}}, {{0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0}, {1, 0, 0, 
              0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1}}, {{0, 0, 1, 0, 0, 0, 0, 1, 
              0, 0, 0, 1, 0, 0, 0}, {0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
              0, 1}}, {{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0}, {0, 
              (1/2), 0, 0, (1/2), 0, (1/2), (1/2), 0, 0, 0, (1/2), (1/2), 0, 
              0}}, {{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0}, {0, (1/2), 
              (1/2), 0, 0, 0, 0, (1/2), (1/2), (1/2), 0, 0, 0, 0, (1/2)}}, {{0, 0, 
              1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 
              0, 1, 0, 0, 0, 1, 0, 0}}, {{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 
              0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0}}, {{0, 
              0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 
              1, 0, 0, 0, 0, 0, 0, 0, 1}}, {{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 
              1, 0, 0, 0}, {(1/2), 0, 0, (1/2), 0, 0, 0, (1/2), 0, (1/2), 0, 
              (1/2), 0, (1/2), 0}}, {{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 
              0}, {(1/2), 0, (1/2), 0, 0, 0, (1/2), 0, 0, 0, (1/2), (1/2), 0, 0, 
              (1/2)}}, {{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0}, {1, 0, 
              0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0}}, {{0, 0, 1, 0, 0, 0, 0, 
              1, 0, 0, 0, 1, 0, 0, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
              0, 1, 0}}, {{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0}, {1, 
              0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1}}, {{0, 0, 1, 0, 0, 1, 
              0, 0, 0, 0, 0, 0, 0, 0, 1}, {0, (1/2), (1/2), 0, 0, 0, 0, (1/2), 
              (1/2), (1/2), 0, 0, 0, 0, (1/2)}}, {{0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 
              0, 0, 0, 0, 1}, {0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 
              0}}, {{0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1}, {0, 1, 0, 
              0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0}}, {{0, 0, 1, 0, 0, 1, 0, 0, 
              0, 0, 0, 0, 0, 0, 1}, {0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 
              0, 1}}, {{0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1}, {(1/2), 
              0, (1/2), 0, 0, 0, (1/2), 0, 0, 0, (1/2), (1/2), 0, 0, (1/2)}}, {{0, 
              0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1}, {(1/2), (1/2), 0, 0, 
              0, (1/2), 0, 0, 0, 0, 0, 0, (1/2), (1/2), (1/2)}}, {{0, 0, 1, 0, 0, 
              1, 0, 0, 0, 0, 0, 0, 0, 0, 1}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
              0, 1, 1, 0, 0}}, {{0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 
              1}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0}}, {{0, 0, 1, 
              0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1}, {1, 0, 0, 0, 0, 0, 0, 0, 
              0, 1, 0, 0, 0, 0, 1}}, {{0, (1/2), 0, 0, (1/2), 0, (1/2), (1/2), 0, 
              0, 0, (1/2), (1/2), 0, 0}, {0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 
              1, 0, 0}}, {{0, (1/2), 0, 0, (1/2), 0, (1/2), (1/2), 0, 0, 0, (1/2), 
              (1/2), 0, 0}, {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 
              0}}, {{0, (1/2), 0, 0, (1/2), 0, (1/2), (1/2), 0, 0, 0, (1/2), (1/2), 
              0, 0}, {0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1}}, {{0, 
              (1/2), 0, 0, (1/2), 0, (1/2), (1/2), 0, 0, 0, (1/2), (1/2), 0, 
              0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0}}, {{0, (1/2), 
              0, (1/2), 0, 0, (1/2), 0, (1/2), 0, (1/2), 0, 0, (1/2), 0}, {0, 1, 
              0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0}}, {{0, (1/2), 0, (1/2), 0, 
              0, (1/2), 0, (1/2), 0, (1/2), 0, 0, (1/2), 0}, {0, 1, 0, 0, 0, 0, 
              0, 1, 0, 0, 0, 0, 0, 1, 0}}, {{0, (1/2), 0, (1/2), 0, 0, (1/2), 0, 
              (1/2), 0, (1/2), 0, 0, (1/2), 0}, {0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 
              0, 0, 0, 0, 1}}, {{0, (1/2), 0, (1/2), 0, 0, (1/2), 0, (1/2), 0, 
              (1/2), 0, 0, (1/2), 0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 
              1, 0}}, {{0, (1/2), (1/2), 0, 0, 0, 0, (1/2), (1/2), (1/2), 0, 0, 0, 
              0, (1/2)}, {0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0}}, {{0, 
              (1/2), (1/2), 0, 0, 0, 0, (1/2), (1/2), (1/2), 0, 0, 0, 0, 
              (1/2)}, {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0}}, {{0, 
              (1/2), (1/2), 0, 0, 0, 0, (1/2), (1/2), (1/2), 0, 0, 0, 0, 
              (1/2)}, {0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1}}, {{0, 
              (1/2), (1/2), 0, 0, 0, 0, (1/2), (1/2), (1/2), 0, 0, 0, 0, 
              (1/2)}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1}}, {{0, 1, 
              0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 
              1, 0, 0, 0, 0, 0, 1, 0}}, {{0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 
              1, 0, 0}, {0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1}}, {{0, 
              1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0}, {(1/2), 0, 0, 0, 
              (1/2), 0, 0, 0, (1/2), (1/2), (1/2), 0, (1/2), 0, 0}}, {{0, 1, 0, 0, 
              0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0}, {(1/2), (1/2), 0, 0, 0, (1/2), 
              0, 0, 0, 0, 0, 0, (1/2), (1/2), (1/2)}}, {{0, 1, 0, 0, 0, 0, 0, 0, 
              1, 0, 0, 0, 1, 0, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 
              0, 0}}, {{0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0}, {1, 0, 
              0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0}}, {{0, 1, 0, 0, 0, 0, 0, 
              0, 1, 0, 0, 0, 1, 0, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 
              0, 0, 1}}, {{0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0}, {0, 
              1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1}}, {{0, 1, 0, 0, 0, 0, 
              0, 1, 0, 0, 0, 0, 0, 1, 0}, {(1/2), 0, 0, (1/2), 0, 0, 0, (1/2), 
              0, (1/2), 0, (1/2), 0, (1/2), 0}}, {{0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 
              0, 0, 0, 1, 0}, {(1/2), (1/2), 0, 0, 0, (1/2), 0, 0, 0, 0, 0, 0, 
              (1/2), (1/2), (1/2)}}, {{0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 
              0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0}}, {{0, 1, 0, 
              0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 
              0, 0, 1, 0, 0, 1, 0}}, {{0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
              1, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1}}, {{0, 1, 
              0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1}, {(1/2), 0, (1/2), 0, 0, 
              0, (1/2), 0, 0, 0, (1/2), (1/2), 0, 0, (1/2)}}, {{0, 1, 0, 0, 0, 0, 
              1, 0, 0, 0, 0, 0, 0, 0, 1}, {(1/2), (1/2), 0, 0, 0, (1/2), 0, 0, 
              0, 0, 0, 0, (1/2), (1/2), (1/2)}}, {{0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 
              0, 0, 0, 0, 1}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 
              0}}, {{0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1}, {1, 0, 0, 
              0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0}}, {{0, 1, 0, 0, 0, 0, 1, 0, 
              0, 0, 0, 0, 0, 0, 1}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 
              0, 1}}, {{(1/2), 0, 0, 0, (1/2), 0, 0, 0, (1/2), (1/2), (1/2), 0, 
              (1/2), 0, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 
              0}}, {{(1/2), 0, 0, 0, (1/2), 0, 0, 0, (1/2), (1/2), (1/2), 0, (1/2), 
              0, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0}}, {{(1/2), 
              0, 0, 0, (1/2), 0, 0, 0, (1/2), (1/2), (1/2), 0, (1/2), 0, 0}, {1, 
              0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1}}, {{(1/2), 0, 0, (1/2), 
              0, 0, 0, (1/2), 0, (1/2), 0, (1/2), 0, (1/2), 0}, {1, 0, 0, 0, 0, 
              0, 0, 0, 0, 0, 0, 1, 1, 0, 0}}, {{(1/2), 0, 0, (1/2), 0, 0, 0, 
              (1/2), 0, (1/2), 0, (1/2), 0, (1/2), 0}, {1, 0, 0, 0, 0, 0, 0, 0, 
              0, 0, 1, 0, 0, 1, 0}}, {{(1/2), 0, 0, (1/2), 0, 0, 0, (1/2), 0, 
              (1/2), 0, (1/2), 0, (1/2), 0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
              0, 0, 0, 1}}, {{(1/2), 0, (1/2), 0, 0, 0, (1/2), 0, 0, 0, (1/2), 
              (1/2), 0, 0, (1/2)}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 
              0}}, {{(1/2), 0, (1/2), 0, 0, 0, (1/2), 0, 0, 0, (1/2), (1/2), 0, 0, 
              (1/2)}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0}}, {{(1/2), 
              0, (1/2), 0, 0, 0, (1/2), 0, 0, 0, (1/2), (1/2), 0, 0, (1/2)}, {1, 
              0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1}}, {{(1/2), (1/2), 0, 0, 
              0, (1/2), 0, 0, 0, 0, 0, 0, (1/2), (1/2), (1/2)}, {1, 0, 0, 0, 0, 
              0, 0, 0, 0, 0, 0, 1, 1, 0, 0}}, {{(1/2), (1/2), 0, 0, 0, (1/2), 0, 
              0, 0, 0, 0, 0, (1/2), (1/2), (1/2)}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 
              0, 1, 0, 0, 1, 0}}, {{(1/2), (1/2), 0, 0, 0, (1/2), 0, 0, 0, 0, 0, 
              0, (1/2), (1/2), (1/2)}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 
              0, 1}}, {{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0}, {1, 0, 
              0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0}}, {{1, 0, 0, 0, 0, 0, 0, 
              0, 0, 0, 0, 1, 1, 0, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 
              0, 0, 1}}, {{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0}, {1, 
              0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1}}};

edges = 
      Select[edges,  
        nonfractional[#[[1]]]  &&  
            nonfractional[#[[2]]]  &]

dvert = 
        Table[vertices[[i]] - vertices[[1]], {i, 2, 
            Length[vertices]}];
nszzzz = NullSpace[dvert];
If[nszzzz ≠ {}, 
        nszzzz = GramSchmidt[nszzzz, 1]];
Print["The polyhedron dimension is ", 
        Length[vertices[[1]]] - Length[nszzzz]];

randrawit

Case for nn=4

nn = 4;

A0 = 
      Transpose[
        Flatten[Table[
            Table[If[k == i  ||  k == j, 1, 0], {k, nn}], {i, 
              nn - 1}, {j, i + 1, nn}], 1]]

MatrixForm[A0]

b0=Table[1,{nn}];

A1 = {}; b1 = {}

generateverticeseq0[A0,b0,A1,b1]

findedges

randrawit

Core of an n-person game

n = 4

A0={{1,1,1,1}};

A1 =  Table[Reverse[IntegerDigits[i, 2, n]], {i, 2^n - 2}]

b0={20}

b1 = {3,  4,  8,  3,  9, 12, 
        17, 
       2,  6,   8,  11,  7, 12, 
        11}

generateverticeseq0[A0,b0,-A1,-b1]

vertices

findedges

randrawit

drawit[{0, 3, -1, 0}, {-2, 1, 2, 0}]

Shapley value computation

np = n

p=Table[Binomial[np,i](np-i),{i,0,np-1}]

vv = Transpose[{Map[Flatten[Position[#, 1] ] &, A1], b1}]

AppendTo[vv, {Range[n], b0[[1]]}]

v=Table[{0,0},{2^np}];

Do[sv=vv[[i,1]];k=Sum[2^(sv[[j]]-1),{j,Length[sv]}]+1;
v[[k,2]]=vv[[i,2]];
v[[k,1]]=Length[vv[[i,1]]];
  ,{i,Length[vv]}]

v

x=Table[0,{np}];

Do[x[[i]]=Sum[(v[[h+j 2^i+2^(i-1),2]]-v[[h+j 2^i,2]])/
                p[[v[[h+j 2^i,1]]+1]]
             ,{h,2^(i-1)},{j,0,2^(np-i)-1}]
  ,{i,np}]

N[x]

Apply[Plus,x]

Core membership check

Table[{Apply[Plus,N[x[[vv[[i,1]]]]]],N[vv[[i,2]]]},{i,Length[vv]}]

Facet computation

A two dimensional example

X = {{0, 0}, {0, 1}, {1, 0}}

generatefacets[X]

facets

showfacets[facets]

A three dimensional example

X = {{0, 0, 1}, {0, 1, 0}, {1, 0, 0}, {1, 1, 1}}

generatefacets[X]

facets

showfacets[facets]

Stable sets

A three node clique plus an edge

X = {{0, 0, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 1}, {0, 1, 0, 0}, {0, 1, 0, 
          1}, {0, 0, 1, 0}, {0, 0, 0, 1}}

generatefacets[X]

facets

showfacets[facets]

getting back to the points to find out the edges

generatevertices[facets[[1]], facets[[2]]]

findedges

vertices

edges

randrawit

A three node clique

X = {{0, 0, 0}, {1, 0, 0}, {0, 1, 0}, {0, 0, 1}}

generatefacets[X]

facets

showfacets[facets]

getting back to the points to find out the edges

generatevertices[facets[[1]], facets[[2]]]

findedges

vertices

edges

ThreeDimDrawit

A four node clique

X = {{0, 0, 0, 0}, {1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 
          1}}

generatefacets[X]

printoutlevel = 1

Transpose[somefacets]

facets

showfacets[facets]

getting back to the points to find out the edges

generatevertices[facets[[1]], facets[[2]]]

findedges

vertices

edges

drawit[{3, -1, -2, 0}, {-2, 0, 1, 3}]

randrawit

Matching

Complete graph with four nodes

X = {{0, 0, 0, 0, 0, 0},  {1, 0, 0, 0, 0, 1}, {0, 1, 0, 0, 1, 0}, {0, 
          0, 1, 1, 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, 0}, {0, 0, 0, 0, 0, 
          1}}

generatefacets[X]

facets

showfacets[facets]

getting back to the points to find out the edges

generatevertices[facets[[1]], facets[[2]]]

findedges

vertices

edges

drawit[{-1, 3, 2, -2, 0, 3}, {-2, 0, 3, -1, 3, 
        2}]

randrawit

graph with four nodes and arcs ((1,2),(1,3),(1,4),(2,4),(3,4))

X = {{0, 0, 0, 0, 0},  {1, 0, 0, 0, 1}, {0, 1, 0, 1, 0}, {0, 0, 1, 0, 
          0}, {1, 0, 0, 0, 0}, {0, 1, 0, 0, 0}, {0, 0, 0, 1, 0}, {0, 0, 0, 0, 
          1}}

generatefacets[X]

facets

showfacets[facets]

getting back to the points to find out the edges

generatevertices[facets[[1]], facets[[2]]]

findedges

vertices

edges

drawit[{-1, 3, 2, -2, 0}, {-2, 0, 3, -1, 3}]

randrawit

Cuts

two adjacent nodes  x1 and x2 nodes, x3 arc

X = {{0, 0, 0},  {1, 0, 1}, {0, 1, 1}, {1, 1, 0}}

generatefacets[X]

facets

showfacets[facets]

clique of six arcs

cliquesize = 5;

binppts = 
      Map[IntegerDigits[#, 2, cliquesize]  &, 
        Table[i, {i, 0, 2^(cliquesize - 1) - 1}]]

arcs = 
      Flatten[Table[{i, j}, {i, cliquesize - 1}, {j, i + 1, cliquesize}], 
        1]

arcs = Drop[arcs, -1]

X = 
      Map[     Table[{ki, kj} = arcs[[j]]; 
            If[#[[ki]] == #[[kj]], 0, 1], {j, 
              Length[arcs]}]  & , binppts  ]

generatefacets[X]

facets

showfacets[facets]

getting back to the points to find out the edges

generatevertices[facets[[1]], facets[[2]]]

findedges

vertices

edges

drawit[{-1, 3, 2, -2, 0, 3}, {-2, 0, 3, -1, 3, 
        2}]

randrawit

Random generation of vertices and facets

Random generation of facets

X = {{1, 1, 0}, {0, 0, 0}, {1, 0, 1}, {0, 0, 1}}

The convex hull of the point set X must be a convex body!
Check it by the following. If the NullSpace is empty, then it is a convex body.

NX = NullSpace[Map[# -  X[[1]] &, X]]

This generates  randomly just one facet. The second parameter is set to True if the computation is in floating point. In this case the third parameter is the maximum error between the floating point coefficients and their rational representations. If the second parameter is set to False the computation is in exact arithmetic and the third parameter is not effective

onerandomfacet[X, False, 0]

This generates randomly many facets  as specified in the second parameter. The third parameter is set to True if the computation is in floating point. In this case the fourth parameter is the maximum error between the floating point coefficients and their rational representations. If the third parameter is set to False the computation is in exact arithmetic and the third parameter is not effective.
The newly generated facets are stored in somefacets and immediately displayed

randomfacets[X, 5000, False, 0]

This shows the same facets displayed in an ordered way

showfacets[Transpose[Sort[somefacets]]]

checking if all facets have been generated

somefacets = Sort[somefacets];

it may be convenient to drop trivial inequalities x≥0 and x≤1

relfacets = 
      Select[somefacets, 
        Count[#[[1]],  _?Positive ] + 
              Count[#[[1]],  _?Negative ]  > 1  &]

build the inequalities

A1 = Transpose[relfacets] [[1]]

b1 = Transpose[relfacets] [[2]]

compute the vertices

randomvertices01[A1, b1, 5000, False, 0]

if the two sets below are equal, all facets have been generated

MatrixForm[Sort[somevertices]]

MatrixForm[Sort[X]]

If the following is true all facets have been generated

Sort[X] == Sort[somevertices]

Random generation of vertices

A single vertex is generated randomly by
generaterandomvertex[A,b,float,tol]      for  A x <= b, 
generaterandomvertex0[A,b,float_tol]      for  A x <= b,  x>= 0
generaterandomvertex01[A,b,float_tol]      for  A x <= b, 0<=x<=1
generaterandomvertexeq0[A0,b0,A1,b1,float,tol]   for   A0 x = b0,  A1 x <= b1, x>= 0
generaterandomvertexeq01[A0,b0,A1,b1,float,tol]   for   A0 x = b0,  A1 x <= b1, 0<=x<=1

where  float  is set to True if the computation is in floating point. In this case the  parameter  tol is the maximum error between the floating point coefficients and their rational representations. If float  is set to False the computation is in exact arithmetic and tol is not effective.

Many vertices are generated by 
randomvertices[A,b,float,tol]      for  A x <= b, 
randomvertices0[A,b,float_tol]      for  A x <= b,  x>= 0
randomvertices01[A,b,float_tol]      for  A x <= b, 0<=x<=1
randomverticeseq0[A0,b0,A1,b1,float,tol]   for   A0 x = b0,  A1 x <= b1, x>= 0
randomverticeseq01[A0,b0,A1,b1,float,tol]   for   A0 x = b0,  A1 x <= b1, 0<=x<=1

The newly generated vertices  are stored in somevertices and immediately displayed

A={{1,1,0,0,0},{0,1,1,0,0},{0,0,1,1,0},{0,0,0,1,1},{1,0,0,0,1},{1,1,1,1,1}};

b={1,1,1,1,1,2}

A = {{1, 0, 0}, {-1, 0, 0}, {1, 0, 1}, {0, 1, 0}, {-1, 1, 
            0}, {0, 0, 1}, {0, -1, 1}, {0, -1, 0}, {1, -1, 
            0}, {1, -1, 1}, {0, 1, -1}, {0, 0, -1}, {-1, 
            0, -1}, {-1, 1, -1}};

b = {1, 0, 2, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0}

randomvertices[A, b, 2000, False, 0]

somevertices

randomfacets[somevertices , 2000, False, 0]

This shows the same facets displayed in an ordered way

somefacets = Sort[somefacets];

showfacets[Transpose[somefacets]]

it may be convenient to drop trivial inequalities x≥0 and x≤1

relfacets = 
      Select[somefacets, 
        Count[#[[1]],  _?Positive ] + 
              Count[#[[1]],  _?Negative ]  > 1  &]

newA1 = Transpose[somefacets][[1]];

MatrixForm[newA1]

MatrixForm[A]

Sort[A] == Sort[newA1]

edges computation

somevertices

Map[  #[[1]] . somevertices[[3]]  -  #[[2]]  &  , 
      somefacets]

zeronumber

someedges = {};
Do[ 
      zeroi = Count[ 
          Map[  #[[1]] . 
                  somevertices[[i]]  -  #[[2]]  &  , 
            somefacets], 0]; 
      zeroj = 
        Count[ Map[  #[[1]] . 
                  somevertices[[j]]  -  #[[2]]  &  , 
            somefacets], 
          0]; 
      midpoint = (somevertices[[i]] + somevertices[[j]])/
          2  ; 
                                   If[ 
        Count[ Map[  #[[1]] . midpoint -  #[[2]]  &  , 
              somefacets], 0]  == 
          Min[zeroi, zeroj] - 
            1 , 
                                   AppendTo[
          someedges, {somevertices[[i]], 
            somevertices[[j]]} ]  ] , {i, 
        Length[somevertices] - 1}, {j, i + 1, 
        Length[somevertices]}]

someedges

edges = someedges; ThreeDimDrawit

edges = someedges; vertices = somevertices; randrawit