Separation Algorithm for Tree Partitioning Inequalities

Sunil Chopra; Kangbok Lee; Minseok Ryu; Sangho Shim

doi:10.1016/j.endm.2016.03.015

Separation Algorithm for Tree Partitioning Inequalities

Sunil Chopra
, Kangbok Lee
, Minseok Ryu
, Sangho Shim

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

Abstract

We consider the tree partition problem to partition the node set of a tree into subsets where the induced subgraph by each subset is connected and the total weight of nodes in a subset cannot exceed the capacity of the subset. We identify exponentially many valid inequalities for an integer programming formulation of the problem and develop a linear time separation algorithm for the valid inequalities.

Original language	English (US)
Pages (from-to)	109-116
Number of pages	8
Journal	Electronic Notes in Discrete Mathematics
Volume	52
DOIs	https://doi.org/10.1016/j.endm.2016.03.015
State	Published - Jun 1 2016
Externally published	Yes

Keywords

Integer programming
Separation algorithm
Tree partitioning
Valid inequality

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.endm.2016.03.015

Cite this

@article{52249edcb8e344c3931068e01220990d,

title = "Separation Algorithm for Tree Partitioning Inequalities",

abstract = "We consider the tree partition problem to partition the node set of a tree into subsets where the induced subgraph by each subset is connected and the total weight of nodes in a subset cannot exceed the capacity of the subset. We identify exponentially many valid inequalities for an integer programming formulation of the problem and develop a linear time separation algorithm for the valid inequalities.",

keywords = "Integer programming, Separation algorithm, Tree partitioning, Valid inequality",

author = "Sunil Chopra and Kangbok Lee and Minseok Ryu and Sangho Shim",

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

year = "2016",

month = jun,

day = "1",

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

language = "English (US)",

volume = "52",

pages = "109--116",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier BV",

}

TY - JOUR

T1 - Separation Algorithm for Tree Partitioning Inequalities

AU - Chopra, Sunil

AU - Lee, Kangbok

AU - Ryu, Minseok

AU - Shim, Sangho

PY - 2016/6/1

Y1 - 2016/6/1

N2 - We consider the tree partition problem to partition the node set of a tree into subsets where the induced subgraph by each subset is connected and the total weight of nodes in a subset cannot exceed the capacity of the subset. We identify exponentially many valid inequalities for an integer programming formulation of the problem and develop a linear time separation algorithm for the valid inequalities.

AB - We consider the tree partition problem to partition the node set of a tree into subsets where the induced subgraph by each subset is connected and the total weight of nodes in a subset cannot exceed the capacity of the subset. We identify exponentially many valid inequalities for an integer programming formulation of the problem and develop a linear time separation algorithm for the valid inequalities.

KW - Integer programming

KW - Separation algorithm

KW - Tree partitioning

KW - Valid inequality

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

UR - https://www.scopus.com/pages/publications/84969543330#tab=citedBy

U2 - 10.1016/j.endm.2016.03.015

DO - 10.1016/j.endm.2016.03.015

M3 - Article

SN - 1571-0653

VL - 52

SP - 109

EP - 116

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

Separation Algorithm for Tree Partitioning Inequalities

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this