Column selection by machine learning in exact branch-and-price algorithms
Guy Desaulniers  1, *@  , Mouad Morabit  1@  , Andrea Lodi  2@  
1 : Polytechnique Montreal and GERAD
2 : Polytechnique Montreal, GERAD, CERC in Data science for real-time decision making
* : Corresponding author

Branch-and-price is the leading solution methodology for several classes of vehicle routing and crew scheduling problems. For certain problems where the restricted master problem (RMP) consumes a large proportion of the total computational time, it is important to add a limited number of columns to the RMP at each iteration. These columns are usually selected based on their reduced cost. In this paper, we propose a new selection procedure that relies on a machine learning tool which relies on a graph convolutional network. This tool tries to identify the generated columns that would take a positive value in the solution to the RMP if all columns were added. The columns identified as such are added to the RMP, together with a small subset of the remaining ones. Preliminary tests on some vehicle and crew scheduling problems show that speedups of up to 40% of the computational time can be achieved.

Online user: 1 RSS Feed