When attempting to set up an ILP formulation for a weight-minimal cubic spanning tree (i.e. one with vertex degrees either 1 or 3) I needed connectivity constraint, but misremembered the contents of this answer to another question I had posed. I thought that the solution was based on degree sums and so played around a bit and arrived at the following iteration:
- $\omega^0(v_i):=0\quad \forall v_i\in V$
- $\omega^1(e_{ij}):=1\quad \forall e_{ij} \in E$
- $\omega^{2k}(v_i)\ =\ \sum_{j}\omega^{2k-1}(e_{ij})$
- $\omega^{2k+1}(e_{ij})\ =\ \omega^{2k}(v_i)+\omega^{2k}(v_j)$
As it turned out, that iteration yields a tour-elimination constraints, that are different from the MTZ constraints but they require a reformulation of TSP problems as optimal Hamilton path problems.
The image shows a worked example with and without a disconnected cycle and, as can be seen, after a certain number of iterations the maximum of the $\omega^{2k+1}(e_{ij})$ of the connected linear graph lags behind the disconnected one that has a cyclic component; the highlighted powers of two make the different behavior more visible:
Caveat:
The number of constraints is bigger than in the MTZ formulation and besides that, the value of the constants factors can depend super-polynomially on the number of iterations.
For those reasons I doubt that my findings are of any relevance for the practical solution of TSP problem instances, even if their size is moderate.
Questions:
has the described graph iteration already been encountered before?
what is the limit behavior of the generated edge weights, i.e. what can be said about the set of edges of non-regular graphs, that (in the limit) generate the maximal values (for regular graphs the answer is of course trivial)?
