We consider branch and price solution methodologies for optimal aircrew scheduling. Utilizing an optimization model termed master, these methodologies aim to assign a roster to each member of the group under consideration, so that the total system cost is minimized. The master problem is typically formulated as a set-partition optimization model. In order to expedite the identification of the attainable duty coverage, we propose its formulation as a set-cover optimization model instead, in which duty over-coverage is allowed while roster quality is ignored. The resulting set-cover solution is transformed into an equivalent set-partition one through the employment of a mixed integer optimization model which removes overcovered duties from the rosters, so as to optimize roster quality without affecting optimal coverage. We use tests on realistic problem instances for evaluating the proposed methodology.