login
A300795
Number of vertices of the master corner polyhedron on the cyclic group of order n + 1.
1
1, 2, 3, 5, 7, 10, 16, 19, 31, 32, 55, 53, 89, 89, 147, 128, 232, 191, 356, 301, 491
OFFSET
1,2
COMMENTS
The master corner polyhedron P(G_{n+1},n) on the additive cyclic group G_{n+1} of order n+1 (with addition modulo n+1) is the convex hull of solutions t=(t_1,t_2,..,t_n) in R^n, t_i integer, t_i >= 0, to the equation t_1 + 2*t_2 + ... + n*t_n == n (mod (n+1)).
The master corner polyhedron P(G,g_0) was defined by R. E. Gomory for an arbitrary finite Abelian group G and arbitrary group element g_0. It is of great importance for integer linear programming.
R. E. Gomory computed vertices of P(G,g_0) for all groups G of the order up to 11 and all g_0 in G.
The point t=(0,0,0,0,1,0,0,0,3,0) was erroneously indicated to be a vertex of P(G_11,10).
a(11)-a(21) were computed with the use of the Parma Polyhedra Library [(PPL)]. - Dominic Yang, Oct 04 2018
LINKS
R. E. Gomory, Some polyhedra related to combinatorial problems, Journal of Linear Algebra and Its Applications, 1969. Vol. 2, No. 4, 451-558.
V. A. Shlyk, Master corner polyhedron: vertices, European Journal of Operational Research, 2013. Vol. 226, No. 2, 203-210.
EXAMPLE
The 6 integer points in the convex hull of the vertices of P(G_5,4) are (4,0,0,0), (2,1,0,0), (1,0,1,0), (0,2,0,0), (0,0,3,0), (0,0,0,1) but a(4) = 5 since (2,1,0,0) = (1/2)(4,0,0,0) + (1/2)(0,2,0,0).
CROSSREFS
Similar to A203898.
Sequence in context: A116975 A286227 A134792 * A033068 A234368 A052011
KEYWORD
nonn,more
AUTHOR
Vladimir A. Shlyk, Mar 13 2018
EXTENSIONS
a(11)-a(21) from Dominic Yang, Oct 04 2018
STATUS
approved