An extended edge-representative formulation for the K-partitioning problem

Zacharie Ales; Arnaud Knippel

doi:10.1016/j.endm.2016.03.044

An extended edge-representative formulation for the K-partitioning problem

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

Abstract

We introduce an edge-representative formulation for the K-partitioning problem and show how it can be extended to improve its linear relaxation.A branch-and-cut algorithm based on a polyhedral study and a thorough cutting-plane strategy at the root node is described. We illustrate our approach with numerical results on some random hard instances.

Original language	English
Pages (from-to)	333-342
Number of pages	10
Journal	Electronic Notes in Discrete Mathematics
Volume	52
DOIs	https://doi.org/10.1016/j.endm.2016.03.044
Publication status	Published - 1 Jun 2016
Externally published	Yes

Keywords

Branch-and-cut
Combinatorial optimization
Graph partitioning
Polyhedral approach

Access to Document

10.1016/j.endm.2016.03.044

Cite this

@article{81ecd5412794422d894f4cc04324bfa8,

title = "An extended edge-representative formulation for the K-partitioning problem",

abstract = "We introduce an edge-representative formulation for the K-partitioning problem and show how it can be extended to improve its linear relaxation.A branch-and-cut algorithm based on a polyhedral study and a thorough cutting-plane strategy at the root node is described. We illustrate our approach with numerical results on some random hard instances.",

keywords = "Branch-and-cut, Combinatorial optimization, Graph partitioning, Polyhedral approach",

author = "Zacharie Ales and Arnaud Knippel",

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

year = "2016",

month = jun,

day = "1",

doi = "10.1016/j.endm.2016.03.044",

language = "English",

volume = "52",

pages = "333--342",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

}

TY - JOUR

T1 - An extended edge-representative formulation for the K-partitioning problem

AU - Ales, Zacharie

AU - Knippel, Arnaud

PY - 2016/6/1

Y1 - 2016/6/1

N2 - We introduce an edge-representative formulation for the K-partitioning problem and show how it can be extended to improve its linear relaxation.A branch-and-cut algorithm based on a polyhedral study and a thorough cutting-plane strategy at the root node is described. We illustrate our approach with numerical results on some random hard instances.

AB - We introduce an edge-representative formulation for the K-partitioning problem and show how it can be extended to improve its linear relaxation.A branch-and-cut algorithm based on a polyhedral study and a thorough cutting-plane strategy at the root node is described. We illustrate our approach with numerical results on some random hard instances.

KW - Branch-and-cut

KW - Combinatorial optimization

KW - Graph partitioning

KW - Polyhedral approach

U2 - 10.1016/j.endm.2016.03.044

DO - 10.1016/j.endm.2016.03.044

M3 - Article

AN - SCOPUS:84969549312

SN - 1571-0653

VL - 52

SP - 333

EP - 342

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

An extended edge-representative formulation for the K-partitioning problem

Abstract

Keywords

Access to Document

Fingerprint

Cite this