convex-hull description

The polytope of binary sequences with bounded variation

  • Christoph Buchheim
  • Maja Hügging
    • Categories 0-1 Programming, Polyhedra Tags , , ,

    We investigate the problem of optimizing a linear objective function over the set of all binary vectors of length n with bounded variation, where the latter is defined as the number of pairs of consecutive entries with different value. This problem arises naturally in many applications, e.g., in unit commitment problems or when discretizing binary … Read more

    The Bipartite Boolean Quadric Polytope with Multiple-Choice Constraints

  • Andreas Bärmann
  • Alexander Martin
  • Oskar Schneider
    • Categories (Mixed) Integer Nonlinear Programming, Chemical Engineering, Polyhedra Tags , , , ,

    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 … Read more