首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号