User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

An extended formulation of the convex recoloring problem on a tree

Primary tabs

Chopra, Sunil Filipecki, Bartosz [UCL] Lee, Kangbok Ryu, Minseok Shim, Sangho Van Vyve, Mathieu [UCL]

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.

Document type Article de périodique (Journal article)
Access type Accès restreint
Publication date 2017
Language Anglais
Journal information "Mathematical Programming" - Vol. 165, p. 529-548 (2017)
Peer reviewed yes
Publisher Springer (Heidelberg)
issn 0025-5610
e-issn 1436-4646
Publication status Publié
Affiliations Louvain School of Management - Operations and Information
Louvain School of Management - Operations and Information
UCL - SSH/LIDAM/CORE - Center for operations research and econometrics
Links
  1. Bar-Yehuda Reuven, Feldman Ido, Rawitz Dror, Improved Approximation Algorithm for Convex Recoloring of Trees, 10.1007/s00224-007-9069-7
  2. Campêlo Manoel B., Huiban Cristiana G., Sampaio Rudini M., Wakabayashi Yoshiko, On the Complexity of Solving or Approximating Convex Recoloring Problems, Lecture Notes in Computer Science (2013) ISBN:9783642387678 p.614-625, 10.1007/978-3-642-38768-5_54
  3. Campêlo Manoel, Lima Karla R., Moura Phablo F.S., Wakabayashi Yoshiko, Polyhedral studies on the convex recoloring problem, 10.1016/j.endm.2013.10.036
  4. Campêlo Manoel, Freire Alexandre S., Lima Karla R., Moura Phablo F. S., Wakabayashi Yoshiko, The convex recoloring problem: polyhedra, facets and computational experiments, 10.1007/s10107-015-0880-7
  5. Chopra, S., Owen, J.L.: Extended formulations for the A-cut problem. Math. Progr. 73, 7–30 (1996)
  6. Chopra Sunil, Rao M. R., The partition problem, 10.1007/bf01581239
  7. Chor, B., Fellows, M., Ragan, M., Razgon, I., Rosamond, F., Snir, S.: Connected coloring completion for general graphs: algorithms and complexity. Lect. Comput. Sci. 4598, 75–85 (2007)
  8. Conforti Michele, Kaibel Volker, Walter Matthias, Weltge Stefan, Subgraph polytopes and independence polytopes of count matroids, 10.1016/j.orl.2015.06.011
  9. Conforti Michele, Cornuéjols Gérard, Zambelli Giacomo, Extended formulations in combinatorial optimization, 10.1007/s10288-010-0122-z
  10. Goemans Michel X., The Steiner tree polytope and related polyhedra, 10.1007/bf01582064
  11. Kaibel, V.: Extended Formulations in Combinatorial Optimization, arXiv:1104.1023v1 [math.CO] 6 Apr (2011), manuscript
  12. Kammer Frank, Tholey Torsten, The complexity of minimum convex coloring, 10.1016/j.dam.2011.09.022
  13. Kanj Iyad A., Kratsch Dieter, Convex Recoloring Revisited: Complexity and Exact Algorithms, Lecture Notes in Computer Science (2009) ISBN:9783642028816 p.388-397, 10.1007/978-3-642-02882-3_39
  14. Korte, B., Lovász, L., Schrader, R.: Greedoids, Algorithms and Combinatorics, vol. 4. Springer, Berlin (1991)
  15. Lima Karla Roberta, Wakabayashi Yoshiko, Convex recoloring of paths, 10.1016/j.dam.2013.02.034
  16. Moran Shlomo, Snir Sagi, Convex Recolorings of Strings and Trees: Definitions, Hardness Results and Algorithms, Lecture Notes in Computer Science (2005) ISBN:9783540281016 p.218-232, 10.1007/11534273_20
  17. Moran Shlomo, Snir Sagi, Efficient approximation of convex recolorings, 10.1016/j.jcss.2007.03.006
  18. Moran Shlomo, Snir Sagi, Convex recolorings of strings and trees: Definitions, hardness results and algorithms, 10.1016/j.jcss.2007.10.003
  19. Moran Shlomo, Snir Sagi, Sung Wing-Kin, Partial convex recolorings of trees and galled networks : Tight upper and lower bounds, 10.1145/2000807.2000810
  20. Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley-Interscience, New York (1988)
  21. Ponta Oriana, Hüffner Falk, Niedermeier Rolf, Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems, Lecture Notes in Computer Science ISBN:9783540792277 p.490-501, 10.1007/978-3-540-79228-4_43
  22. Vanderbeck François, Wolsey Laurence A., Reformulation and Decomposition of Integer Programs, 50 Years of Integer Programming 1958-2008 (2010) ISBN:9783540682745 p.431-502, 10.1007/978-3-540-68279-0_13
  23. Wang, Y., Buchanan, A., Butenko, S.: On Imposing Connectivity Constraints in Integer Programs. www.optimization-online.org/DB_HTML/2015/02/4768.html
Bibliographic reference Chopra, Sunil ; Filipecki, Bartosz ; Lee, Kangbok ; Ryu, Minseok ; Shim, Sangho ; et. al. An extended formulation of the convex recoloring problem on a tree. In: Mathematical Programming, Vol. 165, p. 529-548 (2017)
Permanent URL http://hdl.handle.net/2078/179085