Polyhedral combinatorics of the K-partitioning problem with representative variables

Zacharie Alès, Arnaud Knippel, Alexandre PauchetDiscret. Appl. Math 2016 · OpenReview

Abstract

The K<math><mi is="true">K</mi></math>-partitioning problem consists in partitioning the vertices of a weighted graph in K<math><mi is="true">K</mi></math> sets in order to minimize a function related to the edge weights. We introduce a linear mixed integer formulation with edge variables and representative variables. We investigate the polyhedral combinatorics of the problem, study several families of facet-defining inequalities and evaluate their efficiency on the linear relaxation.
BibTeX
@inproceedings{ales2016polyhedral,
  author = {Zacharie Alès and Arnaud Knippel and Alexandre Pauchet},
  title = {{Polyhedral combinatorics of the K-partitioning problem with representative variables}},
  booktitle = {Discret. Appl. Math},
  year = {2016},
  url = {https://openreview.net/forum?id=NDtbx8CdGm},
}

Loading related content...

Figure