On the Matrix-Cut Rank of Polyhedra

DOI10.1287/moor.26.1.19.10593zbMath1073.90574OpenAlexW2146471456MaRDI QIDQ2757665

Sanjeeb Dash, William Cook

Publication date: 26 November 2001

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/a556a78ee9c3325455399e8289e7b35b0778a429

zbMATH Keywords

Semidefinite programming, integer hull, rank of polytopes, cutting planes, projection operators

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items (31)

Approximation Limits of Linear Programs (Beyond Hierarchies) ⋮ Tree-width and the Sherali-Adams operator ⋮ Theoretical challenges towards cutting-plane selection ⋮ Handelman rank of zero-diagonal quadratic programs over a hypercube and its applications ⋮ Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators ⋮ Sum of Squares Bounds for the Empty Integral Hull Problem ⋮ Rank of Handelman hierarchy for Max-Cut ⋮ Sum-of-squares hierarchy lower bounds for symmetric formulations ⋮ On polytopes with linear rank with respect to generalizations of the split closure ⋮ Complexity of optimizing over the integers ⋮ Lower bounds on the size of general branch-and-bound trees ⋮ Complexity of branch-and-bound and cutting planes in mixed-integer optimization ⋮ Tightening simple mixed-integer sets with guaranteed bounds ⋮ Random half-integral polytopes ⋮ Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra ⋮ Approximate formulations for 0-1 knapsack sets ⋮ Rank bounds for a hierarchy of Lovász and Schrijver ⋮ Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes ⋮ Design and Verify: A New Scheme for Generating Cutting-Planes ⋮ Lift \& project systems performing on the partial-vertex-cover polytope ⋮ Design and verify: a new scheme for generating cutting-planes ⋮ A new lift-and-project operator ⋮ On the complexity of cutting-plane proofs using split cuts ⋮ Elementary closures for integer programs. ⋮ Unnamed Item ⋮ A Comprehensive Analysis of Polyhedral Lift-and-Project Methods ⋮ Valid inequalities for mixed integer linear programs ⋮ Convexification techniques for linear complementarity constraints ⋮ On the polyhedral lift-and-project methods and the fractional stable set polytope ⋮ Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II ⋮ Approximate fixed-rank closures of covering problems

This page was built for publication: On the Matrix-Cut Rank of Polyhedra