Maximally Violated Mod-p Cuts for the Capacitated Vehicle-Routing Problem.

This paper makes a contribution to the branch and cut approach to the capacitated vehicle-routing problem (CVRP). In the CVRP, the demands of a set of customers have to be met at minimum total travel cost using vehicles of identical capacity based at a single depot. The potential of maximally violated mod-p cutting-planes (Caprara et al. 2000) for the CVRP is investigated via a computational study. The foundation of the assessment is formed by classes of problem-specific constraints taken from the literature. In several separation algorithms for the CVRP, it is advantageous to shrink inclusionwise maximal minimum-weight cuts in support graphs as preprocessing. It is mentioned how a partition of the set of customers into such mincuts can be computed in a fast and elegant way using the mincut algorithm of Hao and Orlin (1994). Interestingly, maximally violated mod-p cuts, which are general-purpose cuts of Chvátal-Gomory type, stand comparison with problem-specific cuts for the CVRP and they are clearly useful on top of such cuts. The first-time proven optimal solution of the CVRP instance B-n68-k9 is reported. The computation used a branching strategy with far lookahead and relied on maximally violated mod-p cuts. This paper on maximally violated cuts belongs to a set of papers originating from Applegate et al. (1995) where a separation of maximally violated combs for the traveling-salesman problem (TSP) is suggested. [ABSTRACT FROM AUTHOR]