Algorithms for Highly Symmetric Linear and Integer Programs

Abstract

This paper deals with exploiting symmetry for solving linear and integer programming problems. Basic properties of linear representations of finite groups can be used to reduce symmetric linear programming to solving linear programs of lower dimension. Combining this approach with knowledge of the geometry of feasible integer solutions yields an algorithm for solving highly symmetric integer linear programs which only takes time which is linear in the number of constraints and quadratic in the dimension.

21 pages, 1 figure; some references and further comments added, title slightly changed

References in corpus (2)

• Lectures on 0/1-polytopes
• Symmetry groups, semidefinite programs, and sums of squares

Cited by in corpus (8)

• Computing symmetry groups of polyhedra
• Exploiting Symmetry in Integer Convex Optimization using Core Points
• Explicit Polyhedral Bounds on Network Coding Rate Regions via Entropy Function Region: Algorithms, Symmetry, and Computation
• On Lattice-Free Orbit Polytopes
• On Symmetry Groups of Some Quadratic Programming Problems
• Finding the symmetry group of an LP with equality constraints and its application to classifying orthogonal arrays
• Equivalence of Lattice Orbit Polytopes
• Symmetry Detection for Quadratically Constrained Quadratic Programs Using Binary Layered Graphs