A note on critical-set and lifted surrogate inequalities for cardinality-constrained linear programs

• Generalize critical-set cuts for cardinality-constrained LP (CCLP) sets.
• Show how to derive lifted surrogate cuts for the CCLP polytope on-the-fly.
• Test the use of both cuts within branch-and-cut to solve CCLP.
• Analyze the results of the computational tests.

We study the polyhedral approach to the cardinality-constrained linear programming problem (CCLP). First, we generalize Bienstock’s critical-set inequalities. We find necessary and sufficient conditions for the generalized inequalities to define facets of the convex hull of CCLP’s feasible set. Then, we show how to derive lifted surrogate cutting planes on-the-fly. We test the use of both families of inequalities on branch-and-cut to solve difficult instances of CCLP to proven optimality. Our computational results indicate that the use of the inequalities can reduce the time required to solve CCLP by branch-and-cut considerably.