An extended formulation of the convex recoloring problem on a tree

Abstract

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.