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, source links to R. E. Gomory's papers.
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.
Vladimir A. Shlyk, Number of Vertices of the Polytope of Integer Partitions and Factorization of the Partitioned Number, arXiv:1805.07989 [math.CO], 2018.
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
KEYWORD
nonn,more
AUTHOR
Vladimir A. Shlyk, Mar 13 2018
EXTENSIONS
a(11)-a(21) from Dominic Yang, Oct 04 2018
STATUS
approved