TSP examples showing how to use separation. The first set of codes solve the subtour elimination linear program ("subtour LP"). The latter codes solve the "full" TSP using callback functions where violated inequalities are added on-the-fly.
First is a multi-commodity flow (MCF) code that doesn't use separation, but is useful for debugging purposes.
Second is a CUT model that uses inequalities of the form x(S,V\S) >= 1. Separating these inequalities reduces to a min cut problem which we solve via NetworkX. We adopt a cutting plane approach in which the LP relaxation is solved, a violated cut constraint is added, then repeat until there are no more violated inequalities.
Third is a Dantzig-Fulkerson-Johnson (DFJ) model that uses inequalities of the form x(E(S)) <= |S|-1. Separating these inequalities also reduces to a min cut problem.
The fourth and fifth codes exploit situations where the support graph (of the LP solution) is disconnected. Whenever this is the case, we can easily find an inequality whose violation is one. Only when the support graph is connected does it resort to solving min cut problems.
Again, we have an MCF code that doesn't use separation, but is useful for debugging purposes.
Next are codes that separate integer solutions x, including CUT and DFJ models. Because x is assumed to be integer, the separation problem reduces to finding connected components.
Then we have codes that separate (possibly) fractional solutions x, including CUT and DFJ codes that solve a min cut problem in each callback.
Finally, we have CUT and DFJ codes that exploit situations where the support graph is disconnected and violated inequalities are easy to find. Min cut problems are solved only as a last resort.
When the costs are symmetric, we can work with an undirected graph and compute min cuts using a Gomory-Hu tree.
There are also some 'hybrid' codes that choose whether to add DFJ or CUT constraints depending on which has fewer nonzeros.