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.
