Suppose you have finitely many line segments in the Euclidean plane. How do you "connect them to form one chain of line segments of minimal length?"
More formally and generally, what I'm looking for is an algorithm to solve the following modification of the TSP.
Suppose you have a digraph $G = (V, A)$ with edge weights and an even number of vertices $V = \{ v_{2i}, v_{2i + 1} : i < n \}$. Find, if it exists, the closed walk $C$ of minimal weight such that for every $i < n$, either $v_{2i} \in C$ or $v_{2i+1} \in C$.
(So in order to solve the above question, one would have two vertices for each line segment, one corresponding to each direction the line segment can be walked along.)
I tried formulating the problem as a mixed integer linear program, but it seems making this program choose between two vertices for each $i < n$ inevitably results in something non-convex.
It seems as if this should be a problem that has been studied before, but I cannot find any references.
Edit: I think the following mixed integer linear program solves the problem, although maybe not as elegantly as one could. It's a modification of the standard way to turn a TSP into a MILP:
Suppose $V = 2n = \{ 0, \ldots, 2n -1 \}$. Let $c_a$ be the weight of an arc $a \in A$. The intended meaning of the variables $x_a$ is that $x_a = 1$ iff the arc $a$ is in the tour. For a vertex $k \in V$, $\delta^-(k)$ and $\delta^+(k)$ denote the set of all incoming or outgoing arcs respectively.
Minimize
$$ \sum_{a \in A} c_a x_a $$
such that:
\begin{eqnarray*}
x_a \in \{0, 1\} &\qquad& \forall a \in A\\
\sum_{a \in \delta^+(2i)} x_a + \sum_{a \in \delta^+(2i + 1)} x_a = 1 &\qquad& \forall i < n\\
\sum_{a \in \delta^-(2i)} x_a + \sum_{a \in \delta^-(2i + 1)} x_a = 1 &\qquad& \forall i < n\\
\sum_{i \in K} \left( \sum_{a \in \delta^+(2i)} x_a + \sum_{a \in \delta^+(2i + 1)} x_a \right) \geq 1 &\qquad& \forall K \subset n\ \text{with}\ K \neq \emptyset, n
\end{eqnarray*}
Now the problem remains that the solution could go into a vertex 2i but exit vertex 2i+1. This is where I thought things would become non-convex. But adding artificial dimensions via helper variables $t_i$ with the intended meaning that $t_i = 0$ if the node $2i$ is picked, and $t_i = 1$ if node $2i + 1$ is picked, we can add as constraints
\begin{eqnarray*}
t_i \in \{ 0, 1 \} &\qquad& \forall i < n\\
\sum_{a \in \delta^+(2i)} x_a + \sum_{a \in \delta^-(2i)} x_a = 2 (1 – t_i) &\qquad& \forall i < n\\
\sum_{a \in \delta^+(2i + 1)} x_a + \sum_{a \in \delta^-(2i + 1)} x_a = 2 t_i &\qquad& \forall i < n
\end{eqnarray*}
I hope this makes sense and apologize if it doesn't, I basically have no background in any form of optimization.
Best Answer
Another way to solve the problem might be to reduce it to a traditional version of the TSP and then use a free, off-the-shelf solver like one of these. At the very least, it should be a relatively easy way of validating that your MILP construction is programmed correctly.
Note that this problem can be described as a TSP problem where the solution must cross certain edges (i.e., the "line segments"). For each "forced" edge in the graph, replace the edge
o-----o
with a new node and two edges in series, like this:
o--o--o
Consider a traditional TSP solution on the new graph. In order to reach the new node, any valid TSP closed walk must cross the entire "o--o--o" structure. Therefore, a minimal closed walk on the new graph corresponds to a minimal closed walk on the original graph that crosses all the desired edges.
There are no constant-time approximations for your general problem (because, with length zero links, the general TSP problem is a special case of your problem). However, there are constant-factor approximation algorithms for metric TSP, and even a PTAS for the TSP in the Euclidean plane (Arora 1998), so it's possible that there might be an approximation algorithm for your "connect the segments in the plane" special case. I spent a while unsuccessfully tinkering with Christofides' algorithm to try to find one for this problem; perhaps someone else might have more luck?