Groupe d’études et de recherche en analyse des décisions


Branch and Cut at the Subproblem Level in a Column Generation Approach: Application to the Airline Industry

, et

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.

, 23 pages