6
$\begingroup$

I am looking for an idea on how to formulate the following problem as a MILP. Given a connected graph, find the shortest path route starting from a node (not given) and visit all other nodes. All nodes should be visited at least once.

Some example

Enter image description here

The TSP MTZ formulation can not be used since we might need to revisit a node.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Why might we need to revisit a node? Is the graph non-complete? $\endgroup$
    – PeterD
    Commented Jul 28, 2023 at 8:41
  • $\begingroup$ How can you visit all nodes without visiting some nodes more than once ? $\endgroup$
    – Optimization team
    Commented Jul 28, 2023 at 9:07
  • 1
    $\begingroup$ In the TSP, all nodes are visited exactly once. $\endgroup$
    – PeterD
    Commented Jul 28, 2023 at 10:04
  • $\begingroup$ @Optimizationteam, also the problem is similar to the multi-tsp. $\endgroup$
    – A.Omidi
    Commented Jul 28, 2023 at 13:07
  • $\begingroup$ @Optimizationteam, for connected graphs generally, there is no guarantee that you can visit all nodes exactly once each, but there plenty of graphs, and some categories of graphs, where you can do. For example, complete graphs; or connected graphs in which no vertex has more than two edges. More generally, the set of graphs G containing subgraphs S in which all the nodes of G are nodes of S, S is connected, and no node of S is an endpoint for more than two edges is exactly the set of graphs containing a path that traverses each node exactly once. $\endgroup$
    – John Bollinger
    Commented Jul 28, 2023 at 16:40

2 Answers 2

Reset to default
6
$\begingroup$

My first thought was Rob's model, but for what it's worth here is an alternative formulation that does not require solving a bunch of shortest path problems at the outset. Whether it is faster or not I don't know.

I'm going to write $N$ for the set of nodes and $A$ for the set of directed arcs in the graph (so each line in the examples corresponds to two arcs). I assume that any node can be the start node (which means the path shown for the star graph is actually not optimal -- you can reduce it by one arc if you start anywhere except 1). I'm also going to guess an a priori upper limit $k^*$ on the number of arcs needed to visit every node, and let $K=\lbrace 1,\dots,k^* \rbrace.$ If the guess is too low, the model will be infeasible, requiring another run with a larger guess. Guessing too high does not hurt the model's accuracy but might slow it down.

Variables are as follows:

  • $s_i\in \lbrace 0, 1 \rbrace$ is 1 if node $i\in N$ is the starting node for the path;
  • $x_{i,j,k}\in \lbrace 0, 1 \rbrace$ is 1 if the $k$-th move is from node $i$ to node $j$ (with $x_{i,j,k}$ fixed at 0 whenever $(i,j)\notin A$);
  • $y_{i,k}\ge 0$ will be 1 if the path exits node $i\in N$ at step $k\in K;$ and
  • $z_{i,k}\ge 0$ will be 1 if the path enters node $i\in N$ at step $k\in K.$

The objective is to minimize the number $\sum_{i,j,k} x_{i,j,k}$ of arcs crossed (or some appropriate distance measure).

Constraints are as follows:

  • $y_{i,k} = \sum_{(j,i)\in A} x_{j,i,k}\quad \forall i, k$ (defining the exit variables);
  • $z_{i,k} = \sum_{(i,j)\in A} x_{i,j,k}\quad \forall i, k$ (defining the entry variables);
  • $\sum_{(i,j)\in A} x_{i,j,k} \le 1\quad \forall k\in K$ (at most one arc can occupy each slot in the trip);
  • $\sum_{i\in N} s_i = 1$ (there must be exactly one origin);
  • $y_{i,1} = s_i \quad \forall i\in N$ (the first step must exit the origin);
  • $y_{i,k} \le z_{i, k-1} \quad \forall i\in N, k > 1$ (other than the first step, exiting a node requires entering it at the previous step); and
  • $s_i + \sum_{k\in K} z_{i,k} \ge 1 \quad \forall i\in N$ (every node other than the origin must be entered at least once).
Improve this answer
$\endgroup$
8
  • $\begingroup$ I think this is what i am looking for. Let me check if i understand it. As you got the point, this is not a classic tsp since in some graphs we might need to pass a node more than once $\endgroup$
    – Optimization team
    Commented Jul 29, 2023 at 1:46
  • $\begingroup$ It works ! the only issue is that xijk creates too many binary variable ! also the number of required steps (k) is not predetermined and it is computationally expensive Thanks for your suggestions $\endgroup$
    – Optimization team
    Commented Jul 29, 2023 at 3:48
  • 1
    $\begingroup$ You're welcome. If you have a heuristic that finds a feasible solution, the number of arc crossings in that solution is a valid choice for $K.$ $\endgroup$
    – prubin ♦
    Commented Jul 29, 2023 at 15:35
  • $\begingroup$ The objective coincides with $K$, so we can assure that lower $K$ only causes infeasible rather than not optimal. But it will not be the case if there are costs/distance on the arcs, right? In that case, do you think we can still somehow assure a solution under some $K$ is overall optimal? Like ($\lceil\frac{z}{\min d_{i, j}} \rceil$) for some feasible solution with objective $z$? Is that too loose? $\endgroup$
    – xd y
    Commented Aug 1, 2023 at 1:48
  • $\begingroup$ @xdy You are correct: if there are costs on the arcs, then the number of arcs in a feasible heuristic solution will not work for $K$ because there could be a cheaper solution using more arcs. Assuming all arc costs are strictly positive, your idea for $K$ will work. Is it too loose? That's an empirical question. $\endgroup$
    – prubin ♦
    Commented Aug 1, 2023 at 2:27
8
$\begingroup$

You can solve this problem by transforming to a TSP in a complete graph where the edge weights are the shortest-path distances in the original graph. So it is three steps:

  1. Compute all-pairs shortest paths in the original graph.
  2. Solve a TSP in the complete graph with these shortest-path distances as the new edge weights.
  3. Expand the TSP solution back to the original graph by replacing each edge in the TSP tour with its corresponding shortest path.

This same approach generalizes to visiting a specified subset $S$ of nodes, but the shortest paths are computed only for all pairs of $S$, and the complete graph is over $S$. See

How to visit a subset of network nodes in a single trip?

and

https://math.stackexchange.com/questions/4466582/find-the-shortest-path-in-a-graph-which-must-pass-certain-nodes

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Worth a mention? (1) The Floyd-Warshall algorithm will find all shortest paths in one gulp. (2) This approach lets you use a specialized TSP solver like Concorde. $\endgroup$
    – prubin ♦
    Commented Jul 30, 2023 at 13:14

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