An extended formulation of the convex recoloring problem on a tree

Sunil Chopra, Bartosz Filipecki, Kangbok Lee, Minseok Ryu, Sangho Shim*, Mathieu Van Vyve

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

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 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. 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 Campêlo et al. (2016) and larger sized instances at the root node of the branch-and-bound tree without branching.

Original languageEnglish (US)
Pages (from-to)529-548
Number of pages20
JournalMathematical Programming
Volume165
Issue number2
DOIs
StatePublished - Oct 1 2017

Keywords

  • 90C05 Linear programming
  • 90C10 Integer programming
  • 90C27 Combinatorial optimization
  • 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
  • 92B05 General biology and biomathematics

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'An extended formulation of the convex recoloring problem on a tree'. Together they form a unique fingerprint.

Cite this