Resource-robust valid inequalities for set covering and set partitioning models

For a variety of routing and scheduling problems in aviation, shipping, rail, and road transportation, the state-of-the-art solution approach is to model the prob- lem as a set covering type problem and to use a branch-price-and-cut algorithm to solve it. The pricing problem typically takes the form of a Shortest Path Problem with Resource Constraints (SPPRC). In this context, valid inequalities are known to be `robust' if adding them does not complicate the pricing problem, and `non- robust' otherwise. In this paper, we introduce `resource-robust' as a new category of valid inequalities between robust and non-robust that can still be incorporated without changing the structure of the pricing problem, but only if the SPPRC includes specic resources. Elementarity-robust and ng-robust are introduced as widely applicable special cases that rely on the resources that ensure elementary routes and ng-routes, respectively, and practical considerations are discussed. The use of resource-robust valid inequalities is demonstrated with an application to the Capacitated Vehicle Routing Problem. Computational experiments show that re- placing robust valid inequalities by ng-robust valid inequalities may result in better lower bounds, a reduction in the number of nodes in the search tree, and a decrease in solution time.