The Bipartite Boolean Quadric Polytope with Multiple-Choice Constraints
From MaRDI portal
Publication:6060149
Abstract: We consider the bipartite boolean quadric polytope (BQP) with multiple-choice constraints and analyse its combinatorial properties. The well-studied BQP is defined as the convex hull of all quadric incidence vectors over a bipartite graph. In this work, we study the case where there is a partition on one of the two bipartite node sets such that at most one node per subset of the partition can be chosen. This polytope arises, for instance, in pooling problems with fixed proportions of the inputs at each pool. We show that it inherits many characteristics from BQP, among them a wide range of facet classes and operations which are facet preserving. Moreover, we characterize various cases in which the polytope is completely described via the relaxation-linearization inequalities. The special structure induced by the additional multiple-choice constraints also allows for new facet-preserving symmetries as well as lifting operations. Furthermore, it leads to several novel facet classes as well as extensions of these via lifting. We additionally give computationally tractable exact separation algorithms, most of which run in polynomial time. Finally, we demonstrate the strength of both the inherited and the new facet classes in computational experiments on random as well as real-world problem instances. It turns out that in many cases we can close the optimality gap almost completely via cutting planes alone, and, consequently, solution times can be reduced significantly.
Recommendations
Cites work
- A new reformulation-linearization technique for bilinear programming problems
- A new separation algorithm for the Boolean quadric and cut polytopes
- A polyhedral approach for a constrained quadratic 0-1 problem
- A polytope for a product of real linear functions in 0/1 variables
- A relevant two qubit Bell inequality inequivalent to the CHSH inequality
- A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope
- A symmetrical linear maxmin approach to disjoint bilinear programming
- Advances for the pooling problem: modeling, global optimization, and computational studies (Survey)
- Analysis of Preflow Push Algorithms for Maximum Network Flow
- Bell inequalities and entanglement
- Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions
- Cardinality constrained Boolean quadratic polytope
- Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
- Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets
- Correlation polytopes: Their geometry and complexity
- Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions
- Domination analysis of algorithms for bipartite Boolean quadratic programs
- Exploiting special structures in constructing a hierarchy of relaxations for 0-1 mixed integer problems
- Extended formulations for convex hulls of some bilinear functions
- Generating facets for the cut polytope of a graph by triangular elimination
- Geometric proofs for convex hull defining formulations
- Geometry of cuts and metrics
- Global optimization of bilinear programs with a multiparametric disaggregation technique
- scientific article; zbMATH DE number 2107164 (Why is no real title available?)
- Jointly constrained bilinear programs and related problems: An overview
- New classes of facets of the cut polytope and tightness of \(I_{mm22}\) Bell inequalities
- On linear programs with linear complementarity constraints
- On The Boolean Quadric Forest Polytope
- On the Boolean-quadric packing uncapacitated facility-location polytope
- On the cut polytope
- On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study
- polymake: a framework for analyzing convex polytopes
- Relaxations and discretizations for the pooling problem
- Set characterizations and convex extensions for geometric convex-hull proofs
- Solving mixed integer bilinear problems using MILP formulations
- Staircase compatibility and its applications in scheduling and piecewise linearization
- Subset Algebra Lift Operators for 0-1 Integer Programming
- The 0-1 knapsack problem with multiple choice constraints
- The bilinear assignment problem: complexity and polynomially solvable special cases
- The bipartite Boolean quadric polytope
- The bipartite quadratic assignment problem and extensions
- The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases
- The Boolean quadratic polytope: Some characteristics, facets and relatives
- The clique problem with multiple-choice constraints under a cycle-free dependency graph
- The cut polytope and the Boolean quadric polytope
- Two-party Bell inequalities derived from combinatorics via triangular elimination
- Valid Inequalities for the Pooling Problem with Binary Variables
Cited in
(2)
This page was built for publication: The Bipartite Boolean Quadric Polytope with Multiple-Choice Constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6060149)
