An extended formulation of the convex recoloring problem on a tree
SCIE
SCOPUS
- Title
- An extended formulation of the convex recoloring problem on a tree
- Authors
- SUNIL CHOPRA; BARTOSZ FILIPECKI; LEE, KANGBOK; MINSEOK RYU; SANGHO SHIM; MATHIEU VAN VYV
- Date Issued
- 2017-10
- Publisher
- Springer Berlin Heidelberg
- 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.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/36719
- DOI
- 10.1007/S10107-016-1094-3
- ISSN
- 0025-5610
- Article Type
- Article
- Citation
- Mathematical Programming, vol. 165, no. 2, page. 529 - 548, 2017-10
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.