The Boolean quadric polytope

DOI10.1007/978-3-031-04520-2_4MaRDI QIDQ5050144zbMATH OpenOpenAlexFDO

Authors Adam N. Letchford

Publication date 15 November 2022

Published in The Quadratic Unconstrained Binary Optimization Problem (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-031-04520-2_4

zbMATH Keywords

Boolean quadric polytopepolyhedral theory

Mathematics Subject Classification ID

Boolean programming (90C09) Quadratic programming (90C20)

Recommendations

• The Boolean quadratic polytope: Some characteristics, facets and relatives
• scientific article; zbMATH DE number 4185387
• scientific article; zbMATH DE number 4131953
• A polyhedral approach for a constrained quadratic 0-1 problem
• The cut polytope and the Boolean quadric polytope

Cites work

• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• A convex polytope of diameter one
• A cut-and-branch algorithm for the quadratic knapsack problem
• A Cutting Plane Algorithm for the Linear Ordering Problem
• A new separation algorithm for the Boolean quadric and cut polytopes
• A note on the 2-circulant inequalities for the MAX-cut problem
• A note on the Boolean quadric polytope
• A polyhedral approach for nonconvex quadratic programming problems with box constraints
• A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
• A study of the quadratic semi-assignment polytope
• A tight bound for the boolean quadratic optimization problem and its use in a branch and bound algorithm¹
• An Automatic Method of Solving Discrete Programming Problems
• Binary positive semidefinite matrices and associated integer polytopes
• Box-inequalities for quadratic assignment polytopes
• Cardinality constrained Boolean quadratic polytope
• Correlation polytopes: Their geometry and complexity
• Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions
• Discrete and Computational Geometry
• Elementare Theorie der konvexen Polyeder
• Enhancing RLT relaxations via a new class of semidefinite cuts
• Experiments in quadratic 0-1 programming
• Fifty-plus years of combinatorial integer programming
• Gap inequalities for non-convex mixed-integer quadratic programs
• Gap inequalities for the cut polytope
• Gap inequalities for the max-cut problem: a cutting-plane algorithm
• Geometric algorithms and combinatorial optimization
• Geometry of cuts and metrics
• scientific article; zbMATH DE number 4070633 (Why is no real title available?)
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 1131473 (Why is no real title available?)
• scientific article; zbMATH DE number 1175944 (Why is no real title available?)
• scientific article; zbMATH DE number 1516564 (Why is no real title available?)
• scientific article; zbMATH DE number 3432276 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Improved semidefinite bounding procedure for solving max-cut problems to optimality
• Integer programming approaches to the travelling salesman problem
• Lifting and separation procedures for the cut polytope
• Max-cut in circulant graphs
• New facets and a branch-and-cut algorithm for the weighted clique problem.
• Nonpolyhedral Relaxations of Graph-Bisection Problems
• On a positive semidefinite relaxation of the cut polytope
• On Linear Characterizations of Combinatorial Optimization Problems
• On the cut polytope
• Outline of an algorithm for integer solutions to linear programs
• Polyhedral techniques in combinatorial optimization I: Theory
• Polyhedral techniques in combinatorial optimization II: applications and computations
• Separating subdivision of bicycle wheel inequalities over cut polytopes
• Solving Large-Scale Zero-One Linear Programming Problems
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
• Some simplified NP-complete graph problems
• Stronger linear programming relaxations of max-cut
• Technical Note—Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program
• Testing the Odd Bicycle Wheel Inequalities for the Bipartite Subgraph Polytope
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• The cut polytope and the Boolean quadric polytope
• The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations
• The expected relative error of the polyhedral approximation of the max- cut problem
• The hypermetric cone is polyhedral

Cited in

(8)

• The Boolean quadratic polytope: Some characteristics, facets and relatives
• The cut polytope and the Boolean quadric polytope
• The bipartite Boolean quadric polytope
• scientific article; zbMATH DE number 4131953 (Why is no real title available?)
• Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions
• scientific article; zbMATH DE number 4185387 (Why is no real title available?)
• Revisiting some classical linearizations of the quadratic binary optimization problem and linkages with constraint aggregations
• Proximity guarantees of a lift-and-project approach for the cardinality-constrained Boolean quadric polytope

Describes a project that uses

Uses Software

• Biq Mac

This page was built for publication: The Boolean quadric polytope

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