Fundamental Domains for Symmetric Optimization: Construction and Search
本文提出了两个多项式算法，用于构造对称多面体集的最小基本域，并将多面体中的元素映射到其基本域中的代表点，在最大割问题等实例中展示了应用。
Symmetries of a set are linear transformations that map the set to itself. A fundamental domain of a symmetric set is a subset that contains at least one representative from each of the symmetric equivalence classes (orbits) in the set. This paper contributes a novel polynomial algorithm for constructing minimal polytopic fundamental domains of polytopic sets. Our algorithm is applicable for generic linear symmetries of the set and has linear complexity in the number of facets and dimension of the symmetric polytope, e.g., the feasible region of an optimization problem. In addition, this paper contributes a novel polynomial algorithm for mapping an element of the polytope to its representative in the fundamental domain. The algorithms are demonstrated in four examples---two illustrative and two practical. In the first practical example, we show that a minimal fundamental domain of the hypercube under the symmetric group is the set of points with sorted elements. In the second practical example, we show how the construction algorithm can be applied to the max-cut problem.