×

Equivalence of lattice orbit polytopes. (English) Zbl 1486.52027

Summary: Let \(G\) be a finite permutation group acting on \(\mathbb R^d\) by permuting coordinates. A core point (for \(G\)) is an integral vector \(z\in\mathbb Z^d\) such that the convex hull of the orbit \(Gz\) contains no other integral vectors but those in the orbit \(Gz\). K. Herr et al. [Discrete Comput. Geom. 53, No. 1, 144–172 (2014; Zbl 1325.52010)] considered the question for which groups there are infinitely many core points up to translation equivalence, that is, up to translation by vectors fixed by the group. In the present paper, we propose a coarser equivalence relation for core points called normalizer equivalence. These equivalence classes often contain infinitely many vectors up to translation, for example when the group admits an irrational invariant subspace or an invariant irreducible subspace occurring with multiplicity greater than 1. We also show that the number of core points up to normalizer equivalence is finite if \(G\) is a so-called QI-group. These groups include all transitive permutation groups of prime degree. We give an example to show how the concept of normalizer equivalence can be used to simplify integer convex optimization problems.

MSC:

52B20 Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry)
20C10 Integral representations of finite groups
16U60 Units, groups of units (associative rings and algebras)
20B25 Finite automorphism groups of algebraic, geometric, or combinatorial structures
20C15 Ordinary representations and characters
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
90C10 Integer programming

Citations:

Zbl 1325.52010

Software:

