Separation Algorithm for Tree Partitioning Inequalities

详细信息    查看全文

• 作者：Sunil Chopra^a ; Kangbok Lee^b ; ^{klee5@york.cuny.edu" class="auth_mail" title="E-mail the corresponding author} ; Minseok Ryu^c ; Sangho Shim^d
• 关键词：tree partitioning ; integer programming ; valid inequality ; separation algorithm
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2016
• 出版时间：June 2016
• 年：2016
• 卷：52
• 期：Complete
• 页码：109-116
• 全文大小：208 K

文摘

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.