Polyhedral results and a Branch-and-cut algorithm for the $$k$$ -cardinality tree problem
- PDF / 459,614 Bytes
- 28 Pages / 439.37 x 666.142 pts Page_size
- 5 Downloads / 180 Views
Polyhedral results and a Branch-and-cut algorithm for the k-cardinality tree problem Luidi Simonetti · Alexandre Salles da Cunha · Abilio Lucena
Received: 9 November 2011 / Accepted: 17 August 2012 / Published online: 6 September 2012 © Springer and Mathematical Optimization Society 2012
Abstract Given an undirected graph G with vertex and edge weights, the k-cardinality tree problem asks for a minimum weight tree of G containing exactly k edges. In this paper we consider a directed graph reformulation of the problem and carry out a polyhedral investigation of the polytope defined by the convex hull of its feasible integral solutions. Three new families of valid inequalities are identified and two of them are proven to be facet implying for that polytope. Additionally, a Branch-and-cut algorithm that separates the new inequalities is implemented and computationally tested. The results obtained indicate that our algorithm outperforms its counterparts from the literature. Such a performance could be attributed, to a large extent, to the use of the new inequalities and also to some pre-processing tests introduced in this study. Electronic supplementary material The online version of this article (doi:10.1007/s10107-012-0590-3) contains supplementary material, which is available to authorized users. Luidi Simonetti is partially funded by FAPERJ grant E-26/111.819/2010 and CNPq grants 483.243/2010-8, 304793/2011-6. Alexandre Salles da Cunha is partially funded by CNPq grants 302276/2009-2, 477863/2010-8 and FAPEMIG PRONEX APQ-01201-09. Abilio Lucena is partially funded by CNPq grant 310561/2009-4 and FAPERJ grant E26-110.552/2010. L. Simonetti Instituto de Computação, Universidade Federal Fluminense, Rio de Janeiro, Brazil e-mail: [email protected] A. S. da Cunha Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, Belo Horizonte, Brazil e-mail: [email protected] A. Lucena (B) Departamento de Administração/Programa de Engenharia de Sistemas e Computação, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil e-mail: [email protected]
123
512
L. Simonetti et al.
Keywords Branch-and-cut algorithm · Polyhedral study · k-Cardinality tree problem Mathematics Subject Classification
90C27 · 90C35 · 90C57
1 Introduction Assume that an undirected graph G = (V, E) is given with a set V of n vertices and a set E of m edges. Assume as well that vertex weights {di : i ∈ V }, edge weights {we : e ∈ E} and a positive integer 1 ≤ k ≤ n − 1 are also associated with T = (VT , E T ) of G then has a corresponding weight that graph. Any tree and is called k-cardinality whenever |E T | = k. Accordingly, d + w i e i∈VT e∈E T the problem of finding a k-cardinality tree with the least weight is known as the k-cardinality tree problem (KCTP). KCTP was introduced by Fischetti et al. [16] who proved it to be NP-hard whenever 2 ≤ k ≤ n − 2. Polynomial solvable cases of the problem occur when k ∈ {1, n − 1} or when the input graph G is a tree [5]. Whenever k = 1, an optimal solution is implied by an
Data Loading...
