Separation algorithms for tree partitioning inequalities, Electronic notes in discrete mathematics
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.
Sunil Chopra, Sangho Shim
Chopra, Sunil, and Sangho Shim. 2016. Separation algorithms for tree partitioning inequalities. Electronic notes in discrete mathematics. 52: 109-116.