A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope

DOI10.1016/0167-6377(94)00065-EzbMath0835.90080OpenAlexW2091430165MaRDI QIDQ1892658

Hanif D. Sherali, Youngho Lee, Warren P. Adams

Publication date: 15 April 1996

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(94)00065-e

zbMATH Keywords

liftingfacetsquadric polytope

Mathematics Subject Classification ID

Quadratic programming (90C20) Combinatorial optimization (90C27) Boolean programming (90C09)

Related Items

Surrogate-RLT cuts for zero-one integer programs, On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study, The bipartite Boolean quadric polytope, The Bipartite Boolean Quadric Polytope with Multiple-Choice Constraints, Foundation-penalty cuts for mixed-integer programs., New facets and a branch-and-cut algorithm for the weighted clique problem., A Lagrangian relaxation approach to the edge-weighted clique problem, Volume computation for sparse Boolean quadric relaxations, A study of the quadratic semi-assignment polytope, A note on the Boolean quadric polytope, Closed-form formulas for evaluating \(r\)-flip moves to the unconstrained binary quadratic programming problem, Some classes of valid inequalities and convex hull characterizations for dynamic fixed-charge problems under nested constraints

Cites Work

• Unnamed Item
• The inequicut cone
• Upper-bounds for quadratic 0-1 maximization
• Lifting facets of the cut polytope
• A decomposition method for minimizing quadratic pseudo-Boolean functions
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Experiments in quadratic 0-1 programming
• Facets for the cut cone. I
• On the equivalence between roof duality and Lagrangian duality for unconstrained \(0\)-\(1\) quadratic programming problems
• The cut polytope and the Boolean quadric polytope
• Unconstrained 0-1 optimization and Lagrangean relaxation
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Nonlinear 0–1 programming: I. Linearization techniques
• Nonlinear 0–1 programming: II. Dominance relations and algorithms
• Roof duality, complementation and persistency in quadratic 0–1 optimization
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• Methods of Nonlinear 0-1 Programming
• Lifting the facets of zero–one polytopes
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• State-of-the-Art Survey—Constrained Nonlinear 0–1 Programming
• Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions
• On the cut polytope