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

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, Some results on the strength of relaxations of multilinear functions, On convex relaxations for quadratically constrained quadratic programming, Some thoughts on combinatorial optimisation, On tail dependence matrices. The realization problem for parametric families, Gap inequalities for non-convex mixed-integer quadratic programs, New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph, A class of hypergraphs and vertices of cut polytope relaxations, On the impact of running intersection inequalities for globally solving polynomial optimization problems, Separation and relaxation for cones of quadratic forms, Knapsack problem with probability constraints, An integer linear programming approach for bilinear integer programming, Upper-bounds for quadratic 0-1 maximization, New facets and a branch-and-cut algorithm for the weighted clique problem., Exact algorithms for the joint object placement and request routing problem in content distribution networks, On a problem of integer optimization, Convex and concave envelopes: revisited and new perspectives, A note on representations of linear inequalities in non-convex mixed-integer quadratic programs, Box-constrained quadratic programs with fixed charge variables, Exploiting partial correlations in distributionally robust optimization, Binary positive semidefinite matrices and associated integer polytopes, The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds, Valid inequalities for quadratic optimisation with domain constraints, A new framework to relax composite functions in nonlinear programs, A network approach for specially structured linear programs arising in 0-1 quadratic optimization, On reduced semidefinite programs for second order moment bounds with applications, A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO), Berge-acyclic multilinear 0-1 optimization problems, The MIN-cut and vertex separator problem, An exact solution method for quadratic matching: the one-quadratic-term technique and generalisations, On the Lovász theta function and some variants, Addendum to: ``Vertex adjacencies in the set covering polyhedron, Facets for the cut cone. I, The generalized vertex cover problem and some variations, Maximum-entropy sampling and the Boolean quadric polytope, Optimal design of a distributed network with a two-level hierarchical structure, Pseudo-Boolean optimization, Solving the maximum edge-weight clique problem in sparse graphs with compact formulations, On a recognition problem on cut polytope relaxations, A polyhedral study of nonconvex quadratic programs with box constraints, Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem, Exact and heuristic algorithms for the weighted total domination problem, Membership testing for Bernoulli and tail-dependence matrices, Theoretical and computational study of several linearisation techniques for binary quadratic problems, Assortment optimization under the multinomial logit model with product synergies, Volume computation for sparse Boolean quadric relaxations, A study of the quadratic semi-assignment polytope, An evolutionary heuristic for quadratic 0-1 programming, Solving multistatic sonar location problems with mixed-integer programming, Cliques and clustering: A combinatorial approach, Convex hull representations of special monomials of binary variables, A linearization framework for unconstrained quadratic (0-1) problems, Matroid optimization problems with monotone monomials in the objective, Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case, An extended formulation approach to the edge-weighted maximal clique problem, The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations, Exact and heuristic algorithms for the maximum weighted submatrix coverage problem, Extended formulations for convex hulls of some bilinear functions, New SOCP relaxation and branching rule for bipartite bilinear programs, Set characterizations and convex extensions for geometric convex-hull proofs, A new separation algorithm for the Boolean quadric and cut polytopes, Multilinear sets with two monomials and cardinality constraints, The partial constraint satisfaction problem: Facets and lifting theorems, Separating subdivision of bicycle wheel inequalities over cut polytopes, Relaxation optical bistability: A new class of optically bistable elements, Boolean polynomials and set functions, Formulating logical implications in combinatorial optimisation, Cutting planes for RLT relaxations of mixed 0-1 polynomial programs, Min-cut clustering, Complete positivity and distance-avoiding sets, ``Miniaturized linearizations for quadratic 0/1 problems

Cites Work