The Boolean quadratic polytope: Some characteristics, facets and relatives

DOI10.1007/BF01589101zbMath0675.90056OpenAlexW2078992232WikidataQ92959382 ScholiaQ92959382MaRDI QIDQ1122479

Publication date: 1989

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

Full work available at URL: https://doi.org/10.1007/bf01589101

zbMATH Keywords

facet-defining inequalities facets series-parallel graphs polyhedral combinatorics polynomial solvability Boolean quadric polytope sparse quadratic forms unconstrained quadratic zero-one programming vertex- packing polytope

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Quadratic programming (90C20) Linear programming (90C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Boolean programming (90C09) Polytopes and polyhedra (52Bxx)

Related Items (only showing first 100 items - show all)

A Polytope for a Product of Real Linear Functions in 0/1 Variables ⋮ Query Complexity in Expectation ⋮ Introduction to QUBO ⋮ The Boolean Quadric Polytope ⋮ Mathematical Programming Models and Exact Algorithms ⋮ The Random QUBO ⋮ Unnamed Item ⋮ An application of the Lovász-Schrijver \(M(K, K)\) operator to the stable set problem ⋮ On the copositive representation of binary and continuous nonconvex quadratic programs ⋮ On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study ⋮ Cutting Plane Generation through Sparse Principal Component Analysis ⋮ SDP-Based Bounds for the Quadratic Cycle Cover Problem via Cutting-Plane Augmented Lagrangian Methods and Reinforcement Learning ⋮ Exact Facetial Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization ⋮ Template-Based Minor Embedding for Adiabatic Quantum Optimization ⋮ The Maximum k-Colorable Subgraph Problem and Related Problems ⋮ Tractable Relaxations of Composite Functions ⋮ Discrete equal-capacityp-median problem ⋮ A cut-and-branch algorithm for the quadratic knapsack problem ⋮ The bipartite Boolean quadric polytope ⋮ A note on the 2-circulant inequalities for the MAX-cut problem ⋮ Nonlinear formulations and improved randomized approximation algorithms for multicut problems ⋮ Efficient joint object matching via linear programming ⋮ Inductive linearization for binary quadratic programs with linear constraints ⋮ The Bipartite Boolean Quadric Polytope with Multiple-Choice Constraints ⋮ An efficient model for the multiple allocation hub maximal covering problem ⋮ Binary Positive Semidefinite Matrices and Associated Integer Polytopes ⋮ Exact Solution Algorithms for the Chordless Cycle Problem ⋮ Partitioning through projections: strong SDP bounds for large graph partition problems ⋮ (Global) optimization: historical notes and recent developments ⋮ Unnamed Item ⋮ Branch-and-bound performance estimation programming: a unified methodology for constructing optimal optimization methods ⋮ On Integrality in Semidefinite Programming for Discrete Optimization ⋮ Optimal design of line replaceable units ⋮ Efficient linear reformulations for binary polynomial optimization problems ⋮ Dendrograms, minimum spanning trees and feature selection ⋮ On the complexity of binary polynomial optimization over acyclic hypergraphs ⋮ A polyhedral study of lifted multicuts ⋮ Using general triangle inequalities within quadratic convex reformulation method ⋮ Competitive equilibrium always exists for combinatorial auctions with graphical pricing schemes ⋮ The symmetric quadratic traveling salesman problem ⋮ Unbounded convex sets for non-convex mixed-integer quadratic programming ⋮ The Multilinear Polytope for Acyclic Hypergraphs ⋮ Classical cuts for mixed-integer programming and branch-and-cut ⋮ Quadratic knapsack relaxations using cutting planes and semidefinite programming ⋮ Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement ⋮ Polyhedral methods for piecewise-linear functions. I: The lambda method ⋮ The cut cone. III: On the role of triangle facets ⋮ Disconnecting graphs by removing vertices: a polyhedral approach ⋮ A Lagrangian relaxation approach to the edge-weighted clique problem ⋮ The QAP-polytope and the star transformation ⋮ A tight lower bound for a special case of quadratic 0-1 programming ⋮ The cut cone. III: On the role of triangle facets ⋮ Models and solution techniques for frequency assignment problems ⋮ The Multistatic Sonar Location Problem and Mixed-Integer Programming ⋮ A polyhedral study of the maximum edge subgraph problem ⋮ Image Labeling Based on Graphical Models Using Wasserstein Messages and Geometric Assignment ⋮ Lagrangian heuristics for the quadratic knapsack problem ⋮ Semidefinite relaxations for partitioning, assignment and ordering problems ⋮ Exact and Heuristic Algorithms for Capacitated Vehicle Routing Problems with Quadratic Costs Structure ⋮ The Running Intersection Relaxation of the Multilinear Polytope ⋮ Evaluating the quality of image matrices in blockmodeling ⋮ A Polyhedral Study of the Quadratic Traveling Salesman Problem ⋮ Semidefinite relaxations for partitioning, assignment and ordering problems ⋮ Mixed Integer Linear Programming Formulation Techniques ⋮ A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem ⋮ Construction de facettes pour le polytope du sac-à-dos quadratique en 0-1 ⋮ Generalized network design polyhedra ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Tight Cycle Relaxations for the Cut Polytope ⋮ A new family of facet defining inequalities for the maximum edge-weighted clique problem ⋮ Mixed integer formulations using natural variables for single machine scheduling around a common due date ⋮ Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods ⋮ On the diameter of lattice polytopes ⋮ Application of cut polyhedra. I ⋮ A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope ⋮ A heuristic-based branch and bound algorithm for unconstrained quadratic zero-one programming ⋮ On integer programming with bounded determinants ⋮ The width and integer optimization on simplices with bounded minors of the constraint matrices ⋮ Mining for diamonds -- matrix generation algorithms for binary quadratically constrained quadratic problems ⋮ Facets of the \(k\)-partition polytope ⋮ Lower bounding procedure for the asymmetric quadratic traveling salesman problem ⋮ Refined proximity and sensitivity results in linearly constrained convex separable integer programming ⋮ A lower bound for a constrained quadratic \(0\)-\(1\) minimization problem ⋮ The volume of relaxed Boolean-quadric and cut polytopes ⋮ Matroid optimisation problems with nested non-linear monomials in the objective function ⋮ A polyhedral approach for a constrained quadratic 0-1 problem ⋮ Algorithmic and modeling insights via volumetric comparison of polyhedral relaxations ⋮ Lower bounds and exact algorithms for the quadratic minimum spanning tree problem ⋮ Graph bisection revisited ⋮ On decomposability of multilinear sets ⋮ In situ column generation for a cutting-stock problem ⋮ Designing cost-effective content distribution networks ⋮ Cardinality constrained Boolean quadratic polytope ⋮ Non-local energetics of random heterogeneous lattices ⋮ Graphic vertices of the metric polytope ⋮ Alternative formulations for the set packing problem and their application to the winner determination problem ⋮ The quadratic knapsack problem -- a survey ⋮ Convexifications of rank-one-based substructures in QCQPs and applications to the pooling problem ⋮ DRL\(^*\): A hierarchy of strong block-decomposable linear relaxations for 0-1 mips

Cites Work

This page was built for publication: The Boolean quadratic polytope: Some characteristics, facets and relatives