An extended formulation of the convex recoloring problem on a tree
(2017) Mathematical Programming — Vol. 165, p. 529-548 (2017)
Files
document.pdf
Restricted Access - Adobe PDF
- 563.03 KB
Details
- Authors
- Abstract
- We introduce a strong extended formulation of the convex recoloring prob- lem on a tree, which has an application in analyzing phylogenetic trees. The extended formulation has only a polynomial number of constraints, but dominates the con- ventional formulation and the exponentially many valid inequalities introduced by Campêlo et al. (Math Progr 156:303–330, 2016). We show that all valid inequalities introduced by Campêlo et al. can be derived from the extended formulation. Wealso show that the natural restriction of the extended formulation provides a completeinequality description of the polytope of subtrees of a tree. The solution time usingthe extended formulation is much smaller than that with the conventional formulation.Moreover the extended formulation solves all the problem instances attempted in Cam-pêlo et al. (2016) and larger sized instances at the root node of the branch-and-boundtree without branching.
- Affiliations
Louvain School of Management Operations and Information Louvain School of Management Operations and Information
Citations
Chopra, S., Filipecki, B., Lee, K., Ryu, M., Shim, S., & Van Vyve, M. (2017). An extended formulation of the convex recoloring problem on a tree. Mathematical Programming, 165, 529-548. https://doi.org/10.1007/s10107-016-1094-3 (Original work published 2017)