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

Zacharie Ales
, Arnaud Knippel

LITIS - Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes
INSA Rouen Normandie

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

7 Citations (Scopus)

Résumé

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.

langue originale	Anglais
Pages (de - à)	333-342
Nombre de pages	10
journal	Electronic Notes in Discrete Mathematics
Volume	52
Les DOIs	https://doi.org/10.1016/j.endm.2016.03.044
état	Publié - 1 juin 2016
Modification externe	Oui

Accès au document

10.1016/j.endm.2016.03.044

Contient cette citation

@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",

publisher = "Elsevier B.V.",

}

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

Résumé

Accès au document

Empreinte digitale

Contient cette citation