Polyhedral combinatorics of the K-partitioning problem with representative variables

Zacharie Ales; Arnaud Knippel; Alexandre Pauchet

doi:10.1016/j.dam.2016.04.002

Polyhedral combinatorics of the K-partitioning problem with representative variables

Zacharie Ales
, Arnaud Knippel
, Alexandre Pauchet

Research output: Contribution to journal › Article › peer-review

Abstract

The K-partitioning problem consists in partitioning the vertices of a weighted graph in K 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.

Original language	English
Pages (from-to)	1-14
Number of pages	14
Journal	Discrete Applied Mathematics
Volume	211
DOIs	https://doi.org/10.1016/j.dam.2016.04.002
Publication status	Published - 1 Oct 2016
Externally published	Yes

Keywords

Combinatorial optimization
Graph partitioning
Polyhedral approach

Access to Document

10.1016/j.dam.2016.04.002

Cite this

@article{2676043a584f4cbc8a878fe3e9ced84f,

title = "Polyhedral combinatorics of the K-partitioning problem with representative variables",

abstract = "The K-partitioning problem consists in partitioning the vertices of a weighted graph in K 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.",

keywords = "Combinatorial optimization, Graph partitioning, Polyhedral approach",

author = "Zacharie Ales and Arnaud Knippel and Alexandre Pauchet",

note = "Publisher Copyright: {\textcopyright} 2016 Elsevier B.V.",

year = "2016",

month = oct,

day = "1",

doi = "10.1016/j.dam.2016.04.002",

language = "English",

volume = "211",

pages = "1--14",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

}

TY - JOUR

T1 - Polyhedral combinatorics of the K-partitioning problem with representative variables

AU - Ales, Zacharie

AU - Knippel, Arnaud

AU - Pauchet, Alexandre

PY - 2016/10/1

Y1 - 2016/10/1

N2 - The K-partitioning problem consists in partitioning the vertices of a weighted graph in K 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.

AB - The K-partitioning problem consists in partitioning the vertices of a weighted graph in K 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.

KW - Combinatorial optimization

KW - Graph partitioning

KW - Polyhedral approach

UR - https://www.scopus.com/pages/publications/84992311288

U2 - 10.1016/j.dam.2016.04.002

DO - 10.1016/j.dam.2016.04.002

M3 - Article

AN - SCOPUS:84992311288

SN - 0166-218X

VL - 211

SP - 1

EP - 14

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Polyhedral combinatorics of the K-partitioning problem with representative variables

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this