A Lagrangian relaxation approach to large-scale flow interception problems