Separation algorithms for tree partitioning inequalities
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.
Chopra, Sunil, Sangho Shim and Kangbok Lee. Forthcoming. Separation algorithms for tree partitioning inequalities. Electronic notes in discrete mathematics.