Geometric quadratic separators for symmetric integer programs

Abstract

Symmetry in integer linear programming (ILP) often increases computational effort by generating many equivalent solutions under group actions. One effective approach is to focus on core points—distinguished integer representatives whose orbit polytopes are lattice-free—so that optimizing over these representatives preserves optimality while avoiding redundant symmetry. Symmetry groups acting on Rn naturally induce invariant subspaces through their coordinate-permutation actions. In previous core-point approaches, the case where core points lie in such invariant subspaces was particularly difficult to handle and motivates the main focus of this thesis.

This thesis begins with a two-subspace setting, consisting of the fixed space and Layer 0, and then extends the analysis to a multi-subspace framework based on invariant subspaces induced by cyclic symmetry. We introduce a cone-based separation scheme that constructs quadratic separators using the geometry of these invariant subspaces. The goal is to exclude a candidate point while keeping the relevant symmetry-invariant subspaces feasible. The theoretical framework is developed through coordinate transformations that reveal invariant structure and link algebraic symmetry to geometric feasibility conditions.

We integrate these separators into the SCIP (Solving Constraint Integer Programs) environment through its Python interface, PySCIPOpt, which provides programmatic access to SCIP. This integration enables direct tests on both feasible and infeasible ILP instances. The experiments show that the cone method can reveal repeated symmetry-related incumbent patterns and convert them into additional quadratic cuts that are added during the search. These results support the method as a geometric cutting procedure and provide a geometric foundation for extending core-point methods to symmetric ILPs.