Polyhedra

Branch-and-cut for the k-way equipartition problem

  • John E. Mitchell
    • Categories Cutting Plane Approaches, Polyhedra Tags , , , ,

    We investigate the polyhedral structure of a formulation of the k-way equipartition problem and a branch-and-cut algorithm for the problem. The k-way equipartition problem requires dividing the vertices of a weighted graph into k equally sized sets, so as to minimize the total weight of edges that have both endpoints in the same set. Applications … Read more

    Stable Multi-Sets

  • Arie M.C.A. Koster
  • Adrian Zymolka
    • Categories Graphs and Matroids, Polyhedra Tags ,

    In this paper we introduce a generalization of stable sets: stable multi-sets. A stable multi-set is an assignment of integers to the vertices of a graph, such that specified bounds on vertices and edges are not exceeded. In case all vertex and edge bounds equal one, stable multi-sets are equivalent to stable sets. For the … Read more