Scientific Program > Talks by Speaker > Desaulniers Guy

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.