Separation Algorithm for Tree Partitioning Inequalities

Sunil Chopra, Kangbok Lee*, Minseok Ryu, Sangho Shim

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


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 languageEnglish (US)
Pages (from-to)109-116
Number of pages8
JournalElectronic Notes in Discrete Mathematics
StatePublished - Jun 1 2016


  • Integer programming
  • Separation algorithm
  • Tree partitioning
  • Valid inequality

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Separation Algorithm for Tree Partitioning Inequalities'. Together they form a unique fingerprint.

Cite this