Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

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.