Polyhedral results and a Branch-and-cut algorithm for the k-cardinality tree problem

• 成果类型: Article
• 署名作者: Simonetti, Luidi; da Cunha, Alexandre Salles; Lucena, Abilio
• 署名单位: Universidade Federal Fluminense; Universidade Federal de Minas Gerais; Universidade Federal do Rio de Janeiro
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-012-0590-3
• 发表日期: 2013
• 页码: 511-538
• 关键词: steiner problem; search

摘要

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.