Integer Linear Programming models are presented for two generalizations of the well know Minimum Spanning Tree Problem: the "Cost Constrained Minimum Label Spanning Tree Problem" and the "Label Constrained Minimum Spanning Tree Problem". The two considered problems are NP-Hard. Metaheuristic algorithms are proposed for their solution. Computational results on benchmark instances from the literature show the effectiveness of the proposed approaches.