Limited memory Rank-1 Cuts for Vehicle Routing Problems

作者：Pecin Diego^*; Pessoa Artur; Poggi Marcus; Uchoa Eduardo; Santos Haroldo

来源：Operations Research Letters, 2017, 45(3): 206-209.

DOI：10.1016/j.or1.2017.02.006

• Set Partitioning
• Polyhedral combinatorics
• Branch-cut-and-price algorithms

Pecin et al. (2016) introduced a "limited memory" technique that allows an efficient use of Rank-1 cuts in the Set Partitioning Formulation of Vehicle Routing Problems, motivating a deeper investigation of those cuts. This work presents a computational polyhedral study that determines the best possible sets of multipliers for cuts with up to 5 rows. Experiments with CVRP instances show that the new multipliers lead to significantly improved dual bounds and contributes decisively for solving an open instance with 420 customers.

• 出版日期2017-5