(Submitted on 11 Apr 2020)

Abstract: We address the problem of accelerating column generation for set cover
problems in which we relax the state space of the columns to do efficient
pricing. We achieve this by adapting the recently introduced smooth and
flexible dual optimal inequalities (DOI) for use with relaxed columns. Smooth
DOI exploit the observation that similar items are nearly fungible, and hence
should be associated with similarly valued dual variables. Flexible DOI exploit
the observation that the change in cost of a column induced by removing an item
can be bounded. We adapt these DOI to the problem of capacitated vehicle
routing in the context of ng-route relaxations. We demonstrate significant
speed ups on a benchmark data set, while provably not weakening the relaxation.