Spanning Cover Inequalities for the Capacitated Vehicle Routing Problem
In the k-Minimum Spanning Subgraph problem with d-Degree Center we want to find a minimum cost spanning connected subgraph with n - 1 + k edges and at least degree d in the center vertex, with n being the number of vertices. In this paper we describe an algorithm for this problem and present correctness demonstrations which we believe are simpler than those found in the literature. A solution for the k-Minimum Spanning Subgraph problem with d-Degree can be used to formulate spanning cover inequalities for the capacitated vehicle routing problem.
Christofides, N., Mingozzi, A., and Toth, P. (1981). Exact algorithms for the vehiclerouting problem, based on spanning tree and shortest path relaxations. Mathematical programming, 20(1):255–282.
Fisher, M. L. (1994). Optimal solution of vehicle routing problems using minimum k-trees. Operations research, 42(4):626–642.
Wolsey, L. A. (1975). Faces for a linear inequality in 0–1 variables. Mathematical Pro-gramming, 8(1):165–178.