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.

1more comment