Stabilizing Column Generation via Dual Optimal Inequalities with Applications in Logistics and Robotics

Loading...
Thumbnail Image

Files

Publication or External Link

Date

2020

Citation

Abstract

This work addresses the challenge of stabilizing column generation (CG) via dual optimal inequalities (DOI). We present two novel classes of DOI for the general context of set cover problems. We refer to these as Smooth DOI (S-DOI) and Flexible DOI (F-DOI). S-DOI can be interpreted as allowing for the undercovering of items at the cost of overcovering others and incurring an objective penalty. SDOI leverage the fact that dual values associated with items should change smoothly over space. F-DOI can be interpreted as offering primal objective rewards for the overcovering of items. We combine these DOI to produce a joint class of DOI called Smooth-Flexible DOI (SF-DOI). We apply these DOI to three classical problems in logistics and operations research: the Single Source Capacitated Facility Location Problem, the Capacitated p-Median Problem, and the Capacitated Vehicle Routing Problem. We prove that these DOI are valid and are guaranteed to not alter the optimal solution of CG. We also present techniques for their use in the case of solvingCG with relaxed column restrictions.

This work also introduces a CG approach to Multi-Robot Routing (MRR). MRR considers the problem of routing a fleet of robots in a warehouse to collectively complete a set of tasks while prohibiting collisions. We present two distinct formulations that tackle unique problem variants. The first we model as a set packing problem, while the second we model as a set cover problem. We show that the pricing problem for both approaches amounts to an elementary resource constrained shortest path problem (ERCSPP); an NP-hard problem commonly studied in other CG problem contexts. We present an efficient implementation of our CG approach that radically reduces the state size of the ERCSPP. Finally, we present a novel heuristic algorithm for solving the ERCSPP and offer probabilistic guarantees forits likelihood to deliver the optimal solution.

Notes

Rights