Cutting planes are frequently used for solving large integer programs. A common strategy is to derive cutting planes from building blocks or substructure of the integer program. In this presentation, we focus on knapsack constraints that arise from single row relaxations. Among the most popular classes derived from knapsack constraints are lifted minimal cover inequalities. Yet the separation problem for these inequalities is NP-hard, and one usually separates them heuristically, therefore not fully exploiting their potential.

In practice however, it turns out that many knapsack constraints only have few different coefficients. This motivates the concept of sparse knapsacks where the number of different coefficients is a small constant, independent of the number of variables present. For such knapsacks, we observe that there are only polynomially many different classes of structurally equivalent minimal covers. This opens the door to specialized techniques for using lifted minimal cover inequalities.

In this presentation we will discuss two such techniques, which are based on specialized sorting methods. On the one hand, we present new separation routines that separate equivalence classes of inequalities rather than individual inequalities. On the other hand, we derive compact extended formulations that express all minimal cover inequalities by means of a polynomial number of constraints. These extended formulations are based on tailored sorting networks that express our separation algorithm by linear inequalities. We conclude the presentation by a numerical investigation of the different techniques for popular benchmarking instances.