On cutting planes for cardinality-constrained linear programs

DOI10.1007/S10107-018-1306-0zbMATH Open1461.90081OpenAlexW2806314820WikidataQ129715004 ScholiaQ129715004MaRDI QIDQ2330656FDOQ2330656

Authors: Jinhak Kim, Mohit Tawarmalani, Jean-Philippe Richard 

Publication date: 22 October 2019

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-018-1306-0

Recommendations

• On the structure of linear programs with overlapping cardinality constraints
• On the Complexity of a Cutting Plane Algorithm for Solving Combinatorial Linear Programs
• Cutting plane algorithms for \(0-1\) programming based on cardinality cuts
• Cutting planes in integer and mixed integer programming
• On disjunctive cuts for combinatorial optimization

zbMATH Keywords

Prim's algorithmcomplementarity/cardinality constraintsconcavity cutsdisjunctive setsequate-and-relax proceduretableau cuts

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Nonconvex programming, global optimization (90C26) Mixed integer programming (90C11) Approximation by convex sets (52A27)

Cites Work

• A note on solving large p-median problems
• Best subset selection via a modern optimization lens
• Generalized power method for sparse principal component analysis
• A Direct Formulation for Sparse PCA Using Semidefinite Programming
• Lectures on Polytopes
• An evolutionary heuristic for the index tracking problem.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Some polyhedra related to combinatorial problems
• Intersection Cuts—A New Type of Cutting Planes for Integer Programming
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Title not available (Why is that?)
• Computational study of a family of mixed-integer quadratic programming problems
• Disjunctive Programming
• Algorithm for cardinality-constrained quadratic optimization
• Title not available (Why is that?)
• An MCDM approach to portfolio optimization.
• Foundations of Optimization
• Heuristic algorithms for the portfolio selection problem with minimum transaction lots
• Simulated annealing for complex portfolio selection problems.
• Heuristics for cardinality constrained portfolio optimization
• A hybrid optimization approach to index tracking
• Technical Note—An Algorithm for the p-Median Problem
• A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer gomory cuts for 0-1 programming
• Lift-and-project for general two-term disjunctions
• A polyhedral study of the cardinality constrained knapsack problem
• Branch-and-cut for combinatorial optimisation problems without auxiliary binary variables
• On Connections Between Zero-One Integer Programming and Concave Programming Under Linear Constraints
• On the Use of Exact and Heuristic Cutting Plane Methods for the Quadratic Assignment Problem
• A polyhedral study on \(0\)-\(1\) knapsack problems with disjoint cardinality constraints: strong valid inequalities by sequence-independent lifting
• A polyhedral study on \(0\)-\(1\) knapsack problems with disjoint cardinality constraints: facet-defining inequalities by sequential lifting
• On the \(p\)-median polytope
• A family of facets for the uncapacitated \(p\)-median polytope
• Ensemble pruning via semi-definite programming
• Computational aspects of alternative portfolio selection models in the presence of discrete asset choice constraints
• Technical Note—The Use of Cuts in Complementary Programming
• A tree search algorithm for the p-median problem
• Technical Note—A Branch-and-Bound Algorithm for Seeking the P-Median
• Convexity Cuts and Cut Search
• Title not available (Why is that?)

Cited In (10)

• Cardinality and the Simplex Tableau for the Set Partitioning Problem
• Cutting plane algorithms for \(0-1\) programming based on cardinality cuts
• Cardinality minimization, constraints, and regularization: a survey
• Cardinality constrained and multicriteria (multi)cut problems
• A Note on Bounding a Class of Linear Programming Problems, Including Cutting Stock Problems
• Logical constraints as cardinality rules: Tight representation
• Convexification techniques for linear complementarity constraints
• Face dimensions of general-purpose cutting planes for mixed-integer linear programs
• On the redundancy of cutting planes for linear complementarity problems
• Cardinality Constrained Decomposition

Uses Software

• PORTA

This page was built for publication: On cutting planes for cardinality-constrained linear programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2330656)