TY - GEN A1 - Lutz, Frank H. T1 - Triangulated Manifolds with Few Vertices: Centrally Symmetric Spheres and Products of Spheres N2 - The aim of this paper is to give a survey of the known results concerning centrally symmetric polytopes, spheres, and manifolds. We further enumerate nearly neighborly centrally symmetric spheres and centrally symmetric products of spheres with dihedral or cyclic symmetry on few vertices, and we present an infinite series of vertex-transitive nearly neighborly centrally symmetric 3-spheres. T3 - ZIB-Report - 04-11 KW - centrally symmetric polytopes KW - crosspolytope KW - combinatorial manifolds KW - products of spheres Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7863 ER - TY - GEN A1 - Helmes, Kurt A1 - Röhl, Stefan T1 - A Geometrical Characterization of the Multidimensional Hausdorff and Dale Polytopes with Applications to Exit Time Problems N2 - We present formulae for the corner points of the multidimensional Hausdorff and Dale Polytopes and show how these results can be used to improve linear programming models for computing e.\,g.\ moments of exit distribution of diffusion processes. Specifically, we compute the mean exit time of twodimensional Brownian motion from the unit square and the unit triangle, as well as higher moments of the exit time of time space Brownian motion from a triangle. T3 - ZIB-Report - 04-05 KW - linear programming KW - special polytopes KW - moment problems KW - Brownian motion on a triangle KW - numerical methods for exit time problems Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7807 ER - TY - GEN A1 - Berthold, Timo A1 - Pfetsch, Marc T1 - Detecting Orbitopal Symmetries N2 - Orbitopes can be used to handle symmetries which arise in integer programming formulations with an inherent assignment structure. We investigate the detection of symmetries appearing in this approach. We show that detecting so-called orbitopal symmetries is graph-isomorphism hard in general, but can be performed in linear time if the assignment structure is known. T3 - ZIB-Report - 08-33 KW - Symmetrie-Erkennung KW - Orbitope KW - Ganzzahlige Programmierung KW - Symmetrie-Brechung KW - Graphenisomorphie KW - symmetry detection KW - orbitopes KW - integer programming KW - symmetry breaking KW - graph ismorphism Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10842 SN - 1438-0064 ER - TY - GEN A1 - Kaibel, Volker A1 - Peinhardt, Matthias A1 - Pfetsch, Marc T1 - Orbitopal Fixing N2 - The topic of this paper are integer programming models in which a subset of 0/1-variables encode a partitioning of a set of objects into disjoint subsets. Such models can be surprisingly hard to solve by branch-and-cut algorithms if the permutation of the subsets of the partition is irrelevant. This kind of symmetry unnecessarily blows up the branch-and-cut tree. We present a general tool, called orbitopal fixing, for enhancing the capabilities of branch-and-cut algorithms in solving this kind of symmetric integer programming models. We devise a linear time algorithm that, applied at each node of the branch-and-cut tree, removes redundant parts of the tree produced by the above mentioned permutations. The method relies on certain polyhedra, called orbitopes, which have been investigated in (Kaibel and Pfetsch (2006)). However, it does not add inequalities to the model, and thus, it does not increase the difficulty of solving the linear programming relaxations. We demonstrate the computational power of orbitopal fixing at the example of a graph partitioning problem motivated from frequency planning in mobile telecommunication networks. T3 - ZIB-Report - 06-48 KW - symmetry breaking KW - variable fixing KW - orbitopes Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9422 ER - TY - GEN A1 - Kaibel, Volker A1 - Pfetsch, Marc T1 - Packing and Partitioning Orbitopes N2 - We introduce orbitopes as the convex hulls of 0/1-matrices that are lexicographically maximal subject to a group acting on the columns. Special cases are packing and partitioning orbitopes, which arise from restrictions to matrices with at most or exactly one 1-entry in each row, respectively. The goal of investigating these polytopes is to gain insight into ways of breaking certain symmetries in integer programs by adding constraints, e.g., for a well-known formulation of the graph coloring problem. We provide a thorough polyhedral investigation of packing and partitioning orbitopes for the cases in which the group acting on the columns is the cyclic group or the symmetric group. Our main results are complete linear inequality descriptions of these polytopes by facet-defining inequalities. For the cyclic group case, the descriptions turn out to be totally unimodular, while for the symmetric group case, both the description and the proof are more involved. The associated separation problems can be solved in linear time. T3 - ZIB-Report - 06-17 KW - integer programming KW - symmetry breaking KW - lexicographic representatives Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9104 ER - TY - GEN A1 - Bortoletto, Enrico A1 - Lindner, Niels A1 - Masing, Berenike T1 - The tropical and zonotopal geometry of periodic timetables N2 - The Periodic Event Scheduling Problem (PESP) is the standard mathematical tool for optimizing periodic timetabling problems in public transport. A solution to PESP consists of three parts: a periodic timetable, a periodic tension, and integer periodic offset values. While the space of periodic tension has received much attention in the past, we explore geometric properties of the other two components, establishing novel connections between periodic timetabling and discrete geometry. Firstly, we study the space of feasible periodic timetables, and decompose it into polytropes, i.e., polytopes that are convex both classically and in the sense of tropical geometry. We then study this decomposition and use it to outline a new heuristic for PESP, based on the tropical neighbourhood of the polytropes. Secondly, we recognize that the space of fractional cycle offsets is in fact a zonotope. We relate its zonotopal tilings back to the hyperrectangle of fractional periodic tensions and to the tropical neighbourhood of the periodic timetable space. To conclude we also use this new understanding to give tight lower bounds on the minimum width of an integral cycle basis. T3 - ZIB-Report - 22-09 KW - periodic event scheduling KW - tropical geometry KW - zonotopal tilings Y1 - 2022 SN - 1438-0064 ER - TY - GEN A1 - Bortoletto, Enrico A1 - Lindner, Niels A1 - Masing, Berenike T1 - Tropical Neighbourhood Search: A New Heuristic for Periodic Timetabling N2 - Periodic timetabling is a central aspect of both the long-term organization and the day-to-day operations of a public transportation system. The Periodic Event Scheduling Problem (PESP), the combinatorial optimization problem that forms the mathematical basis of periodic timetabling, is an extremely hard problem, for which optimal solutions are hardly ever found in practice. The most prominent solving strategies today are based on mixed-integer programming, and there is a concurrent PESP solver employing a wide range of heuristics [3]. We present tropical neighborhood search (tns), a novel PESP heuristic. The method is based on the relations between periodic timetabling and tropical geometry [4]. We implement tns into the concurrent solver, and test it on instances of the benchmarking library PESPlib. The inclusion of tns turns out to be quite beneficial to the solver: tns is able to escape local optima for the modulo network simplex algorithm, and the overall share of improvement coming from tns is substantial compared to the other methods available in the solver. Finally, we provide better primal bounds for five PESPlib instances. T3 - ZIB-Report - 22-13 KW - Periodic Timetabling KW - Tropical Geometry KW - Neighbourhood Search KW - Mixed-Integer Programming Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-87385 SN - 1438-0064 ER -