2020/04/11 by Naveed Haghani, Haghani, Naveed, Claudio Contardo +3 · 1 citation
Business, Management and Accounting · Engineering · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Facility Location and Emergency Management #Optimization and Packing Problems #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2004.05499
openalex publication_date 2020/04/11 · openalex created_date 2020/04/17 · openalex updated_date 2026/07/28
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.