Paper Info
Title
The k-Cardinality Tree Problem: Reformulations and Lagrangian Relaxation
Abstract
Given an undirected defining graph for the k-Cardinality Tree Problem (KCTP), an associated directed graph involving two additional vertices is introduced in this paper and gives rise to two compact reformulations of the problem. For the first one, connectivity of feasible solutions is enforced through multicommodity flows while, for the other, lifted Miller-Tucker-Zemlin constraints are used. Comparing the two reformulations, much stronger Linear Programming relaxation bounds are obtained from the first one, albeit at much higher CPU times. However, a Branch-and-Bound algorithm based on the second reformulation proved much more effective and managed to obtain, for the first time, optimality certificates for a large number of KCTP instances from the literature. Additionally, for some instances where optimality could not be proven within the given pre-specified CPU time limit, new best upper bounds were generated. Finally, a Lagrangian heuristic based on the first reformulation was also implemented and proved capable of generating feasible KCTP solutions comparable in quality with the best overall results obtained by metaheuristic based heuristics found in the literature. For our test cases, Lagrangian upper bounds are no more than 3.8% away from the best upper bounds known. Additionally, several new best upper bounds and optimality certificates were obtained by the heuristic. Corresponding Lagrangian heuristic CPU times, however, are typically higher than those associated with their competitors.
Year
DOI
Venue
2010
10.1016/j.dam.2009.01.017
Discrete Applied Mathematics
Keywords
Field
DocType
k-cardinality tree problem,lagrangian heuristic cpu time,cpu time limit,kctp instance,lagrangian relaxation,lagrangian heuristic,optimality certificate,new best upper bound,upper bound,feasible kctp solution,cpu time,integer programming,lagrangian upper bound,k -cardinality tree problem,linear programming relaxation,multicommodity flow,branch and bound algorithm,directed graph,k
Discrete mathematics,Mathematical optimization,Heuristic,Combinatorics,Upper and lower bounds,CPU time,Directed graph,Linear programming,Lagrangian relaxation,Connectivity,Linear programming relaxation,Mathematics
Journal
Volume
Issue
ISSN
158
12
Discrete Applied Mathematics
Citations 
PageRank 
References 
5
0.49
24
Authors
4
Name
Order
Citations
PageRank
Frederico P. Quintão180.97
Alexandre Salles da Cunha224222.32
Geraldo R. Mateus313413.00
Abilio Lucena436234.05