MIPLIB; GAP
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] K. Aardal and F. Eisenbrand, Integer programming, lattices, and results in fixed dimension, in Discrete Optimization, K. Aardal, G. L. Nemhauser, and R. Weismantel, eds., Handbooks Oper. Res. Management Sci. 12, Elsevier, Amsterdam, 2005, pp. 171–243, . · Zbl 1172.90445
[2] O. Braun, R. Coulangeon, G. Nebe, and S. Schönnenbeck, Computing in arithmetic groups with Voronoï’s algorithm, J. Algebra, 435 (2015), pp. 263–285, . · Zbl 1323.16014
[3] D. Bremner, M. Dutour Sikirić, D. V. Pasechnik, T. Rehn, and A. Schürmann, Computing symmetry groups of polyhedra, LMS J. Comput. Math., 17 (2014), pp. 565–581, . · Zbl 1351.52009
[4] D. A. Bulutoglu and F. Margot, Classification of orthogonal arrays by integer programming, J. Statist. Plann. Inference, 138 (2008), pp. 654–666, . · Zbl 1139.62041
[5] R. Bödi, K. Herr, and M. Joswig, Algorithms for highly symmetric linear and integer programs, Math. Program. Ser. A, 137 (2013), pp. 65–90, . · Zbl 1262.90101
[6] P. J. Cameron, Bounding the rank of certain permutation groups, Math. Z., 124 (1972), pp. 343–352, . · Zbl 0215.39101
[8] J. D. Dixon, Permutation representations and rational irreducibility, Bull. Austral. Math. Soc., 71 (2005), pp. 493–503, . · Zbl 1114.20003
[9] P. Faccin, W. A. de Graaf, and W. Plesken, Computing generators of the unit group of an integral abelian group ring, J. Algebra, 373 (2013), pp. 441–452, . · Zbl 1271.16038
[10] B. Farb and R. K. Dennis, Noncommutative Algebra, Grad. Texts in Math. 144, Springer, New York, 1993, . · Zbl 0797.16001
[12] M. Fischetti and L. Liberti, Orbital shrinking, in Combinatorial Optimization, A. R. Mahjoub et al., eds., Lecture Notes in Comput. Sci. 7422, Springer, Berlin, 2012, pp. 48–58, . · Zbl 1370.90209
[13] E. J. Friedman, Fundamental domains for integer programs with symmetries, in Combinatorial Optimization and Applications, A. Dress, Y. Xu, and B. Zhu, eds., Lecture Notes in Comput. Sci. 4616, Springer, Berlin, 2007, pp. 146–153, . · Zbl 1175.90296
[14] The GAP Group, GAP—Groups, Algorithms, and Programming, Version 4.8.6, 2016, (accessed 2017-03-02).
[15] A. Ghoniem and H. D. Sherali, Defeating symmetry in combinatorial optimization via objective perturbations and hierarchical constraints, IIE Trans., 43 (2011), pp. 575–588, .
[17] K. Herr, Core Sets and Symmetric Convex Optimization, Dissertation, Technische Universität Darmstadt, Darmstadt, Germany, 2013. · Zbl 1291.90002
[18] K. Herr, T. Rehn, and A. Schürmann, Exploiting symmetry in integer convex optimization using core points, Oper. Res. Lett., 41 (2013), pp. 298–304, . · Zbl 1286.90097
[19] K. Herr, T. Rehn, and A. Schürmann, On lattice-free orbit polytopes, Discrete Comput. Geom., 53 (2015), pp. 144–172, . · Zbl 1325.52010
[20] K. Hoechsmann, Constructing units in commutative group rings, Manuscripta Math., 75 (1992), pp. 5–23, . · Zbl 0773.16016
[21] C. Hojny and M. E. Pfetsch, Polytopes associated with symmetry handling, Math. Program. Ser. A, to appear, . · Zbl 1421.90088
[22] I. M. Isaacs, Finite Group Theory, Grad. Stud. Math. 92, AMS, Providence, RI, 2008, . · Zbl 1169.20001
[23] V. Kaibel and M. Pfetsch, Packing and partitioning orbitopes, Math. Program. Ser. A, 114 (2008), pp. 1–36, . · Zbl 1171.90004
[24] E. Kleinert, Units of classical orders: A survey, Enseign. Math. (2), 40 (1994), pp. 205–248, . · Zbl 0846.16027
[25] T. Koch, T. Achterberg, E. Andersen, O. Bastert, T. Berthold, R. E. Bixby, E. Danna, G. Gamrath, A. M. Gleixner, S. Heinz, A. Lodi, H. Mittelmann, T. Ralphs, D. Salvagnin, D. E. Steffy, and K. Wolter, MIPLIB 2010, Math. Program. Comput., 3 (2011), pp. 103–163, , .
[26] T. Y. Lam, A First Course in Noncommutative Rings, 2nd ed., Grad. Texts in Math. 131, Springer, New York, Berlin, Heidelberg, 2001, . · Zbl 0980.16001
[27] H. W. Lenstra, Jr., Integer programming with a fixed number of variables, Math. Oper. Res., 8 (1983), pp. 538–548, . · Zbl 0524.90067
[28] J. Linderoth, F. Margot, and G. Thain, Improving bounds on the football pool problem by integer programming and high-throughput computing, INFORMS J. Comput., 21 (2009), pp. 445–457, . · Zbl 1243.90006
[29] Z. Marciniak and S. K. Sehgal, Generic units in abelian group rings, J. Group Theory, 8 (2005), pp. 777–799, . · Zbl 1087.16018
[30] F. Margot, Exploiting orbits in symmetric ILP, Math. Program. Ser. B, 98 (2003), pp. 3–21, . · Zbl 1082.90070
[31] F. Margot, Symmetry in integer linear programming, in 50 Years of Integer Programming 1958–2008, M. Jünger, et al., eds., Springer, Berlin, 2010, pp. 647–686, . · Zbl 1187.90200
[32] J. Neukirch, Algebraische Zahlentheorie, reprint of the 1992 original ed., Springer, Berlin, Heidelberg, 2007, . · Zbl 0747.11001
[33] J. Ostrowski, J. Linderoth, F. Rossi, and S. Smriglio, Orbital branching, Math. Program. Ser. A, 126 (2011), pp. 147–148, . · Zbl 1206.90101
[34] M. E. Pfetsch and T. Rehn, A computational comparison of symmetry handling methods for mixed integer programs, preprint, 2015, (accessed 2017-02-24). · Zbl 1411.90233
[35] T. Rehn, Exploring Core Points for Fun and Profit: A Study of Lattice-Free Orbit Polytopes, Dissertation, Universität Rostock, Rostock, Germany, 2014, .
[36] I. Reiner, Maximal Orders, London Math. Soc. Monogr. 5, Academic Press, London, New York, 1975. · Zbl 0305.16001
[38] J.-P. Serre, Linear Representations of Finite Groups, Grad. Texts in Math. 42, Springer, New York, 1977, . · Zbl 0355.20006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.