Recommended Article

Newest Articles

Phase Transitions of Traveling Salesperson Problems solved with Linear Programming and Cutting Planes

In this Article, we introduce an ensemble of the Traveling Salesperson problem (TSP) that can be tuned with a parameter \(\sigma\) from the trivial case of cities equidistant on a circle to the random Euclidean TSP in a plane. For this ensemble we determine some phase transitions from an “easy” phase to a “not-that-easy” phase using linear programming. For each of these transitions we present structural properties of the optimal solution, which change at these points characteristically. Since the optimal solution is independent of the solution method, those phase transitions are not only relevant for the specific linear program respectively the solver implementation used to solve them, but a fundamental property of this TSP ensemble.

We used the classical linear program of Dantzig:

\begin{align} \label{eq:objective} &\text{minimize} & \sum_i \sum_{j<i} c_{ij} x_{ij}\\ \label{eq:int} &\text{subject to} & x_{ij} &\in \{0,1\}\\ %\mathbb{Z}\\ \label{eq:inout} & & \sum_{j} x_{ij} &= 2& & \forall i \in V \\ \label{eq:sec} & & \sum_{i \in S, j \notin S} x_{ij} &\ge 2& & \forall S \varsubsetneq V, S \ne \varnothing \end{align}

As the order parameter of the transitions we use the probability that a simplex solver yields an integer, and therefore optimal, solution. Without the last contraint \eqref{eq:sec}, the “Subtour Elimination Constraints”, the transition occurs at the point at which the optimal solution deviates from the order of the cities on the initial circle. With the “Subtour Elimination Constraints” the transition coincides with the point at which the optimal tour changes from a zig-zag course to larger meandering arcs. This is measured by the tortuosity

\begin{align*} \tau = \frac{n-1}{L} \sum_{i=1}^{n} \left( \frac{L_i}{S_i}-1 \right). \end{align*}

which is maximal at this point. For the tortuosity the tour is divided in \(N\) parts of same-sign-curvature. For each part the ratio of the direct end-to-end distance \(S_i\) to the length along the arc \(L_i\) is summed.

relay ssh

Connect via a server relay with target. Useful if target is behind a firewall, but reachable from relay.

ssh -J user1@relay user2@target

This can be combined with other options. This way a port forwarding can be established over which, e.g., sshfs can be used.

ssh -L 9999:localhost:22 -J user1@relay user2@target
sshfs user2@localhost:/path /mountpoint -C -p 9999

latexdiff

Visualize the differences between two Latex files.

latexdiff old.tex new.tex > diff.tex
pdflatex diff.tex