linear programming – Identifying essential degree constraints for ILP formulations of combinatorial optimal graph problems

Many combinatorial graph problems impose degree constraints on vertices; e.g. that the degree of every vertex in the solution to the TSP must be 2.

In all LP-formulations I have encountered so far, these constraints were formulated as an equality constraint for every vertex, which I think may not be the most conservative way of imposing those constraints:

If we take the TSP for example, one might identify the need for imposing degree constraints by calculating the optimal solution to the same instance without any degree contraints which would yield the optimal 1-tree if all other constraints, i.e. integrality, connectivity and cardinality of the solution, were left intact.
If the optimal solution to that relaxed problem doesn’t resemble a Hamiltonian cycle, there will be “defective” vertices of degree 1, leading to the following exemplary


defining $n-#2$ as the topological “distance” of a connected graph with $n$ vertices and edges , when $#2$ denotes the vertices of degree $2$,
what can be said about the relation of topological distances of the optimal solution to the TSP instance

  • with all constraints except any degree constraints activated vs
  • with all constraints with the degree constraints only for vertices that are of degree 1 in the MST.

In the question the MST rather than the optimal 1-tree was chosen for identifying degree defective vertices because of purely practical considerations and to hint that the optimal 1-tree shouldn’t be calculated via a linear program; adding to the MST the shortest edge that isn’t in it is much more efficient.

The degree constraints for the leaf nodes of the MST can also be reformulated to: for every leaf node in the MST there must be at least one edge in solution to the degree-relaxed TSP that is adjacent to that leaf node but not an MST edge.

I didn’t ask for the impact on the performance of TSP algorithms if the degree constraints are added lazily for vertices of degree 1 as they show up, but it seems worth investigating the effects.
Other combinatorial problems where that lazy installation of degree constraints to vertices of degree 1 may be beneficial, are of course the undirected and directed vertex-disjoint cycle cover.

The key idea of the subject of this question is to decide to impose degree constraints only vertices with a degree defect in the case of minimization proplems and only for vertices with a degree surplus in the case of maximization problems.