An extended formulation of the convex recoloring problem on a tree

• 成果类型: Article
• 署名作者: Chopra, Sunil; Filipecki, Bartosz; Lee, Kangbok; Ryu, Minseok; Shim, Sangho; Van Vyve, Mathieu
• 署名单位: Northwestern University; Universite Catholique Louvain; Pohang University of Science & Technology (POSTECH); University of Michigan System; University of Michigan; Robert Morris University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1094-3
• 发表日期: 2017
• 页码: 529-548
• 关键词: algorithms; approximation; complexity; polyhedra

摘要

We introduce a strong extended formulation of the convex recoloring problem on a tree, which has an application in analyzing phylogenetic trees. The extended formulation has only a polynomial number of constraints, but dominates the conventional formulation and the exponentially many valid inequalities introduced by Camplo et al. (Math Progr 156:303-330, 2016). We show that all valid inequalities introduced by Camplo et al. can be derived from the extended formulation. We also show that the natural restriction of the extended formulation provides a complete inequality description of the polytope of subtrees of a tree. The solution time using the extended formulation is much smaller than that with the conventional formulation. Moreover the extended formulation solves all the problem instances attempted in Camplo et al. (2016) and larger sized instances at the root node of the branch-and-bound tree without branching.