홈 › Papers

Neural Column Generation for Capacitated Vehicle Routing

The column generation technique is essential for solving linear programs with an exponential number of variables. Many important applications such as the vehicle routing problem (VRP) now require it. However, in practice, getting column generation to converge is challenging. It often ends up adding too many columns. In this work, we frame the problem of selecting which columns to add as one of sequential decision-making. We propose a neural column generation architecture that iteratively selects columns to be added to the problem. The architecture, inspired by stabilization techniques, first predicts the optimal duals. These predictions are then used to obtain the columns to add. We show using VRP instances that in this setting several machine learning models yield good performance on the task and that our proposed architecture learned using imitation learning outperforms a modern stabilization technique.

Code (0)

등록된 구현이 없습니다.

Tasks

Similar Papers 제목 키워드 기반