The Circuit Polytope: Facets

Given an undirected graph G = (V, E) and a cost vector c ∈ ℝ^E, the weighted girth problem is to find a circuit in G having minimum total cost. This problem is in general 𝒩𝒫-hard.

A promising approach to the solution of hard combinatorial optimization problems is given by the so-called cutting plane methods. These involve linear programming techniques based on a partial description of the convex hull of the incidence vectors of possible solutions.

We consider the weighted girth problem in the case where G is the complete graph K_n and study the facial structure of the circuit polytope P_Cⁿ and some related polyhedra. In the appendix we give complete characterizations of P_Cⁿ for n up to 6.

We were motivated to study the weighted girth problem by the fact that this problem and variations of it appear as a subproblem, namely the pricing problem, in a column generation approach to the vehicle routing problem.