Optimization Online


On the Structure of Linear Programs with Overlapping Cardinality Constraints

Tobias Fischer(tfischer***at***mathematik.tu-darmstadt.de)
Marc Pfetsch(pfetsch***at***mathematik.tu-darmstadt.de)

Abstract: Cardinality constraints enforce an upper bound on the number of variables that can be nonzero. This article investigates linear programs with cardinality constraints that mutually overlap, i.e., share variables. We present the components of a branch-and-cut solution approach, including new branching rules that exploit the structure of the corresponding conflict hypergraph. We also investigate valid or facet defining cutting planes for the convex hull of the feasible solution set. Our approach can be seen as a continuous analogue of independence system polytopes. We study three different classes of cutting planes: hyperclique bound cuts, implied bound cuts, and flow cover cuts. In a computational study, we examine the effectiveness of an implementation based on the presented concepts.

Keywords: Cardinality constraints, Complementarity constraints, Flow cover inequalities, Mixed-integer programming, Branch-and-cut

Category 1: Integer Programming

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )


Download: [PDF]

Entry Submitted: 01/25/2017
Entry Accepted: 01/25/2017
Entry Last Modified: 01/25/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society