Exploiting symmetries in polyhedral computations

DOI10.1007/978-3-319-00200-2_15zbMATH Open1273.90127arXiv1406.5281OpenAlexW1550959500MaRDI QIDQ2849003FDOQ2849003

Authors: Achill Schürmann 

Publication date: 13 September 2013

Published in: Discrete Geometry and Optimization (Search for Journal in Brave)

Abstract: In this note we give a short overview on symmetry exploiting techniques in three different branches of polyhedral computations: The representation conversion problem, integer linear programming and lattice point counting. We describe some of the future challenges and sketch some directions of potential developments.

Full work available at URL: https://arxiv.org/abs/1406.5281

Recommendations

• Polyhedral representation conversion up to symmetries
• Computing symmetry groups of polyhedra
• Algorithms for highly symmetric linear and integer programs
• Symmetry in mathematical programming
• Polytopes associated with symmetry handling

zbMATH Keywords

symmetryinteger linear programmingEhrhart theoryvolume computationsrepresentation conversionpolyhedral computations

Mathematics Subject Classification ID

Integer programming (90C10) Lattice points in specified regions (11P21) Polytopes and polyhedra (52B99)

Cites Work

• PORTA
• Combinatorial optimization and small polytopes
• polymake: a framework for analyzing convex polytopes
• SCIP: solving constraint integer programs
• A proof of the Kepler conjecture
• MathOverflow
• Title not available (Why is that?)
• Title not available (Why is that?)
• Reducibility among combinatorial problems
• On the complexity of polytope isomorphism problems
• The Ehrhart polynomial of the Birkhoff polytope
• Computing symmetry groups of polyhedra
• Computing the Continuous Discretely
• The many aspects of counting lattice points in polytopes
• Title not available (Why is that?)
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Probability calculations under the IAC hypothesis
• Integer Programming with a Fixed Number of Variables
• Title not available (Why is that?)
• Abstract Regular Polytopes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Classification algorithms for codes and designs
• Counting linear extensions
• How to integrate a polynomial over a simplex
• Title not available (Why is that?)
• Convex Polytopes
• Title not available (Why is that?)
• Computational geometry of positive definite quadratic forms. Polyhedral reduction theories, algorithms, and applications
• Generating all vertices of a polyhedron is hard
• Voting paradoxes and group coherence. The Condorcet efficiency of voting rules.
• Packing and partitioning orbitopes
• Algebraic algorithms for sampling from conditional distributions
• A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
• On the Complexity of Computing the Volume of a Polyhedron
• Tensor product multiplicities, canonical and totally positive varieties
• Sur un probl?me de g?om?trie diophantienne lin?aire. I. Poly?dres et r?seaux.
• Orbital branching
• Title not available (Why is that?)
• Integer points in polyhedra
• The many facets of linear programming
• A counterexample to the Hirsch conjecture
• Symmetry in integer linear programming
• On the face lattice of the metric polytope
• The strong dodecahedral conjecture and Fejes Tóth's conjecture on sphere packings with kissing number twelve
• The honeycomb model of $GL_n(\mathbb C)$ tensor products I: Proof of the saturation conjecture
• Algorithms for highly symmetric linear and integer programs
• Experimental study of energy-minimizing point configurations on spheres
• Optimality and uniqueness of the Leech lattice among lattices
• Exploiting orbits in symmetric ILP
• Complexity and algorithms for computing Voronoi cells of lattices
• Fundamental Domains for Integer Programs with Symmetries
• On the integral homology of \(\text{PSL}_4(\mathbb Z)\) and other arithmetic groups
• Exploiting polyhedral symmetries in social choice
• The computation of generalized Ehrhart series in normaliz
• Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra
• Improving bounds on the football pool problem by integer programming and high-throughput computing
• Classification of eight-dimensional perfect forms
• Classification of orthogonal arrays by integer programming
• Title not available (Why is that?)
• Title not available (Why is that?)
• Counting lattice points
• Permutation group algorithms based on partitions. I: Theory and algorithms
• Polyhedral representation conversion up to symmetries
• The contact polytope of the Leech lattice
• DECOMPOSITION AND PARALLELIZATION TECHNIQUES FOR ENUMERATING THE FACETS OF COMBINATORIAL POLYTOPES
• Linear and Integer Programming vs Linear Integration and Counting
• A counterexample to the dominating set conjecture
• C++ tools for exploiting polyhedral symmetries
• Exploiting symmetry in integer convex optimization using core points

Cited In (9)

• Mini-workshop: Exploiting symmetry in optimization. Abstracts from the mini-workshop held August 22nd -- August 28th, 2010.
• Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization
• Local orientation-preserving symmetry preserving operations on polyhedra
• Computing symmetry groups of polyhedra
• An effective solution to convex 1-body \(N\)-representability
• C++ tools for exploiting polyhedral symmetries
• Polyhedral representation conversion up to symmetries
• On the geometry of symmetry breaking inequalities
• On the geometry of symmetry breaking inequalities

Uses Software

• Normaliz
• PORTA
• PermLib
• SymPol
• Polyhedral
• kepler98
• MathOverflow

This page was built for publication: Exploiting symmetries in polyhedral computations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2849003)