Problem Size Reduction for Set Partitioning Problems

Very large Set Partitioning Problems arising in practice often contain redundancies because of the way the problem instances are generated. We examine techniques that remove redundancies based on logical implications without eliminating any optimal solutions. These problem size reduction techniques are useful not only for preprocessing problem instances but also for propagating the effects of decisions made during a solution process (whether it be heuristics or Branch and Bound). Our main contribution is a theorem of exhaustive reduction for a set of well-known reduction operations. We show that applying these operations in any order until no more reductions are possible always results in the same reduced problem. We also examine which reduction operations lead to (and to what kind of) new reduction instances. We also sketch an efficient implementation of these techniques that relies on lexicographically ordering the columns of the problem matrix before the reductions. The ordering of the columns allows us to implement one of the reduction operations that was thought to be too expensive before. Computational results are presented for a set of
crew scheduling problems.