This paper proposes a two-stage process for selecting an optimal starting eleven in football. In the first stage, a LASSO-induced multinomial logistic regression model analyses the probabilities of match outcomes, accounting for player strengths, opponent characteristics, home advantage, and player combinations. In the second stage, a GRASP-type meta-heuristic selects the best team to maximise the probability of winning. Using English Premier League data of eight seasons, we demonstrate the model’s ability in providing valuable insights about team performance and determining the best lineup. Our analysis and case studies also demonstrate how the algorithm can evaluate managerial efficiency of different clubs.