Set characterizations and convex extensions for geometric convex-hull proofs

DOI10.1007/S10107-021-01705-3zbMATH Open1504.90202OpenAlexW3199794724WikidataQ113904813 ScholiaQ113904813MaRDI QIDQ2089779FDOQ2089779

Authors Andreas Bärmann, Oskar Schneider

Publication date 24 October 2022

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

Full work available at URL https://arxiv.org/abs/2101.09267

zbMATH Keywords

integer polytopesconvex-hull proofsproof-by-picture methodset characterizationsZuckerberg's method

Mathematics Subject Classification ID

Convex programming (90C25) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Integer programming (90C10) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05)

Abstract: In the present work, we consider Zuckerberg's method for geometric convex-hull proofs introduced in [Geometric proofs for convex hull defining formulations, Operations Research Letters 44(5), 625-629 (2016)]. It has only been scarcely adopted in the literature so far, despite the great flexibility in designing algorithmic proofs for the completeness of polyhedral descriptions that it offers. We suspect that this is partly due to the rather heavy algebraic framework its original statement entails. This is why we present a much more lightweight and accessible approach to Zuckerberg's proof technique, building on ideas from [Extended formulations for convex hulls of some bilinear functions, Discrete Optimization 36, 100569 (2020)]. We introduce the concept of set characterizations to replace the set-theoretic expressions needed in the original version and to facilitate the construction of algorithmic proof schemes. Along with this, we develop several different strategies to conduct Zuckerberg-type convex-hull proofs. Very importantly, we also show that our concept allows for a significant extension of Zuckerberg's proof technique. While the original method was only applicable to 0/1-polytopes, our extended framework allows to treat arbitrary polyhedra and even general convex sets. We demonstrate this increase in expressive power by characterizing the convex hull of Boolean and bilinear functions over polytopal domains. All results are illustrated with indicative examples to underline the practical usefulness and wide applicability of our framework.

Recommendations

• Extended formulations for convex hulls of some bilinear functions
• Geometric proofs for convex hull defining formulations
• Convex hulls of algebraic sets
• Strengthening convex relaxations of 0/1-sets using Boolean formulas
• Deriving convex hulls through lifting and projection

Cites work

• scientific article; zbMATH DE number 3121293 (Why is no real title available?)
• scientific article; zbMATH DE number 3568353 (Why is no real title available?)
• Alternating orientation and alternating colouration of perfect graphs
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Extended formulations for convex hulls of some bilinear functions
• Geometric proofs for convex hull defining formulations
• Incidence matrices and interval graphs
• Locally ideal formulations for piecewise linear functions with indicator variables
• On the stable set polytope of a series-parallel graph
• Production Planning by Mixed Integer Programming
• Staircase compatibility and its applications in scheduling and piecewise linearization
• Subset Algebra Lift Operators for 0-1 Integer Programming
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• The clique problem with multiple-choice constraints under a cycle-free dependency graph
• The strong perfect graph theorem

Cited in

(3)

• The Bipartite Boolean Quadric Polytope with Multiple-Choice Constraints
• Extended formulations for convex hulls of some bilinear functions
• scientific article; zbMATH DE number 2156778 (Why is no real title available?)

This page was built for publication: Set characterizations and convex extensions for geometric convex-hull proofs

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