Polyhedral results and a Branch-and-cut algorithm for the k-cardinality tree problem |
| |
Authors: | Luidi Simonetti Alexandre Salles da Cunha Abilio Lucena |
| |
Institution: | 1. Instituto de Computa??o, Universidade Federal Fluminense, Rio de Janeiro, Brazil 2. Departamento de Ciência da Computa??o, Universidade Federal de Minas Gerais, Belo Horizonte, Brazil 3. Departamento de Administra??o/Programa de Engenharia de Sistemas e Computa??o, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil
|
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|