On the structure of linear programs with overlapping cardinality constraints (Q2297664)

A cardinality constrained linear programming problem $(P)$ is of the form $\max c^{T}x$ s.t. $Ax \le b$, $x \geq 0$, the number of nonzero entries of $x$ not exceeding a positive integer $k$. The authors provide an efficient solution approach to $(P)$ based on branch-and-cut. To this end, they reformulate $(P)$ as a disjunctive programming problem resulting from a relation with independent sets in the conflict hypergraph, and they investigate the polyhedral structure of the feasible solution set. Problem $(P)$ is then shown to be NP-hard to solve in general, but polynomially solvable for special cases such as co-triangulated conflict hypergraphs. Branching rules such as hyperclique and neighborhood branching are investigated and a procedure to derive valid or facet-defining inequalities is presented and illustrated for classes of cutting planes such as hyperclique bound cuts and flow cover cuts. Based on these concepts, the authors develop an efficient branch-and-cut algorithm which for specifically structured problem instances is reported to outperform CPLEX 12.6.1.