On the structure of linear programs with overlapping cardinality constraints
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.
- Branch-and-cut for complementarity and cardinality constrained linear programs
- Branch-and-cut for linear programs with overlapping SOS1 constraints
- On cutting planes for cardinality-constrained linear programs
- Cardinality constraints and systems of restricted representatives
- A polyhedral study of the cardinality constrained knapsack problem
- A class of hypergraphs that generalizes chordal graphs
- A generalization of antiwebs to independence systems and their canonical facets
- A polyhedral study of the cardinality constrained knapsack problem
- Branch-and-cut for combinatorial optimisation problems without auxiliary binary variables
- Branch-and-cut for complementarity and cardinality constrained linear programs
- Branch-and-cut for complementarity-constrained optimization
- Branch-and-cut for linear programs with overlapping SOS1 constraints
- Computational study of a family of mixed-integer quadratic programming problems
- Disjunctive programming: Properties of the convex hull of feasible points
- Facets of the independent set polytope
- Formulations for dynamic lot sizing with service levels
- Generalizations of Cliques, Odd Cycles and Anticycles and Their Relation to Independence System Polyhedra
- Geometric algorithms and combinatorial optimization
- scientific article; zbMATH DE number 192986 (Why is no real title available?)
- scientific article; zbMATH DE number 1107728 (Why is no real title available?)
- LATIN 2004: Theoretical Informatics
- Mathematical programs with cardinality constraints: reformulation by complementarity-type conditions and a regularization method
- Maximal chordal subgraphs
- Monoidal cut strengthening and generalized mixed-integer rounding for disjunctions and complementarity constraints
- NP-completeness of the linear complementarity problem
- On the dimension of projected polyhedra
- On the facial structure of the set covering polytope
- On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\)
- On the set covering polytope: Facets with coefficients in \(\{0,1,2,3\}\)
- Optimal cardinality constrained portfolio selection
- Polyhedral approaches to mixed integer linear programming
- Preprocessing and Probing Techniques for Mixed Integer Programming Problems
- Recent advances in mathematical programming with semi-continuous variables and cardinality constraint
- Representability in mixed integer programming. I: Characterization results
- SCIP: solving constraint integer programs
- The complementary class of generalized flow cover inequalities
- Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints
- Valid inequalities for 0-1 knapsacks and MIPs with generalised upper bound constraints
- Valid inequalities for mixed 0-1 programs
- Branch-and-cut for linear programs with overlapping SOS1 constraints
- On cutting planes for cardinality-constrained linear programs
- On a Reformulation of Mathematical Programs with Cardinality Constraints
- Tight LP-Relaxations of Overlapping Global Cardinality Constraints
- Branch-and-cut for complementarity and cardinality constrained linear programs
- Cardinality minimization, constraints, and regularization: a survey
- The cardinality and precedence constrained maximum value sub-hypergraph problem and its applications
This page was built for publication: On the structure of linear programs with overlapping cardinality constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2297664)
