An extended formulation of the convex recoloring problem on a tree

Sunil Chopra, Kangbok Lee, Minseok Ryu, Sangho Shim

Research output: Working paper

Abstract

We introduce a strong extended formulation of the convex recoloring problem on a tree, which has an application in analyzing a phylogenetic tree. The extended formulation has only polynomial number of constraints, but dominates the conventional formulation and the exponentially many valid inequalities introduced by Campêlo et al. (Mathematical Programming, Published Online on March 4). We show that all valid inequalities introduced by Campêlo et al. can be derived from the extended formulation. The extended formulation solves all the problem instances attempted in Campêlo et al. and larger sized instances at the root node of the branch-and-bound tree without branching. The solution time using the extended formulation is much faster.
Original languageEnglish (US)
PublisherResearchGate
StatePublished - Apr 2015

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