Separation Algorithm for Tree Partitioning Inequalities

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

*Corresponding author for this work

Research output: Contribution to journalArticle

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

Keywords

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

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

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

  • Cite this