[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

An extended formulation of the convex recoloring problem on a tree

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Notes

  1. Thanks to one of the referees, we identified that Wang, Buchanan and Butenko [23] have independently proved a similar result. They showed that all inequalities in (20) are dominated by inequalities (6) and (7).

References

  1. Bar-Yehuda, R., Feldman, I., Rawitz, D.: Improved approximation algorithm for convex recoloring of trees. Theory Comput. Syst. 43, 3–18 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  2. Campêlo, M., Huiban, C.G., Sampaio, R.M., Wakabayashi, Y.: On the complexity of solving or approximating convex recoloring problems. Lect. Notes Comput. Sci. 7936, 614–625 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  3. Campêlo, M., Lima, K.R., Moura, P., Wakabayashi, Y.: Polyhedral studies on the CR problem. Electron. Notes Discret. Math. 44, 233–238 (2013)

    Article  Google Scholar 

  4. Campêlo, M., Freire, A.S., Lima, K.R., Moura, P., Wakabayashi, Y.: The convex recoloring problem: polyhedra, facets and computational experiments. Math. Progr. 156, 303–330 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  5. Chopra, S., Owen, J.L.: Extended formulations for the A-cut problem. Math. Progr. 73, 7–30 (1996)

    MathSciNet  MATH  Google Scholar 

  6. Chopra, S., Rao, M.R.: The partition problem. Math. Progr. 59, 87–115 (1993)

    Article  Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  8. Conforti, M., Kaibel, V., Walter, M., Weltge, S.: Subgraph polytopes and independence polytopes of count matroids. Oper. Res. Lett. 43, 457–460 (2015)

    Article  MathSciNet  Google Scholar 

  9. Conforti, M., Cornuéjols, G., Zambelli, G.: Extended formulations in combinatorial optimization. 4OR 8, 1–48 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  10. Goemans, M.X.: The Steiner tree polytope and related polyhedra. Math. Progr. 63, 157–182 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  11. Kaibel, V.: Extended Formulations in Combinatorial Optimization, arXiv:1104.1023v1 [math.CO] 6 Apr (2011), manuscript

  12. Kammer, F., Tholey, T.: The complexity of minimum convex coloring. Discret. Appl. Math. 160, 810–833 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  13. Kanj, I.A., Kratsch, D.: Convex recoloring revisited: complexity and exact algorithms. Lect. Notes Comput. Sci. 5609, 388–397 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  14. Korte, B., Lovász, L., Schrader, R.: Greedoids, Algorithms and Combinatorics, vol. 4. Springer, Berlin (1991)

    MATH  Google Scholar 

  15. Lima, K.R., Wakabayashi, Y.: Convex recoloring of paths. Discret. Appl. Math. 164, 450–459 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  16. Moran, S., Snir, S.: Convex recolorings of strings and trees: definitions, hardness results and algorithms, In: Proceedings WADS 2005: 9th International Workshop on Algorithms and Data Structures, pp. 218–232 (2005)

  17. Moran, S., Snir, S.: Efficient approximation of convex recolorings. J. Comput. Syst. Sci. 73, 1078–1089 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  18. Moran, S., Snir, S.: Convex recolorings of strings and trees: definitions, hardness results and algorithms. J. Comput. Syst. Sci. 74, 850–869 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  19. Moran, S., Snir, S., Sung, W.K.: Partial convex recolorings of trees and galled networks: tight upper and lower bounds. ACM Trans. Algorithms 7, 42 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  20. Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley-Interscience, New York (1988)

    Book  MATH  Google Scholar 

  21. Ponta, O., Hüffner, F., Niedermeier, R.: Speeding up dynamic programming for some NP-hard graph recoloring problems, In: Proceedings of the 5th International Conference on Theory and Applications of Models of Computation, TAMC08, pp. 490–501. Springer (2008)

  22. Vanderbeck, F., Wolsey, L.A.: Reformulation and decomposition of integer programs. In: Michael Jünger, T., Liebling, D.N., George, N., William, P., Gerhard, R., Giovanni, R., Laurence, W. (eds.) Fifty Years of Integer Programming 1958–2008, pp. 431–502. Springer, Berlin (2010)

  23. Wang, Y., Buchanan, A., Butenko, S.: On Imposing Connectivity Constraints in Integer Programs. www.optimization-online.org/DB_HTML/2015/02/4768.html

Download references

Acknowledgements

We thank Professor Yoshiko Wakabayashi and the other authors of [4] for sharing their data. We are of course grateful for their paper that inspired our work. Mathieu Van Vyve and Bartosz Filipecki were supported by the Interuniversity Attraction Poles Programme P7/36 COMEX of the Belgian Science Policy Office and the Marie Curie ITN “MINO” from the European Commission.

Author information

Authors and Affiliations

  1. Kellogg School of Management, Northwestern University, Evanston, IL, 60208, USA

    Sunil Chopra

  2. Center for Operations Research and Econometric, Université catholique de Louvain, Louvain, Belgium

    Bartosz Filipecki & Mathieu Van Vyve

  3. Department of Industrial and Management Engineering, Pohang University of Science and Technology, Pohang, Republic of Korea

    Kangbok Lee

  4. Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI, 48109, USA

    Minseok Ryu

  5. Department of Engineering, Robert Morris University, Moon Twp, PA, 15108, USA

    Sangho Shim

Authors
  1. Sunil Chopra
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bartosz Filipecki
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Kangbok Lee
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Minseok Ryu
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Sangho Shim
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Mathieu Van Vyve
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sangho Shim.

Electronic supplementary material

Below is the link to the electronic supplementary material.

Supplementary material 1 (pdf 222 KB)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chopra, S., Filipecki, B., Lee, K. et al. An extended formulation of the convex recoloring problem on a tree. Math. Program. 165, 529–548 (2017). https://doi.org/10.1007/s10107-016-1094-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-016-1094-3

Mathematics Subject Classification

Search

Navigation