5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ In the case that the line segments are of length zero, doesn't this reduce to the typical traveling salesman problem? Or is that not an issue? $\endgroup$ – Bill Bradley Dec 17 '14 at 19:04
  • $\begingroup$ @BillBradley yes, it does. But I don't understand how this would be an issue? $\endgroup$ – Xoph Dec 17 '14 at 20:21
  • $\begingroup$ So, you're not concerned that your problem is NP-hard; you just want an algorithm that will do the best it can and is fast in practice? How big is $n$? And are approximately optimal solutions useful? $\endgroup$ – Bill Bradley Dec 17 '14 at 21:30
  • 1
    $\begingroup$ Your informal description of the problem seems to imply that the given line segments should be part of the resulting path while the mathematical description states that only one vertex of each given line segment is used. Can you clarify this? $\endgroup$ – J. Fabian Meier Dec 18 '14 at 9:24
  • 1
    $\begingroup$ @J.FabianMeier The vertices do not represent the endpoints of the line segments. Rather each of the two vertices stands for traversing the line segment in one of the two possible directions. $\endgroup$ – Xoph Dec 18 '14 at 14:13
2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ This is actually a great solution. Alas I need an asymmetric TSP that violates the triangle inequality, so there are no polynomial time approximations available. Still this is a very nice way to approach it! $\endgroup$ – Xoph Dec 24 '14 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.