THE BIPARTITE BOOLEAN QUADRIC POLYTOPE WITH MULTIPLE-CHOICE CONSTRAINTS

Bärmann A, Martin A, Schneider O (2023)


Publication Type: Journal article

Publication year: 2023

Journal

Book Volume: 33

Pages Range: 2909-2934

Journal Issue: 4

DOI: 10.1137/22M147579X

Abstract

We consider the bipartite boolean quadric polytope (BQP) with multiple-choice constraints and analyze 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 for a pooling application stemming from tea production, using real-world problem data. It turns out that in many cases solution times can be reduced significantly.

Authors with CRIS profile

Involved external institutions

How to cite

APA:

Bärmann, A., Martin, A., & Schneider, O. (2023). THE BIPARTITE BOOLEAN QUADRIC POLYTOPE WITH MULTIPLE-CHOICE CONSTRAINTS. SIAM Journal on Optimization, 33(4), 2909-2934. https://doi.org/10.1137/22M147579X

MLA:

Bärmann, Andreas, Alexander Martin, and Oskar Schneider. "THE BIPARTITE BOOLEAN QUADRIC POLYTOPE WITH MULTIPLE-CHOICE CONSTRAINTS." SIAM Journal on Optimization 33.4 (2023): 2909-2934.

BibTeX: Download