Highly Symmetric Integer Linear ProgramsAlgebra & Discrete Mathematics
|Prof. Michael Joswig, Technical Univ. Darmstadt Germany
|Fri, Sep 2 2011, 12:00PM
A symmetry of an ILP is a linear transformation which acts as a signed permutation on the variables. Deciding the feasibility of an ILP is a well-known NP-dard problem. However, provided that the group of symmetries contains the alternating group A_n (in its standard action), we can present an algorithm which solves an ILP with m constraints in n variables in O(mn^2) time. Further, it will be discussed how finding ILP symmetries can be reduced to a graph isomorphism problem. This is joint work with Richard B\"odi and Katrin Herr.