This paper presents a new branching strategy that is applied on the cost of a subproblem during the solution of a large-scale linear program by a column generation technique. This branch and cut strategy has been used to improve the solution time for the preferential bidding problems encountered in the airline industry. Moreover, it is shown that this strategy can also be applied to other problems with particular structures.