Exploiting symmetry in integer convex optimization using core points

Abstract We consider convex programming problems with integrality constraints that are invariant under a linear symmetry group. To decompose such problems, we introduce the new concept of core points, i.e., integral points whose orbit polytopes are lattice-free. For symmetric integer linear programs, we describe two algorithms based on this decomposition. Using a characterization of core points for direct products of symmetric groups, we show that prototype implementations can compete with state-of-the-art commercial solvers, and solve an open MIPLIB problem.