Algorithms for highly symmetric linear and integer programs

DOI10.1007/s10107-011-0487-6zbMath1262.90101arXiv1012.4941OpenAlexW2072303328WikidataQ117245075 ScholiaQ117245075MaRDI QIDQ1942261

Katrin Herr, Michael Joswig, Richard Bödi

Publication date: 18 March 2013

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

symmetrypermutation group

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10) Linear programming (90C05)

Related Items

Equivalence of Lattice Orbit Polytopes, Exploiting symmetries for scaling loopy belief propagation and relational training, Finding the symmetry group of an LP with equality constraints and its application to classifying orthogonal arrays, Finding Symmetry Groups of Some Quadratic Programming Problems, Exploiting symmetries for single- and multi-agent partially observable stochastic domains, Exploiting symmetry in integer convex optimization using core points, Using symmetry to optimize over the Sherali-Adams relaxation, A computational comparison of symmetry handling methods for mixed integer programs, Relational linear programming, On lattice-free orbit polytopes, Orbital shrinking: theory and applications, On the geometry of symmetry breaking inequalities, On the geometry of symmetry breaking inequalities, Computing symmetry groups of polyhedra, Exploiting Symmetries in Polyhedral Computations, Fundamental Domains for Symmetric Optimization: Construction and Search

Uses Software

• nauty
• polymake

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on detecting simple redundancies in linear systems
• Orbital branching
• Lower bounds for the Chvàtal-Gomory rank in the 0/1 cube
• Packing and partitioning orbitopes
• Computing isometries of lattices
• Pruning by isomorphism in branch-and-cut
• On the complexity of polytope isomorphism problems
• Exploiting orbits in symmetric ILP
• Symmetry groups, semidefinite programs, and sums of squares
• Integer Programming with a Fixed Number of Variables
• Automatic Detection of Variable and Value Symmetries
• Fundamental Domains for Integer Programs with Symmetries
• Finite Permutation Groups and Finite Simple Groups
• Lectures on Polytopes
• Detecting Orbitopal Symmetries