In this thesis, exact and heuristic methods for solving the k-node minimum label spanning arborescence (k-MLSA) problem are developed. The k-MLSA problem is a combination of the minimum label spanning tree problem and the k-cardinality tree problem, which are both NP-complete. Given a complete, directed graph in which one or more labels are associated with each arc, the goal is to derive a minimum cardinality subset of labels such that their corresponding arcs contain a directed tree connecting at least k nodes of the graph. The problem arises in the context of a data-compression model, which has been developed as part of a project at the Institute of Computer Graphics and Algorithms (Vienna University of Technology). In addition to exact and heuristic methods for solving the k-MLSA problem, this thesis contributes a new preprocessing algorithm for constructing the initial labels. The heuristic method is a memetic algorithm (MA), i.e. a combination of a genetic algorithm with local search methods, which are used to further improve candidate solutions derived by the evolutionary operators. The exact algorithm is based on mathematical programming. It solves the underlying integer programming formulation by combining branch-and-cut with column generation in a branch-and-cut-and-price (BCP) approach. In this approach, new (label) variables and constraints are added dynamically to an incomplete initial model during the branch-and-bound process. The new variables are generated by solving the pricing problem, which is based on the values of the dual variables of the current solution. Hence, the label variables no longer need to be constructed in a preprocessing step. As the pricing problem needs to be solved frequently as part of the overall BCP process, efficient algorithms are required. For this purpose, a method based on non-dominated interval search is proposed. It provides an efficient solution to the pricing problem as well as to the preprocessing step.
The BCP approach proposed in this thesis can solve larger instances than previously developed branch-and-cut and branch-and-price algorithms.
However, for practical applications, the MA is more appropriate as it is able to find near-optimal solutions for larger instances within short running times. The new preprocessing method significantly reduces computational complexity compared to the previous method, which has been the bottleneck in the overall procedure.