Symmetries in Integer Programs

2009/08/23 by Richard Bödi, R. Bödi, Bödi, R. +3
Computer Science · Engineering · Mathematics · #Constraint Satisfaction and Optimization #Optimization and Packing Problems #Vehicle Routing Optimization Methods #math.CO #math.OC

paper · pdf · doi:10.48550/arxiv.0908.3331

16 pages, 4 figures

arxiv created 2009/08/23 · arxiv updated 2009/12/01

Abstract

The notion of symmetry is defined in the context of Linear and Integer Programming. Symmetric integer programs are studied from a group theoretical viewpoint. We investigate the structure of integer solutions of integer programs and show that any integer program on n variables having an alternating group A_n as a group of symmetries can be solved in linear time in the number of variables.

Related

• Symmetries in Linear and Integer Programs
• Handling Sub-symmetry in Integer Programming using Activation Handlers
• Automatic Generation of Polynomial Symmetry Breaking Constraints
• Linear Programming Hierarchies Collapse under Symmetry
• A proof system for certifying symmetry and optimality reasoning in integer programming