Valid inequalities and computational results for SOS1-, SOS2-, and cardinality-constrained linear programs

Abstract

In this dissertation, we consider three types of constraints that are frequently used in mixed integer programming (MIP), namely: SOS1, SOS2, and cardinality. We study and develop cutting planes for those types of constraints, and use them within branch-and-cut to solve difficult MIP instances.

Our computational results indicate that the cutting planes used are very effective in reducing the solution times of our instances. We also study the effect of other common features present in commercial solvers, such as preprocessing, "standard" cutting planes, and heuristics.