Annika Jaeger

Structure-Preserving Symmetry Presolving for Mixed-Binary Linear Problems

Categories (Mixed) Integer Linear Programming, 0-1 Programming Tags , ,

This paper investigates a presolving method for handling symmetries in mixed-binary programs, based on inequalities computed from so-called Schreier-Sims tables. We show that an iterative application of this method together with merging variables will produce an instance for which the symmetry group is trivial. We then prove that the problem structure can be preserved for … Read more

The Impact of Symmetry Handling for the Stable Set Problem via Schreier-Sims Cuts

Categories Integer Programming Tags , , ,

Symmetry handling inequalities (SHIs) are an appealing and popular tool for handling symmetries in integer programming. Despite their practical application, little is known about their interaction with optimization problems. This article focuses on Schreier-Sims (SST) cuts, a recently introduced family of SHIs, and investigates their impact on the computational and polyhedral complexity of optimization problems. … Read more